一、     广义表

(一)、广义表的基础概念

1.广义表（Generalized List），也称为列表的列表（List of Lists），是线性表的推广。由n(n ≧0)个元素组成的有穷序列： LS=(a1，a2，…，an)，ai或者是原子项，或者是一个广义表，若ai是广义表，则称为LS的子表。这种结构允许进行递归定义，因此广义表是一种非常有用的数据结构，可以用来表示复杂的数据结构。LS是广义表的名字，n为它的长度。通常原子用小写字母，子表用大写字母。

1.原子（Atomic）元素：单个的数据项，如整数、实数或字符等。

2.子表（Sublist）：广义表中的元素也可以是一个广义表。

若广义表LS非空时，a1(表中第一个元素)称为表头；其余元素组成的子表称为表尾；(a2，a3，…，an)；

3.表头（Head）：广义表中的第一个元素，它可以是原子元素或子表。

4.表尾（Tail）：广义表中除了表头之外的其余部分，它本身也是一个广义表。

广义表中所包含的元素(包括原子和子表)的个数称为表的长度。广义表中括号的最大层数称为表深 (度)。

2.广义表的表示方法

广义表通常用以下方式表示：

使用圆括号 `()` 来表示广义表的界限。

表头和表尾之间用逗号 `,` 分隔。

空表用空圆括号 `()` 表示。

例如，以下是一些广义表的表示：

`()`：空表

`(a)`：只包含一个原子项a的广义表

`(a, b)`：包含两个原子项a和b的广义表

`(a, (b, c))`：第一个元素是原子项a，第二个元素是包含原子项b和c的子表

`((a, b), (c, d))`：包含两个子表，每个子表都包含两个原子项

3.广义表的特点:

(1)广义表的元素可以是原子，也可以是子表。

(2)广义表可以被其它广义表所共享，也可以共享其它广义表。

(3)广义表本身可以是一个递归表。

(4) 根据对表头、表尾的定义，任何一个非空广义表的表头

可以是原子，也可以是子表， 而表尾必定是广义表。

(二)、广义表的存储结构

广义表通常用链式存储结构表示，每个数据元素用一个结点表示。广义表中有两类结点：

（1）表结点，用来表示广义表项，由标志域，表头指针

域，表尾指针域组成;

（2）原子结点，用来表示原子项，由标志域，原子的值

域组成。

广义表的数据结构定义

typedef struct GLNode

{

int tag ; /* 标志域，为1：表结点;为0 ：原子结点 */

union

{

elemtype value; /* 原子结点的值域 */

struct

{

struct GLNode *hp , *tp ;

}ptr ; /* ptr和atom两成员共用 */

}Gdata ;

} GLNode ; /* 广义表结点类型 */