栈和队列和串

栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。

通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。

将链表头部作为栈顶的一端，可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。

链表的头部作为栈顶，意味着：
在实现数据”入栈”操作时，需要将数据从链表的头部插入；
在实现数据”出栈”操作时，需要删除链表头部的首元节点；

因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。

数据从表的一端进，从另一端出，且遵循 “先进先出” 原则的线性存储结构就是队列。

通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。

栈和队列不要混淆，栈结构是一端封口，特点是”先进后出”；而队列的两端全是开口，特点是”先进先出”。

作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为”假溢出”。也就是说，整个顺序队列在数据不断地进队出队过程中，在顺序表中的位置不断后移。

链式队列数据入队

链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：
将该数据元素用节点包裹，例如新节点名称为 elem；
与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
最后移动 rear 指针指向该新节点，即 rear=elem；

链式队列数据出队

链式队列中队头元素出队，需要做以下 3 步操作：
通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
将 p 节点（即要出队的队头节点）从链表中摘除；
释放节点 p，回收其所占的内存空间；

串存储结构的具体实现

存储一个字符串，数据结构包含以下 3 种具体存储结构：

定长顺序存储：实际上就是用普通数组（又称静态数组）存储，可以简单地理解为采用 “固定长度的顺序存储结构” 来存储字符串，因此限定了其底层实现只能使用静态数组。例如 C 语言使用普通数据存储字符串的代码为 char a[20] = “data.biancheng.net”。

堆分配存储：用动态数组存储字符串；动态数组相比普通数组（静态数组）的优势是长度可变，换句话说，根据需要动态数组可额外申请更多的堆空间（使用 relloc 函数）；

char * a = (char*)malloc(5*sizeof(char));
此行代码创建了一个动态数组 a，通过使用 malloc 申请了 5 个 char 类型大小的堆存储空间。

a = (char*)realloc(a, 10*sizeof(char));
通过使用这行代码，之前具有 5 个 char 型存储空间的动态数组，其容量扩大为可存储 10 个 char 型数据。

块链存储：用链表存储字符串；串的块链存储，指的是使用链表结构存储字符串。

链表各节点存储数据个数的多少可参考以下几个因素：

串的长度和存储空间的大小：若串包含数据量很大，且链表申请的存储空间有限，此时应尽可能的让各节点存储更多的数据，提高空间的利用率（每多一个节点，就要多申请一个指针域的空间）；反之，如果串不是特别长，或者存储空间足够，就需要再结合其他因素综合考虑；

程序实现的功能：如果实际场景中需要对存储的串做大量的插入或删除操作，则应尽可能减少各节点存储数据的数量；反之，就需要再结合其他因素。

串的模式匹配算法，通俗地理解，是一种用来判断两个串之间是否具有”主串与子串”关系的算法。

主串与子串：如果串 A（如 “shujujiegou”）中包含有串 B（如 “ju”），则称串 A 为主串，串 B 为子串。主串与子串之间的关系可简单理解为一个串 “包含” 另一个串的关系。

实现串的模式匹配的算法主要有以下两种：

普通的模式匹配算法；
快速模式匹配算法；

普通模式匹配算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。

BF算法时间复杂度
该算法最理想的时间复杂度 O(n)，n 表示串 A 的长度，即第一次匹配就成功。

BF 算法最坏情况的时间复杂度为 O(n*m)，n 为串 A 的长度，m 为串 B 的长度。例如，串 B 为 “0000000001”，而串 A 为 “01”，这种情况下，两个串每次匹配，都必须匹配至串 A 的最末尾才能判断匹配失败，因此运行了 n*m 次。

KMP算法

https://blog.csdn.net/v_JULY_v/article/details/7041827

KMP算法与前文的暴力匹配算法，核心的区别就是没有不匹配的回溯，而是根据整个字符串的情况进行一次位移，这样大大减少了回溯产生的缺陷，KMP算法的时间复杂度可以优化到 O( n + m)级别，是二次优化到线性的程度。

给定一个主字符串 T = “AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB”(47位)
同时给定模式串 P = “AAAAAB”（6位）

构造next表(以-1开头)

对于模式串P而言，我们需要知道模式串中P的每一位的前一位是否存在相等的完全相等的前后缀，并且求这个最大的完全相等的前后缀，如一个模式串”ABCABDE”对于第倒数第二位字符而言，其符合情况的前后缀就是”AB”，而最后一位则没有完全相等的前后缀。

PS：何为前后缀：如一个字符串”ABCD”,其前缀有可能为”A”“AB”“ABC”(即除去本身的全部字符)，同理，则后缀可能为：”D””CD””BCD”

我们需要求的就是每一个字符其相对应的最大前后缀数，这样与模式串P一一对应的表称之为next表。

因此”ABCABDE”的next表为：-1 0 0 0 1 2 0 （字符用空格隔开）

A	B	C	A	B	D	E
-1	0	0	0	1	2	0

对于每一个当前需要判断的字符而言，在构造next表时，应该向前进行比对，以上一个已经判断的情况为基础（初始值赋-1，部分教程中初始值赋0，两者没有实质区别），后缀如果+1位置的字符与前缀+1位置的字符相等，则next[i]就是next[i-1]+1，而如果不相等，则说明无法匹配，则next[i]=0。

KMP实现

与暴力匹配极其相似，利用while循环的条件控制， 进行匹配失败时，只需要将失败的模式串P的索引指向next表中对应的数值即可，其余匹配照旧线性执行即可。

要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

　　－　“A”的前缀和后缀都为空集，共有元素的长度为0；

　　－　“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；

　　－　“ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

　　－　“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

　　－　“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；

　　－　“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；

　　－　“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。