数据结构笔记（其五）--串
目录
12.串
12.1 基本操作
12.2 串的存储结构
12.3 字符串的模式匹配算法
（1）.朴素模式匹配算法
（2）.KMP算法
i.next[]数组的求解
ii.next[]数组的优化——nextval数组
iii.手算nextval数组
iiii.机算nextval数组 + KMP函数
12.串
串，即字符串（string），由零个或多个字符组成的有限序列。串也是线性表。
子串，串中任意个连续的字符组成的序列。
主串，包含子串的串。
空串，没有字符的串，空格串不是空串。
字符在串中位置的描述，S = "a1a2a3..."，其编号由1开始，另外，一般都是指的该字符首次出现的位置，另外的另外，空格也算作字符。
子串在主串中的位置，以子串第一个字符在主串中的位置来代替。
12.1 基本操作
串的操作一般作用于子串，而非单个的字符。
StrAssign(&T, chars)：赋值，把chars 赋值给T.
StrCopy(&T, S)：复制，把S 复制给T.
StrEmpty(S)：判空，判断S 是否为空串，为空，返回true；未空，返回false.
StrLength(S)：求串长。
ClearString(&S)：清空，将S串变为空串。（内存空间并没有收回）（所以直接length = 0，在逻辑上清除就可以了）
DestoryString(&S)：销毁，回收串的存储内存空间。
Concat(&T, S1, S2)：串的联接，用T 返回S1与S2 联接成的新串。
SubString(&Sub, S, pos, len)：求子串，用Sub返回S串的从第pos个字符起往后len个的字符子串。
Index(S, T)：定位，尝试寻找子串T在主串S中的位置，返回首次出现的位置，若没有，则返回0.
StrCompare(S, T)：比较大小，从各串的第一个字符开始依次比较，字符的ASCll码值，值相同，则比较各串的下一位字符，先出现更大的字符的串，更大。
当串中含有空格字符，且串中非空格字符都相等，则更长的串更大，比较时是先忽略空格的。
只有当串的字符、长度都相等时，串才相等。
12.2 串的存储结构
以下代码是串的存储结构以及一些重要的基本操作
//顺序
#define MAXSIZE 255 //预先定义的最大串长
class SString
{
public:char ch[MAXSIZE]; //对字符的储存int length; //记录串的实际长度//也可以省去此变量，用ch[0]储存长度//为了使下标统一和变量分离，所以之后会将ch[0]废弃不用，并继续使用length
};
//顺序（动态分配）（堆分配存储）
class HString
{
public://构造函数HString(){ch = new char();length = 0;}char* ch;int length;
};
//链式
class StringNode
{
public:char ch[4]; //如果只是ch ，不是数组的话，单个节点的储存密度非常低，为了提高内存利用率，所以采用每个结点都存储一个小数组的方法StringNode* next;
};
using LString = StringNode*;//求串长
int StrLength(SString S)
{return S.leng