什么是广义表

广义表是个递归定义，广义表一般记作：LS = (a1,a2, ... ,an)其中ai可以是单个元素称作原子，也可以是广义表称作子表，LS是广义表的名称，n是它的长度。习惯上用大写字母表示广义表的名称，用小写字母表示原子。当广义表LS非空时，称第一个元素a1为LS的表头（Head），称其余元素组成的表(a2,a3, ... ,an)是LS的表尾（Tail）。显然：任何一个非空列表其表头可能是原子也可能是列表，而其表尾必定为列表。

广义表的存储结构

根据定义很容易构造广义表的存储结构，下面给出代码：

//广义表的头尾链表存储表示
typedef enum { ATOM, LIST } ElemTag;    //  ATOM == 0 : 原子；  LIST == 1 : 子表
typedef struct GLNode {
	ElemTag    tag;    //公共部分，用于区分原子节点和表节点
	union {    //原子节点和表节点的联合部分
		AtomType    atom;    //atom是原子节点的值域，AtomeType有用户定义
		struct {  struct GLNode    *hp,  *tp ;  } ptr;    //ptr是表节点的指针域，ptr.hp和ptr.tp分别指向表头和表尾
	};
}  *GList;    //广义表类型

可见：对于广义表无论表头节点类型如何，表尾一定为广义表，则有广义表的另一种表达：

//广义表的扩展线性链表存储表示
typedef enum { ATOM, LIST } ElemTag;    //  ATOM == 0 : 原子；  LIST == 1 : 子表
typedef struct GLNode {
	ElemTag    tag;    //公共部分，用于区分原子节点和表节点
	union {    //原子节点和表节点的联合部分
		AtomType    atom;    //atom是原子节点的值域，AtomeType有用户定义
		struct GLNode    *hp;    //hp指向表头
	};
	struct GLNode    *tp ;    //tp指向表尾
}  *GList;    //广义表类型

这种结构非常类似于线性表的链式存储结构。

总结：广义表的存储结构表示中很难分清其表中的层次关系，根据广义表定义结合其存储结构表示结合线性表的链式存储结构，就很容易明白（可以看广义表的第二种代码表示促进理解），对于广义表同一层次的节点表示，子表只可能出现在表头的位置，若表头的类型不为原子节点，则必为广义表的字表。表达的依然不清楚下面上图：此图对应于第一种C语言描述，可见：原子a和e在同一层次上，而b、c和d在同一层次上且比a和e低一层，B和C是同一层的字表，也就是我上面说的只有出现在表头的非原子结构才是广义表的子表。此图对应于第二种C语言描述，也同样：只有出现在表头的非原子结构才是广义表的子表。

广义表的一些算法

广义表的深度

理解了广义表中广义表和子表的关系很容易就写出了它的递归求法，不过首先我还是先写出递归表示，再上代码： DEPTH(LS)的递归定义：

基本项： * DEPTH(LS) = 1 当LS为空表时； * DEPTH(LS) = 0 当LS为原子时；
归纳项： * `DEPTH(LS) = 1 + MAX{DEPTH(ai)} n >= 1, 1 <= i <= n。

代码：

int GListDepth(GList L) {
	//采用头尾链表存储结构（即是第一种表示），求广义表的深度。
	if(!L) return 1;    //空表深度为1
	if(L->tag == ATOM) return 0;    //原子深度为0
	for(max = 0, pp = L; pp; pp = pp -> ptr.tp) {
		dep = GListDepth(pp->ptr.hp);    //求以pp->ptr.hp为头指针的子表深度，前面也解释了为什么表头指针表示的是子表
		if(dep > max) max = dep;
	}
	return max+1;    //非空表的深度是各元素的深度的最大值加一
}

广义表的复制

赋值的递归实现也是非常简单的，下面我只给出它的递归定义，不再给出代码：

基本项：InitGList(NEWLS) {置空表} 当LS为空表时；
归纳项： * COPY(GetHead(LS), GetHead(NEWLS)) {复制表头} * COPY(GetTail(LS), GetTail(NEWSLS)) {复制表尾}

广义表的其他操作：略

总结自：《数据结构（C语言版）》清华大学出版社严蔚敏、吴伟民编著