文档介绍：广义表的定义
第8章广义表
广义表的存储结构
广义表的运算
本章小结
广义表的定义
广义表简称表,它是线性表的推广。一个广义表是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和表尾tail(GL) = ( a2,…,an) 两部分。
为了简单起见,下面讨论的广义表不包括前面定义的再入表和递归表,即只讨论一般的广义表。另外,我们规定用小写字母表示原子,用大写字母表示广义表的表名。例如:
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个广义表可相应地表示如下:
A()
B(e)
C(a,(b,c,d))
D(A(),B(e),C(a,(b,c,d)))
E((a,(a,b),((a,b),c)))
若用圆圈和方框分别表示表和单元素,并用线段把表和它的元素(元素结点应在其表结点的下方)连接起来,则可得到一个广义表的图形表示。例如,上面五个广义表的图形表示如下图所示。
A() B(e) C(a,(b,c,d)) D(A(),B(e),C(a,(b,c,d)))
E((a,(a,b),((a,b),c)))
广义表的存储结构
广义表是一种递归的数据结构,因此很难为每个广义表分配固定大小的存储空间,所以其存储结构只好采用动态链式结构。
我们将一个广义表看成一棵树,为了方便存储,将其转换成一棵二叉树。其转换过程已在第6章中介绍过,这里以示例中的广义表C说明其转换过程。如下图所示,左边的图表示转换的中间状态,右边的图表示转换的最终状态,即一棵二叉树。从二叉树中看到,有两类结点,一类为圆圈结点,在这里对应子表;另一类为方形结点,在这里对应原子。
广义表的存储结构
typedef struct lnode
{ int tag; /*结点类型标识*/
union
{ ElemType data;
struct lnode *sublist;
} val;
struct lnode *link; /*指向下一个元素*/
} GLNode; /*广义表结点类型定义*/
广义表的两种基本情况:
为原子的情况: