第七章广义表
1 第七章 广义表
§71广义表的逻辑结构 §71.1基本概念 °广义表是一个二元组 Lists=D, R) 其中, D={d1i=1,2,…,n;n>0;d∈D或属于某广义表, D是数据对象} R=LRI LR={<d;d>|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-1 , di> | 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 )) ：其它情况 •从定义知，广义表的深度，相当于广义表表达式中括号的最大嵌套 层数