《广义表的定义与实现课件.ppt》由会员分享，可在线阅读，更多相关《广义表的定义与实现课件.ppt（33页珍藏版）》请在三一办公上搜索。
1、第5章 广义表,5.1 广义表的定义5.2 广义表操作的实现,5.1 广义表的定义5.1.1 定义,广义表（Lists）简称表，它是线性表的推广。一个广义表是n（n0）个元素的序列，当n=0时称为空表。在一个非空的广义表中，其元素可以是某一确定类型的对象（这种元素被称作单元素），也可以是由单元素构成的表（这种元素可相对地被称作子表或表元素）。显然，广义表的定义是递归的，广义表是一种递归的数据结构。,设ai为广义表的第i个元素，广义表LS可表示为：LS=（a1，a2，an）其中：LS广义表的名字；n广义表的长度；n=0 空表；当广义表非空时，称a1为表头（head），其余元素组成的表（a2，a3
2、，an）为表尾（tail）；广义表的抽象数据类型：P107,5.1.2 举例,分别用圆圈和方框表示表（表元素）和单元素A=（）空表，其长度为零。B=（e）B中只有一个单元素，长度为1，表头为e，表尾为空。,C=（a，（b，c，d）长度为2，表头为a，表尾为子表（b，c，d）。,D=（A，B，C）长度为3，表头为A,表尾为（B，C）。E=（a，E）长度为2，表头为a，表尾为（E）-表头为E，表尾为（）。E相当于无穷表（a，（a,（a，（）。,5.1.3广义表的几个性质,有次序性：广义表中的数据元素有固定的相对次序。线性排列-线性表的推广层次结构-树的推广有长度：广义表的长度定义为最外层括弧中包含
3、的数据元素个数。表元素个数一定，不能无限，可以是空表。,有深度：广义表的深度（多少层）定义为广义表书写形式中括弧的最大重数，因此空表的深度为1，因为一个单原子不是广义表，所以没有深度可言，但可以认为它的深度为0。如：A，B：1；C：2；D：3；E：无穷大。可递归：如E。可共享：子表可共享。,5.1.4 广义表的存储结构,由于广义表中的数据元素可以是原子，也可以是广义表，显然难以用顺序存储结构表示。由于列表中的数据元素可能为原子或列表，由此需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。,为了在存储结构中便于分辩原子和子表，令表示广义表的链表中的结点为异构结点，如图
4、所示，结点中设有一个标志域tag，并约定 tag=0 表示原子结点，tag=1 表示表结点。原子结点中的 data 域存储原子，表结点中指针域的两个值分别指向表头和表尾。,原子结点,表结点,广义表的头尾链表存储表示：,enum ElemTag ATOM,LIST;typedef char AtomType;struct GLNodeElemTag tag;union AtomType atom;struct GLNode*hp,*tp;ptr;typedef GLNode*GList;,例：广义表 L=(a,(x,y),(z)的存储结构。,可由对L进行表头和表尾的分析得到-若列表不空，则可分解
5、成表头和表尾（采用头尾链表存储结构）。分析：L为一非空列表,L的表头为原子a,L的表尾为列表(x,y),(z),(x,y),(z)的表头为列表(x,y),其余分析同上。,5.2 广义表操作的实现,基于广义表是递归定义的结构，因此实现广义表操作的算法均为递归函数。,5.2.1 分治法与递归求解,分治法是进行算法设计的一种方法，其严格定义为：对于一个输入规模为 n 的函数或问题，用某种方法把输入分割成 k(1kn)个子集，从而产生m个子问题，分别求解这m个问题，得出m个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直
6、接求解为止。在利用分治法求解时，若所得子问题的性质和原问题相同，则可递归求解。,何谓递归函数？,一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：在每一次调用自己时，必须是(在某种意义上)更接近于解；函数中必须有一个终止处理或计算的准则。,5.2.2 广义表的头尾链表存储表示glist.h,#include#include using namespace std;enum ElemTag ATOM,LIST;typedef char AtomType;,struct GLNodeElemTag tag;union/匿名共用体AtomType atom;struct
7、GLNode*hp,*tp;ptr;typedef GLNode*GList;,void initGList(GList,5.2.3 操作的实现glist.cpp,#include glist.h 初始化void initGList(GList,求广义表的深度int getDepth(GList L)/采用头尾链表存储结构，求广义表L的深度 int max=0,dep;GList p;if(!L)return 1;/空表深度为1if(L-tag=ATOM)return 0;/原子深度为0 for(p=L;p;p=p-ptr.tp)dep=getDepth(p-ptr.hp);/求以p-a.pt
8、r.hp为头指针的子表深度if(depmax)max=dep;return max+1;/非空表的深度是各元素的深度的最大值加1,建立广义表以广义表字符串S建立广义表。从前面的讨论可知，非空广义表可分解成表头和表尾两个部分。建表时，可分别建立（分解为两个子问题）：表头有两种情况，为单原子或为列表，当为列表时与原问题相同；表尾必为列表，与原问题相同。设string sever(string&S)函数的功能为:从广义表字符串S中提取表头串返回，并将S置成表尾串。,/将非空串str分割成两部分：/hsub为最外层第一个,之前的子串，str为之后的子串string sever(string,if(in
9、)hstr=str.substr(1,i-2);str=(+str.substr(i,n-i);else hstr=str.substr(1,n-2);str=;return hstr;,S的值有三种情况：()-空表单字符串-原子结点多字符串-列表算法：当S=()，广义表L为空-L=NULL；否则，L为列表-创建表结点；A.当S为单字符串时，为原子结点-建原子结点的子表；B.否则，S为列表字符串-创建表结点；a.从S中提取表头串hsub及表尾串tsub；b.以hsub建表头-与原问题相同，递归；c.如表尾串tsub为空-置表尾为NULL；否则，以tsub建表尾，递归。,/由广义表的书写形式串S
10、创建广义表Lvoid creatGList(GList/创建单原子广义表,else L-tag=LIST;hsub=sever(S);/从sub中分离出表头串hsub creatGList(L-ptr.hp,hsub);if(S.empty()/表尾串为空L-ptr.tp=NULL;elsecreatGList(L-ptr.tp,S);,以字符串形式输出广义表void printGList(GList,if(L-ptr.tp)coutptr.tp,1);if(k=0)coutatom;,5.2.4 应用main.cpp,#include glist.hint main()string S1=(),(e),(a,(b,c,d);string S2=(a,(x,y),(z);string S3=(a,b);string S4=();GList L;initGList(L);creatGList(L,S2);coutgetLength(L)endl;coutgetDepth(L)endl;printGList(L);,
