首页 > 代码库 > 串和广义表
串和广义表
参考文章:http://blog.csdn.net/lijuwen/article/details/1353084
然后又按照自己的方式敲了一遍,各种错。。。。
下面是我的代码:
#include "stdafx.h"#include <iostream>#include <string.h>using namespace std;typedef char AtomType;//定义tag类型typedef char AtomType;//定义原子类型为字符型typedef enum{ATOM,LIST} ElemTag;typedef struct{ char *ch; int length;}HString;typedef struct GLNode{ ElemTag tag; union{ AtomType data; GLNode *subList; }a; GLNode *next;}*GLList,GLNode;//生成一个串等于charsvoid strAssign(HString *T,char *chars){ //如果T存在值,释放T的空间 if((*T).ch) free((*T).ch); //求chars的长度 int i = strlen(chars); if(i ==0) { T->ch =NULL; T->length =0; }else{ //T= (HString*)malloc(sizeof(HString)); (*T).ch = (char*)malloc(sizeof(char));//分配串的空间 if(!(*T).ch) exit(0); for(int j=0;j<i;j++) T->ch[j]=chars[j]; T->length = i; }}//将S的值复制给Tvoid strCopy(HString *T,HString *S){ if((*T).ch) free((*T).ch); (*T).ch = (char*)malloc(sizeof(char)); if(!(*T).ch) exit(0); for(int i=0;i<S->length;i++) T->ch[i] = S->ch[i]; T->length = S->length;}//判断串是否为空int strEmpty(HString *S){ if(S->length==0&&S->ch==NULL) return 1; else return 0;}//比较两个字符的大小,前者大于后者返回1,相等返回0,前者小于后者返回-1int strCompare(HString *T,HString *S){ int i,j; for(i=0,j=0;i<T->length,j<S->length;i++,j++) if(T->ch[i] != T->ch[j]) return T->ch[i]-T->ch[j]; return T->length - S->length;}//得到串的长度int strLen(HString *S){ return S->length;}//清空串void clearStr(HString *S){//这样写跟.ch应该没差别 if(S->ch){ free(S->ch); S->ch = NULL; } S->length =0;}//连接串void strConcat(HString *T,HString *S1,HString *S2){ if((*T).ch) free((*T).ch); T->length = S1->length + S2->length; (*T).ch = (char*)malloc(sizeof(char)); if(!(*T).ch) exit(0); for(int i=0;i<S1->length;i++) T->ch[i] = S1->ch[i]; for(int j=0;j<S2->length;j++) T->ch[S1->length+j]=S2->ch[j];}//将S从pos位置截取length长的字符串赋值给subvoid subStr(HString *sub,HString *S,int pos,int length){ if(pos <1||pos>S->length||length<0||length>S->length+1-pos) { printf("%s","pos or length invalid"); exit(0); } if((*sub).ch) free((*sub).ch); if((*S).ch == NULL){ (*sub).ch = NULL; (*sub).length=0; }else { (*sub).ch = (char*)malloc(sizeof(char)); if(!(*sub).ch) exit(0); for(int i=0;i<length;i++) sub->ch[i]=S->ch[pos+i]; sub->length = length; }}//初始化串void initStr(HString *S){ (*S).length =0; (*S).ch = NULL;}//两个字符串是否有重合,在S的pos位置之后,重合返回第一次重合的下标,不重合返回-1 int indexStr(HString *T,HString *S,int pos){ int length = (*S).length-(*T).length+1; if(pos>0) { for(int i=pos;i<length;i++) { HString temp; subStr(&temp,S,i,length); if(!strCompare(&temp,T)) return i; } } return -1;}//在S的pos位置插入Tvoid strInsert(HString *S,int pos,HString *T){ if(pos<1||pos>(*S).length+1||(*T).length<0) exit(0); if((*S).ch) free((*T).ch); (*S).ch = (char*)malloc(sizeof(char)); if(!(*S).ch) exit(0); for(int i=(*S).length-1;i>pos-1;i--) //(*S).ch[i+pos] = (*S).ch[i]; (*S).ch[i+(*T).length] = (*S).ch[i]; for(int i=0;i<(*T).length;i++) (*S).ch[pos+i-1] = (*T).ch[i]; (*S).length +=(*T).length;}//在S的pos位置删除len长度void strDelete(HString *S,int pos,int len){ if(len < 1||len>(*S).length-1||pos<1||pos>(*S).length-1||pos<(*S).length-1-len) exit(0); for(int i=pos;i<(*S).length;i++) (*S).ch[pos]=(*S).ch[pos+len]; (*S).length -=len; (*S).ch = (char*)realloc((*S).ch,(*S).length*sizeof(char));}//替换字符串,将V替换成Tvoid strReplace(HString *S,HString *T,HString *V){ int i=1; if(strEmpty(S)) exit(0); do { i = indexStr(S,V,i);//i为上次寻找的位置 if(i) { strDelete(S,i,(*V).length); strInsert(S,i,T); i+=(*V).length; } }while(i);}//输出strvoid strPrint(HString *S){ for(int i=0;i<(*S).length;i++) printf("%c",(*S).ch[i]); printf("/n");}//初始化广义表int initGList(GLList *L){ *L = NULL; return 1;}//将str分成两部分,hstr为第一个,之前的字符串,str为第一个,之后的字符串int sever(HString *str,HString *hstr){ printf("%s","开始执行sever/n"); HString ch,c1,c2,c3; initStr(&ch);initStr(&c1);initStr(&c2);initStr(&c3); printf("%s","init success/n"); strAssign(&c1,",");strAssign(&c2,"(");strAssign(&c3,")"); printf("%s","strassgin success/n"); int n = strLen(str); int i=1; int k=0; do{ printf("%s","begin to inter do/n"); printf("i=%d/n",i); subStr(&ch,str,i,1); printf("substr:%c",&ch); if(!strCompare(&ch,&c2)) k++; else if(!strCompare(&ch,&c3)) k--; ++i; }while(i<=n&&strCompare(&ch,&c1)||k!=0); printf("&ch=%c",ch); if(i<n) { strCopy(&ch,str); subStr(hstr,&ch,1,i-2); subStr(str,&ch,i,n-i+1); } else { strCopy(hstr,str); clearStr(str); } return 1;}//s为广义表格式的字符串,L为要创建的表,void createList(GLList &L,HString *S){ GLList p; HString emp,sub,hsub; initStr(&emp);initStr(&sub);initStr(&hsub); strAssign(&emp,"()"); L = (GLList)malloc(sizeof(GLNode)); if(!L) { printf("%s","创建表失败"); exit(0); } if(!strCompare(S,&emp))//创建空表 { L->tag = LIST; L->next = NULL; L->a.subList = NULL; }else if(strLen(S)==1)//创建原子表 { L->tag = ATOM; L->next = NULL; L->a.data = http://www.mamicode.com/(*S).ch[0];"脱外层括号之后:%s",sub); sever(&sub,&hsub); printf("sublist=%s",hsub); printf("next=%s",sub); createList(L->a.subList,&hsub); p = L->a.subList; while(!strEmpty(&sub)) { sever(&sub,&hsub); createList(p->next,&hsub); p = p->next; } }}//销毁广义表void destroyList(GLList *L){ GLList subList,next; if(*L) { if((*L)->tag = ATOM) subList = NULL; else subList = (*L)->a.subList; next = (*L)->next; free(*L); (*L) = NULL; destroyList(&subList); destroyList(&next); }}// 由广义表L复制得到广义表Tint copyList(GLList *T,GLList L){ if(!L) { *T = NULL; return 1; }; T = (GLList *)malloc(sizeof(GLList)); if(!(*T)) exit(0); (*T)->tag = L->tag; if(L->tag = ATOM) (*T)->a.data = http://www.mamicode.com/L->a.data;"%c",&ch); if(ch == ‘#‘)*L = NULL; else if(ch == ‘(‘) { L = (GLList *)malloc(sizeof(GLList)); if(!L) exit(0); (*L)->tag = LIST; createByScanf(&(*L)->a.subList); } else { L = (GLList *)malloc(sizeof(GLList)); if(!L) exit(0); (*L)->tag = ATOM; (*L)->a.data = http://www.mamicode.com/ch;"%c",&ch); if(ch == ‘,‘) createByScanf(&(*L)->next); else if(ch == ‘)‘) (*L)->next = NULL;}void main(){ HString t; GLList l,m; initStr(&t); initGList(&l); initGList(&m); /*char c[80]; gets_s(c); strAssign(&t,c); createList(l,&t);//每次循环sub出来的的值都一样,但是每次执行的sub都不同 printf("广义表l的长度=%d/n",listLength(&l));*/ createByScanf(&l); printf("广义表l的长度=%d/n",listLength(&l)); /*HString t,m; initStr(&t); initStr(&m); char c[10]; gets_s(c); strAssign(&t,c); subStr(&m,&t,1,1); strPrint(&m);*/}
显示是调不通了,有机会再好好调下
串和广义表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。