《数据结构》课程教学资源：电子教案 第8章 广义表

第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))) 若用圆圈和方框分别表示表和单元素,并用线段把表 和它的元素(元素结点应在其表结点的下方)连接起来,则 可得到一个广义表的图形表示。例如,上面五个广义表 的图形表示如下图所示

Ao B(e) c(a, (b, c, d) D(AO, B(e), C(a, (b, c, d)) E(a,(a2b)2(a,b),c) ○ 面Q□ b

a b c a b E d e a b c D A B C b c d C a B e A a A() B(e) C(a,(b,c,d)) D(A(),B(e),C(a,(b,c,d))) E((a,(a,b),((a,b),c)))

8.2广义表的存储结构 广义表是一种递归的数据结构,因此很难为每个 广义表分配固定大小的存储空间所以其存储结构只 好采用动态链式结构。 我们将一个广义表看成一棵树为了方便存储将 其转换成一棵二叉树。其转换过程已在第6章中介绍 过这里以示例中的广义表C说明其转换过程。如下 图所示左边的图表示转换的中间状态右边的图表示 转换的最终状态,即一棵二叉树。从二叉树中看到有 两类结点,一类为圆圈结点,在这里对应子表;另一类 为方形结点在这里对应原子

8.2 广义表的存储结构 广义表是一种递归的数据结构,因此很难为每个 广义表分配固定大小的存储空间,所以其存储结构只 好采用动态链式结构。 我们将一个广义表看成一棵树,为了方便存储,将 其转换成一棵二叉树。其转换过程已在第6章中介绍 过,这里以示例中的广义表C说明其转换过程。如下 图所示,左边的图表示转换的中间状态,右边的图表示 转换的最终状态,即一棵二叉树。从二叉树中看到,有 两类结点,一类为圆圈结点,在这里对应子表；另一类 为方形结点,在这里对应原子

C d C→h[ pob+-叫→d小

C a b c d C a b c d C 1 ∧ 0 a 1 ∧ 0 b 0 c 0 d ∧

typedef struct Inode int tag, /结点类型标识 union t ElemType data; struct Inode *sublist 3 val; struct Inode *link;/指向下一个元素* 3 GLNode; /广义表结点类型定义

typedef struct lnode { int tag; /*结点类型标识*/ union { ElemType data; struct lnode *sublist; } val; struct lnode *link; /*指向下一个元素*/ } GLNode; /*广义表结点类型定义*/

广义表的两种基本情况: g …- 第1个元素第2个元素 第n个元素 (a)空表 (b)非空表 为原子的情况:

广义表的两种基本情况 ： g1 1 ∧ ∧ … g2 1 ∧ * * * * * * ∧ 第 1 个元素 第 2 个元素 第 n 个元素 （a）空表 （b）非空表 为原子的情况 ： g3 0 a ∧