广义表(Lists 又称列表)是线性表的推广 即广义表中放松对表元素的原子限制 容许它们具有其自身结构
广义表定义 广义表是n(n≥ )个元素a a … ai … an的有限序列 其中 ①ai 或者是原子或者是一个广义表 ②广义表通常记作 Ls=( a a … ai … an) ③Ls是广义表的名字 n为它的长度 ④若ai是广义表 则称它为Ls的子表 注意 ①广义表通常用圆括号括起来 用逗号分隔其中的元素 ②为了区分原子和广义表 书写时用大写字母表示广义表 用小写字母表示原子 ③若广义表Ls非空(n≥ ) 则al是LS的表头 其余元素组成的表(a a … an)称为Ls的表尾 ④广义表是递归定义的
广义表表示 （ ）广义表常用表示 ① E=() E是一个空表 其长度为 ② L=(a b) L是长度为 的广义表 它的两个元素都是原子 因此它是一个线性表 ③ A=(x L)=(x (a b)) A是长度为 的广义表 第一个元素是原子x 第二个元素是子表L ④ B=(A y)=((x (a b)) y) B是长度为 的广义表 第一个元素是子表A 第二个元素是原子y ⑤ C=(A B)=((x (a b)) ((x (a b)) y)) C的长度为 两个元素都是子表 ⑥ D=(a D)=(a (a (a (…)))) D的长度为 第一个元素是原子 第二个元素是D自身 展开后它是一个无限的广义表
（ ）广义表的深度 一个表的 深度 是指表展开后所含括号的层数 【例】表L A B C的深度为分别为 表D的深度为∞
（ ）带名字的广义表表示 如果规定任何表都是有名字的 为了既表明每个表的名字 又说明它的组成 则可以在每个表的前面冠以该表的名字 于是上例中的各表又可以写成 ①E()②L(a b)③A(x L(a b))④B(A(x L(a b)) y)⑤C(A(x l(a b)) B(A(x L(a b)) y))⑥D(a D(a D(…)))
（ ）广义表的图形表示 （a）广义表的图形表示 ①图中的分支结点对应广义表 ②非分支结点一般是原子 ③但空表对应的也是非分支结点 【例】下图给出了几个广义表的图形表示
（b）广义表的图形形状划分 ①与树对应的广义表称为纯表 它限制了表中成分的共享和递归 ②允许结点共享的表称再入表 【例】上图(d) 子表A是共享结点 它既是C的一个元素 又是子表B的元素 ③允许递归的表称为递归表 【例】上图(e) 表D是其自身的子表
（ ）递归表 再人表 纯表 线性表之间的关系满足 广义表不仅是线性表的推广 也是树的推广
广义表运算 由于广义表是对线性表和树的推广 并且具有共享和递归特性的广义表可以和有向图(见第 章)建立对应 因此广义表的大部分运算与这些数据结构上的运算类似 在此 只讨论广义表的两个特殊的基本运算 取表头head(Ls)和取表尾tail(Ls) 根据表头 表尾的定义可知 任何一个非空广义表的表头是表中第一个元素 它可以是原子 也可以是子表 而其表尾必定是子表 【例】 head(L)=a tail(L)=(b) head(B)=A tail(B)=(y) 由于tail(L)是非空表 可继续分解得到 head(tail(L))=b tail(tail(L))=() 对非空表A和(y) 也可继续分解 注意: 广义表()和(())不同 前者是长度为 的空表 对其不能做求表头和表尾的运算 而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表) 对其可进行分解 得到的表头和表尾均是空表()
lishixinzhi/Article/program/sjjg/201311/23616