相比于线性表，广义表基于递归定义，可以将广义表本身作为结点存储在其元素中从而体现出更灵活的且宽泛的使用性。虽然，抽象数据类型——数组，也可以提供这类似的宽泛的数据储存功能，但它的长度和维度必须是定义时确定的，而广义表基于递归定义，可在使用时随时扩充删减元素。
定义
广义表时线性表的推广，也可以被称作列表（List）。最为常见的广义表的应用就是Lisp语言，其源程序本身就是一系列广义表。
广义表一般记作：$LS = (a_1,a_2,…,a_n)$。
其中，LS为广义表的名称，n为其长度。与线性表不同的地方在于，$a_i$可以是单个元素也可以是广义表，它们分别成为广义表LS的原子和子表。习惯上，大写字母用来表示广义表的名称，小写字母用来表示原子。
当广义表LS非空时，第一个元素$a_1$为LS的表头(Head)，其余元素组成的表$(a_2,a_3,…,a_n)$是LS的表尾(Tail)。
- $A = ()$ ， A是一个空表，它的长度为0。
- $B = (e)$，B是一个只包含一个原子$e$的表，它的长度为1。
- $C = (a,(b,c,d))$，C的长度为2，元素分别为原子$a$和子表$(b,c,d)$。
- $D = (A,B,C)$，D的长度是3，元素分别为A,B,C一共3个子表。
$GetHead(D) = A \qquad GetTail(D) = (B,C)$
存储结构
广义表的数据元素具有不同的结构，因此难以使用顺序存储结构表示，通常使用链式存储结构表示，主要有两种方式。
头尾链表存储表示
由于数据元素既可能是原子又可能是广义表，所以需要两种结构的结点（可以使用联合类型实现）：
- 表结点，用于表示列表
- 原子结点，用于表示原子。
由于上述定义，只要列表非空则可以确定为表头和表尾。
所以，一个表结点可以由三个域组成：标志域、指示表头的指针域和指示表尾的指针域。
然而，一个原子结点只需要两个域组成：标志域和值域。
// 广义表的头尾链表存储表示
typedef enum {ATOM, LIST} ElemTag; // ATOM 原子 LIST 子表
typedef struct GLNode{
ElemTag tag; // 标志域
union{
AtomType atom; // 值域
struct{ struct GLNode * hp, *tp;}ptr; // 表头指针域 表尾指针域
}
}* GList;
基于头尾链表存储表示的具体广义表示意图：
可以总结如下规律：
- 空表的表头指针指向空。
- 非空列表的表头指针指向具体的表结点。（而不是说表头指针自身就是表结点）
- 可以直接的看出原子和子表所在的层次。
- 最高层表结点的个数就是列表的长度。
扩展线性链表存储表示
这种表示方式和传统的线性表（链表）很相似，至少每种结点都存在一个Next指针，表结点还存在表头指针。
// 广义表的扩展线性链表存储表示
typedef enum {ATOM, LIST} ElemTag; // ATOM 原子 LIST 子表
typedef struct GLNode{
ElemTag tag; // 标志域
union{
AtomType atom; // 值域
struct GLNode *hp; // 表结点的表头指针
};
struct GLNode *tp; // 相当于线性链表的next,指向下一个元素结点
}* GList;
基于扩展线性链表存储表示的具体广义表示意图：
$m$元多项式的表示
对于m元多项式，可以通过抽离公共元的形式将大式化成以少一个元的小式为系数的一元多项式。
例如:
$P(x, y, z)=x^{10} y^{3} z^{2}+2 x^{6} y^{3} z^{2}+3 x^{5} y^{2} z^{2}+x^{4} y^{4} z+6 x^{3} y^{4} z+2 y z+15$
可以改写成：
$p(x, y, z)=\left(\left(x^{10}+2 x^{6}\right) y^{3}+3 x^{5} y^{2}\right) z^{2}+\left(\left(x^{4}+6 x^{3}\right) y^{4}+2 y\right) z+15$
再把化简后的式子用广义表表示，（其实这个书上的(A,2)这样的表示不正确，2应该是A的元信息，而不是和A同级）
$P=z((A, 2),(B, 1),(15,0))$
右边的列表中的每个元素分别为，关于$z$的一元多项式的每个系数和指数构成的列表。同理的，可以递推出$A,B$。
$A=y((C, 3),(D, 2))$ $C=x((1,10),(2,6))$ $D=x((3,5))$ $B=y((E, 4),(F, 1))$ $E=x((1,4)),(6,3) )$ $F=x((2,0))$
若以广义表的扩展线性链表存储表示其存储结构，则结点结构为：
typedef struct MPNode{
ElemTag tag; // 区分结点类型
int exp; // 指数域
union{
float coef; // 系数域
struct MPNode * hp; // 表结点的表头指针
}
struct MPNode * tp; // next指针
}* MPList;
广义表的递归算法
求广义表的深度
广义表的深度定义为广义表中括弧的重数，例如多元多项式广义表的深度就是该多项式中的变元个数。
分析
设非空广义表为
$LS = (a_1,a_2,…,a_n)$
其中$a_i(i=1,2,…,n)$或为原子或为子表，那么求LS的深度可以分解为n个问题。每个子问题为求$a_i$的深度，若$a_i$是原子，则深度为0。若$a_i$为广义表，则按照上述处理，而$LS$为上述n个深度的最大值加1。定义空表的深度为1。
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;
}
广义表的复制
任何一个非空广义表都可以分解成表头和表尾，一对确定的表头和表尾也可以唯一确定一个广义表。所以，复制一个广义表只需要分别复制表头和表尾，然后合成即可。
Status CopyGList(GList &T, GList L){
// 采用头尾链表存储结构，由广义表L复制得到广义表T。
if(!L) T = null;
else{
// 不是空表，就需要建立表结点
if(!(T = (GList)malloc(sizeof(GLNode)))) exit(OVERFLOW);
T->tag = L->tag;
if(L->tag == ATOM) T->atom = L->atom; // 如果是原子直接复制
else{
// 复制表头
CopyGList(T->ptr.hp, L->ptr.hp);
// 复制表尾
CopyGList(T->ptr.tp, L->ptr.tp);
}
}
return OK;
}
基于字符串创建广义表
下方将讨论如何将形如广义表形式的字符串解释成一个广义表。对于任意一个广义表字符串都可能有两种情况：
S = '()'，这是一个空的广义表。S = '(a1,a2,...,an)'，$a_i$是S的子串，即S有n个子表。
若采用头尾链表存储结构的方式存储生成的广义表，那么这个广义表有$n$个表结点序列。且第$i$个表结点的表尾指针指向第$i+1$个表结点。第$n$个表结点的表尾指针为NULL。如果把原子也看做子表的话，第$i$个表结点的表头指针hp指向由$a_i$建立的子表。
由此，由S建广义表的问题可以转化成由$a_i$建子表的问题。$a_i$又有三种情况:
- 带括弧的空白串
- 长度为1的单字符串
- 长度$>1$的字符串
显然前两种情况为递归的终结状态，后一种情况为递归调用。
假定函数server(str,hstr)的功能为，从字符串str中取出第一个","之前的子串复制给hstr，并使str成为删除子串hstr和','之后的剩余串。若str中没有字符,则操作后的hstr即为当前的str，而操作后的str为空串NULL。
Status CreateGList(GList &L, SString S){
// 采用头尾链表存储结构，由广义表的书写形式串S创建广义表L。设emp= "()"
if(StrCompare(S,emp)) L = NULL; // 创建空表
else{
// 字符串非空，所以表中存在结点，所以初始化一个结点
if(!(L = (GList)malloc(sizeof(GLNode)))) exit(OVERFLOW);
if(StrLength(S) == 1){
// 如果就是单独的一个原子，一个字符
L->tag = ATOM;
L->atom = S;
}else{
L->tag = LIST; p = L;
SubString(sub,S,2,StrLength(S) - 2); // 脱外层括号
do{
// 重复建造n个子表
server(sub,hsub);
CreateGList(p -> p.hp, hsub); q = p;
if(!StrEmpty(sub)){
// 表尾不空
if(!(p = (GLNode *)malloc(sizeof(GLNode)))) exit(OVERFLOW);
p->tag = LIST; q->p.tp = p;
}
}while(! strEmpty(sub));
q->p.tp = NULL;
}
}
}