第10讲广义表分析解析

1EssentialofLectureTen：一、广义表的类型定义二、广义表的存储结构难点2由于广义表本属线性类型的数据结构，它和数组类似，每个数据元素本身又可以是一个数据结构，因此在教材中和“数组”合为一章。但广义表比数组更为复杂，它兼有“多层次”的特点，特别是它的存储表示和操作的实现和树的操作极为类似。因此在本小节的学习中应善于和第六章树的内容相对照，反之通过本章的学习恰好是对实现树操作的递归算法的预习和巩固。希望通过本小节的学习能自己总结出如何利用“分治法”的算法思想设计递归定义的结构的递归算法的规律来。广义表（GeneralList）----人工智能等领域的LISP语言使用的一种数据结构，是对线性表的一个推广。一、广义表的类型定义3一、广义表的类型定义1、广义表的概念n(0)个表元素组成的有限序列记作GL=(a1,a2,a3,…,an)GL是表名,ai是表元素,它可以是表(称为子表),可以是数据元素(称为原子)2、n为表的长度。n=0的广义表为空表3、n0时,表的第一个表元素称为广义表的表头(head),除此之外,其它表元素组成的表称为广义表的表尾(tail)4例如:A=()空表，无表头，无表尾，表长为0；B=(x,y,z)单元素表，表头为x，表尾为(y,z)，表长为3；C=(B,y,z)非单元素表，表头为B，表尾为(y,z)，表长为3；D=(x,(y,z))非单元素表，表头为x，表尾为((y,z))，表长为2；E=(x,E)递归表，表头为x，表尾为(E)，表长为2。一、广义表的类型定义5一、广义表的类型定义由于广义表中的元素又可以是广义表，因此对于广义表有深度的概念。广义表GL的深度Depth(GL)定义如下：广义表的深度本质上就是广义表表达式中括号的最大嵌套层数。其它情况为空表为原子元素)1|)((110)(niaDepthMaxGLGLGLDepthi6例如:A=()深度为1；B=(x,y,z)深度为1；C=(B,y,z)深度为2；D=(x,(y,z))深度为2；E=(x,E)深度为∞。一、广义表的类型定义BxyzBxyzCByzDxyz7若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表。对非空广义表：称第一个元素为L的表头，其余元素组成的表称为LS的表尾；B=(a,(b,c,d))表头：a表尾((b,c,d))即HEAD（B）=a,TAIL(B)=((b,c,d)),C=(e)表头：e表尾()D=(A,B,C,f)表头：A表尾(B,C,f)运算可以嵌套，如：HEAD（HEAD（TAIL（B）））=b,TAIL（HEAD（TAIL（B）））=（c,d）。一、广义表的类型定义任何一个非空广义表LS=(1,2,…,n)均可分解为表头Head(LS)=1和表尾Tail(LS)=(2,…,n)两部分例如:D=(E,F)=((a,(b,c))，F)Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)Head((c))=cTail((c))=()9实战：利用广义表的head和tail操作，把原子d分别从下列广义表中分离出来。L1=（（（（（a），b），d），e））L2=（a，（b，（（d）），e））1、head（tail（head（head（L1））））2、head（head（head（tail（head（tail（L2））））））求广义表的深度例如，对于广义表E(B(a,b),D(B(a,b),C(u,(x,y,z)),A()))1111234其它情况为空表为原子元素)1|)((110)(niaDepthMaxGLGLGLDepthi11DABCfaEebcd一、广义表的类型定义广义表的特性:有次序性,有长度,有深度,可共享,可递归。121．GenListNodeElemType*First()const初始条件：广义表已存在。操作结果：返回广义表的第一个元素。2．GenListNodeElemType*Next(GenListNodeElemType*elemPtr)const初始条件：广义表已存在，elemPtr指向的广义表元素。操作结果：返回elemPtr指向的广义表元素的后继3．boolEmpty()const初始条件：广义表已存在。操作结果：如广义表为空，则返回true，否则返回false广义表基本操作134．voidPush(constElemType&e)初始条件：广义表已存在。操作结果：将元子元素e作为表头加入到广义表最前面。5．voidPush(GenListElemType&subList)初始条件：广义表已存在。操作结果：将子表subList作为表头加入到广义表最前面。6．intDepth()初始条件：广义表已存在。操作结果：返回广义表的深度。广义表基本操作14由于广义表中数据元素可以具有不同结构，故难以用顺序结构表示广义表。通常采用链表存储方式。引用数法广义表：每一个表结点由三个域组成，结点三分三类：（1）头结点（2）原子结点（3）表结点二、广义表的存储结构15tag=HEAD(0)refnextLinktag=ATOM(1)atomnextLinktag=LIST(2)subLinknextLink(a)头结点(b)原子结点(c)表结点ref引用数表示能访问此广义表的广义表或指针个数16A=()，B=(x,y,z)，C=(B,y,z)，D=(x,(y,z))，E=(x,E)01∧A02B1x1y1z∧0121y1z∧C011x2∧D011y1z∧022∧E17存储特点：不论哪一层的子表，都带有一个头结点，空表也不例外。优点是便于操作。表中结点的层次分明。所有位于同一层的表元素，在其存储表示中也在同一层。可以很容易计算出表的长度。沿着nextLink链能找到的结点个数即为表长。18三、广义表操作的递归函数对于一个输入规模为n的函数或问题，用某种方法把输入分割成k(1k≤n)个子集，从而产生L个子问题，分别求解这L个问题，得出L个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。分治法的设计思想:DivideandConquer19三、广义表操作的递归函数例1求广义表的深度P174DepthHelp()例2复制广义表P173CopyHelp()例3创建广义表的存储结构P174CreateHelp()templateclassElemTypeintRefGenListElemType::DepthHelp(constRefGenListNodeElemType*hd)//操作结果：返回以hd为表头的引用数法广义表的深度{if(hd-nextLink==NULL)return1;//空广义表的深度为1intsubMaxDepth=0;//子表最大深度for(RefGenListNodeElemType*tmpPtr=hd-nextLink;tmpPtr!=NULL;tmpPtr=tmpPtr-nextLink){//求子表的最大深度if(tmpPtr-tag==LIST){//子表intcurSubDepth=DepthHelp(tmpPtr-subLink);//子表深度if(subMaxDepthcurSubDepth)subMaxDepth=curSubDepth;}}returnsubMaxDepth+1;//深度为子表最大深度加1}22本讲小结重点：1、广义表的基本概念2、广义表的存储难点：1、广义表的递归算法