《数据结构 设计性实验 广义表的抽象数据类型》由会员分享，可在线阅读，更多相关《数据结构 设计性实验 广义表的抽象数据类型（24页珍藏版）》请在金锄头文库上搜索。
1、题目：广义表的抽象数据类型抽象数据类型广义表的定义ADT Gllistf数据对家=D=込1)=12站n壬匕&j AtaSet或用匸GlisAt口证et为某个敌据 对象数据关系；Rl=(馆_i ,驴 |*1 ,日FD,2WiWti基本操作: InitGList(&L); 操作结果：创建空的广义表 L。CreateGList(&L,S);初始条件：S是广义表的书写形式串。操作结果：由S创建广义表L。DestroyGList(&L);初始条件：广义表L存在。操作结果：销毁广义表 L。CopyGList(&T,L);初始条件：广义表L存在。操作结果：由广义表L复制得到广义表T。GlistLength(
2、L);初始条件：广义表L存在。操作结果：求广义表L的长度，即元素个数。GlistDepth(L);初始条件：广义表L存在。操作结果：求广义表的深度。GlistEmpty(L);初始条件：广义表L存在。操作结果：判定广义表L是否为空。GetHead(L);初始条件：广义表L存在。操作结果：取广义表L的头。GetTail(L);初始条件：广义表L存在。操作结果：取广义表L的尾。InsertFirst_GL(&L,e);初始条件：广义表L存在。操作结果：插入元素e作为广义表L的第一元素。DeleteFirst_GL(&L,&e);初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其
3、值。Traverse_GL(L,Visit();初始条件：广义表L存在。操作结果：遍历广义表L,用函数Visit处理每个元素。ADT存储结构定义由于广义表中的数据元素可以具有不同的结构,（或是原子,或是列表） 因此难以用顺序存储结构表示,通常有采用链式存储结构,每个数据元素可用 一个结点表示。由于列表中的数据元素可能为原子或列表,由此需要两种结构 的结点：一种是表结点,以表示列表；一种是原子结点,用以表示原子。若列不 空,则可分解成表头和表尾；反之,一对确定的表头和表尾可唯一确定列表。 由此,一个表结点可由三个域组成：标志域、指示域和指示表尾的指针域；而 原子结点只需两个域：标志域和值域（如图
4、 8 所示）。其形式定义说明如下：存储结构: 公用头文件 DS0.h:#include#include#include#include#include#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef char AtomType; /* 定义原子类型为字符型 */广义表的头尾链表存储表示/typedef enumATOM,LISTElemTag;/ATOM= =0:原子，LIST= =1：子表 typedef st
5、ruct GLNodeElemTag tag;/公共部分，用于区分原子结点和表结点union/原子结点和表结点的联合部分AtomType atom;/atom是原子结点的值域，AtomType由用户定义Structstruct GLNode *hp, *tp;ptr;ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾；*Glist; /广义表类型/广义表的扩展线性链表存储表示/typedef enumATOM,LISTElemTag; /ATOM= =0:原子， LIST= =1:子表typedef struct GLNodeElemTagtag; /公共部分，用于区分原子结
6、点和表结点union/原子结点和表结点的联合部分AtomTypeatom; /原子结点的值域Struct GLNode *hp; /表结点的表头指针；struct GLNode *tp; 相当于线性链表的next，指向下一个元素结点* Glist;广义表类型Glist是一种扩展的线性链表四, 算法设计#include#include#include#include#include#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1
7、typedef char AtomType; /* 定义原子类型为字符型 */typedef int Status; /* Status 是函数的类型 ,其值是函数结果状态代码，如 OK 等 */typedef int Boolean;typedef structchar *ch; /*若是非空串则按串长分配存储区否则ch为NULL */int length; /* 串长度 */HString;typedef enumATOM,LISTElemTag; /* ATOM=0:原子,LIST=1:子表*/typedef struct GLNodewo mnE宀iflp8lIgF) 莒 WHIP口
8、lpF) AeME(+:-?v 穴 ohdjoj 段 CTMHaAO)方 a 暮水叵Hepa E (* apoNQoIurs-OIOIE adxxulsvuofunM5MEHmgHStatus StrCopy(HString *T,HString S) /*初始条件:串S存在。操作结果:由串S复制得串T */ int i;if(*T).ch)free(*T).ch); (*T).ch=(char*)malloc(S.length*sizeof(char);if(!(*T).ch) exit(OVERFLOW);for(i=0;iT,则返回值0若S=T则返回值=0;若SvT,则返回值0 */ i
9、nt i;for(i=0;iS.length&iT.length;+i) if(S.chi!=T.chi)return S.chi-T.chi; return S.length-T.length;int StrLength(HString S) /*返回S的元素个数称为串的长度*/return S.length;Status ClearString(HString *S) /* 将 S 清为空串 */if(*S).ch)free(*S).ch); (*S).ch=NULL;(*S).length=0;return OK;Status Concat(HString *T,HString S1,H
10、String S2) /*用T返回由S1和S2联接而成的新串*/int i;if(*T).ch) free(*T).ch); /* 释放旧空间 */(*T).length=S1.length+S2.length;(*T).ch=(char *)malloc(*T).length*sizeof(char); if(!(*T).ch)exit(OVERFLOW);for(i=0;iS1.length;i+) (*T).chi=S1.chi;for(i=0;iS2.length;i+) (*T).chS1.length+i=S2.chi;return OK;Status SubString(HStr
11、ing *Sub, HString S,int pos,int len) /*用Sub返回串S的第pos个字符起长度为len的子串。*/* 其中,1WposWStrLength(S)且 0WlenWStrLength(S)-pos+1 */ int i;if(posS.length|lenS.length-pos+1) return ERROR;if(*Sub).ch)free(*Sub).ch); /* 释放旧空间 */if(!len) /* 空子串 */(*Sub).ch=NULL;(*Sub).length=0;else /* 完整子串 */ (*Sub).ch=(char*)malloc(len*sizeof(char); if(!(*Sub).ch)exit(OVERFLOW);for(i=0;i0)n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1)SubString(&sub,S,i,m);if(StrCompare(sub,T)!=0)+i;elsereturn i;return 0;Status StrInsert(HString *S,int pos,
