广义表实验报告.docVIP

数据结构实验报告 题目：广义表抽象数据类型的实现 学 院 计算机学院 专 业 计算机科学与技术 年级班别 2010级班 学生姓名 指导教师 成 绩 ____________________ 2012年6月 1. 题目 实现广义表抽象数据类型GList ADT GList{ 数据对象：D＝{ i | i=1,2,...,n; n≥0; ei∈AtomSet或ei∈GList，AtomSet为某个数据对象} 数据关系：R1＝{ i-1,ei|ei-1, ei∈D, 2=i=n } 基本操作： InitGlist(L); 操作结果:创建空的广义表L CreateGList(L,S); 初始条件:S是广义表的书写形式串 操作结果:由S创建广义表L DestroyGlist(L); 初始条件:广义表L存在 操作结果:销毁广义表L CopyGlist(T,L); 初始条件:广义表L存在 操作结果:由广义表L复制得到广义表T GListLength(L); 初始条件:广义表L存在 操作结果:求广义表L的长度,即元素个数 GListDepth(L); 初始条件:广义表L存在 操作结果:求广义表L的深度 GlistEmpty(L); 初始条件:广义表L存在 操作结果:判断广义表L是否为空 GetHead(L); 初始条件:广义表L存在 操作结果:广义表L GetTail(L) 初始条件:广义表L存在 操作结果:广义表L InsertFirst_GL(L,e) 初始条件:广义表L存在 操作结果: DeleteFirst_GL(GList L,e) 初始条件:广义表L存在 操作结果: Traverse_GL(GList L,void(*v)(AtomType)) 初始条件:广义表L存在 操作结果: } ADT GList 2．存储结构定义 由于广义表中的数据元素可以具有不同的结构（或是原子，或是列表），因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个节点表示。 由于列表中的数据元素可能为原子或列表，由此需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。一个表结点可以由3个域组成：标志域，指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域。其形式定义说明如下： -------广义表的扩展线性链表存储表示------ typedef enum{ATOM,LIST}ElemTag; // ATOM==0:原子,LIST==1:子表 typedef struct GLNode { ElemTag tag; // 公共部分,用于区分原子结点和表结点 union { // 原子结点和表结点的联合部分 AtomType atom; // atom是原子结点的值域AtomType由用户定义 struct {struct GLNode *hp,*tp;}ptr; //ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾 }; }*GList； //广义表类型 void visit(GList L){ //visit函数 printf(%c,L-atom); } void GetGList(char s[]) { //接收建表元素--书写形式串的函数 int i; printf(\nInput GList to creat:\n); for(i=0;i50;i++) { scanf(%c,s[i]); if(s[i]==\n) break; } } 3. 算法设计 int InitGList(GList L) //建空广义表 { L=(GList)malloc(sizeof(struct GLNode)); if(!L) return ERROR; L-tag=LIST; L-ptr.hp=NULL; L-ptr.tp=NULL; return OK; } GList CreatGList(GList L,char *s){ //由书写形式串建广义表 GList q; char x; x=*s; s++; if(x!=\n){ q=(GList)malloc(sizeof(struct GLNode)); if(x==