数据结构C语言版-广义表的头尾链表存储表示(共11页).doc
精选优质文档-倾情为你奉上数据结构C语言版 广义表的头尾链表存储表示.txtcopy（复制）别人的个性签名，不叫抄袭，不叫没主见，只不过是感觉对了。遇到过的事一样罢了。/*数据结构C语言版 广义表的头尾链表存储表示P109编译环境：Dev-C+ 4.9.9.2日期：2011年2月13日*/#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <string.h>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 <= S0; i+)Ti = Si;return 1;/ 若S为空串,则返回1,否则返回0 int StrEmpty(SString S)if(S0 = 0)return 1;elsereturn 0;/ 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<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 < 1 | pos >S0 | len < 0 | 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 <= n)SubString(hstr, str, 1, i-2);SubString(str, str, i, n - i + 1);elseStrCopy(hstr, str);ClearString(str);/ 算法5.7 P117/ 采用头尾链表存储结构,由广义表的书写形式串S(即类似(,()创建/ 广义表L。设emp="()" int CreateGList(GList *L, SString S)SString sub,hsub,emp;GList p,q;StrAssign(emp,"()");if(!StrCompare(S, emp)*L = NULL;/ 创建空表 else*L = (GList)malloc(sizeof(GLNode);if(!*L)/ 建表结点 exit(0);if(StrLength(S) = 1)/ S为单原子 (*L)->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);system("pause");return 0;/*输出效果：空广义表L的深度 = 1L是否空？1(1:是 0:否)广义表L的长度 = 4广义表L的深度 = 3L是否空？0(1:是 0:否)遍历广义表L：a b c d e复制广义表m = L广义表m的长度 = 4广义表m的深度 = 3遍历广义表m：a b c d em是L的表头，遍历广义表m：am是L的表尾，遍历广义表m：b c d e插入L为m的表头，遍历广义表m：a b c d e b c d e删除m的表头，遍历广义表m：b c d e请按任意键继续. . .*/ 专心-专注-专业
