目录
一、广义表的定义
二、广义表的存储结构
2.1 头尾链表表示法
2.2 扩展线性链表表示法
附：系列文章
一、广义表的定义
广义表是线性表的推广。广义表是由零个或多个单元素或子表所组成的有限序列，也称其为列表。
在线性表的定义中，a[i]只限于单个元素。而在某些情况下需要扩充线性表，a[i]不在局限于单个元素，也可以是个广义表。广义表一般记为：LS=(a[1],a[2],……,a[n])
其中，LS为广义表的名称；n 为广义表的长度；a[i]可以是单个元素，也可以是广义表，称为LS的原子和子表。通常用大写字母表示广义表的子表，用小写字母表示原子。当广义表非空时，称第一个元素a[i]为表头，称其余元素组成的表（a[2],a[3],a[4],……,a[n]）为表尾。
显然，广义表的定义是一个递归的定义，在描述广义表的同时又用到了广义表的概念。下面列举一些广义表的例子：
（1）A=（）：A是一个空表，长度为零。
（2）B=（e）：B是只有一个原子e的广义表，长度为 1。
（3）C=（a,(b,c,d)）：列表C的长度为2，两个元素分别为原子a和子表（b,c,d）
（4）D=（A,B,C）：列表D的长度为3，包含三个列表元素。将子表的值带入后，则有D=（(),(e),(a,(b,c,d))）
（5）E=（a,E）：这是一个递归的表，它的长度为2。E相当于一个无限的列表E=（a,(a,(a,……）
从上述广义表的定义和例子可以得到广义表的下列重要性质：
（1）广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表……
（2）广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表，如E就是一个递归的表。
（3）广义表可以为其他表所共享。例如，表A、表B、表C和表D的共享子表。在表D中可以不必列出子表的值，而用子表的名称来引用。
（4）广义表有两个重要的基本操作，取表头操作Get Head（）和取表尾操作Get Tail（）。根据表头和表尾的定义可知，任何一个非空列表的表头可以是原子，也可能是列表，而其表尾必定为列表。
例如：Get Head（B）= e
列表（）和（（））是不同的，前者为空表，长度为0；后者为非空表，长度为1，其表头和表尾均为空表（）。
广义表可以看成是线性表的推广，线性表是广义表的特例。广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构，列表是一个多层次的结构，可以用图形直观地表示其层次。
二、广义表的存储结构
由于广义表中的数据元素可以具有不同的结构，因此难以用顺序的存储结构来表示。而链式的存储结构分配较为灵活，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。在这种表示方式下，每个数据元素可以用一个结点表示。
按结点形式的不同，广义表的链式存储结构又可以分为两种不同的存储方式，一种称为头尾链表表示法；另一种称为扩展线性链表表示法。
2.1 头尾链表表示法
由于列表中的数据元素可以是原子或列表，由此需要两种结构的特点：一种是表结点，用来表示子表；另一种是原子结点，用来表示原子。若子表不为空，则可分解为表头和表尾；由此一对表头和表尾可唯一确定子表。一个表头结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域。原子结点只需要标志域和值域两个域。
Typedef enum {ATOM,LIST} ElemTag;Typedef struct GLNode{int tag;Union{ElemType data;Struct{struct GLNode *hp,*tp;}sublist;}val;}*Glist;
从上述存储结构示例中可以看出：
（1）除空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点，且该结点中的hp域指示列表表头（或为原子结点或为表结点），tp域指向列表表尾（除非表尾为空，则指针为空，否则必为表结点）
（2）采用头尾表示法容易分清列表中原子或子表所在的层次。例如，在广义表D中，原子 a 和 e 在同一层次上，而 b,c,d在同一层次上且比 a 和 e 低一层，子表B和C在同一层次上。另外，最高层的表结点的个数即为广义表的长度。例如，在广义表D的最高层有三个表结点，其广义表的长度为3。
2.2 扩展线性链表表示法
广义表的另一种表示法称为扩展线性链表表示法。在这种表示法中，也有两种结点形式：一种是表结点，用以表示子表；另一种是原子结点，用以表示原子。在表结点中包括一个指向子表的指针hp和一个指向后继的指针tp；而在原子结点中包括该原子的值域和一个指向后继的指针tp。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为1，则表示该结点为子表结点；如果标志为0，则表示该结点为原子结点。
Typedef enum{ATOM,LIST} ElemTag;Typedef struct GLNode{int tag;Union{ElemType data;struct GLNode hp;}val;struct GLNode tp;}*Glist;
