¶ 字符串
字符串，简称串。由n(n≥0)个字符组成的有限序列
¶ 串的大小比较
根据ASCII码，依次比较每一个字符。
¶ 与线性表的关系
- 字符串属于线性表结构的特例
- 大多数线性结构以“单个元素”作为操作对象，如查找、插入、删除一个元素；串的操作通常以“连续多个元素”作为操作对象。如查找某个子串、插入一个子串以及删除一个子串。
¶ 存储结构
¶ 顺序存储
- 紧缩格式
- 一个字节存放一个字符
- 非紧缩格式
- 一个字存储单元中放一个字符
- 一个字存储单元中放一个字符
¶ 链式存储
更复杂的块链结构：
¶ 模式匹配Pattern Matching
设S（目标串/主串）和P（模式串）是两个给定的串，在S中找到等于P的子串的过程称为模式匹配。
¶ 蛮力(Brute-Force)匹配法
比较 S[i]与 P[j]：
- 若相等，则同时递增 i和 j，继续比较下一个字符
- 若不相等，则主串指针回溯到本次匹配起始位置的下一个位置（即 i=i−j+1），模式串指针重置为 0。
缺点：
- 耗时很大，时间复杂度高，时间复杂度为
¶ KMP匹配法
关键：
- 提前获取最大公共前后缀真子串（next[]数组）
运行过程：
- 主函数中，匹配失败后，不是像蛮力法一样把主指针回溯到开始匹配的第一个字符接着往下对比，而是看next数组，next数组的值是多少就从开始匹配的第一个字符直接向后挪几位，再继续对比
- next数组：最大公共前后缀真子串的长度
- 写的话直接看前后缀公共长度多长就行，和编程方式差异较大
- 每个点之前子串中最大的公共前后缀真子串长度
- nextval数组：next的改进版本，规避了重复比较的一些情况，作用不变，但一些情况下更快一点
- nextval[j]计算方法：nextval[0]=-1，如果t[j]不等于t[next[j]]，nextval[j]=next[j]，否则nextval[j]= nextval[next[j]]
next数组计算：
/*计算模式串pCHD的next数组*/
pCHD->next[j = 0] = k = -1;//初始化当前（第0个字符）字符的下标和next值
while (j < pCHD->Length) //循环条件是字符下标没有越界j=0～pp_str->Length-1
{ //从已有的next[j]推算next[j++]
if (k == -1 || pCHD->chs[j] == pCHD->chs[k])
{
//如果当前位置字符比较成功，下一个next自然推进
j++; k++;
pCHD->next[j] = k; //写入推进后的k到next[j]
}
else //如果不相等，停止步进j，将k作为比较失败位置，查看k之前的子列
k = pCHD->next[k];
}
- 若比较成功->jk都前推，next设为k值
- 若比较失败，k回溯，使用next[k]的值
nextval数组计算：
相比较于next的计算，其实变动点只有匹配成功里面，如果下一个字符也成功，也就是有重复，那么直接使用前面的nextval。
/*计算模式串pCHD改进后的nextval数组*/
pCHD->nextval[j = 0] = k = -1;//初始化当前（第0个字符）字符的下标和next值
while (j < pCHD->Length) //循环条件是字符下标没有越界j=0～pp_str->Length-1
{ //从已有的nextval[j]推算nextval[j++]
if (k == -1 || pCHD->chs[j] == pCHD->chs[k])
{
//如果当前位置字符比较成功，下一个next自然推进
j++; k++;
//如果产生重复，使用之前的nextval
if(pCHD->chs[j] == pCHD->chs[k])
pCHD->nextval[j] = pCHD->nextval[k];
else
pCHD->nextval[j] = k;
}
else //如果不相等，停止步进j，将k作为比较失败位置，查看k之前的子列
k = pCHD->nextval[k];
}
KMP算法匹配：
int/*返回匹配位置*/ KMPIndex(StringCHD* ps_str/*主串*/,
PatternStringCHD* pp_str/*模式串(字串)*/,
int pos/*从pos处开始搜索*/,
int mode/*0或1:普通失败函数next[j]或改进失败函数nextval[j]*/){
int i = pos; //目标串的初始对比下标
int j = 0; //模式串的初始对比下标
//检查输入参数的合法性：串非空、位置合适
if (pp_str->Length == 0){
printf("模式串不能为空\n");
return -1;
}
if (pos < 0 || pos >= ps_str->Length){
printf("下标越界错误!0～%d", ps_str->Length - 1);
return -2;
}
while (i<ps_str->Length && j<pp_str->Length){
if (j == -1 || ps_str->chs[i] == pp_str->chs[j]){//字符相同，顺利推进
i++; j++;
}
else//比较失败，做模式串的位置回溯，目标串无需回溯
j = (mode == 0 ? pp_str->next[j] : pp_str->nextval[j]);
}
return (j == pp_str->Length) ? i - pp_str->Length
/*达到模式串末尾而退出的循环，匹配成功，返回位置*/
:-3/*未达到模式串末尾而退出的循环，匹配失败*/;
}
¶ 作业
¶ 1
设模式串t为”abacabaaad ”，填写其next数组和改进nextval数组。
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| t | a | b | a | c | a | b | a | a | a | d |
| next[j] | -1 | 0 | 0 | 1 | 0 | 1 | 2 | 3 | 1 | 1 |
| nextval[j] | -1 | 0 | -1 | 1 | -1 | 0 | -1 | 3 | 1 | 1 |
¶ 2
通过栈S将输入整数转换N为8进制表示输出的核心代码如下：
while(N){ Push(S, N%8); N=N/8; }
while(!IsStackEmpty(S)) { Pop(S,e); printf(“%d “,e); }
请编写函数void Convert(int)采用递归的方式完成这种输出，Convert函数输入为待转换的整数。说明设计思想。
void Convert(int N){
if(N){
Convert(N/8);
printf("%d ", N%8);
}
}
¶ 3
已知数组int a[N]，设计递归函数：
（1）int find(int* pA, int len, int x)查找x所在的下标并返回，如果无此元素，返回-1.
int find(int* pA, int len, int x)
{
if (pA[--len] == x)return len;
if (len == 0)return -1;
return find(pA, len, x);
}
（2）int get_max(int* pA, int len)求数组的最大值。
int get_max(int* pA, int len)
{
if (len == 0)return pA[0];
int m = get_max(pA, --len);
return m>pA[len] ? m : pA[len];
}
（3）double average(int* pA, int len)求数组的平均值。
double average(int* pA, int len)
{
if (len == 0)return pA[0];
return (average(pA, --len)*len + pA[len]) / (len + 1);
}