全屏显示专题章节

广义表是一种非线性的数据结构,顾名思义,它也是线性表的一种推广。它被广泛应用于人工智能等领域的表处理语言LISP中。在LISP语言中,广义表是一种最基本的数据结构,就连LISP语言的程序也表示为一系列的广义表。

与数组一样,广义表是线性表的扩展。线性表被定义为一个有限的序列（a₁,a₂,a₃,…,a_n）,其中,a_i被限定为是单个数据元素。

广义表也是n（n≥0）数据元素a₁,a₂,a₃,…,a_n的有限序列,通常记作如下形式。

LS是广义表的名字,通常广义表的名字用大写字母表示,n是广义表的长度。与线性表不同的是,广义表中的a_i则既可以是单个元素（称为原子,用单个小写字母表示）,还可以是一个广义表。若a_i是一个广义表,则称a_i是广义表LS的子表。在广义表LS中,a₁是广义表LS的表头,而广义表LS其余部分组成的表（a₂,a₃,…,a_n）则称为广义表的表尾。广义表展开后所含括号重数称为广义表的深度。

由此可见,广义表的定义是递归定义的。因为在定义广义表时,又使用了广义表的概念,它是一种“多层次”的“线性结构”。

2.广义表的表示

以下为以“字符串”的形式来表示广义表。

（1）A＝（）　A是一个空表,并且长度为零,深度为1。

（2）B＝（a）　B表只有一个原子元素a,并且长度为1,深度为1。

（3）C＝（b,c）　C表中有两个原子元素b、c,实际是一个线性表,长度为2,深度为1。

（4）D＝（d,（e,f,g））　D表长度为2,两元素分别为原子元素d和子表（e,f,g）,深度为2。

（5）E＝（B,A,D）　E表长度为3,三元素都是子表。

（6）F＝（B,E）　F表长度为2。

（7）G＝（h,G）　G表示一个递归的表,其长度为2,深度为无穷。

广义表可以用图来形象的表示,图5－14给出了A、B、C、D、E、F、G的图形表示。

3.广义表的特征

从上面广义表定义和表示可推出广义表的具体特征如下。

（1）广义表是一种线性结构。广义表中的数据元素彼此之间有固定的相对次序,如同线性表。

（2）广义表是一种多层次的结构。广义表中的元素可以是子表,而子表中的元素还可以是子表。例如,广义表E由三个子表B、A和D组成,而D又由一个原子d和一个子表（e,f,g）组成。由图5－13可知,广义表不仅是线性表的推广,也是树的推广。

（3）广义表可以为其他广义表所共享。例如,表B、A和D为E的子表,则在E中不必列出子表的值,而是通过子表的名称来引用。

（4）广义表可以是一个递归的表,即广义表也可以是其本身的子表。例如,表G就是一个递归的广义表。

4.广义表抽象数据类型定义

抽象数据类型广义表的定义如下。

由于广义表中的数据元素可能是原子也可能是子表,因此难以用顺序存储结构表示,通常采用链式存储结构,每个数据元素可用一个结点表示。根据结点的定义不同,广义表有头尾链表和扩展线性链表两种存储结构。

由于广义表中的数据元素可能为原子或广义表,因此需要两种结构的结点:一种是表结点,用于表示广义表及子表；一种为原子结点,用于表示原子。从上一小节广义表的定义可知,一个广义表非空,则可分解为表头和表尾；反之,一对表头和表尾可唯一确定一个广义表。因此,一个表结点可由三个域组成:标志域、指示表头的指针域和指示表尾的指针域。而一个原子结点需要两个域:标志域和值域。头尾链表结点结构如图5－15所示。

广义表头尾链表的类型定义如下。

用头尾链表存储上节中的广义表A、B、C、D、E、F、G,存储结构如图5－16所示。

2.扩展线性链表

扩展线性链表与头尾链表的不同之处在于对原子结点的处理。在扩展线性链表中,原子结点增加了一个指向下一个元素结点的指针,即原子结点由三个域组成:标志域、值域和指向下一个元素结点的指针。扩展线性链表结点结构如图5－17所示。

扩展线性链表类型的定义如下。

用扩展线性链表存储上一小节中的广义表A、B、C、D、E、F、G,存储结构如图5－18所示。