广义表
广义表是线性表的推广，也可称之为列表（lists）。广泛地用于人工智能等领域的表处理语言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）称为广义表的表尾。由此可见广义表的定义是递归定义的。因为在定义广义表时，又使用了广义表的概念。（百度百科，发现百度百科上就是抄的《数据结构》的原话嘛）
在广义表的定义中，元素a1可以是单个元素，也可以是广义表，分别称为广西表的原子和子表。
当广义表非空时，称第一个元素a1为广义表的表头，称其余元素组成的表是广义表的表尾。
广义表的定义是一个递归的定义，因为在描述广义表时又用到了广义表的概念。
根据定义，广义表的三条重要结论：
1.广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次结构；
2.广义表可为其他广义表共享（子表）；
3.广义表可以是一个递归的表，即任何广义表可以是其本身的一个子表。
根据表头、表尾的定义可知：任何一个非空广义表其表头可能是原子，也可能是广义表，而其表尾必定为广义表。
注意：列表（）和（（））是不一样的，前者是空表，长度n=0，后者长度n=1，可分解得到其表头、表尾均为空表。即使成员表的长度为零，但因为有成员表，因此长度为1.这也体现了为什么说广义表是一个递归的表。
广义表的存储结构
由于广义表中的数据元素可以具有不同的结构（或原子或广义表），因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据可用一个结点（还有升级空间啊，换上树的话鸟枪换炮啊）。
因为数据元素可能为原子或广义表，因此需要两种结构特点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。
反之，一对确定的表头表尾可唯一确定广义表。因此，一个表结点可由3个域组成：标志域（用枚举类型），指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域。
模型如下：
typedef enum{ATOM,LIST}ElemTag; //ATOM == 0:原子，LISE == 1:子表
typedef struct GLNode{
ElemTag tag; //公共部分，用于区分原子结点和表结点
union{ //原子结点和表结点的联合部分
AtomType atom; //atom是原子结点 的值域，AtomType由用户定义
//ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾
struct{struct GLNode *hp,*tp;}ptr;
};
}*GList; //广义表的类型
这种存储结构吧，是我挺喜欢的一种结构，因为第二种太丑了。
这种存储结构中：
1.除了空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点，且该结点中的hp域指示列表表头（或为原子结点，或为表结点）,tp域指向列表表尾（除非表尾为空，则指针为空，否则必为表结点）；
2. 容易分清列表中原子列表中原子和子表所在层次。
3.最高层的表结点个数即为列表的长度。
还有另外一种结构，刚开始的时候我还没看出这两种结构的区别，仔细琢磨发现这两种结构的区别还是很明显的。
typedef enum{ATOM,LIST}ElemTag; //ATOM == 0:原子，LISE == 1:子表
typedef struct GLNode{
ElemTag tag; //公共部分，用于区分原子结点和表结点
union{ //原子结点和表结点的联合部分
AtomType atom; //atom是原子结点 的值域，AtomType由用户定义
struct GLNode *hp; //表头指针
};
struct GLNode *hp; //相当于next
}*GList; //广义表的类型
看起来没有区别，但是画画图会发现这种存储结构相对离散。如果广义表中的子表需要较强独立访问的时候，还是可以考虑的。
m元多项式的表示
在第二章写线性表的时候就提到过如何存储多项式问题，在这里又提到了m元多项式的存储问题。在《数据结构》中，应用模型是实战的第一步，数据结构模型不是单纯的孤立存在，要有不太复杂的操作存在才有意义，才更有实用性。可以说一个模型是有存储，方法两部分组成的（好像C++的封装，不过这也就是ADT所在吧）。
在一般情况下使用的广义表多数既非是递归表，也不为其他表所共享。广义表中的一个数据元素可以是另一个广义表，这就为存储系数提供了便利。
其实m元多项式的表示和多项式的表示一样无语。其实就是先提取公因式把然后把系数保存下来。
步骤：
1.对一个字母提取公因式
2.分解出系数来依次保存（利用递归的特点）
3.向内递归（就是把系数再进行第一步操作）
typedef struct MPNode{
ElemTag Tag; //区分原子结点还是表结点
int exp; //指数域
union{
float coef //系数域
struct MPNode *hp //表结点的表头指针
}；
struct MPNode *tp //相当于next
}*MPList;
这个用的是第二种存储结构，虽然丑，但尽量保证的系数的独立性，在以后访问、计算速度可能会更棒一些。
在每一层上增设一个表头结构并利用exp指示该层的变元，可用一维数组存储多项式中所有的变元，故exp域存储的是该变元在一维数组的下标。
广义表的递归算法
鞠老师说这是这章最关键的地方，的确，非常有意思。
因为在做竞赛的时候学个一些树，对写一些简单的递归也算轻车熟路，这一节属于难点，但不是我的难点。大体总结之。
先说说递归，让我形容递归，就三个词：
1.慢：因为递归就是栈的应用，在使用栈空间时间是个问题，递归求阶乘就很好说明问题
2.不负责任：我写递归的时候一直处在不负责任状态，先写出来，管他对错呢，写完在想对错问题，= =。其实递归函数不好理解，等你想明白黄瓜菜都凉了，递归就要随心所欲，然后约束之。
3.强大：很多高级算法就是由递归写的，当递归看多了就发现，数学才是硬伤。
递归设计的实质是：当一个复杂的问题可以分解成若干子问题来处理时，其中某些子问题与原问题有相同的特征属性，则可利用和原问题相同的分析处理方法；反之，这些问题之间的转化关系。
由于递归函数的设计用的是归纳的思想，则在设计递归函数的时候注意：
1.严格定义功能和接口
2.把递归的每个操作看着简单操作
求广义表的深度
求广义表的深度和字典树很像，递归遇到子集深入。
复制广义表
因为广义表可以分为表头和表尾，那么只需要分别复制表头和表尾即可（有点分治的意思）。
if(L->tag==ATOM) T->atom = L->atom;
else{
//分而治之
CopyGList(T->ptr.hp,L->ptr.hp);
CopyGList(T->ptr.tp,L->ptr.tp);
}
建立广义表的存储结构
因为前面已经提到过有两种存储结构，一种是把广义表分解为表头和表尾，另一种是把广义表看成含有n个并列子表（假设原子也视为子表）的表。其实递归存储和复制也差不到哪去。不过书中给出的代码的确不错
Status CreateGList(GList &L, SString S) {
// 采用头尾链表存储结构，由广义表的书写形式串S创建广义表L。
// 设emp="()"。
char s[3]="()";
SString emp;
crt_SString(emp,s);
SString sub,hsub;
GList p,q;
if (StrCompare(S, emp)) L = NULL; // 创建空表
else {
if (!(L=(GList)malloc(sizeof(GLNode)))) return ERROR; // 建表结点
if (StrLength(S)==1) { // 创建单原子广义表
L->tag = ATOM; L->atom =S[1]; }
} else {
L->tag = LIST; p = L;
SubString(sub, S, 2, StrLength(S)-2); // 脱外层括号
do { // 重复建n个子表
sever(sub, hsub); // 从sub中分离出表头串 hsub
CreateGList(p->ptr.hp, hsub); q = p;
if (!StrEmpty(sub)) { // 表尾不空
if (!(p = (GLNode *) malloc (sizeof(GLNode)))) return ERROR;
p->tag = LIST; q->ptr.tp = p;
}//if
} while (!StrEmpty(sub));
q->ptr.tp = NULL;
} // else
} // else
return OK;
} // CreateGList
Copyright © 2020 Powered by MWeb, Theme used GitHub CSS.