广义表
广义表是线性表的推广，也可称之为列表（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
串
串（字符串）是有另个或多个组成的有限序列，一般记为S=‘a1...an’(n>=0),其中的S是串名，用单引号括起来的的字符序列是串的值，串中字符的数目n称为串的长度，零个字符的串称为空串，它的长度为零。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。
称两串相等是指两个串的长度相等且对应位置的字符都相等，也可以说当且仅当两个串的值相等。
由一个或者多个空格组成的串叫做空格串，它的长度为串中空格的个数。为了清楚起见，一般用Ø来表示空串（不是空格串）。
串的逻辑结构和线性表极为相似，区别仅在于传的数据对象约束为字符集。然而串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，而串通常以“串的整体”作为操作对象。
如果在程序设计语言中，串只是作为输入输出的常量出现，则只需存储此串的串值，即字符串序列即可，但大多数非数值处理的程序中，串也以变量的形式出现。
类似于线性表的顺序存储结构，用一组地址连续的存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组描述。串的实际长度可在预定义长度的范围内随意分配，超过预定义长度的串值则被舍去，称之为“截断”。而对串长的有两种表示方法，一是以下标为0的数组分量存放串的实际长度（PASCAL），二是在串值后面加一个不计入串长的标记字符（C）。
实现串操作的原操作（各种操作的基础）为“字符序列的复制”，其操作的时间复杂度基于复制的字符序列的长度，如果在操作中出现串值序列的长度超过上限时，约定用截尾处理，克服这个弊病的唯用不限定串长的最大长度，即动态分配串值的存储空间。
堆分配存储表示
名字什么的在高大上也不过是个名字，堆是机内和栈一样重要的自由存储区，一般栈是由计算机管理的，而堆是由程序员管理的。
这种存储表示的特点是：仍以一组地址连续的存储单元存放串值字符序列，但他们的存储空间是程序执行过程中动态分配而得。
这种存储结构表示时的串操作仍然是基于“字符序列的复制”进行的。
其实也不是多么NB，只不过是在拼接序列等可能超出空间的操作，先开一个两个串长度和的空间（保证操作完能完全存放），然后把两个串复制过去，最后把两个串释放掉。
由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，操作中对串长无限制，更显灵活。（但个人感觉好慢）。
曾经幻想过能不能把字符串像链表一样连起来，自己最终得到的模型是n段离散的字符串，通过一个记录地址的链表来把n段字符串链接起来。
但看到第四章发现还真有这样的结构，称为块链结构，为了便于进行串的操作，当以链表存储串值时，除头指针外，还附属一个尾指针指示链表中的最后一个元素。
对串进行操作时，只需要从头到尾顺序扫描即可，设尾指针的目的是为了便于进行联接操作，但联结时一定要注意处理串尾的无效字符。
#define CHUNKSIZE 80 //由用户定义的块大小
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk * next;
}Chunk;
typedef struct{
Chunk * head,*tail; //头指针和尾指针
int len; //串的当前长度
}Lstring;
在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率，由于所处理的串往往很长或很多，这就要求我们考虑串值的存储密度：
存储密度= 串值所有的存储位/实际分配的存储位
显然存储密度小（如结点为1），运算处理方便，然而存储占用量大，如果在串处理过程中需进行内、外存交换的话，则会因为内外存交换操作过多而影响总效率。
还有，串的字符集的大小也是一个重要因素，一般地，字符集小，其机内编码就短，这也影响串值的存储方式的选取。
串值的链式结构对某些串操作，如联接等，有一定的方便性，但对插入等又有着大量的复杂操作，又不是十分方便。总的来说，顺序结构和链式结构各有优势，分具体情况选用是最棒的选择。
话说数据结构包括存储方式和操作，下面说说操作。
在串中最常用的功能莫过于子串的定位操作，也称模式串的匹配。一般使用一个被王政称为朴素算法的时间复杂度为O（n*m）的东西，其中n和m分别是主串和模式串的长度，其实这也是最容易想到的算法。
节选《数据结构》中关键代码：
while(i T[0])
return i - T[0];
return 0;
算法的基本思想是：从主串S的第一个字符起和模式串的第一个字符进行比较，若相等则继续逐个比较后续字符，否者从主串的下一个字符起再重新和模式串的第一个字符起逐个比较，以此类推，直到把主串比较完（匹配不成功）或找到匹配串的位置（匹配成功）。
这种算法容易理解也是最直接简单的查找算法，但往往越好理解的都是越笨拙的，这个算法最大的问题就是慢。有慢的，便必然有快的算法，要看快的，要先直到这个慢的是为什么慢的。
上面那个笨拙的算法，须要两个指针分别指向两个串，当匹配不成功时，两个串都有不同程度的回溯，如果指针不回溯哪怕只有一个指针回溯想必也是极好的。这样，新算法（也可以说是改良算法）就诞生了。
K（Knuth）M（Morris）P（Prate）算法，由前面那3个人同时发现，简称KMP算法，它便实现了只让一个指针回溯，这个指针利用已经得到的“部分匹配”，滑动到模式串的“敲到好处”的位置，继续匹配。
至于怎么确定这个“恰到好处”的位置，就是利用了一个被称之为next函数的东西。
若令next[j] = k，则next[j]表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。由此可以引出模式串的next函数的含义：
next[j] = 0当j=1时
= Max(R|1 1...pk-1'=='pj-k+1...pj-1')
= 1 其他情况
说白了，就是记录了模式串当前位置和前面几个元素相同。
在寒假ACM集训的时候第一次接触了，KMP，其实KMP中的精华就在next函数中，其中的意义使用灵活，但实在是一种难以总结感觉，更像是经验问题，详情见当时的总结 月球美容计划之那些天我们学过的KMP。
在暑假给第3批队员培训的时候，又好好的研究了 KMP，但最后发现王政的KMP理解的比较深入，他的教案文档《Kmp 算法引论》深入浅出，在集训群里又找到这份文档，作为最后对KMP的补充吧。资源链接：KMP字符串匹配算法
总结：
-
传统算法（朴素算法）最坏情况是O(nm)，但一般是在O(n+m)，也不是太坏，所以一般没有特殊要求的程序还在用这种算法；
-
KMP算法在有大量重复的情况下优化明显，对主串较大时比较有效；
-
next函数还是有缺陷的，比如模式串'aaaab'与主串'aabaaaab'匹配时，用时几乎和朴素算法一样；
-
以发展的眼光看问题，其实作为常用算法之一，匹配算法也有发展，KMP已经不是主流。
文本编辑程序问题
文本编辑程序中通过设立页指针、行指针和字符指针，分别指示当前操作的页、行和字符。如果在某行内插入或删除若干字符，则要修改行表中该行的长度。若该行的长度超出了分配给它的存储空间，则要为该行重新分配存储空间，同时还要修改该行的起始位置。
为了查找方便，行表是按行号递增顺序存储的，因此，对行表惊醒的插入或删除运算需移动操作位置以后的全部表项，页表的维护则和行表类似。
由于访问是以页表和行表作为引索的，所以在作行和页的删除操作时，可以只对行表和页表相应的修改，不必删除所涉及的字符，可以节省不少空间。
第四章其实已经看完三天了，这三天又是亚洲区域赛网络赛又是去打针，没有什么比不健康的身体状况更糟糕了，几天终于好些了，一口气把第四章的笔记整理完毕，好收拾旧行装，继续上路。
Copyright © 2020 Powered by MWeb, Theme used GitHub CSS.