资源描述：
《《数据结构与算法c》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、§8.1.5基本操作§8.4.2分枝单链表对象§8.5.3广义表统计计数§8.4.1结点对象§8.3.1广义表元素接口§8.5广义表操作的实现*§8.5.1一般问题§8.2广义表的存贮结构§8.1.3广义表的遍历§8.1.1基本概念§8.1.2广义表逻辑图§8.2.2链式结构的高级语言描述§8.5.4广义表的串行化与逆串行化§8.1.4基本特性§8.3.2广义表接口§8.5.5广义表的复制与求尾§8.1广义表的逻辑结构§8.2.1基本存储方法8.3广义表对象模型*§8.4广义表的分枝单链表对象*§
2、8.5.2遍历操作§8.6广义表结构的应用§8.6.1多元多项式的表示§8.6.2层次结构的表示第8章广义表广义表是一种特殊的结构，它兼有线性表、树、图等结构的特点。从各层元素各自具有的线性关系讲，它应该是线性表的拓广；从元素的分层方面讲，它有树结构的特点，但从元素的递归性和共享性等方面讲，它应该属于图结构。总之，它是一种更为复杂的非线性结构。§8.1广义表的逻辑结构§8.1.1基本概念广义表(Lists)是一个二元组Lists=(D,R)其中，D={di
3、i=1,2,…,n;n≥0;di∈D0或
4、属于某广义表，D0是数据对象}R={LR}LR={
5、di∈D,1≤i≤n}广义表也常简称为表。通常，广义表记为（称为广义表表达式）：Ls=(α1,α2,…,αn)其中，每个αi称为Ls的一个直接元素（也称αi直属Ls），其或为数据对象成员，或为满足本定义的广义表。例如，下面的L=((a,b),c,(d,(e)))就是一个合法的广义表表达式。由上列定义知，若不考虑αi的内部结构，则Ls是一种线性表。但若考虑到αi的内部结构，Ls可能是非常复杂的。下面给出几个相关概念。子表：若某广义
6、表L的某元素结点a本身也是一个广义表，则称a为广义表L的子表。长度：我们仍然称Ls中的元素个数（即各αi的个数，不计αi内部的元素个数）为广义表Ls的长度，它与线性表的长度的概念是相同的。单元素、单元素表：若数据元素为非表元素（即数据对象成员，或说简单元素，如基本数据类型、结构/记录等），则称其为单元素；若Ls中的元素均为单元素，则称其为单元素表。空表：表内无元素（长度为0）的表称为空表。表头：称Ls的第1个元素为Ls的表头。表尾：称Ls中除去表头后其余元素构成的表为表尾。显然，表尾一定是表，但表
7、头不一定。递归表:若表Ls中某成员含有自己(即Ls)，则称Ls为递归表。深度：Ls的深度Depth(Ls)递归地定义为：0：若Ls为单元素Depth(Ls)=1：若Ls为空表1+MAXi(Depth(αi))：其它情况从定义知，广义表的深度，相当于广义表表达式中括号的最大嵌套层数。这里的定义，为了递归，我们将单元素也看作表。层：对任一表Ls，我们称Ls为Ls的第1层（层号为1），Ls的各直接元素均为Ls的第二层元素（层号均为2）;对任意其他元素x，它的直接元素的层号就等于它的层号加1。层号相同者称
8、为同层结点。在这个定义中，我们将不同出现（是不同时出现吗？？？---答：正确，是指不同位置的出现）的相同元素也看作是不同元素，因此，同一个对象，就可能有不同的层号。显然，Ls的深度等于它中层号最大的元素的层号。系列广义表：由于广义表的元素往往也是广义表，所以需要一同考虑。它们称可追溯到同属于某一广义表的各广义表的全体为一个广义表系列（或系列广义表）。下面的叙述中，我们用大写字母表示具体的广义表，用小写字母代表数据对象的成员（单元素）。在同一个广义表系列中，相同字母表示同一对象。下面给出了一个广义表
9、系列。①A=()：空表，无头，无尾，长度为0，深度为1.②B=(a,b,c)：单元素表，头为a，尾为(b,c)，长度为3，深度为1.③C=(a,(b,c,a))：非单元素表，头为a，尾为((b,c,d))，长度为2，深度为2.④D=(B,((a,b),c))：非单元素表，头为B，尾为(((a,b),c)))，长度为2，深度为3.⑤E=(a,E)：非单元素表，头为a，尾为(E)，长度为2，深度为∞，事实上，E=(a,E)=(a,(a(,…)))是个递归表。有时，为了强调广义表名称，可将表名写在表的左
10、括号前面，如上例中的D可写为：D(B(a,b,c),F(G(a,b),c))§8.1.2广义表逻辑图为了表达广义表的逻辑结构，这里用一种图形来形象地表示广义表，称为广义表图。设广义表为L(A1,A2,…,An)，则它的广义表图形成方法为：n画一结点，标为L，称其为广义表L的根；n对每个Ai，若其为单元素，则画一个结点，标为Ai的值（或值的名称），称该结点为终结结点，其即为Ai的根；n对每个Ai，若其为子表，则按该规则画出Ai的广义表图；n从L的根到各Ai的根分别画一条边，将各Ai的
