大学《数据结构》第四章：多维数组和广义表-第三节-广义表基础

1、第三节广义表基础一、广义表的定义广义表是线性表的推广。即广义表中放松对表元素的原子限制，容 许它们具有其自身结构。1、广义表定义广义表是n(n20)个元素al , a2 , . , ai，an的有限序列。其中：ai-或者是原子或者是一个广义表。广义表通常记作：Ls=( al , a2 , . , ai , . , an)0Ls是广义表的名字，n为它的长度。假设ai是广义表，那么称它为Ls的子表。一个表展开后所含括号的层数称为广义表的深度注意：广义表通常用圆括号括起来，用逗号分隔其中的元素。为了区分原子和广义表，书写时用大写字母表示广义表，用小写 字母表示原子。假设广义表Ls非空(nl),那么a

2、l是LS的表头(head),其余元素组 成的表(al, a2 ，,an)称为Ls的表尾(tail)。广义表是递归定义的【例】(1)A=()-A是一个空表，其长度为零，深度为10(2)B=(a)-B是一个只有一个原子的广义表，其长度为1 ,深度为lo(3)C=(a , (b , c)-C是一个长度为2的广义表，第一个元素是原 子，第二个元素是子表，深度为2。(4)D=(A , B , C)=() , (a) , (a , (b , c)-D 是一个长度为 3 的广 义表，其中三个元素均为子表，深度为3。(5)E=(C , d)=(a , (b , c) , d)-E是一个长度为2的广义表,第一

3、个元素是子表，第二个元素是原子，深度为30(6)F=(e , F)=(e , (e , (e ,.)-F是一个递归的表,它的长度为2,第一个元素是原子，第二个元素是表自身，展开后它是一个无限的 广义表,深度为8。2、广义表的几个重要性质：(1 )广义表的元素可以是子表，而子表又可以含有子表，因此广 义表是一个多层次结构的表，它可以用图来形象地表示。=(0, (a), (a, (b, c)Ao=(0, (a), (a, (b, c)A=()(2)广义表具有递归和共享的性质，例如，表F就是一个递归的 广义表，D表是共享的表，在表D中可以不必列出子表的值，而是通 过子表的名字来引用。二、广义表的基本

4、运算广义表是对线性表和树的推广，广义表的大局部运算与这些数据结构上的运算类似。 在此，只讨论广义表的两个特殊的基本运算： 取表头head(Ls)和取表尾tail(Ls)。任何一个非空的广义表其表头可能 是原子,也可能是子表,而其表尾一定是子表。【例】有以下的广义表，试求出下面广义表的表头head。、表 尾 tail。、表长 length。和深度 depth()0(1) A=(a , (b , c , d) , e , (f, g) ;( 2 ) B=(a);(3 ) C=(y , (z , w) , (x , (z , w) , a) ; (4) D=(x , (y) , B),D)o隐藏答案

5、【解答】(1) head(A)=a , tail(A)=(b , c , d) , e , (f, g), length(A)=4 , depth(A)=2 ;(2 ) head(B) = (a) , tail(B)=() , length(B) = l , depth(B)=2 ;(3 ) head(C)=y , tail(C) = (z , w) , (x , (z , w) , a)length(C)=3 , depth(C) = 3 ;(4 ) head(D)=x , tail(D)=(y) , B) , D) , length(D)=3 , depth(D)=ooo【例】取出广义表A

6、=(x , y , z) , (a , b , c , d)中原子b的函数是 o隐藏答案【解析】要从广义表A中取出原子b ,需要先对A取尾运算: tail(A)= (a , b , c , d) z然后再对tai I (A)结果进行取表头运算head(tail(A)= ( a , b , c , d ),然后再对结果进行取表尾运算tail (head (tai I (A) = ( b , c , d ),最后再进行取表头运算tail (head(tail(A) = bo【答案】tail( head(tail(A)真题选解(例题填空题)1、广义表如下：A=(B,y) B = (x , L) L=

7、(a , b)要求：(1)写出以下操作的结果tail(A)=.head(B)=。(2)请画出广义表A对应的图形表示。隐藏答案【答案】(1) (y) x【解析】根据head ()运算和tail ()运算的规那么很容易计算第(1)问，tail(A)= tail(B,y)= ( y ) , head(B)= head(x , L)=xo 第(2 )问画出广义表A对应的图形表示，方法见前面讲解。(例题填空题)2、广义表C=(a , (b , c) , d),那么：tail(head(tail(C)=o隐藏答案【解析】tail(head(tail(C)=tail(head(tail(a , (b , c

8、) , d) = tail(head (b , c), d) = tail(b , c)=(c)【答案】(c)三、广义表的存储结构1、结点结构tagdata slinklink说明：(1) tag标志位,tag = l ,该结点是子表，第二个域为 slink,用以存放子表的地址；当tag=0时，该结点是原子结点，第二 个域为data ,用以存放元素值。(2 ) link域是用来存放与本元素同一层的下一个元素对应结点的 地址，当该元素是所在层的最后一个元素时，link的值为NULLO【例】A=() A=NULLE=(a)C= (a, (b, c)D=(A B, C)= (), (a) 9 (a, (b c)运算的实现考试大纲没做要求，不讲。当前讲授本章小结前两章讨论的线性表、栈和队列都是典型的线性结构，结构中数据 元素都是不能分解的非结构的原子类型。它们的逻辑特征是：每个数 据元素至多有一个直接前趋和直接后续。而多维数组和广义表是一种 复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直 接前趋和直接后继。多维数组可以看成是线性表的推广。因为一旦确定数组是按行或按 列优先顺序存储之后，每个数组元素之间的关系就同一维数