数据结构学到第四章画风突然就变了。前几章还在和链表、栈、队列打交道到了“串”这一章乍一看不就是个字符串吗可真正翻开课本看到KMP算法的next数组和一堆nextval优化时很多人就开始怀疑人生了。严蔚敏这本《数据结构C语言版 第2版》的第四章知识点不算多可课后习题的算法设计题一个比一个能折腾求子串、串替换、删除子串、模式匹配再加上上机调试时的各种越界和野指针虐得人头皮发麻。这篇内容我就拿“串”这一章的课后习题作为主线把教材里那些经典的题目掰开揉碎讲一遍先说清楚这章的知识框架再对照着给代码、给思路、给易错点最后把KMP算法和next数组的算法规避问题讲明白。无论你是期末复习、考研刷题还是刚学到这里被作业卡住照着这个思路去写至少能少踩一半的坑。1. 第四章到底在讲什么别把“串”当成简单的字符数组很多人学这一章的时候心态很放松觉得不就是字符串吗C语言里char[]早就用熟了。但等你真去做课后题就会发现串的操作难点根本不在“能不能实现”而在“怎么在内存受限、长度会变、下标容易乱”的情况下把操作写得严谨。所以先把存储结构这关过了后面做题才能顺。1.1 定长顺序存储看着简单坑也不少定长顺序存储的定义很直接#define MAXSTRLEN 255 typedef struct { char ch[MAXSTRLEN 1]; // ch[0]存串长ch[1..ch[0]]存字符 } SString;教材里这个设计有个很重要的约定下标从1开始用ch[0]存长度。为什么这么干因为这样下标i就天然对应“串的第i个字符”写算法的时候不用来回做“下标减一”的换算。这个约定在你手算next数组的时候尤其舒服。但定长存储的硬伤也明显长度写死255一旦做串连接、插入、替换结果可能直接溢出。所以课后习题里凡是涉及长度变化的操作用定长存储就得先判断“放不放得下”否则就是缓冲区溢出。我建议初学阶段把定长存储当作“理解串结构”的入门版真正写复杂算法题时直接用堆分配。1.2 堆分配存储最常用也是课后题的主力typedef struct { char *ch; // 按需要动态分配 int length; // 串长 } HString;堆分配和定长最大的区别是长度不固定空间靠malloc动态申请用完记得free。这样写Replace、Concat这类长度会变化的操作就灵活很多。但代价是你要自己管内存稍不留神就是内存泄漏或者野指针。课后题里凡是要求“编写算法实现某个串操作”的我建议优先用堆分配来实现。原因很简单实现思路清晰不用像定长存储那样处处防溢出而且动态内存分配在考试和面试里本身就是高频考点顺手把malloc、realloc、free都练了一举两得。1.3 块链存储考研冷门理解思想即可块链存储是串的一种链式表示一个结点里放一串字符比如4个字符结点之间用指针串起来#define CHUNKSIZE 4 typedef struct Chunk { char ch[CHUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { Chunk *head, *tail; int length; } LString;这种结构的好处是插入删除不需要大量移动字符坏处是“取第i个字符”这种操作要沿着链表跳效率低而且每个结点内有空余位置还得特殊处理。考研真题里这块考得不多一般就是选择题里考一下“块链存储的特点”或者让你对比三种存储结构的优缺点。所以我的建议是理解思想、背住特性、不用深挖把时间留给KMP。2. 课后习题精讲字符串操作里的“常驻嘉宾”这一章课后算法题其实有规律可循要么考“查找定位”要么考“插入删除替换”要么考“子串处理”。这几个操作表面是函数题实际上是在训练你处理“下标偏移”和“长度变化”的能力。下面挑几个最有代表性的展开讲。2.1 SubString求子串的“参数合法”是第一道坎题目一般是这样用Sub返回串S的第pos个字符起长度为len的子串。代码本身几行就写完int SubString(SString *Sub, SString S, int pos, int len) { if (pos 1 || pos S.ch[0] || len 0 || pos len - 1 S.ch[0]) { return 0; // 参数不合法 } for (int i 1; i len; i) { Sub-ch[i] S.ch[pos i - 1]; } Sub-ch[0] len; return 1; }注意几个边界条件考试和上机都喜欢在这里挖坑pos 1下标越界必须判断。pos S.ch[0]起始位置不能超过串长。len 0长度不能为负。pos len - 1 S.ch[0]子串范围不能超出主串这里特别容易漏掉-1。我见过很多同学只判断了pos S.length然后len取大了直接越界读内存轻则输出乱码重则程序崩溃。写串的题边界判断永远是第一优先级。2.2 Replace长度变化才是真正的考点替换操作Replace(S, T, V)是这章课后题里比较有分量的一个。因为替换后串的长度会变S的长度变成S.length - T.length V.length。用定长存储你得先判溢出用堆分配就没这个烦恼。完整的实现思路分三步先定位T在S中的位置再构造一个新的临时串最后把原串空间释放掉。// 堆分配存储下用V替换S中第一次出现的T int Replace(HString *S, HString T, HString V) { int pos Index(*S, T, 1); if (pos 0) return 0; // 没找到T不用替换 char *temp (char *)malloc((S-length - T.length V.length 1) * sizeof(char)); if (temp NULL) return 0; int idx 0; // 1. 拷贝pos之前的字符 for (int i 1; i pos; i) { temp[idx] S-ch[i]; } // 2. 拷贝V for (int i 1; i V.length; i) { temp[idx] V.ch[i]; } // 3. 拷贝posT.length之后的字符 for (int i pos T.length; i S-length; i) { temp[idx] S-ch[i]; } free(S-ch); S-ch temp; S-length idx; return 1; }这里有三个细节值得说第一malloc的长度计算不要写成S-length V.length那样空间浪费还不明显最怕的是忘了减掉T.length一旦原串较长多出的空间不是你的后面写入就是越界。第二拷贝完一定记得让idx等于最终长度不要用原来的S-length去赋值。第三替换完S的旧空间必须free。很多同学刚学的时候会忘记释放跑一次两次没问题循环几千次内存就爆了。数据结构固然重要内存管理的肌肉记忆也得练出来。2.3 删除所有子串 T定位-删除-再定位这道题和Replace类似但更考验逻辑删除后新串里可能又出现了新的T所以常见做法是“定位一次、删除一次、再从头定位”。int DeleteAll(HString *S, HString T) { if (T.length 0) return 0; // 空串不能删否则死循环 int count 0; int pos Index(*S, T, 1); while (pos ! 0) { // 把后面的字符往前覆盖 for (int i pos; i T.length S-length; i) { S-ch[i] S-ch[i T.length]; } S-length - T.length; S-ch[S-length 1] \0; count; pos Index(*S, T, 1); // 重新找 } return count; }这个代码里最容易出问题的点是覆盖循环的结束条件。i T.length S-length这个条件的意思是只要后面还有字符可以往前搬就继续搬。等i T.length都超过新串长了说明该搬的都搬完了。如果你写成i S-length就会把已经被覆盖区域末尾的脏数据也搬过来长度对不上结果全是错的。还有一个隐藏的坑如果T是空串Index永远找不到空串的下一次位置吗并不是空串在任意位置都能匹配成功这会导致死循环。所以我在函数开头直接判了T.length 0返回0养成这种防御习惯上机的时候会少很多麻烦。2.4 最长重复子串暴力法也能拿到分“求串S中首次出现的最长重复子串”这类题在教材习题里出现过也经常被老师拿来当课堂思考题。最直观的做法是枚举所有可能的起始位置i和j然后不停往后比较看公共前缀最长能有多长void LongestRepeatSubstring(char *s, int n, int *start, int *len) { *start 0; *len 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { int k 0; while (i k n j k n s[i k] s[j k]) { k; } if (k *len) { *len k; *start i; } } } }这段代码的时间复杂度是O(n^3)的严格说不够高效但作为课后习题验证算法思路完全够用。如果老师要求优化后续可以往“后缀数组”或者“动态规划”的方向做但那是进阶内容。我建议初学阶段先把暴力版本写得完全正确再去追求优化一上来就搞后缀数组容易劝退。3. KMP算法与next数组这一章真正的“分水岭”说实话串这一章前面那些存储结构、子串操作认真写两天代码基本都能会。真正让大量同学卡住的是KMP算法尤其是next数组的含义和手算。但KMP这东西一旦你把“最长相等前后缀”这个概念想透了后面就是照章办事。3.1 先理解BF算法到底慢在哪里暴力匹配BF算法的思路是主串从第i个字符开始模式串从第1个字符开始一个个比一旦失配主串回到这次比较的起点1模式串回到第1个字符重新比。代码很好写int Index(HString S, HString 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; // i回到本次起点的下一位 j 1; // j回到模式串开头 } } if (j T.length) return i - T.length; return 0; }BF慢就慢在明明主串和模式串前面已经比对了很长一段失配后却要把主串的i往回退已经比对过的信息全部作废。最坏情况比如主串是0000000001模式串是00001每次都要比到最后一位才失配然后i回退几乎每个位置都比了一遍复杂度O(n*m)。KMP的核心思想就一句话失配时主串的i不回头只让模式串的j跳到合适的位置。因为主串中已经匹配过的部分和模式串的前缀有重复这些重复信息可以利用起来。3.2 next数组手算背口诀不如理解“最长相等前后缀”next数组的定义在不同教材里略有差别严蔚敏这本书用的是“从1开始next[1]0”的版本。核心含义是当模式串第j个字符失配时j应该跳到next[j]的位置继续和主串比较。手算next的步骤其实不复杂next[1] 0这是固定值。对j 1看模式串前j-1个字符组成的子串找它的最长相等前后缀长度L然后next[j] L 1。什么叫最长相等前后缀举个小例子模式串abab的前3个字符aba前缀有a、ab后缀有a、ba。前后缀都能相等的最长是a长度1所以next[4] 2因为L1加1等于2。再看前4个字符abab最长相等前后缀是ab长度为2所以next[5] 3。来看教材里最常见的例子模式串abaabcac模式串abaabcac下标j12345678next[j]01122312nextval[j]01021302手算几个关键的验证一下j4时看前3个aba最长相等前后缀是a所以next[4]2j6时看前5个abaab前缀ab和后缀ab相等长度为2所以next[6]3j7时看前6个abaabc前缀和后缀没有相等的所以next[7]1。这张表值得你亲手算一遍。算完之后再去看KMP的匹配代码你会发现每一步跳转都是有依据的而不是“玄学跳转”。3.3 nextval为什么还要修正next数组在某些场景下还会做无意义的跳转。比如模式串是aaaaab在某个位置失配时next数组可能让你从j5跳到j4然后j4又跳到j3白白比了好几轮。问题是这些位置的字符都一样既然j5的字符a和主串不匹配那j4的a也大概率不匹配不如直接跳到第一个不会再重复比较的位置。nextval的修正逻辑是求出next后如果P[j] P[next[j]]那么nextval[j] nextval[next[j]]否则nextval[j] next[j]。换句话说跳过去之后字符一样那就再往前跳一步。对照上面那串例子j3时P[3]aP[next[3]]P[1]a字符相同所以nextval[3]nextval[1]0。这样匹配时遇到第三个字符失配直接回到j0也就是主串i前进重新开始省掉一次无效比较。3.4 KMP完整实现与匹配过程推演求next数组的代码用递推写非常简洁void GetNext(SString T, int next[]) { int i 1, j 0; next[1] 0; while (i T.ch[0]) { if (j 0 || T.ch[i] T.ch[j]) { i; j; next[i] j; } else { j next[j]; } } }求nextval也是类似void GetNextval(SString T, int nextval[]) { int i 1, j 0; nextval[1] 0; while (i T.ch[0]) { 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]; } } }匹配过程int IndexKMP(SString S, SString T, int pos, int next[]) { int i pos, j 1; while (i S.ch[0] j T.ch[0]) { if (j 0 || S.ch[i] T.ch[j]) { i; j; } else { j next[j]; } } if (j T.ch[0]) return i - T.ch[0]; return 0; }注意匹配循环里的j 0一定要写这是next[j]跳到0的情况此时主串和模式串已经不可能再比较了必须让i前进一位、j复位为1。漏掉这个条件代码会死循环或者越界访问。我建议你自己挑一组串比如主串ababcabcacbab、模式串abcac然后拿着纸笔按上面代码走一遍完整流程把每次比较过程中i、j的变化写下来。这个过程走完你对KMP的理解绝对比看十遍教材都深刻。4. 算法设计题参考实现串题还能怎么考课后习题除了前面那些典型题还有一些短小精悍的算法设计题单独挑出来也可能成为期末考试的简答题或上机题。下面这几个都是比较常见的代码直接可用。4.1 串的逆置与回文判断逆置串在很多题目里都是基础操作void Reverse(SString *S) { for (int i 1, j S-ch[0]; i j; i, j--) { char t S-ch[i]; S-ch[i] S-ch[j]; S-ch[j] t; } }回文判断就是在逆置思路上加了比较int IsPalindrome(SString S) { for (int i 1, j S.ch[0]; i j; i, j--) { if (S.ch[i] ! S.ch[j]) return 0; } return 1; }这两个题没什么难度但要注意循环终止条件i j而不是i j。如果串长是偶数i j正好把中间两个字符比较完如果串长是奇数中间那个字符不用比较。4.2 统计文本中单词的个数这个题是串的应用题核心在于“单词”怎么定义。简化处理假定单词之间用空格、制表符或换行分隔连续的非分隔符算一个单词。int CountWords(SString S) { int count 0; int inWord 0; for (int i 1; i S.ch[0]; i) { if (S.ch[i] ! S.ch[i] ! \t S.ch[i] ! \n) { if (!inWord) { inWord 1; count; } } else { inWord 0; } } return count; }这里用inWord记录“当前是否处于一个单词内部”碰到分隔符就置0碰到非分隔符且之前不在单词内就计数加一。这个写法比“先去掉多余空格再统计”简单得多而且不会破坏原串。4.3 块链存储下的串插入思路如果题目让你在块链存储的串里做插入操作思路和顺序表插入很像先找到插入位置所在的块以及块内的偏移量。把插入点之后的字符全部往后挪腾出空间。这里可能涉及跨块移动比数组麻烦一些。写入新字符更新串长。块链插入的细节非常容易出错主要在于“块内满了需要申请新块”“块内空了需要释放块”。但考研和期末考一般不会让你完整手写块链插入最多考概念。所以这个题我建议你重点理解“为什么块链插入不需要大量移动字符、但定位慢”就够了代码能写多少写多少不用死磕。4.4 两个串的最长公共子串简单动态规划这个题严格说是“串”这章可以延伸出来的应用部分教材把它放在习题或思考题里。求串A和串B的最长公共子串可以用动态规划int LongestCommonSubstring(char *a, int n, char *b, int m, int *startA, int *startB) { int dp[100][100] {0}; int maxLen 0; for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i - 1] b[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; if (dp[i][j] maxLen) { maxLen dp[i][j]; *startA i - maxLen; *startB j - maxLen; } } } } return maxLen; }dp[i][j]表示“A的前i个字符”和“B的前j个字符”中以最后一个字符结尾的最长公共子串长度。当a[i-1] b[j-1]时dp[i][j]就等于dp[i-1][j-1]1。这个题做出来了说明你已经能把动态规划的思路迁移到串的处理上属于额外加分项。5. 常见问题与避坑指南上机调试和考试都要注意串这章的题逻辑不算最复杂但“小坑”特别多。我把这几年批改作业和自己写代码时经常遇到的问题做个汇总对照着检查能省不少时间。5.1 下标从0还是从1先定好规矩再写代码这是串的题最容易翻车的地方。教材里用ch[0]存长度、下标从1开始很多考研题也沿用这个约定。但你实际用C语言的时候字符串默认下标从0开始这就出现了两种体系的冲突。我的建议是做题前先看题目约定题目没说要按教材你就统一用自己最熟的那套。比如写LeetCode风格的题目就用下标从0开始、字符数组长度参数如果做教材课后题或考研手算next数组就用下标从1开始。最怕的是前后混着来函数内部用从1开始的逻辑打印时又按从0开始取字符出来的结果全对不上。5.2 定长顺序存储的溢出问题用SString做串连接或替换时结果可能超过MAXSTRLEN。教材里这个类型上限是255你写Concat(T, S1, S2)的时候S1和S2都很长T的空间根本不够。所以在定长存储下一切改变长度的操作都要先算“结果会不会超过上限”一旦超过返回ERROR或者截断处理。上机题如果看到莫名其妙的数据错乱先怀疑是不是这里越界写穿了。5.3 KMP的循环里 j 0 这个条件不能丢我见过很多同学手写KMP匹配循环写成while (i S.length j T.length) { if (S.ch[i] T.ch[j]) { i; j; } else { j next[j]; } }看起来“简洁”实际上当next[j]跳到0之后下一次循环会拿S.ch[i]和T.ch[0]比较。如果T.ch[0]里存的是长度那比较的就是长度值和字符的ASCII码必错如果存的是字符又会引入一个并不存在的“模式串第0个字符”。正确写法必须是if (j 0 || S.ch[i] T.ch[j]) { i; j; }这个j 0不是“锦上添花”是KMP算法的必要逻辑。5.4 应对考试和上机题的小技巧最后分享几个我自己的实操习惯第一任何串的题先写一个打印串的函数。不要嫌麻烦串的题全靠肉眼比对结果你把串打印出来中间变量的状态一目了然定位bug快得多。第二手算next数组的时候先画出前缀后缀表。很多同学上来就背口诀“第一个0第二个1第三个看前面”遇到复杂的串就乱了。老老实实把每个位置前面那段子串的前后缀都列出来虽然慢但绝对不出错。第三上机前先跑边界用例。空串、单字符串、模式串比主串还长、模式串正好等于主串这四类用例跑一遍你的代码基本稳了。第四KMP的代码不要背要能自己推。你只要记住“next[j]是j失配时应该跳到的位置”然后从递推定义出发GetNext就是两三分钟的事情。背代码一旦某个符号记错整个算法就崩了而你如果理解了原理就算现场写也能写对。串这一章的课后题本质上就是在训练三件事边界条件的敏感度、内存管理的意识、以及把“匹配过程”抽象成“状态转移”的能力。这些能力在后面的树、图、查找、排序里都会反复用到。把第四章认真啃下来后面的学习会顺畅很多。