因为有事两天没有更新了，今天暂时只介绍一下广义表的数据结构，暂时不实现它，下一篇将会详细介绍广义表的实现。下面我们就开始介绍。
一、广义表定义：广义表也是线性表的推广，不同的是线性表(a1,a2…ai…an)限定ai是单个数据元素，而广义表(a1,a2…ai…an)中的数据元素Li既可以是单个数据元素也可以还是广义表，我们一般把广义表记作：
GL=(a1,a2…ai…an)。
其中GL是广义表的名称，n是广义表的长度，由于广义表数据元素既可以是单个数据元素也可以是广义表，前者成为广义表GL的原子，后者称为子表，广义表名称一般用大写，小写字母表示原子。当广义表非空时上面第一个元素a1表示表头(Head)，后面的(a2,a3…ai…an)表示广义表的表尾(Tail)。由上面定义广义表时又用到了广义表，因此广义表是递归定义的，下面我们举个例子：
GA=()，空表，其长度为零。
GB=(a,(b,c))，第一个元素原子类型，第二个元素为一个子表，长度为2。
GC=(k)，为单个数据元素，长度为1。
GD=(GA,GB,GC)，该长度为3，表头GA,表尾(GB,GC)。
GE=(a，GE)，长度为2，这是一个递归列表，自己包含自己永远循环下去。
由前面对广义表表头与表尾的定义，可以看出，表头可能是原子类型也可能是子表，但是表尾必定是子表，如上面：
Head(GB)=a，Tail(GB)=(b,c)，
Head(GC)=k，Tail(GC)=()，
Head(GD)=GA，Tail(GD)=(GB,GC)，
由上面我们得到：
1、广义表具有递归性，如GE。
2、广义表数据元素可以是子表，当然了，子表还可以是子表，依次类推。
3、广义表可以被其他广义表共享，只需要调用被共享广义表的名称即可，图上面GD。
再来看一下广义表的抽象数据类型的定义：
ADT GList{
数据对象：D={di| i=1,2,3…n n＞=0 di∈GList或者某个数据对象}
数据关系：R={<d(i-1),di>|d(i-1),i＞=2&&i＜=n}
基本操作：1，创建广义表。
2、求广义表的长度。
3、求广义表深度。
4、复制广义表到另一个广义表。
5、销毁广义表。
等等…
}。
二、广义表的存储结构：广义表的数据元素可以是单个数据元素(原子类型)，也可以是子表，因此用顺序结构存储将很困难，因此我们采用链式结构存储，那么怎么用链式结构存储呢？首先我们要分原子类型与列表类型，怎么区分原子类型跟列表类型呢？我们可以用一个标记，如以0作为原子类型，以1作为列表类型，因此我们纵观之前学过的C语言基础知识中想到枚举类型适合用作标记，因此我们可以声明一个枚举类型的变量，第二如何链接表头跟表尾元素呢，很容易想到用指针，我们可以用两个指针，分别作为一个指向表头的指针，记作头指针，指向表尾的指针记作尾指针，因此一个表可以有三个成分组成，分别是标记区、头指针、尾指针，而原子类型只需要标记区与原子数据本身，把他们都定义在一个结构体当中，但是发现，并不是所有数据元素都需要头指针跟尾指针的，当标记区为0时就不需要两指针，只需要原子类型值，因此很容易想到共用体类型就非常适合，如果标记值为0，那么只取原子的值，如果为1，说明为一个列表，那么就需要头指针跟尾指针了，那么我们可以这样定义广义表的结构体类型：
首先枚举类型表示标记：
typedef enum{ATOM,LIST}TagElem;
typedef struct GList{
TagElem T;
union{
ElemT e;
struct {
GList *pHead;
GList *pTail;
}ptr;
}union_G;
};
上面就是广义表结构体。下面我们看一下此种方式定义的广义表的存储结构示意图：
三、广义表长度：
其实这说起来很简单，也就是广义表中元素个数，如上面GB，长度为二，包含一个原子类型a，与一个列表类型为(b,c)。
四、广义表深度：
也很简单，说白了就是广义表中括号最大层数，如上面的GB最大层数为2，因此广义表深度为2，要是GB中子表里面在包含子表，那么深度就为3。
今天时间问题暂时只介绍到这里，当然定义广义表结构体还有其他方法，这里暂不做介绍，要是你能根据示意图，已经广义表的结构体你自己能独立创建一个广义表函数，那么说明你C语言基本知识掌握的蛮扎实的。
