当前位置 博文首页 > XSES_yasuoman的博客：数据结构——串
#define MAXLEN 255
typedef struct{
char ch[MAXLEN];
int length; // 注意 ch[0] 不存储任何字符，所以计算长度需注意！！
}SString;
typedef struct{
char *ch;
int length;
}HString;
HString str = (char *)malloc(sizeof(char) * initsize);
free(str);
使用 malloc 在堆上申请空间，使用结束可以用 free 销毁
typedef struct StringNode {
char ch[4];
struct StringNode *next;
}StringNode, *String;
赋值： StrAssign(&T, chars)
复制：StrCopy(&T, S)
判空：StrEmpty(S)
StrCompare(S, T)int StrCompare(SString S, SString T) {
for (int i = 1; i < S.length; i ++) {
if (S.ch[i] != T.ch[i]) // 不相等时定结果
return S.[i] - T.[i]; // 字符比较
}
return S.length - T.length; // 如果两者前面的字符都对应相等，则比较长度。长的字符串大。
}
求串长：StrLength(S)
SubString(&Sub, S, pos, len)// 静态定长顺序存储结构
bool SubString(SString &Sub, SString S, int pos, int len) {
if (pos + len - 1 > S.length) // 子串范围越界？
return false;
for (int i = pos, i < pos + len - 1; i ++) { // 从 pos 到 pos + len - 1 都需要赋值
Sub.ch[i - pos + 1] = S.ch[i]; // Sub 从下标 1 开始赋值。
}
Sub.length = len; // 不忘 Sub 的length 属性。
return true;
}
串联接：Concat(&T, S1, S2)
Index(S, T)王道书：
思路：求 S 中与 T 长度一样长的子串，依次比较。
int Index(SString S, SString T) {
int i = 1, lenS = StrLength(S), lenT = StrLength(T);
SString sub; // 暂存子串
while (i <= lenS - lenT + 1) {
SubString(sub, S, i, lenT); // 在 S 中 i 位置找长度为 lenT 的子串
if (StrCompare(sub, T) != 0)
i++;
else
return i;
}
return 0;
}
MHH：
依次比较，其实无意中发现了模式匹配呀~
int Index(SString S, SString T) {
int Ti = 1; // 短串下标
int Si; // 长串下标
// 长串 S 遍历至末尾，或 T 匹配到末尾则结束
for (Si = 1; Si <= StrLength(S) || Ti <= StrLength(T); Si++){
if (S.ch[Si] == T.ch[Ti]) // 匹配到，Ti Si 都加 1
Ti ++;
else // 未匹配则 Ti重置为 1，Si 加1
Si = Si - Ti + 2; // Si 从下一个开始重新匹配
Ti = 1;
}
if (Ti = StrLength(T) + 1)
return Si - StrLength(T);
else
return -1;
}
清空操作：ClearString(&S)
销毁串：DestroyString(&S)
int Index(SString S, SString T) {
int Si = 1, Ti = 1;
while (Si <= S.length && Ti <= T.length) {
if (S.ch[Si] == T.ch[Ti]){
Si ++;
Ti ++; // 比较后续
}else {
Si = Si - Ti + 2; // 指针后退并重新开始匹配
Ti = 1;
}
}
if (Ti = T.length + 1)
return Si - T.length;
else
return 0;
}
主串指针不需要回溯，子串（模式串）向后移动
eg：主串：a b a b a b c d d，子串：a b a b c，第一次匹配：
1 2 3 4 5 6 7 8 9 // 匹配到第 5 位失败，则前 4 位 主串子串相等。
a b a b a b c d d // 为了减少匹配，需要找到子串的前 4 位中的重叠部分，使得尽可能将子串后移多位。
a b a b c //
a b a b c // 移动 1 位，第一个便不匹配，则进行 2 位移动，
// 此时最多需要匹配 5 - 1 - 2 次，而它们刚好都匹配。于是从 2 + 1 开始匹配。
a b a b c // 向后能移动的最大位数是 2，则移动 2 位后，下一次从子串的位置 3 开始匹配
next[Sub.length + 1]; // next 数组存储，当该位置匹配失败时，子串指针移动到哪个位置进行匹配
next 的长度为 Sub.length + 1 的原因：
当第一个元素不匹配时，需要将主串和子串的指针都自增 1，但其他元素不匹配时，做的工作都是，令 子串指针等于 next[i]，随后主串指针自增，所以需要将 next[1] 置为 0，此时将 主串指针 和 子串指针都加 1。
在已经求得 next 数组情况下，进行匹配：
int Index_KMP(SString S, SString T, int next[]){
int Si = 1, Ti = 1; // S 串 和 T 串的位置
while (Si <= S.length && Ti <= T.length) {
if (Ti == 0 || S.ch[Si] == T.ch[Ti]) {
Si++;
Ti++;
}else {
Ti = next[Ti];
}
}
if (Ti > T.length)
return Si - T.length;
else
return 0;
}
求 next 数组：
挖坑：
next 数组代码：
next 数组优化：
