数据结构课件第5章广义表幻灯片.ppt

if(L-ptr.tp) { cout,; printGList(L-ptr.tp,1); } if(k==0) cout); } else coutL-atom; } } 5.2.4 应用main.cpp #include glist.h int 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); } 第5章 广义表 5.1 广义表的定义 5.2 广义表操作的实现 5.1 广义表的定义5.1.1 定义 广义表（Lists）简称表，它是线性表的推广。 一个广义表是n（n≥0）个元素的序列，当n=0时称为空表。在一个非空的广义表中，其元素可以是某一确定类型的的对象（这种元素被称作单元素），也可以是由单元素构成的表（这种元素可相对地被称作子表或表元素）。显然，广义表的定义是递归的，广义表是一种递归的数据结构。 设ai为广义表的第i个元素，广义表LS可表示为： LS=（a1，a2，…， an) 其中： ①LS——广义表的名字； ②n——广义表的长度； ③ ； ④n=0 空表； ⑤当广义表非空时，称a1为表头（head），其余元素组成的表（a2，a3， …， an）为表尾（tail）； 广义表的抽象数据类型：P107 5.1.2 举例 分别用圆圈和方框表示表（表元素）和单元素 ①A=（） 空表，其长度为零。 ②B=（e） B中只有一个单元素，长度为1，表头为e，表尾为空。 ③C=（a，（b，c，d）） 长度为2，表头为a，表尾为子表（b，c，d）。表尾仍为表，表头为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广义表的几个性质 ①有次序性： 广义表中的数据元素有固定的相对次序。 线性排列 --线性表的推广 层次结构 --树的推广 ②有长度： 广义表的长度定义为最外层括弧中包含的数据元素个数。 表元素个数一定，不能无限，可以是空表。 ③有深度： 广义表的深度（多少层）定义为广义表书写形式中括弧的最大重数，因此空表的深度为1，因为一个单原子不是广义表，所以没有深度可言，但可以认为它的深度为0。 如：A，B：1；C：2；D：3； E：无穷大。 ④可递归： 如E。 ⑤可共享： 子表可共享。 5.1.4 广义表的存储结构 由于广义表中的数据元素可以是原子，也可以是广义表，显然难以用顺序存储结构表示之。 由于列表中的数据元素可能为原子或列表，由此需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。 并且为了在存储结构中便于分辩原子和子表，令表示广义表的链表中的结点为异构结点，如图所示， 结点中设有一个标志域tag， 并约定 tag=0 表示原子结点，tag=1 表示表结点。原子结点中的 data 域存储原子，表结点中指针域的两个值分别指向表头和表尾。 tag=0 atom 原子结点 ptr---表结点的指针域 tag=1 hp tp 表结点 广义表的头尾链表存储表示： enum ElemTag {ATOM,LIST}; typedef char AtomType; struct GLNode{ ElemTag tag; union { AtomType atom; struct { GLNode *hp,*tp; } ptr; }; }; typedef GLNode* GList; 例：广义表 L=(a,(x,y),((z))) 的存储结构。 可由对L进行表头和表尾的分析得到--若列表不空，则可分解成表头和表尾。 分析： ①L为一非空列表 ②L的表头为原子a ③L的表尾为列表((x,y),((z))) ④((x,y),((z)))的表头为列表(x,y) 其余分析同上。 5.2 广义表操作的实现 基于广义表是递归定义的结构，因此实现广义表操作