数据结构设计性实验——广义表.doc

《数据结构》设计性实验 题 目 _____广义表___________ 学 院 计算机学院 专 业 网络工程 年级班别 学 号 学生姓名 指导教师 杨劲涛 思路 理论 设计 难度系数 代码 总成绩 2013 年 月 一、题目 采用扩展线性链表为存储结构，实现抽象数据类型GList。 抽象数据类型广义表的定义? 基本操作:? ?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存在。?操作结果：求广义表的深度。 ?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返回其值。? Traverse_GL(L,Visit());? 初始条件：广义表L存在。。? 操作结果：遍历广义表L，用函数Visit处理每个元素。?}ADT??? ?二、存储结构定义? 由于广义表中的数据元素可以具有不同的结构，（或是原子，或是列表），因此难以用顺序存储结构表示，通常有采用链式存储结构，每个数据元素可用一个结点表示。 公用头文件GList.h： #includestdio.h #includestdlib.h #includestring.h #define AtomType char #define MAXSIZE 1024 #define ElemTag int #define OK 1 #define ERROR 0 typedef char ElemType; （1）头尾链表存储结构 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;???//广义表类型 （2）扩展性链表存储表示 typedef?enum{ATOM,LIST}ElemTag;?//ATOM=?=0:原子，LIST=?=1:子表? typedef?struct?GLNode{? ElemTag?????tag;????//公共部分，用于区分原子结点和表结点?union{????//原子结点和表结点的联合部分? AtomType????atom;?//原子结点的值域 ?Struct?GLNode?*hp;?//表结点的表头指针?}；? struct?GLNode?*tp;?//相当于线性链表的next，指向下一个元素结点? }＊Glist;????//广义表类型Glist是一种扩展的线性链表 三、算法设计 功能目录：void Menu() void Menu() { printf( 广义表的相关运算\n); printf(====================\n); printf(1 字符串变广义表\n); printf(2 广义表的复制\n); printf(3 广义表的