数据结构（C语言版）---串
1、串：由零个或多个字符组成的有限序列，记作S='a1a2a3...an'(n>=0)，其中，S为串名，单引号括起来的字符序列为串的值。
1）串中字符的个数n为串的长度，n=0时的串称为空串。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。2）串相等：两个串的长度相等且每个对应位置的字符都相等。
3）空格串：由一个或多个空格组成的串，其长度为串中空格字符的个数。
2、串的存储结构
1）定长顺序存储
（1）截断：超过预定义长度的串值被舍去。
（2）串长的表示方法：用额外的变量存储串的长度、在串值后面加上不计入串长的标记符号“\0”。
（3）定长顺序存储结构描述
#define maxlen 250
typedef struct {
char ch[maxlen];
int length;
}SString;
（4）串的模式匹配：确定子串的位置。
int index(SString S, SString T, int pos)
{
int i = pos, j = 1;
while (i <= S.length&&j <= T.length)
{
if (S.ch[i] == T.ch[j])
{
++i;
++j;
}
else
{
i = i - j + 2;
j = 1;
}
}
if (j > T.length)
{
return i - T.length;
}
else
{
return 0;
}
}
2）堆分配存储
（1）存储空间在执行过程中动态得到。
（2）堆分配存储结构描述
typedef struct {
char *ch;
int length;
}HString;
3）块链存储
（1）每个结点被称为块，既可以存放一个字符，也可以存放多个字符，整个链表称为块链结构。
（2）当最后一个结点没有被全部占满时用#填充。
（3）存储密度=串值所占存储位/实际分配存储位。
（4）块链存储结构描述
#define chunksize 50
typedef struct chunk {
char ch[chunksize];
struct chunk * next;
}chunk;
typedef struct {
chunk * head, *tail;
int curlen;
}LString;
3、串的模式匹配：确定子串的位置。
1）主串：包含字串的串。
2）子串：串中任意个连续的字符组成的子序列。
1）简单模式匹配时间复杂度为O(nm)，n为主串长度，m为模式串长度。
2）KMP算法
（1）原理：i指针不回溯，仅将子串向后滑动一个合适的位置，并从该位置开始和主串进行比较，该位置仅与子串本身结构有关，与主串无关。
（2）字符串的前缀：除最后一个字符以外，字符串的所有头部子串。
（3）字符串的后缀：除第一个字符以外，字符串的所有尾部子串。
（4）部分匹配值：字符串的前缀和后缀的最长相等前后缀长度。
例子：
'a'：前缀、后缀均为空集，最长相等前后缀长度为0。
'ab'：前缀为{a}，后缀为{b}，{a}∩{b}=Ø，最长相等前后缀长度为0。
'aba'：前缀为{a,ab}，后缀为{a,ba}，{a,ab}∩{a,ba}={a}，最长相等前后缀长度为1。
'abab'：前缀为{a,ab,aba}，后缀为{b,ab,bab}，{a,ab,aba}∩{b,ab,bab}={ab}，最长相等前后缀长度为2。
'ababa'：前缀为{a,ab,aba,abab}，后缀为{a,ba,aba,baba}，{a,ab,aba,abab}∩{a,ba,aba,baba}={a,aba}，最长相等前后缀长度为3。
（5）时间复杂度为O(n+m)。
（6）移动的位数=已匹配的字符数-对应的部分匹配值。
将部分匹配值写成数组的形式，求next数组
void getnext(SString T, int next[])
{
int i = 1, j = 0;
next[i] = 0;
while (i<T.length)
{
if (j == 0 || T.ch[i] == T.ch[j])
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j];
}
}
}
（7）KMP算法
int kmpindex(SString S, SString T, int next[], int pos)
{
int i = pos, j = 1;
while (i<=S.length&&j<=T.length)
{
if (j == 0 || S.ch[i] == T.ch[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if (j > T.length)
{
return i - T.length;
}
else
{
return 0;
}
}
