1. 为什么“串、数组和广义表”的习题总让人卡壳1.1 这三类结构到底在考什么很多人学到《数据结构》第四章的时候会有一种错觉前面的线性表、栈和队列都还能画图理解到了串、数组和广义表突然就变成了一堆“看起来会做动手就错”的题目。我带过几轮数据结构辅导也见过不少同学在这一章反复栽跟头核心原因其实就一个——这三类结构的习题考的不是你会不会写代码而是你能不能把“逻辑结构”和“存储结构”之间的映射关系想清楚。串本质上是限定元素为字符的线性表但它的习题往往不考“线性”而是考模式匹配和存储密度。数组看起来是最简单的结构但一旦题目涉及多维数组的地址计算、压缩存储、稀疏矩阵很多人就开始晕。广义表更特殊它是线性表的推广允许元素本身又是一个表这种递归定义让很多人在求深度、求长度、求表头表尾的时候直接绕晕。所以这一章的习题表面上是三种结构实际上是三类完全不同的思维训练串训练的是匹配算法的过程模拟数组训练的是下标到地址的数学映射广义表训练的是递归结构的拆解能力。你如果把它们当成同一类题去背一定会出问题。1.2 习题中最容易丢分的三个地方根据我自己的做题和讲题经验这一章的习题丢分集中在三个地方而且这三个地方几乎覆盖了80%以上的错误第一个是串的模式匹配手算过程。很多题目会给你一个主串和一个模式串让你写出KMP算法每一步的匹配状态包括next数组的计算。很多人next数组会算但一到匹配过程就乱因为匹配过程中主串指针和模式串指针的移动规则容易记混。第二个是多维数组的地址计算。题目通常会给出数组的维度、每维的长度、起始地址、每个元素占用的字节数然后问你某个下标元素的地址。这里最容易错的是行优先和列优先的公式搞反以及下标从0开始还是从1开始没有看清。第三个是广义表的深度和长度计算。长度好说就是最外层元素的个数但深度是括号的最大嵌套层数很多人会把原子和子表的层数算错。更麻烦的是GetHead和GetTail的嵌套操作一步错步步错。提示这一章的习题建议先判断题目考的是哪一类结构再调用对应的思维模式不要一上来就硬算。1.3 这篇博文能帮你解决什么接下来我会按照习题的类型把串、数组和广义表这三块拆开来讲。每一块我都会先讲核心原理再讲典型题型的完整解题过程最后给常见错误和排查方法。你可以把它当成一份习题复盘笔记也可以当成考前突击的参考。文章里涉及的计算过程我都会写出完整的推导不会跳步。如果你正在准备考试或者复习数据结构建议拿一张纸跟着算一遍效果比只看要好得多。2. 串的模式匹配习题从next数组到匹配过程2.1 串的存储结构对习题的影响串的习题第一个容易踩的坑是存储结构不同导致的操作差异。串有三种常见存储方式定长顺序存储、堆分配存储、块链存储。考试里最常见的是定长顺序存储也就是用一个字符数组加一个长度字段来表示串。为什么这个点重要因为题目如果问“串的连接操作”在定长顺序存储下你需要考虑是否溢出如果两个串连接后的长度超过数组容量就要截断。而在堆分配存储下你可以动态申请空间不需要截断。很多题目会在题干里暗示存储方式比如给出“数组容量为MAXSIZE”这就是在提醒你考虑溢出。我见过一道题问两个串连接后的结果很多人直接写拼接后的字符串但题目给的数组容量不够正确答案应该是截断后的结果。这种题丢分非常可惜因为不是不会而是没注意存储限制。2.2 next数组的手算方法KMP算法的next数组是这一章的高频考点。我先说一个我自己用的手算方法比很多教材上的定义法更快。假设模式串为P下标从1开始。next[j]的定义是P[1..j-1]中最长相等前后缀的长度加1。特殊地next[1]0。手算步骤写出模式串的所有前缀。对每个位置j看P[1..j-1]的最长相等前后缀。长度加1就是next[j]。举个例子模式串为“ababaa”。jP[1..j-1]最长相等前后缀长度next[j]1空无002a无013ab无014abaa125ababab236ababaaba34所以next数组为0,1,1,2,3,4。这里要注意有些教材的next数组是从0开始定义的结果会整体减1。做题时一定要看题目用的是哪种定义。我个人的习惯是如果题目没有明确说明就按照严蔚敏教材的定义来做因为大多数国内考试都采用这套定义。2.3 匹配过程的逐步模拟算出next数组之后匹配过程的模拟是另一个易错点。我用一个完整例子来演示。主串S “ababcabcacbab”模式串P “abcac”。先算P的next数组jP[1..j-1]最长相等前后缀next[j]1空无02a无13ab无14abc无15abcaa2next [0,1,1,1,2]。匹配过程第一趟从S[1]开始S[1..3]“aba”与P[1..3]“abc”比较到S[3]和P[3]时失配a≠c。此时j3next[3]1所以i不变j回到1。第二趟从S[3]开始S[3]‘a’与P[1]‘a’匹配继续比较S[4]‘b’与P[2]‘b’匹配S[5]‘c’与P[3]‘c’匹配S[6]‘a’与P[4]‘a’匹配S[7]‘b’与P[5]‘c’失配。此时j5next[5]2所以i不变j回到2。第三趟从S[7]开始S[7]‘b’与P[2]‘b’匹配S[8]‘c’与P[3]‘c’匹配S[9]‘a’与P[4]‘a’匹配S[10]‘c’与P[5]‘c’匹配模式串全部匹配成功。所以模式串在主串中第一次出现的位置是S[6..10]即从第6个字符开始。这个过程的关键是失配时主串指针i不回溯模式串指针j回退到next[j]。很多人会把i也回退那就变成朴素匹配了。2.4 串习题的常见陷阱串这一块的习题有几个经典陷阱我列出来供你对照next数组定义不统一有的教材next[1]0有的next[0]-1结果整体差1。做题先看题干。下标从0开始还是从1开始如果模式串下标从0开始next数组的公式要相应调整。匹配过程中i和j的更新时机失配时i不动j回退匹配成功时i和j同时加1。求nextval数组有些题目会要求优化后的nextval规则是如果P[j]P[next[j]]则nextval[j]nextval[next[j]]否则等于next[j]。注意nextval数组的优化是为了避免不必要的比较手算时先算next再逐个判断是否需要优化。3. 数组的地址计算与压缩存储习题3.1 多维数组地址计算的通用公式数组的地址计算题核心就是一个公式。我先给出通用形式然后解释每个参数。对于n维数组A[c1..d1][c2..d2]...[cn..dn]假设每个元素占L个字节起始地址为LOC(c1,c2,...,cn)求LOC(i1,i2,...,in)。行优先先排最右边的下标LOC(i1,i2,...,in) LOC(c1,c2,...,cn) [(i1-c1)(d2-c21)(d3-c31)...(dn-cn1) (i2-c2)(d3-c31)...*(dn-cn1) ... (in-cn)] * L列优先先排最左边的下标LOC(i1,i2,...,in) LOC(c1,c2,...,cn) [(in-cn)(d1-c11)(d2-c21)...(d(n-1)-c(n-1)1) ... (i1-c1)] * L看起来复杂但实际做题时维度通常只有二维或三维套进去就行。3.2 二维数组地址计算实例我拿一道典型题来演示。题目二维数组A[1..5][1..6]每个元素占2个字节起始地址为1000按行优先存储求A[3][4]的地址。行优先公式LOC(i,j) LOC(1,1) [(i-1)*(d2-c21) (j-1)] * L代入LOC(3,4) 1000 [(3-1)(6-11) (4-1)] * 2 1000 [26 3] * 2 1000 15*2 1030。如果按列优先LOC(i,j) LOC(1,1) [(j-1)*(d1-c11) (i-1)] * L 1000 [(4-1)*5 (3-1)] * 2 1000 [152]*2 1034。这两个结果不同所以做题时一定要看清题目要求的是行优先还是列优先。国内教材默认行优先但有些题目会明确说列优先。3.3 对称矩阵和三角矩阵的压缩存储对称矩阵的压缩存储是数组这一块的另一个高频考点。对称矩阵满足a[i][j]a[j][i]所以只需要存储下三角或上三角部分。假设对称矩阵A[n][n]按行优先存储下三角存储一维数组B。B的下标k与矩阵下标(i,j)的关系是当ij时下三角k i*(i-1)/2 j - 1下标从0开始当ij时上三角k j*(j-1)/2 i - 1这个公式的推导思路是前i-1行一共有12...(i-1)i*(i-1)/2个元素第i行第j列是这一行的第j个元素所以总偏移是i*(i-1)/2 j - 1。三角矩阵类似但需要额外存储一个常数c放在最后。下三角矩阵的压缩存储中上三角部分的元素都等于c所以B的最后一个位置存c。3.4 稀疏矩阵的存储与习题稀疏矩阵的习题通常考两种存储方式三元组表和十字链表。三元组表就是把非零元素的行、列、值存成一个三元组按行优先顺序排列。题目通常会给你一个稀疏矩阵让你写出三元组表或者反过来。十字链表更复杂一些每个非零元素是一个节点包含行、列、值、向下指针、向右指针。题目可能会让你画出十字链表的结构或者问某个节点的指针指向。我个人的经验是三元组表的题相对简单只要按行扫描、按列扫描就行。十字链表的题需要画图建议先在草稿纸上画出矩阵再逐个节点连接。提示稀疏矩阵的习题如果题目没有明确要求存储方式优先用三元组表因为计算量小。4. 广义表的深度、长度与表头表尾习题4.1 广义表的基本概念回顾广义表是n个元素的有限序列记作LS(a1,a2,...,an)。其中每个ai可以是原子也可以是子表。广义表的两个基本操作是GetHead和GetTail。GetHead(LS)取广义表的第一个元素。注意如果第一个元素是子表取出来的是子表本身不是子表的表头。GetTail(LS)取广义表去掉第一个元素后剩下的部分。注意GetTail的结果一定是一个广义表。这两个操作的定义看起来简单但嵌套起来就容易出错。比如LS(a,(b,c),d)GetHead(LS)aGetTail(LS)((b,c),d)。如果再对GetTail的结果取GetHead得到的是(b,c)而不是b。4.2 广义表长度和深度的计算方法长度最外层元素的个数。比如LS(a,(b,c),d)长度是3。深度括号的最大嵌套层数。原子的深度为0空表的深度为1。对于LS(a,(b,c),d)a是原子深度0(b,c)是子表其深度为1因为b和c是原子所以整个广义表的深度是112。更复杂的例子LS(a,(b,(c,d)),e)。最外层有3个元素长度3。子表(b,(c,d))的深度b是原子(c,d)是子表深度1所以这个子表的深度是2。整个广义表的深度是213。计算深度时我建议从最内层往外数。先找到最深的原子数它外面有几层括号就是深度。4.3 GetHead和GetTail的嵌套运算这是广义表习题中最容易出错的部分。我拿一道典型题来演示。题目LS((a,b),(c,d))求GetHead(GetTail(GetHead(LS)))。逐步计算GetHead(LS) (a,b)GetTail((a,b)) (b)GetHead((b)) b所以结果是b。再比如LS(a,(b,(c,d)))求GetTail(GetHead(GetTail(LS)))。GetTail(LS) ((b,(c,d)))GetHead(((b,(c,d)))) (b,(c,d))GetTail((b,(c,d))) ((c,d))所以结果是((c,d))。这类题的关键是每一步都严格按照定义来不要跳步。我见过很多人因为跳步导致括号层数搞错。4.4 广义表的存储结构习题广义表的存储结构通常有两种头尾链表和扩展线性链表。头尾链表的每个节点有两个指针一个指向表头一个指向表尾。扩展线性链表的每个节点有三个域标志域、值域或子表指针、后继指针。题目可能会让你画出某个广义表的存储结构图或者问某个节点的指针指向。这种题建议先画出广义表的树形表示再转换成链表。注意广义表的存储结构题画图时要注意区分原子节点和表节点原子节点的标志域通常为0表节点为1。5. 习题实战中的常见问题与排查技巧5.1 串匹配习题的排查清单串匹配习题出错时按以下顺序排查问题现象可能原因排查方法next数组整体差1定义不统一看题干用的是next[1]0还是next[0]-1匹配过程i回退了混淆了朴素匹配和KMP记住KMP中i不回溯nextval算错没有正确比较P[j]和P[next[j]]逐个位置判断是否需要优化下标越界模式串下标从0开始但公式用了从1开始统一下标基准5.2 数组地址计算的排查清单数组地址计算出错时重点检查行优先还是列优先题目有没有明确说下标从0开始还是从1开始公式中的c1和d1要对应。每维的长度是d-c1不是d-c。字节数L有没有乘对起始地址是LOC(c1,c2,...,cn)不是LOC(0,0,...,0)。我个人的习惯是做题时先把公式写出来再把数值代进去最后用估算验证一下。比如二维数组A[1..5][1..6]A[3][4]大概在中间位置地址应该在起始地址加上一半左右的总大小如果算出来差太多肯定有问题。5.3 广义表习题的排查清单广义表习题出错时重点检查长度是最外层元素个数不是所有原子个数。深度是括号最大嵌套层数空表深度为1。GetHead取出的是第一个元素本身如果是子表就是子表。GetTail取出的是去掉第一个元素后的广义表结果一定带括号。嵌套运算时每一步的结果要写清楚不要跳步。5.4 我踩过的几个坑第一个坑是next数组的定义。我一开始学的时候用的是next[0]-1的定义后来做题发现很多教材用的是next[1]0结果算出来的next数组整体差1匹配过程也跟着错。后来我养成了一个习惯做题前先看题干有没有给出next的定义如果没有就按照最常见的严蔚敏教材定义来做。第二个坑是数组地址计算的下标基准。有一次题目给的是A[0..4][0..5]我习惯性地用了从1开始的公式结果地址算错了。后来我每次做题都会先把c1和d1标出来确认下标范围。第三个坑是广义表的GetTail。我一开始总以为GetTail的结果是去掉括号的后来才发现GetTail的结果一定是一个广义表必须带括号。比如GetTail((a,b))(b)不是b。这些坑看起来小但考试时丢分就是丢在这些地方。希望你能避开。6. 从习题到实战这些结构在真实场景中的影子6.1 串匹配在文本处理中的应用串的模式匹配不只是考试题它在真实场景中到处都是。比如文本编辑器的查找功能、日志分析中的关键字提取、DNA序列比对底层都是串匹配算法。KMP算法的价值在于它把朴素匹配的O(m*n)优化到了O(mn)。虽然在实际工程中很多场景用的是更简单的库函数但理解KMP的过程模拟能帮你更好地理解字符串处理的底层逻辑。6.2 数组压缩存储在图像和矩阵计算中的应用数组的压缩存储在实际中也很常见。比如图像处理中很多图像本身就是二维数组如果图像是稀疏的大部分像素为0就可以用稀疏矩阵的方式存储节省空间。对称矩阵的压缩存储在数值计算中也很重要因为很多物理问题的系数矩阵是对称的压缩存储可以减少一半的内存占用。6.3 广义表在配置解析中的应用广义表的递归结构在配置解析中很常见。比如JSON、XML这些配置格式本质上就是广义表的变体。一个JSON对象可以包含嵌套的对象和数组这和广义表的递归定义非常相似。理解广义表的GetHead和GetTail操作能帮你更好地理解递归解析的过程。虽然实际工程中不会直接用广义表的存储结构但递归拆解的思维方式是一样的。6.4 习题训练的真正价值很多人觉得数据结构的习题和实际工作脱节但我个人的体会是习题训练的是把问题抽象成结构、再把结构映射到存储的能力。这种能力在实际工作中非常重要因为你会发现很多复杂问题最终都能归结为几种基本结构的组合。串、数组和广义表这一章的习题表面上是在考计算实际上是在考你对结构本质的理解。你如果能把这三种结构的习题做透后面学树和图的时候会轻松很多。最后分享一个小技巧做这一章的习题时建议准备三种颜色的笔一种画逻辑结构一种画存储结构一种写计算过程。这样能帮你把不同层面的信息分开减少混淆。我在辅导别人的时候用这个方法效果比单纯讲题好很多。