第8章广义表 8.1广义表的定义 8.2广义表的存储结构 8.3广义表的远算 本章小结
8.1 广义表的定义 第8章 广义表 8.2 广义表的存储结构 8.3 广义表的运算 本章小结
8.1广义表的定义 广义表简称表,它是线性表的推广。一个广义 表是n(120)个元素的一个序列,若n=0时则称为空 表。设a1为广义表的第个元素,则广义表GL的 般表示与线性表相同: GL=(a1,a2y…,a…,an) 其中n表示广义表的长度,即广义表中所含元 素的个数,n>0。如果a是单个数据元素则a是广 义表GL的原子;如果a是一个广义表则a是广义 表GL的子表
8.1 广义表的定义 广义表简称表,它是线性表的推广。一个广义 表是n(n≥0)个元素的一个序列,若n=0时则称为空 表。设ai为广义表的第i个元素,则广义表GL的一 般表示与线性表相同： GL=(a1 ,a2 ,…,ai ,…,an ) 其中n表示广义表的长度,即广义表中所含元 素的个数,n≥0。如果ai是单个数据元素,则ai是广 义表GL的原子；如果ai是一个广义表,则ai是广义 表GL的子表
义表具有如下重要的特性 (1)广义表中的数据元素有相对次序 (2)广义表的长度定义为最外层包含元素个数 (3)广义表的深度定义为所含括弧的重数。其中,原 子的深度为0,空表的深度为1 (4)广义表可以共享;一个广义表可以为其他广义 表共享;这种共享广义表称为再入表 (5)广义表可以是一个递归的表。一个广义表可以 是自已的子表。这种广义表称为递归表。递归表的 深度是无穷值,长度是有限值; (6任何一个非空广义表GL均可分解为表头 head(GL)=a1和表尾tai(GL)=(a2,a)两部分
广义表具有如下重要的特性： (1)广义表中的数据元素有相对次序； (2)广义表的长度定义为最外层包含元素个数； (3)广义表的深度定义为所含括弧的重数。其中,原 子的深度为0,空表的深度为1； (4)广义表可以共享；一个广义表可以为其他广义 表共享；这种共享广义表称为再入表； (5)广义表可以是一个递归的表。一个广义表可以 是自已的子表。这种广义表称为递归表。递归表的 深度是无穷值,长度是有限值； (6)任何一个非空广义表GL均可分解为表头 head(GL) = a1和表尾tail(GL) = ( a2 ,…,an ) 两部分
为了简单起见,下面讨论的广义表不包括前面定 义的再入表和递归表,即只讨论一般的广义表。另 外我们规定用小写字母表示原子,用大写字母表示 广义表的表名。例如: A=0 B=(e) (a,(b,c,d) D=(A,B,C)=(0,(e)(a,(b,c,d) E=(a2(a2b),(a2b),)
为了简单起见,下面讨论的广义表不包括前面定 义的再入表和递归表,即只讨论一般的广义表。另 外,我们规定用小写字母表示原子,用大写字母表示 广义表的表名。例如： A=() B=(e) C=(a,(b,c,d)) D=(A,B,C)=((),(e),(a,(b,c,d))) E=((a,(a,b),((a,b),c)))
如果把每个表的名字(若有的话在其表的前面则上 面的5个广义表可相应地表示如下: AO B(e) C(a, (b, c, d)) D(AO, B(e), c(a, (b, c, d)) E((a, (a, b),((a, b), c) 若用圆圈和方框分别表示表和单元素,并用线段把表 和它的元素元素结点应在其表结点的下方)连接起来,则 可得到一个广义表的图形表示。例如,上面五个广义表 的图形表示如下图所示
如果把每个表的名字(若有的话)写在其表的前面,则上 面的5个广义表可相应地表示如下： A() B(e) C(a,(b,c,d)) D(A(),B(e),C(a,(b,c,d))) E((a,(a,b),((a,b),c))) 若用圆圈和方框分别表示表和单元素,并用线段把表 和它的元素(元素结点应在其表结点的下方)连接起来,则 可得到一个广义表的图形表示。例如,上面五个广义表 的图形表示如下图所示