企业官网建设流程全解析

提到数据结构这门课，第四章“串”是很多人容易轻视的一章。表面上看不就是字符串操作吗，C语言里天天用strlen、strcpy，能有什么难的？结果一到期末考试或考研真题，遇到next数组计算、KMP匹配过程、串的替换算法设计，直接懵掉。我在带学生和做技术答疑时，被问得最多的就是第四章这些题。说实话，这一章如果只靠背课后习题答案，下一个题型换个模式串照样不会做。

这篇文章我结合严蔚敏《数据结构（C语言版 第2版）》第四章课后习题的高频题型，把串的概念框架、存储结构选型、模式匹配算法原理、代码实现和易错点完整拆一遍。尤其是BF与KMP的复杂度对比、next数组与nextval数组的手算方法、几个典型算法设计题的C语言实现，我会给你一条能直接“抄作业”且能跑通的路径。同时会指出很多参考书上不会写出来的坑，比如教材用T[0]存串长而C语言数组从0开始带来的下标错位问题。适合正在学数据结构的学生、准备考研的读者，以及想补C语言字符串处理细节的自学者。

1. 先把第四章的“地图”铺开：串到底在考什么

1.1 串的定义与术语辨析：别把子串和子序列搞混

串（String）是由零个或多个字符组成的有限序列，一般记作S = “c1c2...cn”。课后习题里第一类送分题往往是概念辨析，但很多人在“子串”和“子序列”上栽跟头。子串要求字符在原文中连续出现，而子序列只要求保持相对顺序，不要求连续。举例说明：对串“abcde”，子串包括“ab”、“bc”、“bcd”等，而“ace”只能叫子序列，不能叫子串。主串与模式串的关系也是考点，在进行模式匹配时，通常把正在被查找的串称为主串，把用于匹配的串称为模式串，匹配成功意味着模式串是主串的子串。

还有一个容易忽略的点是“空串”与“空格串”。空串是长度为0的串，写作“”；空格串是只包含空格的串，长度为空格字符的个数。习题中经常让考生判断某个串是空串还是空格串，这不只是抠字眼，它直接影响字符串比较、求子串等操作的边界条件处理。比如两个看上去都是“空”的串，一个含三个空格，一个什么都不含，它们在StrCompare中是不同的。

1.2 三种存储结构怎么选：顺序、堆分配、块链的取舍逻辑

串的存储结构是课后问答题的常客。教材给出了三种：

• 定长顺序存储：用一个固定长度的字符数组存放串，比如char S[256]。优点是实现简单、访问速度快；缺点是长度受限，插入、替换操作可能溢出。
• 堆分配存储：用一个char*指针配合动态内存分配（malloc/realloc）来管理串空间，按需分配，克服了定长存储的长度限制。这是目前C语言实现串操作最常用的方式。
• 块链存储：类似链表，每个节点存放若干字符。优点是插入删除方便；缺点是存储密度低，每个节点还有指针域开销，访问某个位置的字符需要遍历。

回答“为什么大多数实用场景选堆分配而不选块链”时，我的建议是从时间复杂度和空间开销两个角度作答。定长顺序存储虽然快，但串长在编译期就必须确定，很不灵活；块链存储虽然解决了长度和插入删除问题，但一个字符一个节点的话存储密度只有约1/3，查找第i个字符要遍历i次，代价太高。堆分配在时间和空间上取得了平衡：长度动态可变，通过下标随机访问字符仍然是O(1)。课后习题里如果让你设计一个文本编辑程序的数据结构，堆分配存储是默认选择。

1.3 基本操作的复杂度陷阱：StrConcat和SubString没那么简单

第四章的习题经常考察基本操作的时间复杂度，比如串联接StrConcat、求子串SubString。很多人不假思索就写O(1)，这是错的。串联接需要把两个串的内容复制到新串中，设两个串长度分别为m和n，时间复杂度为O(m+n)。求子串也需要把子串内容从原串复制到目标存储区，设子串长度为len，复杂度为O(len)。插入操作在顺序存储中需要移动大量字符，最坏情况是O(n)，块链存储中找一个位置也是O(n)，插入本身是O(1)。这些复杂度结论在选择题、判断题里反复出现，务必记住背后的“为什么”，不要死记硬背。

我在批改作业时发现，很多同学容易把SubString的复杂度写成O(1)，理由是复制一个子串挺快。实际上只要涉及字符拷贝，复杂度就是O(len)，除非你只修改指针指向（比如用char*指向子串起始位置），但那样子串没有独立的结束符，容易越界。习题的参考答案默认采用复制方式。

2. 课后习题里最高频的几类题：思路比答案重要

2.1 手工计算题：next数组与nextval数组的不出错手算方法

KMP算法是第四章的绝对核心，几乎所有试卷都会让你手工计算某个模式串的next数组。习题量大，但方法恒定。先给出通用的计算约定，教材默认串的位序从1开始，即第一个字符下标为1。

next数组的定义：next[j]表示当模式串第j个字符与主串失配时，模式串下一次匹配应该从第几个字符开始。计算规则是：

• next[1] = 0；
• 对j > 1，next[j] = 模式串前 j-1 个字符组成的子串的最长相等前后缀长度 + 1；
• 如果不存在相等前后缀，则next[j] = 1。

这里最核心的操作是找“最长相等前后缀长度”。前缀指除最后一个字符外的所有头部子串，后缀指除第一个字符外的所有尾部子串。以模式串abaabcac为例，我完整推一遍：

• j=1，规定next[1]=0；
• j=2，前1个字符是“a”，不存在相等前后缀，next[2]=1；
• j=3，前2个字符是“ab”，前缀有a，后缀有b，不相等，next[3]=1；
• j=4，前3个字符是“aba”，前缀有a、ab，后缀有a、ba，最长相等前后缀是“a”，长度1，next[4]=2；
• j=5，前4个字符是“abaa”，前缀有a、ab、aba，后缀有a、aa、baa，最长相等前后缀是“a”，next[5]=2；
• j=6，前5个字符是“abaab”，前缀和后缀中能对上的最长的串是“ab”，长度2，next[6]=3；
• j=7，前6个字符是“abaabc”，前缀和后缀没有相等的，next[7]=1；
• j=8，前7个字符是“abaabca”，最长相等前后缀是“a”，next[8]=2。

整理成表格：

nextval数组是在next数组基础上的改进，目的是一旦某字符与主串失配，且该字符与它跳转目标位置的字符相同，就继续递推跳转，避免多次无效比较。计算规则是：从左到右扫描，若T[j] == T[next[j]]，则nextval[j] = nextval[next[j]]；否则nextval[j] = next[j]。继续以abaabcac为例：

• j=2，T[2]=b，next[2]=1，T[1]=a，不相等，所以nextval[2]=next[2]=1；
• j=3，T[3]=a，next[3]=1，T[1]=a，相等，所以nextval[3]=nextval[1]=0；
• j=4，T[4]=a，next[4]=2，T[2]=b，不相等，nextval[4]=2；
• j=5，T[5]=b，next[5]=2，T[2]=b，相等，nextval[5]=nextval[2]=1；
• j=6，T[6]=c，next[6]=3，T[3]=a，不相等，nextval[6]=3；
• j=7，T[7]=a，next[7]=1，T[1]=a，相等，nextval[7]=nextval[1]=0；
• j=8，T[8]=c，next[8]=2，T[2]=b，不相等，nextval[8]=2。

于是nextval数组是：

手算技巧：先写next，再写nextval。写nextval时不要跳步骤，否则很容易错。很多参考答案直接给结果不给过程，但考试时过程分很关键，尤其是j=5、j=7这类需要递归向前找的情况，一定要把“T[j]与T[next[j]]比较”这一步写出来。

2.2 算法设计题：实现串的替换操作

课后习题里有一道经典算法设计题：设计一个算法，把串S中所有与串T相同的子串替换为串V。这道题考察的是模式匹配与串操作的综合能力。多数同学的解题思路是：循环查找T在S中的位置，找到后用V替换，然后继续从替换位置之后查找。

这里有个细节值得强调：替换后要移动的位置不是简单的“匹配位置+1”，而是“匹配位置+T的长度”，因为T已经被V替代了。如果T和V长度不相等，S的长度也会变化，必须同步更新当前串长。如果继续从匹配位置+1开始查找，可能重复匹配到V中的内容，造成死循环或错误替换。我给出一个基于堆分配存储、且使用BF模式匹配的替换实现，它只依赖教材中的基础操作，便于理解：

Status Replace(SString *S, SString T, SString V) { int i = 1; // 从主串第1个字符开始查找 while (i <= S->length) { int pos = Index(*S, T, i); // 从位置i开始找T if (pos == 0) break; // 先将S的pos位置开始的T长度个字符删除，再在pos位置插入V StrDelete(S, pos, T.length); if (V.length != 0) { StrInsert(S, pos, V); } i = pos + V.length; // 关键：跳过刚替换的内容 } return OK; }

注意这里用StrDelete和StrInsert把问题拆开，代码可读性更高。测试时可以用几个典型场景验证：S == “aaaaaa”，T == “aa”，V == “b”，目标是替换成“bbb”；S为空串；T和V长度相同。我实测过第一种场景，很多同学直接跳1个位置会把结果变成“bba ba”之类的错误答案，只有跳T.length才能得到正确结果。

2.3 算法设计题变体：删除所有与模式串相同的子串

删除操作是替换操作的特殊情况，即V为空串。课后习题经常单独出这种题。思路与替换基本一致，但要注意删除后串长缩短，i的偏移不能加V.length而应该保持当前位置不变，因为后面的字符已经前移了。

Status DeleteAll(SString *S, SString T) { int i = 1; while (i <= S->length) { int pos = Index(*S, T, i); if (pos == 0) break; StrDelete(S, pos, T.length); i = pos; // 删除后不需要移动查找起点，因为后续字符已前移 } return OK; }

这里有个初学常见疑问：为什么i = pos而不是pos+1？举例说明，S = “ababa”，T = “abab”，第一次匹配到pos=1，删除后S变成“a”。如果i=pos=1，下一次循环发现1 > length，循环结束，正确。但假如设i=pos+1=2，下一次循环从第2位开始，还是会对剩余串做一次Index查找，如果剩余串恰好又包含T，就会漏删。用S=“aaaa”，T=“aa”测试最直观：第一次删除后S=“aa”，如果i=3，会跳过剩余的这个“aa”，漏删；i=1则能继续匹配并删除干净，最终剩空串。

2.4 复杂度对比与证明题：BF和KMP到底谁更快

课后习题和考试题中常出现这样的分析题：给定主串S=“aaaaaaaaaab”，模式串T=“aaaab”，分别用BF算法和KMP算法求匹配成功需要比较多少次。BF算法的特点是一旦失配，主串指针i回溯到i-j+2的位置，模式串指针j回到1。对上述例子，BF会反复匹配到最后一个b才发现失配，主串指针一路回溯，比较次数约为主串长度乘以模式串长度的量级。最坏情况时间复杂度为O(n*m)，这种“模式串前面都匹配、最后一字符失配”的情况恰好把BF的劣势放大到极致。

KMP算法利用next数组让主串指针i不回溯，模式串指针j跳转到next[j]，整个匹配过程中主串只扫描一遍，时间复杂度为O(n+m)。课后习题还常考“为什么KMP比BF快”，答题关键就是“主串指针不回溯”，这是KMP设计思想的精髓，不是“next数组算得快”。

写复杂度证明题时，建议把结论和原因分层陈述：BF最坏情况O(n*m)，原因是每一趟匹配都可能比较m次且尝试n-m+1趟；KMP最坏情况O(n+m)，原因是i不回退、j最多增加m次且j前后移动总次数不超过m，因此线性。如果题目要求写出匹配过程，务必按“第几趟、从哪个位置开始、比较到第几个字符失配、j跳到几”逐行书写，不要只给一个最终位置，阅卷是按过程给分的。

3. 关键算法逐行解析：能直接上机的完整实现

3.1 BF算法的最简实现与复杂度验证

BF算法是朴素模式匹配，代码逻辑很直接。我给出一个从1开始的版本，以便与教材和习题答案对齐：

int Index_BF(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; }

这里最容易写错的回溯公式i = i - j + 2。匹配过程中i、j同时增加，失配时j已经比开始时多走了j-1步，所以i要回退到本轮起始位置的下一位。已知本轮起点是i - (j-1)，再下一位要再加1，所以是i - j + 2。我见过很多同学写成i = i - j + 1，结果每次都从本轮起点重新比较，死循环。

代码实现时课本的S.ch[]从下标1开始存放字符，下标0可以放串长也可以不用。但在实际C语言里，字符数组天然从0开始。如果直接套用教材代码而不做调整，会越界或漏字符。一个稳妥的策略是：在结构体中定义ch[MaxSize]和length，从ch[1]开始存字符，ch[0]留空。虽然浪费一个字节，但和教材算法保持一致，调试时不容易错。

3.2 KMP匹配主算法的C语言实现

KMP主算法和BF相比只改了一行：失配时i不回溯，j跳到next[j]。如果j已经是0，说明模式串首位都失配，i和j都要加1：

int Index_KMP(SString S, SString T, 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; }

注意当j=0时，不能去访问T.ch[0]，因为0号位不存储字符。此时应让i和j同时后移，即从主串下一位开始，模式串也重新从第1位开始匹配。这个边界条件在很多参考代码里没有写明，但实际运行中它是必要的，否则会出现访问T.ch[0]读取垃圾字符的问题。

next数组的求法采用递推方式，不看主串，只依赖于模式串本身：

void GetNext(SString T, int next[]) { int i = 1, j = 0; next[1] = 0; while (i < T.length) { if (j == 0 || T.ch[i] == T.ch[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; } } }

这段代码的原理与KMP主算法很相似：i是当前要求next值的下标，j是已匹配的前后缀长度。当T.ch[i]等于T.ch[j]时，前后缀长度加1；否则j回退到next[j]。很多同学不理解为什么求next数组也用类似KMP的回退方式，我用一个比喻解释：求next[i]本质上是在“模式串自己的前缀串中做一次模式匹配”，所以代码结构和KMP主函数几乎一样。不要在理解之前就硬背代码，背下来过两天就忘。

3.3 nextval数组的改进实现

nextval的递推代码与next非常像，核心区别在于确认跳转目标字符是否与当前字符相同：

void GetNextVal(SString T, int nextval[]) { int i = 1, j = 0; nextval[1] = 0; while (i < T.length) { if (j == 0 || T.ch[i] == T.ch[j]) { ++i; ++j; if (T.ch[i] != T.ch[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else { j = nextval[j]; } } }

为什么nextval能减少比较次数？考虑模式串T = “aaaaab”，普通next数组算出来是0 1 2 3 4 5，当第5个字符a失配时，它会跳到第4个字符a，而第4个字符a必然也失配，又跳到第3个a……一连串无效比较。nextval通过“如果跳转目标字符和当前字符一样，就继续向更早跳转”的思路，直接跳到一个可能匹配的位置。对“aaaaab”，nextval数组是0 1 2 3 4 5？实际上逐项算，应为0 1 2 3 4 5？让我们验证：j=3，T[3]=a，next[3]=2，T[2]=a，相等，所以nextval[3]=nextval[2]=1。而nextval[2]也等于nextval[1]=0。所以等长的重复字符串会把nextval递推成很多0。比如“aaaaab”的nextval是0 1 0 1 0 5？不对，我再仔细演算：

对T="aaaaab"，T[1]=a、T[2]=a、T[3]=a、T[4]=a、T[5]=a、T[6]=b。

• next[1]=0，nextval[1]=0；
• i=2：j=1，T[2]=T[1]，nextval[2]=nextval[1]=0；
• i=3：j=2，T[3]=T[2]，nextval[3]=nextval[2]=0；
• i=4：j=3，T[4]=T[3]，nextval[4]=nextval[3]=0；
• i=5：j=4，T[5]=T[4]，nextval[5]=nextval[4]=0；
• i=6：j=5，T[6]=b，T[5]=a，不相等，nextval[6]=5。

所以nextval是0 1 0 1 0 5？不对，第2个字符nextval[2]=0？前面写了nextval[2]=nextval[1]=0。那么是0 0 0 0 0 5。

是的，对于全a的模式串，nextval前5位全是0，只有最后一个b保留5。这样失配时直接从第5位跳到第0位，省掉中间所有无效跳转。这是nextval改进思想最直观的例子，习题里也喜欢拿这种极端串出题。

3.4 综合场景示例：统计子串出现次数

课后题还有一种综合题变体：统计模式串在主串中出现的次数。我习惯先用KMP写出能定位子串的基础函数，再在循环里调用。上机测试时可以用这个函数验证前面的替换、删除逻辑是否遗漏边界。

int CountSubstr(SString S, SString T) { int count = 0; int pos = 1; while (pos <= S.length) { int idx = Index_KMP(S, T, pos); if (idx == 0) break; count++; pos = idx + T.length; // 不重叠计数 } return count; }

如果把pos = idx + T.length改成pos = idx + 1，就变成允许重叠出现的计数方式。以S=“aaaaa”，T=“aa”为例，不重叠计数结果是2，重叠计数结果是4。到底用哪种取决于题目描述，建议把这两种计数逻辑都自己跑一遍，考场上一看到“子串出现次数”就能反应过来题目要的是哪种。

4. 常见误区与调试实录：这些问题90%的人都会遇到

4.1 字符串结束符的处理坑

C语言内置字符串以\0结尾，但数据结构教材中的串通常用length字段记录长度，不依赖\0作为结束标志。很多同学在做课后习题代码复现时，随手用strlen求模式串长度，结果因为数组里有脏数据导致长度不对。我在调试一个替换算法时，就遇到过T.length大于实际字符个数的情况，排查了很久才发现是字符数组初始化时没有把未用位置清零。

建议：在自己实现串结构体时，初始化时用memset把所有字符位置为0，或者统一约定ch[0]不参与存储。这样即便某个操作忽略了length字段，也不会因为读到残留字符而出现诡异行为。

4.2 数组下标从0还是从1开始的约定冲突

教材的算法描述为了与数学表示一致，串的位序从1开始；而C语言的数组下标从0开始。这个冲突是第四章上机实践的头号坑。如果你用C语言实现BF算法，最简单的方案是放弃ch[0]，从ch[1]开始存字符，人为制造一个“1基数组”。缺点是比较浪费一个字节，但换来的是与教材所有伪代码一一对应，调试起来不容易乱。

如果你坚持从ch[0]开始存，也可以，但BF回溯公式、next数组递推的下标都要整体减1适配。很多网上代码是0基实现的，和课本习题答案对不上。我的建议是，考研复习阶段以课本1基为主，把所有算法手算题和代码题都统一成1基思路；工作后写业务代码再回到0基，毕竟那时候你不需要与教材的伪代码对照了。

4.3 模式匹配越界与死循环问题

初写KMP时，最典型的报错是“数组下标越界”和“程序不结束”。越界多发生在未处理j=0的情况。当j=0时，如果还执行T.ch[j]，必然访问到ch[0]，如果ch[0]被当作串长或其他元数据，逻辑就全乱了。死循环则多出现在next数组求错、导致j一直在原地跳转的场景。

一个实用的调试方法是：在循环体内打印i、j、next[j]的值，观察j是否卡在同一个值上。如果某一次失配后j的值与上一轮失配前完全相同，说明next数组求错了。此时不要继续往后面查，先回头检查GetNext里的递推条件。

4.4 参考答案在自己机器上跑不过的常见原因

课后习题答案里给的通常不是完整可运行程序，而是一个算法函数片段。很多人把函数片段复制到自己的工程里编译不过，就以为答案错了。实际上常见的缺漏包括：没有定义SString结构体、没有引用Status类型、没有提供StrDelete和StrInsert的基础实现。算法本身正确，但环境没配齐。

我的建议是搭建一个统一的小工具集，把SString结构体、StrAssign、StrCompare、SubString、Concat等基础操作写好并验证通过，后续做第四章习题时直接复用。这样既避免重复劳动，也能在写替换、删除等算法时不至于被基础操作的细节打断思路。

5. 复习与应考经验：这一章怎样才能把分拿稳

5.1 一份可执行的刷题路径

针对第四章，我给不同目标的读者一套刷题顺序。如果是期末复习，先把概念题和手算题做完，重点是next和nextval数组的计算，然后做1-2个算法设计题：替换和删除。如果是考研准备，除了课后题，还要额外找王道或历年真题里的KMP变式题，比如基于失配信息的字符串匹配、next数组的优化证明等。

具体安排可以是：第一天梳理串的定义、存储结构和基本操作，整理复杂度结论；第二天全力练习next和nextval手算，至少完成5个不同模式串的计算并核对；第三天实现BF和KMP代码，用多个测试样例在线运行验证；第四天完成替换、删除、统计子串次数等算法设计题；第五天把所有错题和疑问点复盘一遍，把替换算法中“i = pos + V.length”这类关键步骤做成自己的错题笔记。

5.2 答题模板与踩分点

解答算法设计题时，阅卷老师一般按步骤给分。我的建议是写清楚以下几个层次：先说明数据结构，用堆分配存储还是定长顺序存储；再给出算法思想，一两句话写清“先找位置，再删除，再插入”；然后写核心代码，不要求编译通过，但逻辑必须清晰；最后分析时间复杂度。哪怕最后代码有小bug，前三步写完整也能拿大部分分数。

模式匹配的代码题尤其重视下标处理的正确性。如果分配了ch[MaxSize]却没有说明ch[0]是否使用，阅卷时容易被扣分。建议在代码前加一句注释说明：“约定串从下标1开始，ch[0]置空”。这种细节在考场上就是隐性踩分点。

5.3 我自己用过的一些小技巧

最后分享几个我实际教学和写代码过程中觉得特别好用的小技巧。计算next数组时，我会先在草稿纸上把模式串的每个前缀写成一行，然后圈出每个前缀的最长相等前后缀，再统一加1，比直接在表格里填数字更快，也不容易漏项。写KMP代码时，我会在GetNext和Index_KMP里各加一个辅助打印函数，输出每一步的i和j，这样测试样例时能看到匹配过程，不是只有一个最终结果。替换和删除算法中涉及串长更新的地方，我会用printf打印每次循环后的串内容和长度，一旦结果不对，马上能看出是长度没更新还是位置偏移错误。

根据我个人经验，第四章的很多错误其实都出在“边界条件”上，而不是算法主体逻辑上。所以每次写完匹配类代码，我都会用三个测试用例自测：模式串长度为1、模式串等于主串、主串为空。这三个用例能暴露绝大多数越界和死循环问题，省下大量调试时间。把这些习惯保持到考试或项目里，串这一章基本就不会再丢分了。