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”。
| j | P[1..j-1] | 最长相等前后缀 | 长度 | next[j] |
|---|---|---|---|---|
| 1 | 空 | 无 | 0 | 0 |
| 2 | a | 无 | 0 | 1 |
| 3 | ab | 无 | 0 | 1 |
| 4 | aba | a | 1 | 2 |
| 5 | abab | ab | 2 | 3 |
| 6 | ababa | aba | 3 | 4 |
所以next数组为：0,1,1,2,3,4。
这里要注意，有些教材的next数组是从0开始定义的，结果会整体减1。做题时一定要看题目用的是哪种定义。我个人的习惯是，如果题目没有明确说明，就按照严蔚敏教材的定义来做，因为大多数国内考试都采用这套定义。
2.3 匹配过程的逐步模拟
算出next数组之后，匹配过程的模拟是另一个易错点。我用一个完整例子来演示。
主串S = “ababcabcacbab”，模式串P = “abcac”。
先算P的next数组：
| j | P[1..j-1] | 最长相等前后缀 | next[j] |
|---|---|---|---|
| 1 | 空 | 无 | 0 |
| 2 | a | 无 | 1 |
| 3 | ab | 无 | 1 |
| 4 | abc | 无 | 1 |
| 5 | abca | a | 2 |
next = [0,1,1,1,2]。
匹配过程：
第一趟：从S[1]开始，S[1..3]=“aba”与P[1..3]=“abc”比较，到S[3]和P[3]时失配（a≠c）。此时j=3，next[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’失配。此时j=5，next[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-c2+1)(d3-c3+1)...(dn-cn+1) + (i2-c2)(d3-c3+1)...*(dn-cn+1) + ... + (in-cn)] * L
列优先（先排最左边的下标）：
LOC(i1,i2,...,in) = LOC(c1,c2,...,cn) + [(in-cn)(d1-c1+1)(d2-c2+1)...(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-c2+1) + (j-1)] * L
代入：LOC(3,4) = 1000 + [(3-1)(6-1+1) + (4-1)] * 2 = 1000 + [26 + 3] * 2 = 1000 + 15*2 = 1030。
如果按列优先：LOC(i,j) = LOC(1,1) + [(j-1)*(d1-c1+1) + (i-1)] * L = 1000 + [(4-1)*5 + (3-1)] * 2 = 1000 + [15+2]*2 = 1034。
这两个结果不同，所以做题时一定要看清题目要求的是行优先还是列优先。国内教材默认行优先，但有些题目会明确说列优先。
3.3 对称矩阵和三角矩阵的压缩存储
对称矩阵的压缩存储是数组这一块的另一个高频考点。对称矩阵满足a[i][j]=a[j][i]，所以只需要存储下三角（或上三角）部分。
假设对称矩阵A[n][n]，按行优先存储下三角，存储一维数组B。B的下标k与矩阵下标(i,j)的关系是：
当i>=j时（下三角）：k = i*(i-1)/2 + j - 1（下标从0开始）
当i<j时（上三角）：k = j*(j-1)/2 + i - 1
这个公式的推导思路是：前i-1行一共有1+2+...+(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)=a，GetTail(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是原子），所以整个广义表的深度是1+1=2。
更复杂的例子：LS=(a,(b,(c,d)),e)。最外层有3个元素，长度3。子表(b,(c,d))的深度：b是原子，(c,d)是子表深度1，所以这个子表的深度是2。整个广义表的深度是2+1=3。
计算深度时，我建议从最内层往外数。先找到最深的原子，数它外面有几层括号，就是深度。
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-c+1，不是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(m+n)。虽然在实际工程中，很多场景用的是更简单的库函数，但理解KMP的过程模拟，能帮你更好地理解字符串处理的底层逻辑。
6.2 数组压缩存储在图像和矩阵计算中的应用
数组的压缩存储在实际中也很常见。比如图像处理中，很多图像本身就是二维数组，如果图像是稀疏的（大部分像素为0），就可以用稀疏矩阵的方式存储，节省空间。
对称矩阵的压缩存储在数值计算中也很重要，因为很多物理问题的系数矩阵是对称的，压缩存储可以减少一半的内存占用。
6.3 广义表在配置解析中的应用
广义表的递归结构在配置解析中很常见。比如JSON、XML这些配置格式，本质上就是广义表的变体。一个JSON对象可以包含嵌套的对象和数组，这和广义表的递归定义非常相似。
理解广义表的GetHead和GetTail操作，能帮你更好地理解递归解析的过程。虽然实际工程中不会直接用广义表的存储结构，但递归拆解的思维方式是一样的。
6.4 习题训练的真正价值
很多人觉得数据结构的习题和实际工作脱节，但我个人的体会是，习题训练的是把问题抽象成结构、再把结构映射到存储的能力。这种能力在实际工作中非常重要，因为你会发现，很多复杂问题最终都能归结为几种基本结构的组合。
串、数组和广义表这一章的习题，表面上是在考计算，实际上是在考你对结构本质的理解。你如果能把这三种结构的习题做透，后面学树和图的时候会轻松很多。
最后分享一个小技巧：做这一章的习题时，建议准备三种颜色的笔，一种画逻辑结构，一种画存储结构，一种写计算过程。这样能帮你把不同层面的信息分开，减少混淆。我在辅导别人的时候用这个方法，效果比单纯讲题好很多。
