【精品数据结构】广义表.PPTVIP

第七章 广义表 §7.1 广义表的逻辑结构 广义表是一个二元组 　　Lists=(D, R) 其中， D={di | i=1, 2, …, n; n≥0; di∈D0或属于某广义表，D0是数据对象} R={LR} LR={di-1, di | di∈D, 1≤i≤n} 通常，广义表记为（称为广义表表达式）： 　　　Ls=(α1,α2, …, αn) 其中，每个αi或为数据对象成员，或为（广义）表。 例如， L = ((a,b), c, (d, (e)) ) 相关概念 子表：若某广义表L的某元素结点a本身也是一个广义表，则称该元素对应的广义表为广义表L的子表。 长度：我们仍然称Ls中的元素个数（即αi的个数，不计αi内部的元素个数）为广义表Ls的长度，它与线性表的长度的概念是相同的。 单元素、单元素表：若数据元素为非表元素（即简单元素，如基本数据类型、结构/记录等），则称其为单元素；若Ls中的元素均为单元素，则称其为单元素表。 空表：表内无元素（长度为0）的表称为空表。 相关概念(续) 表头：称Ls的第1个元素为Ls的表头。 表尾：称Ls中除去表头后其余元素构成的表为表尾。 显然，表尾一定是表，但表头不一定。 深度：Ls的深度Depth(Ls)递归地定义为： 0 ：若Ls为单元素 　　　 Depth(Ls) = 1 ：若Ls为空表 1 + MAXi(Depth(αi)) ：其它情况 从定义知，广义表的深度，相当于广义表表达式中括号的最大嵌套层数。 相关概念(续) 层：我们将元素的深度值称做该元素的层号，层号相同者称为同层结点。 系列广义表：由于广义表的元素往往也是广义表，所以需要一同考虑。我们称可追塑到同属于某一广义表的所有广义表为一个广义表系列（或系列广义表）。 递归表: 若表Ls中某成员含有自己(即Ls)，则称Ls为递归表。 下面的叙述中，我们用大写字母表示具体的广义表，用小写字母代表数据对象的成员（单元素）。在同一个广义表系列中，相同字母表示同一对象。 广义表例子 ① A=( )：空表，无头，尾为空表，长度为0，深度为1. ② B=(a,b,c)：单元素表，头为a，尾为(b,c)，长度为3，深度为1. ③ C=(a, (b, c, d) )：非单元素表，头为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 (,… ) ) )是个递归表。 有时，为了强调广义表名称，可将表名写在表的左括号前面，如上例中的D 可写为： D( B(a, b, c), F( G(a, b), c) ) §7.1.2 基本特性 宏观线性性：对任意广义表，若不考虑它的元素的内部结构，则它是一个线性表，即它的直接元素之间是线性关系。 元素递归性：广义表的任一元素，又可以是一个广义表（其它广义表或自身）。这种递归性使得广义表具有强有力的表达能力，这是广义表最重要的特性。 元素共享性：在同一广义表系列中，任一元素（单元素或表）均可以出现多次，同一元素的多次出现都代表的是同一个目标，可以认为它们是共享同一目标，具有该特性的表也称再入表。 §7.1.3 基本操作 线性表的基本运算 求深度 求表头 求表尾 求成员 串行化 §7.2 广义表的存贮结构 具有较高的复杂性，因此一般只采用链式存贮结构 分枝单链表法── 一种通用的存贮结构 分枝单链表存贮方法 (a) 为每个αi设置一个结点Hi，称其为αi的头结点，其结构为： ? tag：指示αi是单元素还是广义表(我们设tag为0时表示αi为单元素）。 pElem：若αi为单元素，则指向αi的内容，否则指向αi对应的广义表(可以用第一个头结点H1的指针代表广义表). next：单链表链指针，即指向Hi+1。 分枝单链表存贮方法 (b) αi为单元素时，αi的内容应对应一片连续区域，可在它中设置一个长度字段。 (c) 直接元素构成的单链表，根据具体问题的需要，可以是带头结点的，或循环式的，或双向链式的或这些的组合。 (d)如果不共享单元素内容，且单元素内容的长度相等（或差别不大），则可将单元素内容直接放到元素头结点中。 广义表存储结构示例 广义表存储结构示例 广义表C++描述 template class TElem class TGListNode { char tag; char name[CNST_SizeListNodeName];