数据结构C语言版-广义表的头尾链表存储表示.doc

数据结构C语言版 广义表的头尾链表存储表示.txtcopy（复制）别人的个性签名，不叫抄袭，不叫没主见，只不过是感觉对了。遇到过的事一样罢了。/*数据结构C语言版 广义表的头尾链表存储表示P109编译环境：Dev-C+ 4.9.9.2日期：2011年2月13日*/#include #include #include #include typedef char AtomType;/ 定义原子类型为字符型 typedef enumATOM,/ ATOM=0:原子LIST/ LIST=1:子表 ElemTag; / 广义表的头尾链表存储表示typedef struct GLNodeElemTag tag;/ 公共部分,用于区分原子结点和表结点 union/ 原子结点和表结点的联合部分 AtomType atom; / atom是原子结点的值域, AtomType由用户定义 structstruct GLNode *hp,*tp;ptr; / ptr是表结点的指针域,prt.hp和ptr.tp分别指向表头和表尾 a; *GList, GLNode;/ 广义表类型 / 创建空的广义表Lint InitGList(GList *L) *L = NULL;return 1;/ 销毁广义表Lvoid DestroyGList(GList *L) GList q1,q2;if(*L)if(*L)-tag = ATOM)free(*L);/ 删除原子结点 *L = NULL;else/ 是表结点，则应该删除表头和表尾结点 q1 = (*L)-a.ptr.hp;q2 = (*L)-a.ptr.tp;free(*L);*L = NULL;/ 递归删除表头和表尾结点DestroyGList(&q1);DestroyGList(&q2);/ 算法5.6 P115/ 采用头尾链表存储结构,由广义表L复制得到广义表T。 int CopyGList(GList *T,GList L)if(!L)/ 为空，复制空表 *T = NULL;else*T = (GList)malloc(sizeof(GLNode); / 建表结点 if(!*T)exit(0);(*T)-tag = L-tag;if(L-tag = ATOM)(*T)-a.atom = L-a.atom;/ 复制单原子 else/ 是表结点，则依次复制表头和表尾/ 复制广义表L-ptr.hp的一个副本T-ptr.hp CopyGList(&(*T)-a.ptr.hp), L-a.ptr.hp);/ 复制广义表L-ptr.tp的一个副本T-ptr.tp CopyGList(&(*T)-a.ptr.tp), L-a.ptr.tp);return 1;/ 返回广义表的长度,即元素个数int GListLength(GList L)int len = 0;if(!L)return 0;if(L-tag = ATOM)return 1;while(L)L = L-a.ptr.tp;/根据表尾来判断len+;return len;/ 算法5.5 P114/ 采用头尾链表存储结构,求广义表L的深度。int GListDepth(GList L)int max, dep;GList pp;if(!L)return 1;/ 空表深度为1if(L-tag = ATOM)return 0;/ 原子深度为0for(max = 0, pp = L; pp; pp = pp-a.ptr.tp)/ 递归求以pp-a.ptr.hp为头指针的子表深度 dep = GListDepth(pp-a.ptr.hp);if(dep max)max = dep;return max+1;/ 非空表的深度是各元素的深度的最大值加1 / 判定广义表是否为空int GListEmpty(GList L)if(!L)return 1;elsereturn 0;/ 取广义表L的头GList GetHead(GList L)GList h,p;if(!L)printf(空表无表头!n);exit(0);p = L-a.ptr.tp;/保存表尾L-a.ptr.tp = NULL;CopyGList(&h,L);L-a.ptr.tp = p;/归还表尾return h;/ 取广义表L的尾GList GetTail(GList L)GList t;if(!L)printf(空表无表尾!n);exit(0);CopyGList(&t, L-a.ptr.tp);return t;/ 插入元素e作为广义表L的第一元素(表头,也可能是子表) int InsertFirst_GL(GList *L,GList e)GList p = (GList)malloc(sizeof(GLNode);if(!p)exit(0);p-tag = LIST;p-a.ptr.hp = e;p-a.ptr.tp = *L;*L = p;return 1;/ 删除广义表L的第一元素,并用e返回其值int DeleteFirst_GL(GList *L,GList *e) GList p;*e = (*L)-a.ptr.hp;/ 用*e返回表头p = *L;*L = (*L)-a.ptr.tp;/ 将表尾当成表Lfree(p);/ 删除表头return 1;/ 利用递归算法遍历广义表L void Traverse_GL(GList L,void(*v)(AtomType)if(L) / L不空 if(L-tag = ATOM) / L为单原子 v(L-a.atom);else/ L为广义表 Traverse_GL(L-a.ptr.hp,v);Traverse_GL(L-a.ptr.tp,v);/ 串的定长顺序存储表示#define MAXSTRLEN 40 / 用户可在255以内定义最大串长（1个字节）typedef char SStringMAXSTRLEN+1; / 0号单元存放串的当前长度/ 生成一个其值等于chars的串Tint StrAssign(SString T,char *chars) int i;if(strlen(chars) MAXSTRLEN)return 0;elseT0 = strlen(chars);/ 记录长度/ 一个一个的拷贝,字符串结束符也拷贝了 for(i = 1; i = T0; i+)Ti = *(chars + i - 1);return 1;/ 由串S复制得串Tint StrCopy(SString T, SString S)int i;/ 一个一个的拷贝for(i = 0; i T,则返回值0;若S=T,则返回值=0;若ST,则返回值0 int StrCompare(SString S,SString T)int i;for(i = 1; i = S0 & i = T0; +i)if(Si != Ti)return Si - Ti;return S0-T0;/ 返回串的元素个数int StrLength(SString S)return S0;/ 将S清为空串int ClearString(SString S)S0 = 0;/ 令串长为零return 1;/ 算法4.3 P74/ 用Sub返回串S的第pos个字符起长度为len的子串。int SubString(SString Sub,SString S,int pos,int len) int i;if(pos S0 | len S0-pos+1)return 0;for(i = 1; i = len; i+)Subi=Spos+i-1;Sub0 = len;return 1;/ 算法5.8 P117/ 将非空串str分割成两部分:hsub为第一个,之前的子串,str为之后的子串 void sever(SString str,SString hstr) int n,i,k; / k记尚未配对的左括号个数 SString ch,c1,c2,c3;n = StrLength(str);StrAssign(c1,);StrAssign(c2,();StrAssign(c3,);SubString(ch,str,1,1);/ 搜索最外层的第一个逗号for(i = 1,k = 0;i = n & StrCompare(ch,c1) | k != 0; +i) SubString(ch, str, i, 1);if(!StrCompare(ch, c2)+k;else if(!StrCompare(ch,c3)-k;if(i tag = ATOM;(*L)-a.atom = S1; / 创建单原子广义表 else(*L)-tag = LIST;p = *L;SubString(sub, S, 2, StrLength(S)-2); / 脱外层括号 do/ 重复建n个子表 sever(sub, hsub); / 从sub中分离出表头串hsub CreateGList(&p-a. ptr. hp, hsub);q = p;if(!StrEmpty(sub)/ 表尾不空 p = (GLNode *)malloc(sizeof(GLNode);if(!p)exit(0);p-tag = LIST;q-a.ptr.tp = p;while(!StrEmpty(sub);q-a.ptr.tp = NULL;return 1;/ 打印原子 void visit(AtomType e)printf(%c , e);int main()/ 广义表的表示形式是，空表:(),单原子:a,表:(a,(b),c,(d,(e) char p80 = (a,(b),c,(d,(e);SString t;GList L,m;InitGList(&L);InitGList(&m);printf(空广义表L的深度 = %dnL是否空？%d(1:是 0:否)nn,GListDepth(L), GListEmpty(L);StrAssign(t, p);/ 创建广义表 CreateGList(&L, t);printf(n广义表L的长度 = %dn, GListLength(L);printf(广义表L的深度 = %d nL是否空？%d(1:是 0:否)n,GListDepth(L), GListEmpty(L);printf(遍历广义表L：n);Traverse_GL(L, visit);printf(nn复制广义表m = Ln);CopyGList(&m, L);printf(广义表m的长度 = %dn, GListLength(m);printf(广义表m的深度 = %dn, GListDepth(m);printf(遍历广义表m：n);Traverse_GL(m,visit);/ 重复用的时候记得销毁，相当于初始化DestroyGList(&m);m = GetHead(L);printf(nnm是L的表头，遍历广义表m：n);Traverse_GL(m, visit);/ 重复用的时候记得销毁，相当于初始化DestroyGList(&m);m = GetTail(L);printf(nnm是L的表尾，遍历广义表m：n);Traverse_GL(m,visit);/ 插入到表头 InsertFirst_GL(&m, L);printf(nn插入L为m的表头，遍历广义表m：n);Traverse_GL(m,visit);printf(nn删除m的表头，遍历广义表m：n);DestroyGList(&L);DeleteFirst_GL(&m, &L);Traverse_GL(m, visit);printf(n);DestroyGList(&m);syst