《数据结构设计性实验——广义表.》由会员分享，可在线阅读，更多相关《数据结构设计性实验——广义表.（14页珍藏版）》请在金锄头文库上搜索。
1、序号：数据结构设计性实验 题 目 _广义表_学 院 计算机学院 专 业 网络工程 年级班别 学 号 学生姓名 指导教师 杨劲涛 思路理论设计难度系数代码总成绩2013 年 6 月 28 日一、题目 采用扩展线性链表为存储结构，实现抽象数据类型GList。抽象数据类型广义表的定义基本操作:InitGList(&L);操作结果：创建空的广义表L。CreateGList(&L,S);初始条件：S是广义表的书写形式串。操作结果：由S创建广义表L。DestroyGList(&L);初始条件：广义表L存在。操作结果：销毁广义表L。CopyGList(&T,L);初始条件：广义表L存在。操作结果：由广义表L
2、复制得到广义表T。GlistLength(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存在。操作
3、结果：删除广义表L的第一元素，并用e返回其值。Traverse_GL(L,Visit();初始条件：广义表L存在。操作结果：遍历广义表L，用函数Visit处理每个元素。ADT二、存储结构定义由于广义表中的数据元素可以具有不同的结构，（或是原子，或是列表），因此难以用顺序存储结构表示，通常有采用链式存储结构，每个数据元素可用一个结点表示。公用头文件GList.h：#include#include#include#define AtomType char#define MAXSIZE 1024#define ElemTag int#define OK 1#define ERROR 0typedef
4、 char ElemType;（1）头尾链表存储结构typedefenumATOM,LISTElemTag;/ATOM=0:原子，LIST=1：子表typedefstructGLNodeElemTagtag;/公共部分，用于区分原子结点和表结点union/原子结点和表结点的联合部分AtomTypeatom;/atom是原子结点的值域，AtomType由用户定义StructstructGLNode*hp,*tp;ptr;/ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾；*Glist;/广义表类型（2）扩展性链表存储表示typedefenumATOM,LISTElemTag;
5、/ATOM=0:原子，LIST=1:子表typedefstructGLNodeElemTagtag;/公共部分，用于区分原子结点和表结点union/原子结点和表结点的联合部分AtomTypeatom;/原子结点的值域StructGLNode*hp;/表结点的表头指针；structGLNode*tp;/相当于线性链表的next，指向下一个元素结点Glist;/广义表类型Glist是一种扩展的线性链表三、算法设计1. 功能目录：void Menu()void Menu()printf( 广义表的相关运算n);printf(=n);printf(1 字符串变广义表n);printf(2 广义表的复制
6、n);printf(3 广义表的长度n);printf(4 广义表的深度n);printf(5 广义表的表头n);printf(6 广义表的表尾n);printf(0 推出程序n);printf(=n);printf( 请 选 择 0 - 9n); 函数功能：此函数为功能菜单选择函数，当在主函数中输完广义表字符串并按回车后，调用此函数，由这个函数打印出有关函数的各项操作。2. 主函数：int main()int main()while(EOF)GList *L=NULL;int n=0,i=0,a;char ch,*str=NULL,string50=,s50=;printf(输入要建立广义表
7、的字符串(形如(a,b),c,(d,e)：);scanf(%s,&string);getchar();str=string;L=StrToLists(str); Menu();while(EOF)printf(请输入您需要进行的步骤：);scanf(%d,&a);getchar();switch(a)case 1:printf(字符串变广义表:); PrintGList(L); printf(n); break;case 2:printf(广义表的复制是:); PrintGList(CopyGList(L); printf(n); break;case 3:printf(广义表的长度是：%dn
8、,length(L); break;case 4:printf(广义表的深度是:%dn,depth(L); break; case 5:printf(广义表的表头是：); PrintGList(head(L); printf(n); break; case 6:printf(广义表的表尾是：); PrintGList(tail(L); printf(n); break; case 0:return 0; default:printf(输入错误！); if(a=9)break; return 0;函数功能： 当程序运行时，首先运行的就是主函数。在此函数中，首先打印出输入提示，提供出入的样例。输入
9、完成之后，将数据保存进内存，然后后通过调用Menu函数提供用户功能选择提示，再打印输入提示，然后根据输入的选项执行不同的操作，通过循环可以进行不同的操作选择。3. 字符串变广义表：GList *StrToLists(char *&s)GList *StrToLists(char *&s) /字符串变广义表 GList *h; char ch; ch=*s+; if(ch!=t) h=new GList; if(ch=() h-tag=1; h-ptr.ph=StrToLists(s); else if(ch=) h=NULL; else h-tag=0; h-ptr.data=ch; else
10、 h=NULL; ch=*s+; if(h!=NULL) if(ch=,) h-pt=StrToLists(s); else h-pt=NULL; return h;函数功能： 将一串字符串以广义表的形式保存，先判断表头是原子结点还是表结点，是表节点的话，标志位tag=1，然后递归输入表头。是原子结点的话tag=0，将数据存入ptr.data中。输入玩表头之后同样以递归输入表尾。4. 广义表的复制：GList *CopyGList(GList *p)GList *CopyGList(GList *p)GList *q;if(p=NULL)return NULL;q=new GList;q-ta
11、g=p-tag;if(p-tag=1)q-ptr.ph=CopyGList(p-ptr.ph);else q-ptr.data=p-ptr.data;q-pt=CopyGList(p-pt);return q;函数功能： 将一个广义表复制给另一个广义表。新建一个广义表，将形参的表头和表尾分别赋给新建的广义表，再返回新建的广义表。5. 广义表的输出：void PrintGList(GList *L)void PrintGList(GList *L)if(L!=NULL) if(L-tag=1)printf();if(L-ptr.ph=NULL)printf( );elsePrintGList(L-ptr.ph);elseprintf(%c,L-ptr.data);if(L-tag=1)printf();if(L-pt!=NULL)printf(,); PrintGList(L-pt); 函数功能： 输出广义表。首先判断标志位，tag=1，则输出（，然后递归输出表头，tag=0，则输出
