资源描述：
《数据结构C语言版-广义表的头尾链表存储表示.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构C语言版广义表的头尾链表存储表示.txtcopy（复制）别人的个性签名，不叫抄袭，不叫没主见，只不过是感觉对了。遇到过的事一样罢了。/*数据结构C语言版广义表的头尾链表存储表示P109编译环境：Dev-C++4.9.9.2日期：2011年2月13日*/#include#include#include#includetypedefcharAtomType;//定义原子类型为字符型typedefenum{ATOM,//ATOM==0:原子LIST//LIST==1:子表}ElemTag;//广义表
2、的头尾链表存储表示typedefstructGLNode{ElemTagtag;//公共部分,用于区分原子结点和表结点union//原子结点和表结点的联合部分{AtomTypeatom;//atom是原子结点的值域,AtomType由用户定义struct{structGLNode*hp,*tp;}ptr;//ptr是表结点的指针域,prt.hp和ptr.tp分别指向表头和表尾}a;}*GList,GLNode;//广义表类型//创建空的广义表LintInitGList(GList*L){*L=NULL;return1;}//销毁广义表LvoidDestroyGList(GLis
3、t*L){GListq1,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.6P115//采用头尾链表存储结构,由广义表L复制得到广义表T。intCopyGList(GList*T,GListL){if(!L)//为空，复制空表*T=NULL;else
4、{*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.hpCopyGList(&((*T)->a.ptr.hp),L->a.ptr.hp);//复制广义表L->ptr.tp的一个副本T->ptr.tpCopyGList(&((*T)->a.ptr.tp),L->a.ptr.tp);}}return1;
5、}//返回广义表的长度,即元素个数intGListLength(GListL){intlen=0;if(!L)return0;if(L->tag==ATOM)return1;while(L){L=L->a.ptr.tp;//根据表尾来判断len++;}returnlen;}//算法5.5P114//采用头尾链表存储结构,求广义表L的深度。intGListDepth(GListL){intmax,dep;GListpp;if(!L)return1;//空表深度为1if(L->tag==ATOM)return0;//原子深度为0for(max=0,pp=L;pp;pp=pp->a.
6、ptr.tp){//递归求以pp->a.ptr.hp为头指针的子表深度dep=GListDepth(pp->a.ptr.hp);if(dep>max)max=dep;}returnmax+1;//非空表的深度是各元素的深度的最大值加1}//判定广义表是否为空intGListEmpty(GListL){if(!L)return1;elsereturn0;}//取广义表L的头GListGetHead(GListL){GListh,p;if(!L){printf("空表无表头!");exit(0);}p=L->a.ptr.tp;//保存表尾L->a.ptr.tp=NULL;Cop
7、yGList(&h,L);L->a.ptr.tp=p;//归还表尾returnh;}//取广义表L的尾GListGetTail(GListL){GListt;if(!L){printf("空表无表尾!");exit(0);}CopyGList(&t,L->a.ptr.tp);returnt;}//插入元素e作为广义表L的第一元素(表头,也可能是子表)intInsertFirst_GL(GList*L,GListe){GListp=(GList)malloc(sizeof(GLNode))
