|
广义表(Lists又称列表)是线性表的推广即广义表中放松对表元素的原子限制容许它们具有其自身结构 广义表定义 广义表是n(n≥)个元素aa…ai…an的有限序列 其中 ①ai或者是原子或者是一个广义表 ②广义表通常记作 Ls=( aa…ai…an) ③Ls是广义表的名字n为它的长度 ④若ai是广义表则称它为Ls的子表 注意 ①广义表通常用圆括号括起来用逗号分隔其中的元素 ②为了区分原子和广义表书写时用大写字母表示广义表用小写字母表示原子 ③若广义表Ls非空(n≥)则al是LS的表头其余元素组成的表(aa…an)称为Ls的表尾 ④广义表是递归定义的 广义表表示 （）广义表常用表示 ① E=() E是一个空表其长度为 ② L=(ab) L是长度为的广义表它的两个元素都是原子因此它是一个线性表 ③ A=(xL)=(x(ab)) A是长度为的广义表第一个元素是原子x第二个元素是子表L ④ B=(Ay)=((x(ab))y) B是长度为的广义表第一个元素是子表A第二个元素是原子y ⑤ C=(AB)=((x(ab))((x(ab))y)) C的长度为两个元素都是子表 ⑥ D=(aD)=(a(a(a(…)))) D的长度为第一个元素是原子第二个元素是D自身展开后它是一个无限的广义表 （）广义表的深度 一个表的深度是指表展开后所含括号的层数 【例】表LABC的深度为分别为表D的深度为∞ （）带名字的广义表表示 如果规定任何表都是有名字的为了既表明每个表的名字又说明它的组成则可以在每个表的前面冠以该表的名字于是上例中的各表又可以写成 ①E() ②L(ab) ③A(xL(ab)) ④B(A(xL(ab))y) ⑤C(A(xl(ab))B(A(xL(ab))y)) ⑥D(aD(aD(…))) （）广义表的图形表示 （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的非空表(只不过该表中惟一的一个元素是空表)对其可进行分解得到的表头和表尾均是空表() |
