第七章广义表
1 第七章 广义表
§71广义表的逻辑结构 §71.1基本概念 °广义表是一个二元组 Lists=D, R) 其中, D={d1i=1,2,…,n;n>0;d∈D或属于某广义表, D是数据对象} R=LRI LR={|di∈D,1≤in}
2 §7.1 广义表的逻辑结构 •广义表是一个二元组 Lists=(D, R) 其中， D={di | i=1, 2, …, n; n≥0; di∈D0或属于某广义表， D0是数据对象} R={LR} LR={ | di∈D, 1≤i≤n} §7.1.1 基本概念
§7.1.1基本概念 通常,广义表记为(称为广义表表达式): LS=(α1,a 其中,每个α或为数据对象成员,或为(广义) 表 例如, L=(a,b),c,(d,(e)
3 §7.1.1 基本概念 •通常，广义表记为（称为广义表表达式）： Ls=(α1 ,α2 , …, αn ) 其中，每个αi或为数据对象成员，或为（广义） 表。 •例如， L = ((a,b), c, (d, (e)) )
相关概念 子表:若某广义表L的某元素结点a本身也是一个广义表, 则称该元素对应的广义表为广义表L的子表 长度:我们仍然称Ls中的元素个数(即a的个数,不计a 内部的元素个数)为广义表Ls的长度,它与线性表的长 度的概念是相同的 单元素、单元素表:若数据元素为非表元素(即简单元 素,如基本数据类型、结构/记录等),则称其为单元素; 若Ls中的元素均为单元素,则称其为单元素表 空表:表内无元素(长度为0)的表称为空表
4 相关概念 •子表：若某广义表L的某元素结点a本身也是一个广义表， 则称该元素对应的广义表为广义表L的子表。 •长度：我们仍然称Ls中的元素个数（即αi的个数，不计αi 内部的元素个数）为广义表Ls的长度，它与线性表的长 度的概念是相同的。 •单元素、单元素表：若数据元素为非表元素（即简单元 素，如基本数据类型、结构/记录等），则称其为单元素； 若Ls中的元素均为单元素，则称其为单元素表。 •空表：表内无元素（长度为0）的表称为空表
相关概念(续) 表头:称Ls的第1个元素为Ls的表头。 表尾:称Ls中除去表头后其余元素构成的表为表尾。 显然,表尾一定是表,但表头不一定。 深度:Ls的深度 Depth(Ls)递归地定义为 :若Ls为单元素 Depth (ls)=1 :若Ls为空表 1+ MAX Depth(a ) 其它情况 从定义知,广义表的深度,相当于广义表表达式中括号的最大嵌套 层数
5 相关概念(续) •表头：称Ls的第1个元素为Ls的表头。 •表尾：称Ls中除去表头后其余元素构成的表为表尾。 显然，表尾一定是表，但表头不一定。 •深度：Ls的深度Depth(Ls)递归地定义为： 0 ：若Ls为单元素 Depth(Ls) = 1 ：若Ls为空表 1 + MAXi (Depth(αi )) ：其它情况 •从定义知，广义表的深度，相当于广义表表达式中括号的最大嵌套 层数
相关概念(续) 层:我们将元素的深度值称做该元素的层号,层号相同者称为同层 结点 系列广义表:由于广义表的元素往往也是广义表,所以需要一同考 虑。我们称可追塑到同属于某一广义表的所有广义表为一个广义表 系列(或系列广义表) 递归表:若表Ls中某成员含有自己(即Ls,则称Ls为递归表。 下面的叙述中,我们用大写字母表示具体的广义表,用小写字母代 表数据对象的成员(单元素)。在同一个广义表系列中,相同字母 表示同一对象
6 相关概念(续) •层：我们将元素的深度值称做该元素的层号，层号相同者称为同层 结点。 •系列广义表：由于广义表的元素往往也是广义表，所以需要一同考 虑。我们称可追塑到同属于某一广义表的所有广义表为一个广义表 系列（或系列广义表）。 •递归表:若表Ls中某成员含有自己(即Ls)，则称Ls为递归表。 •下面的叙述中，我们用大写字母表示具体的广义表，用小写字母代 表数据对象的成员（单元素）。在同一个广义表系列中，相同字母 表示同一对象
广义表例子 ①A=():空表,无头,尾为空表,长度为0,深度为1 ②B=(a,b,c):单元素表,头为a,尾为(bc),长度为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 广义表例子 ① 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) )
§712基本特性 宏观线性性:对任意广义表,若不考虑它的元素的内部结构,则它 是一个线性表,即它的直接元素之间是线性关系 元素递归性:广义表的任一元素,又可以是一个广义表(其它广义 表或自身)。这种递归性使得广义表具有强有力的表达能力,这是 广义表最重要的特性 元素共享性:在同一广义表系列中,任一元素(单元素或表)均可 以出现多次,同一元素的多次出现都代表的是同一个目标,可以认 为它们是共享同一目标,具有该特性的表也称再入表
8 §7.1.2 基本特性 •宏观线性性：对任意广义表，若不考虑它的元素的内部结构，则它 是一个线性表，即它的直接元素之间是线性关系。 •元素递归性：广义表的任一元素，又可以是一个广义表（其它广义 表或自身）。这种递归性使得广义表具有强有力的表达能力，这是 广义表最重要的特性。 •元素共享性：在同一广义表系列中，任一元素（单元素或表）均可 以出现多次，同一元素的多次出现都代表的是同一个目标，可以认 为它们是共享同一目标，具有该特性的表也称再入表
§713基本操作 线性表的基本运算 求深度 求表头 求表尾 求成员 串行化
9 §7.1.3 基本操作 • 线性表的基本运算 • 求深度 • 求表头 • 求表尾 • 求成员 • 串行化
§72广义表的存贮结构 §721基本存储方法 ·具有较高的复杂性,因此一般只采用链式存贮 结构 ·分枝单链表法—一种通用的存贮结构
10 §7.2 广义表的存贮结构 • 具有较高的复杂性，因此一般只采用链式存贮 结构 • 分枝单链表法── 一种通用的存贮结构 §7.2.1 基本存储方法
