1. 先搞清楚第四章在考什么串的学习地图如果你正捧着严蔚敏《数据结构C语言版 第2版》刷第四章的课后习题大概率会在两个地方卡住一是教材里那些用类C语言写出来的算法读起来能懂但自己动手写答案时无从下手二是只要一碰到KMPnext数组怎么算都对不上标准答案。我当初复习这一章时也一样第一遍做课后题几乎是照着答案抄的抄完依然没想明白为什么有的位置的next值会是2。这篇内容就是把第四章串这章的课后习题按题型归纳成一条清晰的路径先讲清楚每个概念在考什么再给出存储结构、基本操作、KMP、算法设计这几大类题目的完整解法和思路最后聊一聊我自己踩过的坑。适用人群是正在学数据结构的本科生、考研复习第一轮的朋友以及期末考前想快速突击串这一章的选手。1.1 为什么这一章看着简单做习题却容易卡壳串这章在整本教材里处在线性表和数组/广义表之间位置有点尴尬。很多同学觉得字符串谁不会啊结果翻开课后习题才发现求next数组绕晕了、定长顺序存储的截断问题没考虑到、Index函数边界条件写不全。明明每个字都认识组合在一起就是做不对。这里有个关键原因教材里的串操作是用抽象数据类型ADT方式定义的算法部分用的是类C语言重点在逻辑正确不在语法细节。这和前面线性表、栈、队列章节的风格一致但串这一章的操作数量特别多——StrAssign、StrCompare、StrLength、Concat、SubString、Index、Replace、StrInsert、StrDelete……单是记住这些操作的名字和参数就够呛。再加上KMP算法和next数组的推导这一章的课后习题其实区分度很大期末卷子里串这章往往能拉开十几分。1.2 课后习题的四类题型与复习顺序结合教材课后练习和历年考研真题串这一章的习题基本可以归成四类概念与名词解释题空串、空格串、子串、串相等、模式串等术语的定义与辨析。存储结构分析题定长顺序存储、堆分配存储、块链存储的特点、图示和存储密度计算。基本操作实现题在某种存储结构下实现StrCompare、SubString、Index等操作通常要求写出算法思路或可运行代码。KMP算法题手工求next数组、nextval数组分析匹配过程对比次数。外加少数提优性质的算法设计题比如删除指定字符、删除与某子串相同的部分、判断回文、统计单词个数等。我的建议是复习时先过概念再做存储结构相关的题然后趁热打铁把基本操作实现一遍最后集中突破KMP按照这个顺序你做完一套题之后对串这章的框架会清晰很多。2. 概念与名词解释题空串、空格串、子串、串相等一个都不能含糊2.1 经典概念题的答题模板这类题在课后练习里通常以简述下列术语的形式出现。网上的答案文档里最常见的几组是串string由零个或多个字符组成的有限序列一般记作S a1a2...an其中S是串名引号内是串值。串长串中字符的个数n0时称为空串。空串长度为0的串写作不含任何字符。空格串只包含一个或多个空格的串长度等于空格的数量写作 引号内有空格。子串与主串串中任意连续字符组成的子序列称为该串的子串包含子串的串称为主串。注意连续两个字这是子串和子序列的本质区别。模式串在模式匹配中用于查找定位的那个子串通常称为模式串。答题的时候最容易被扣分的是空串和空格串的区别。这两者的字数看起来差不多但定义完全不同空串的长度是0空格串的长度是它包含的空格个数。比如s1, s2 s1是空串s2是长度为1的空格串。判断一个串是否为空串要看它的字符个数而不是看它看起来空不空。2.2 串与线性表的区别高频判断/简答题还有一道几乎年年出现的题串和线性表有什么关系逻辑上讲串是一种数据元素限定为字符类型的线性表所以串具有线性表的逻辑结构特征——元素之间存在一对一的前后关系。但串的操作和普通线性表有很大差异线性表的操作对象通常是单个元素比如在第i个位置插入一个元素、删除第i个元素而串的操作对象往往是串整体比如把两个串连接起来、在串中查找某个子串、替换某段子串。正因如此串在存储时很注重连续和整体性定长顺序存储里甚至专门要讨论串长超过存储容量时的截断问题这是普通线性表不太需要关心的事。如果判断题里出现串是特殊的线性表这种说法通常是正确的但如果说串的操作和线性表完全相同那就要打叉。答题时把逻辑结构相同、操作对象不同这一句话点出来分数基本就到手了。2.3 子串位置的计数陷阱有一类小题是给一个具体串求指定子串的位置。比如S ababaaaba问子串aa出现的位置。这里有个约定俗成的坑很多教材里字符位置从1开始计数也就是第一个字符的位置是1不是C语言数组下标那样从0开始。所以aa在S中的位置分别是6和7因为这个串是a b a b a a a b a第6和第7位都是a两个相邻的a组成了aa。还有一道常见变形求aba在ababa中出现的次数和位置。这里要注意子串可以重叠所以位置1开始的aba是一个位置3开始的aba也是一个答案是出现2次。如果题目里限定了不重叠地查找那才算1次。做题前先看题干了没限定重叠这两个答案都有人写关键看你有没有踩中出题人的陷阱。3. 存储结构分析题定长顺序、堆分配、块链的图怎么画、优缺点怎么答3.1 定长顺序存储一切从截断开始定长顺序存储就是用一块连续的、长度固定的内存来存放串。教材里给的SString定义大致长这样#define MAXLEN 255 typedef struct { char ch[MAXLEN 1]; // 字符数组下标0闲置或存串长 int length; // 当前串长 } SString;课后习题里关于定长存储的题十有八九是在考截断。典型问法用定长顺序存储实现两个串的连接操作StrConcat当串长超过MAXLEN时怎么办你需要分三种情况讨论S1和S2的长度之和小于等于MAXLEN结果串完整保存在ch数组中length直接等于两个串长度之和。S1的长度小于MAXLEN但S1和S2长度之和大于MAXLENS2会被截断只保留能放得下的那部分。S1的长度已经等于MAXLENS2整个被丢弃结果就是S1本身。答题时最好画一个示意把ch数组的格子画出来标出哪些位置存放S1、哪些位置存放S2、哪些位置被截断。这样阅卷老师一眼就能看出你理解了定长带来的限制。3.2 堆分配存储动态背后的free问题堆分配存储解决了定长存储的长度限制问题。它用malloc等动态内存分配函数在堆区申请空间按实际需要分配串长所以理论上不会因为预分配空间不足而截断。习题里常考的考点是StrAssign时要用malloc申请长度加1的空间多出来的一个位置存字符串结束符\0用完记得free释放。很多同学在做这类题时只写分配不写释放这在考试里会被扣分。教材的类C描述里不会刻意强调free但如果你用标准C语言实现内存泄漏就是实打实的问题。回答优缺点时堆分配存储的优点是灵活、无截断、能充分利用空间缺点是管理复杂需要动态分配和释放频繁操作时可能产生内存碎片。3.3 块链存储存储密度的计算题块链存储是串这一章比较有特色的一块内容。它用链表来存储串每个结点可以存放一个或多个字符。如果每个结点只存一个字符那这个链表和普通的字符链表没有本质区别但空间利用率很低——每个字符都要带一个指针域。所以通常让每个结点存放多个字符这个多个就是结点大小。课后习题里常考存储密度的计算。存储密度的定义为串值所占存储量与整个存储结构总存储量的比值。举个例子假设一个结点的数据域能放4个字符每个字符占1字节指针域占4字节那么一个结点总共占1×448字节其中4字节存数据存储密度就是4/850%。如果把结点大小改为8存储密度就是8/(84)≈66.7%。最后一个结点如果没存满通常用特殊符号填充比如#或\0计算实际存储密度时要按实际字符数算也可以按结构占用量算两种口径要分清楚。还有一道经典题结点大小为4存储字符串abcdefghij一共需要几个结点答案是3个第一个结点存a、b、c、d第二个存e、f、g、h第三个存i、j、#、#或\0填充。3.4 三种存储结构的对比表回答比较三种存储结构优缺点这类综合题时可以用这个角度组织答案存储结构优点缺点适合场景定长顺序实现简单、访问方便、支持随机存取长度受限连接可能截断串长变化不大的场景堆分配长度灵活、动态扩展、无截断问题需要手动管理内存、可能产生碎片串频繁变化、长度不定的场景块链插入删除方便、不需要大块连续空间存取效率低、存储密度与结点大小相关编辑类软件中的行文本存储这个表不用死记理解了三种结构各自的取舍之后考试时现场推也能推出来。4. 基本操作实现题StrConcat、SubString、Index这类题的递进思路4.1 StrCompare的完整实现课后习题里有一道很基础的代码题实现串的比较操作StrCompare。规则是先按字典序比较字符如果某个位置字符不同返回两者的差值如果前面字符都相同比较长度长度长的串更大。以下是基于教材SString约定的实现int StrCompare(SString S, SString T) { int i 1; while (i S.length i T.length) { if (S.ch[i] ! T.ch[i]) { return S.ch[i] - T.ch[i]; } i; } return S.length - T.length; }这道题虽然简单但考察了一个很重要的习惯比较的是字符序不是先比长度。很多同学上来就写长度长的大结果碰到abc和abz这种长度相同但字符位置不同的情况就错了。字典序比较是字符串处理的基础KMP里也比较字符只是换了匹配逻辑而已。4.2 SubString的边界条件SubString是另一道高频实现题它要求从串S的第pos个字符起取出长度为len的子串。审题时注意三件事pos从1开始、len不能为负、取出的子串长度不能超出S的范围。写实现时可以这样考虑Status SubString(SString *Sub, SString S, int pos, int len) { if (pos 1 || pos S.length || len 0 || pos len - 1 S.length) { return ERROR; // 参数不合法 } int i; for (i 0; i len; i) { Sub-ch[i 1] S.ch[pos i]; } Sub-ch[len 1] \0; Sub-length len; return OK; }这个题目最容易出错的地方是边界条件判断pos len - 1 S.length这一步漏掉的话可能会读取越界数据。习题答案里常见的错误版本就是少了这个判断。建议做题时把几种非法输入列出来pos太小、pos太大、len太大、len为负然后一一验证自己的代码能想到这些边界条件说明你是真的理解了串的下标规则。4.3 朴素模式匹配Index的代码与模拟Index问题子串定位是第四章的核心操作之一。朴素算法的思路是从主串的第pos个字符开始把模式串逐位对齐比较失配就让主串指针回退到本次比较的起始位置的下一个字符模式串从第一位重新开始。教材里的类C描述改写成标准C长这样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; // 匹配成功返回起始位置 } return 0; // 匹配失败 }理解这段代码的关键在i i - j 2这一句。其实它的意思是把p指针恢复到本次比较的起点1。手动模拟一遍比如主串S ababcabcacbab模式串T abcac从pos1开始第一次比较到第3个字符时失配主串指针回退到第2位模式串回到第1位然后重新比较……整个过程虽然繁琐但手工模拟两遍之后你对串匹配的基本逻辑就通了。后面KMP的改进点恰恰就是优化这个主串回退的过程。5. KMP与next数组课后习题里区分度最高的部分5.1 next数组的手算规则到了KMP很多同学就开始发懵。其实KMP解决的是朴素匹配中主串指针反复回退的问题当模式串在第j个字符失配时主串指针不动模式串跳到某个位置继续比。这个跳到哪里由next数组决定。严蔚敏教材里next数组的定义严格说是这样的next[1] 0当j1时如果存在最长的k1kj使得p1...p_{k-1}等于p_{j-k1}...p_{j-1}那么next[j] k否则next[j] 1。用人话说就是看模式串第j个字符前面的那j-1个字符组成的串找它的最长相等前后缀长度再加1。找不到就写1特殊规定第1位写0。手算有个很实用的口诀第1位固定为0。第2位固定为1因为前面只有1个字符最长相等前后缀长度为0加1等于1。从第3位起看前j-1个字符的最长相等前后缀长度加1得到next[j]。5.2 手算实例abaabcac 与 ababaaaba教材里最经典的例子是模式串T abaabcac。我用表格带大家推一遍j12345678T[j]abaabcacnext[j]01122312逐个推导next[1] 0规定。next[2] 1规定。j3时看前2个字符ab最长相等前后缀长度为0011。j4时看前3个字符aba前缀a、ab后缀a、ba最长相等是a长度1112。j5时看前4个字符abaa前缀a、ab、aba后缀a、aa、baa最长相等还是a长度1112。j6时看前5个字符abaab前缀a、ab、aba、abaa后缀b、ab、aab、baab最长相等是ab长度2213。j7时看前6个字符abaabc前缀a、ab、aba、abaa、abaab后缀c、bc、abc、aabc、baabc没有相等前后缀011。j8时看前7个字符abaabca前缀a、ab、aba、abaa、abaab、abaabc后缀a、ca、bca、abca、aabca、baabca最长相等是a长度1112。另一个考研习题里常见的串是ababaaabaj123456789T[j]ababaaabanext[j]011234223这里重点看j5到j9的推导过程。j5时前面是abab最长相等前后缀是ab长度2所以next[5]3j6时前面是ababa最长相等前后缀是aba长度3所以next[6]4j7时前面是ababaa最长相等前后缀变成了a长度只有1所以next[7]2。这一步很多人会惯性写成5因为前面连续相等部分到第6位戛然而止中间加了个a前缀后缀对不上了。手算时一定要老老实实列出前后缀别跳步。5.3 nextval修正为什么标准答案里还有一套数组有些习题答案里除了next数组还会给一套nextval数组这是KMP的改进版。为什么需要改进看一个极端的例子模式串aaaaab如果第5个字符a失配next[5]4可第4个字符还是a让j跳到4再比较a必然还是失配等于多做了一次无用比较。nextval的作用就是把这些跳到相同字符的情况继续往前压缩。手算nextval的口诀nextval[1] 0。从第2位起比较T[j]和T[next[j]]若相等则nextval[j] nextval[next[j]]若不相等则nextval[j] next[j]。还是用ababaaaba来算结果如下j123456789T[j]ababaaabanext[j]011234223nextval[j]010104210检查几个关键位j3时T[3]aT[next[3]]T[1]a相等所以nextval[3]nextval[1]0j6时T[6]aT[next[6]]T[4]b不相等所以nextval[6]next[6]4。这个思路要理顺否则只背公式到考场上会乱。5.4 KMP算法的可运行代码手工会求next数组之后再看KMP匹配代码就轻松多了。下面是完整的get_next和KMP匹配函数void get_next(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]; } } } int Index_KMP(SString S, SString T, int pos, int next[]) { 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; } return 0; }注意j 0这个条件是KMP和朴素算法的一个关键差异。它的含义是当模式串第一个字符就和主串失配时主串指针和模式串指针要同时移动否则会陷入死循环。理解了这一点再看KMP代码就不会一头雾水了。6. 算法设计大题删除、替换、统计、回文这四类常考代码6.1 删除串中指定字符课后算法设计题里最基础的一类是删除串S中所有值为x的字符。这个题可以用双指针的思路一个指针负责遍历原串另一个指针指向结果串的末尾。C语言实现如下void DeleteChar(SString *S, char x) { int i, j 1; for (i 1; i S-length; i) { if (S-ch[i] ! x) { S-ch[j] S-ch[i]; j; } } S-length j - 1; S-ch[S-length 1] \0; }这道题考的是原地删除的思路不需要额外开一个数组只需要用一个慢指针j维护下一个保留字符应该放的位置。这个思路在线性表的顺序存储删除、数组中移除元素等题目里反复出现掌握了就不只是会做串的题。6.2 删除所有与T相同的子串再进阶一点从串S中删除所有与子串T相同的子串。这道题其实就是先找子串位置再执行删除的组合操作。比较稳妥的实现思路是用Index_KMP找到T在S中的起始位置pos。若找到则将S中pos之后的部分整体前移覆盖被删除的那一段。重复步骤1和2直到S中不再包含T。写成伪代码是void DeleteSubString(SString *S, SString T) { int pos; while ((pos Index_KMP(*S, T, 1, next)) ! 0) { int i; for (i pos T.length; i S-length; i) { S-ch[i - T.length] S-ch[i]; } S-length - T.length; S-ch[S-length 1] \0; } }这道题能帮你把定位和删除两个知识点串起来考试时如果出现得分点通常在两部分定位逻辑是否正确、删除后串长是否更新。遗漏后者是常见的失分点。6.3 判断回文与单词统计判断一个串是否为回文正读反读一样也是串这一章的高频算法题。双指针从两端向中间扫描即可int IsPalindrome(SString S) { int low 1, high S.length; while (low high) { if (S.ch[low] ! S.ch[high]) { return 0; } low; high--; } return 1; }统计串中单词个数的题也偶尔出现。思路很经典按空格分隔遇到空格就标记当前在单词外遇到非空格且之前处于单词外就计数加1并标记当前在单词内。这类题在C语言基础练习里也有但放到串的习题里用的是串的下标遍历本质上考察的是对连续字符块状态的判断能力。6.4 最长公共子串进阶方向对学有余力的同学可以考虑做一下最长公共子串问题。它要求找两个串中共同出现的最长连续子串常见的解法是动态规划。虽然严蔚敏教材正文没有展开讲但课后思考题和一些院校的考研题里会露脸。思路是维护一个二维数组dp[i][j]表示以S的第i个字符和T的第j个字符结尾的最长公共子串长度当S.ch[i] T.ch[j]时dp[i][j] dp[i-1][j-1] 1同时用一个变量记录最大值和结束位置。这个方向属于提优内容基础题还没做扎实的同学可以暂时跳过但数据结构学到后期会发现动态规划在串处理里的出场率非常高。7. 我做这章习题时踩过的坑写在最后的实操提醒7.1 题号对不上是常态先说一个让人抓狂的体验网上流传的各种严蔚敏第四章课后习题答案题号经常对不上。有的写着4.3你的书上对应内容却是4.5。这其实不全是文档的锅不同印次、不同出版社印刷的教材课后习题编号确实会有调整。所以我不建议你抱着必须按题号一个一个对的心态刷题更好的做法是按知识点归类这一章的每道题你先判断它属于概念、存储、操作、KMP中的哪一类然后带着这个判断去对照答案核心逻辑一致就够了。7.2 教材代码是类C不是标准C第一次照着教材的伪代码敲进编译器报错报了一屏的时候别怀疑自己能力有问题。教材里那些Status、SString、Concat(T, S1, S2)是抽象描述不补上结构体定义和函数声明是没法直接运行的。我在复习时自己动手补全了SString的定义、Status的枚举、基本赋值函数之后才跑通了所有算法。这个过程虽然费时间但对理解存储结构非常有帮助。如果你只是应付考试可以不用运行但建议至少手工模拟一遍否则KMP代码里的j next[j]很容易变成单纯背诵。7.3 别把子串当子序列做概念题时最容易犯的一个错误是把子串和子序列混为一谈。子串要求字符在原串中是连续出现的而子序列只要求保持相对顺序不要求连续。比如Sabcdeacd是S的子序列但不是S的子串因为a、c、d在原串里不连续。这个点看起来基础但判断以下哪个是子串的选择题里专门有人掉坑。还有类似空串是不是任意串的子串的说法按教材定义空串是任意串的子串这属于约定问题但很多同学心里犯嘀咕考场上反而选错。7.4 实用建议先手算再对答案最后说说经验。串这一章的课后习题最忌讳的就是直接看答案、觉得看懂了就翻篇。下次遇到原题你还是不会。我自己的做法是准备一张草稿纸把每个模式串的next数组推一遍推完先不查答案再用KMP匹配函数实际运行一遍验证。对不上的时候十有八九是我求最长相等前后缀时漏了某个前缀或后缀。这个过程很枯燥但极其有效因为它逼着你去处理每一个下标细节而不是停留在大概知道KMP怎么回事的层面。期末复习时把串这章的课后题按题型刷两遍性价比真的很高。第一遍过思路第二遍掐时间写答案你会发现KMP的next数组、存储结构对比、基本操作实现这些知识点会牢牢刻在脑子里。后面学到树、图、查找、排序串的基础不会拖后腿至少遇到字符串相关的算法题你会比那些跳过这章的人多一份从容。