广义表，顾名思义，它也是线性表的一种推广。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构，就连LISP 语言的程序也表示为一系列的广义表。
在第二章中，线性表被定义为一个有限的序列（a1，a2，a3，…，an）其中ai被限定为是单个数据元素。广义表也是n个数据元素d1，d2，d3，…，dn的有限序列，但不同的是，广义表中的di 则既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，…，dn）。GL是广义表的名字，通常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表，则称di是广义表GL的子表。在广义表GL中，d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，…，dn）称为广义表的表尾。由此可见广义表的定义是递归定义的。因为在定义广义表时，又使用了广义表的概念。下面给出一些广义表的例子，以加深对广义表概念的理解。
l D=（） 空表；其长度为零。
l A=（a，（b，c）） 表长度为2的广义表，其中第一个元素是单个数据a，第二个元素是一个子表（b，c）。
l B=（A，A，D） 长度为3的广义表，其前两个元素为表A，第三个元素为空表D。
l C=（a，C） 长度为2递归定义的广义表，C相当于无穷表C=（a，（a，（a，（…））））。
其中，A，B，C，D是广义表的名字。下面以广义表A为例，说明求表头、表尾的操作如下：
head（A）=a； 表A的表头是：a
tail（A）=（（b，c））； 表A的表尾是（（b，c））。广义表的表尾一定是一个表。
从上面的例子可以看出：
（1） 广义表的元素可以是子表，而子表还可以是子表…，由此，广义表是一个多层的结构。
（2） 广义表可以被其他广义表共享。如：广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。
（3） 广义表具有递归性，如广义表C。
由于广义表GL=（d1，d2，d3，…，dn）中的数据元素既可以是单个元素，也可以是子表，因此对于广义表，我们难以用顺序存储结构来表示它，通常我们用链式存储结构来表示。表中的每个元素可用一个结点来表示。广义表中有两类结点，一类是单个元素结点，一类是子表结点。从上节得知，任何一个非空的广义表都可以将其分解成表头和表尾两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。由此，一个表结点可由三个域构成：标志域，指向表头的指针域，指向表尾的指针域。而元素结点置需要两个域：标志域和值域。其形式说明如下：
/*广义表的头尾链表存储结构*/
typedef enum {ATOM, LIST} ElemTag; /* ATOM＝0，表示原子；LIST＝1，表示子表*/
typedef struct GLNode
{
ElemTag tag; /*标志位tag用来区别原子结点和表结点*/
union
{
AtomType atom; /*原子结点的值域atom*/
struct { struct GLNode * hp, *tp;} htp; /*表结点的指针域htp， 包括
表头指针域hp和表尾指针域tp*/
} atom_htp; /* atom_htp 是原子结点的值域atom和
表结点的指针域htp的联合体域*/
} *GList；
实现
#include "stdio.h"
typedef struct node
{
int tag;
union{struct node *sublist;
char data;
}dd;
struct node *link;
}NODE;
NODE *creat_GL(char **s)
{
NODE *h;
char ch;
ch=*(*s);
(*s)++;
if(ch!='\0')
{
h=(NODE*)malloc(sizeof(NODE));
if(ch=='(')
{
h->tag=1;
h->dd.sublist=creat_GL(s);
}
else
{
h->tag=0;
h->dd.data=ch;
}
}
else
h=NULL;
ch=*(*s);
(*s)++;
if(h!=NULL)
if(ch==',')
h->link =creat_GL(s);
else
h->link=NULL;
return(h);
}
void prn_GL(NODE *p)
{
if(p!=NULL)
{
if(p->tag==1)
{
printf("(");
if(p->dd.sublist ==NULL)
printf(" ");
else
prn_GL(p->dd.sublist );
}
else
printf("%c",p->dd.data);
if(p->tag==1)
printf(")");
if(p->link!=NULL)
{
printf(",");
prn_GL(p->link);
}
}
}
NODE *copy_GL(NODE *p)
{
NODE *q;
if(p==NULL) return(NULL);
q=(NODE *)malloc(sizeof(NODE));
q->tag=p->tag;
if(p->tag)
q->dd.sublist =copy_GL(p->dd.sublist );
else
q->dd.data =p->dd.data;
q->link=copy_GL(p->link);
return(q);
}
int depth(NODE *p)
{
int h,maxdh;
NODE *q;
if(p->tag==0) return(0);
else
if(p->tag==1&&p->dd.sublist==NULL) return 1;
else
{
maxdh=0;
while(p!=NULL)
{
if(p->tag==0) h=0;
else
{q=p->dd.sublist;
h=depth(q);
}
if(h>maxdh)
maxdh=h;
p=p->link;
}
return(maxdh+1);
}
}
int count(NODE *p)
{
int m,n;
if(p==NULL) return(0);
else
{
if(p->tag==0) n=1;
else
n=count(p->dd.sublist);
if(p->link!=NULL)
m=count(p->link);
else m=0;
return(n+m);
}
}
main()
{
NODE *hd,*hc;
char s[100]="(a,(b,(c,d)))",*p;
/*p=gets(s);*/
p=s;
hd=creat_GL(&p);
hc=copy_GL(hd);
printf("\ncopy after:");
prn_GL(hc);
printf("\ndepth=%d (wrong?)",depth(hc));
printf("\ncount=%d",count(hc));
getch();
}
