【王道考研·数据结构】第四章 数组、特殊矩阵与串（整合版）

引言

第四章的内容看起来有点“拼盘”：前半部分是数组和特殊矩阵，后半部分是串与字符串匹配算法。但它们其实有一条共同主线：

如何把具有特殊结构的数据，用更紧凑、更高效的方式存起来，并在此基础上进行访问和处理。

这一章主要解决三类问题：

  1. 数组在内存里到底怎么放
  2. 特殊矩阵怎样压缩存储
  3. 串怎样存储，以及如何高效做模式匹配

本篇基于现有旧文章内容，把第四章整合成一篇完整复习文章。

图像化理解（Mermaid）

一句话：前半章省空间，后半章省比较次数。

一、数组的物理存储结构

1. 一维数组

一维数组在内存中是连续存放的。

若：

  • 首地址为 LOC
  • 元素类型大小为 sizeof(ElemType)

则下标从 0 开始时：

1
Address(a[i]) = LOC + i * sizeof(ElemType)

2. 二维数组的本质

二维数组在逻辑上是一个平面，但在物理内存中必须“拉平”为一维。

因此会有两种常见存储方式：

  • 行优先
  • 列优先

假设二维数组 b[M][N]，下标从 0 开始。

（1）行优先

先存第一行，再存第二行……

1
LOC + (i * N + j) * sizeof(ElemType)

（2）列优先

先存第一列，再存第二列……

1
LOC + (j * M + i) * sizeof(ElemType)

这一部分是后面矩阵压缩映射公式的基础。

二、特殊矩阵的压缩存储

压缩存储的核心思想是：

只存有用信息，不存重复信息和大量无意义的常量。

1. 对称矩阵

（1）定义

若 a[i][j] = a[j][i]，则该矩阵是对称矩阵。

（2）压缩策略

因为上三角和下三角完全对称，所以只需要存：

  • 主对角线
  • 下三角区（或上三角区）

元素个数为：

1
1 + 2 + ... + n = n(n + 1) / 2

（3）行优先存下三角时的映射公式

在考研里要特别注意：

  • 矩阵行列号常从 1 开始
  • 一维数组下标常从 0 开始

当 i >= j 时：

1
k = i(i - 1)/2 + j - 1

若访问的是上三角元素 i < j，则利用对称性转成 a[j][i]：

1
k = j(j - 1)/2 + i - 1

2. 三角矩阵

（1）定义

  • 下三角矩阵：主对角线及下三角区是有效值，上三角区全为同一个常量 c
  • 上三角矩阵：反过来，下三角区全为同一个常量 c

（2）压缩策略

和对称矩阵类似，但需要在一维数组最后额外留一个位置存常量 c。

所需空间：

1
n(n + 1)/2 + 1

（3）以行优先存下三角矩阵为例

若 i >= j：

1
k = i(i - 1)/2 + j - 1

若 i < j：

1
k = n(n + 1)/2

即都映射到最后一个位置，取常量 c。

3. 三对角矩阵

（1）定义

若当 |i - j| > 1 时有 a[i][j] = 0，则称为三对角矩阵。

也就是说，只有：

  • 主对角线
  • 主对角线上方一条线
  • 主对角线下方一条线

可能为非零。

（2）压缩策略

按行优先只存这条“带状区域”。

总元素数：

1
3n - 2

（3）映射公式

当元素位于带状区域内时：

1
k = 2i + j - 3

如果已知 k 反推 (i, j)，则：

  • i = floor((k + 1)/3 + 1) 或 ceil((k + 2)/3)
  • j = k - 2i + 3

而若 |i - j| > 1，则该位置元素为 0。

4. 稀疏矩阵

（1）定义

若非零元素个数远远少于矩阵元素总数，则称为稀疏矩阵。

（2）为什么不适合普通压缩公式

对称矩阵、三角矩阵、三对角矩阵都还有规则可用；但稀疏矩阵的非零分布不规则，因此更适合直接记录“有哪些非零元素”。

（3）三元组表

顺序存储方案是只记录非零元素的：

1
<行号, 列号, 值>

这就形成了三元组表。

优点：

  • 节省大量空间

缺点：

  • 失去了随机访问特性
  • 查某个 (i, j) 位置常常需要从头遍历三元组

（4）十字链表

若稀疏矩阵经常需要插入、删除非零元素，则三元组表会频繁移动元素，不够灵活，因此可用十字链表。

每个非零元素结点包含：

  • row, col, value
  • right：同行下一个非零元素
  • down：同列下一个非零元素

十字链表的优势在于：

  • 更适合动态插删

5. 特殊矩阵做题防坑指南

这一部分最容易出错的不是公式本身，而是条件混乱。

做题时一定先确认：

  1. 行列下标从 0 开始还是 1 开始
  2. 一维数组下标从 0 开始还是 1 开始
  3. 是行优先还是列优先
  4. 是存上三角还是下三角

如果公式忘了，最稳的办法不是硬想，而是自己画一个 3×3 或 4×4 小矩阵，手动编号去找规律。

三、串的定义与基本概念

1. 什么是串

串（String）是由零个或多个字符组成的有限序列，一般记为：

1
S = 'a1a2...an' (n >= 0)

其中：

  • S 是串名
  • 字符序列是串值
  • n 是串长

当 n = 0 时，称为空串。

2. 子串、主串、位置

  • 子串：串中任意个连续字符组成的子序列
  • 主串：包含某个子串的串
  • 字符在主串中的位置：字符序号
  • 子串在主串中的位置：子串第一个字符在主串中的位置

3. 空串和空格串

  • ""：空串，长度为 0
  • " "：空格串，长度等于空格字符个数

空格也是字符，因此空格串不是空串。

4. 位序问题

在串的教材讨论中：

  • 字符位序通常从 1 开始

而在 C 语言中：

  • 数组下标通常从 0 开始

这一点在 SubString、Index、KMP 中必须始终保持清醒。

四、串与线性表的关系、基本操作与比较规则

1. 串和线性表的关系

串本质上是一种特殊的线性表，因为它也满足：

  • 元素之间是一对一线性关系
  • 可以顺序访问

但它与一般线性表不同在于：

  1. 串的元素通常是字符
  2. 串的操作对象更强调子串而不是单个元素
  3. 多个字符组合起来才更有实际语义

2. 串的基本操作

常见操作包括：

  • StrAssign(&T, chars)：赋值
  • StrCopy(&T, S)：复制
  • StrEmpty(S)：判空
  • StrLength(S)：求串长
  • ClearString(&S)：清空
  • DestroyString(&S)：销毁
  • Concat(&T, S1, S2)：串联接
  • SubString(&Sub, S, pos, len)：求子串
  • Index(S, T)：模式匹配定位
  • StrCompare(S, T)：比较大小

它们本质上可分为三类：

  1. 构造与销毁
  2. 访问与判断
  3. 组合与查找

3. 串的比较规则

串的大小比较采用逐字符比较：

  1. 从前往后依次比较
  2. 一旦出现不同字符，谁的字符大谁就大
  3. 若短串是长串前缀，则长串更大
  4. 全部字符相同且长度相同，两个串才相等

这就是字典序比较。

4. 字符集、编码与乱码

字符能比较大小，是因为最终都被编码成二进制数。

  • 字符集：规定有哪些字符
  • 编码：规定这些字符如何映射为二进制

乱码的本质不是文件损坏，而是：

写入和读取使用了不同编码规则。

五、串的存储结构

1. 顺序存储

串的顺序存储就是用一段连续空间存字符，再配合长度信息或结束标记描述有效范围。

常见教材写法：

1
2
3
4
typedef struct {
    char ch[MAXLEN + 1];
    int length;
} SString;

典型特点：

  • ch[0] 废弃不用
  • 位序从 1 开始
  • length 单独记录长度

优点

  • 随机访问方便
  • 按位序取字符快
  • 实现简单

缺点

  • 容量可能受限
  • 插入、删除需要移动大量字符

2. 链式存储

链式存储的最朴素方式是：

  • 每个结点存一个字符
  • 用指针把字符链接起来

缺点明显：

  • 指针开销大
  • 存储密度低
  • 不利于随机访问

因此实际中常用块链结构，一个结点存多个字符。

3. 顺序串基本操作的实现意识

基于顺序串结构，常见操作都能直接写出来，例如：

  • StrAssign
  • StrEmpty
  • StrLength
  • ClearString
  • StrCompare
  • SubString
  • Concat

做题时必须特别注意：

  • pos 合法性
  • len 是否越界
  • 串长是否超过容量上限

六、字符串模式匹配

1. 什么是模式匹配

给定：

  • 主串 S
  • 模式串 T

模式匹配要解决的问题是：

在主串中找到一个与模式串值相同的子串，并返回它第一次出现的位置；若不存在，则返回 0。

2. 模式串与子串的区别

  • 子串：一定存在于主串中
  • 模式串：只是拿来匹配的目标，不一定真的出现在主串中

这是概念题很常见的陷阱。

七、朴素模式匹配算法（BF）

1. 核心思想

设：

  • 主串长度为 n
  • 模式串长度为 m

则主串中一共有 n - m + 1 个长度为 m 的候选子串。

朴素算法的做法是：

  1. 先比较第 1 个候选子串和模式串
  2. 若不匹配，再比较下一个候选子串
  3. 直到找到匹配位置或试完所有候选子串

2. 指针写法

用两个指针：

  • i：主串当前位置
  • j：模式串当前位置

若匹配成功：

1
2
i++;
j++;

若失配：

1
2
i = i - j + 2;
j = 1;

3. 为什么是 i = i - j + 2

设当前候选子串起点是 k，已经匹配了 j - 1 个字符，则：

1
i = k + (j - 1)

所以：

1
k = i - j + 1

下一个候选子串起点应为 k + 1，因此：

1
i = i - j + 2

4. 时间复杂度

最坏情况下：

1
O(nm)

典型情形就是前面不断几乎匹配成功，只在最后一个字符失败。

八、KMP 算法与 next 数组

1. KMP 的优化本质

朴素算法失配后会让主串指针回退，而 KMP 的核心思想是：

主串指针不回溯，只有模式串指针回跳。

原因是失配前那一段匹配信息其实没有浪费，可以通过模式串内部结构复用。

2. next 数组的含义

在王道教材的 1 基写法里：

  • 当模式串第 j 个字符失配时
  • 模式串指针应跳到 next[j] 继续比较

特别地：

1
next[1] = 0

3. next[j] 的本质

对 j > 1，next[j] 表示：

T[1...j-1] 的最长相等真前缀和真后缀长度，再加 1。

之所以要“加 1”，是因为记录的不是长度，而是“下一次该从模式串第几个字符继续比”。

4. KMP 匹配规则

若当前字符匹配：

1
2
i++;
j++;

若失配：

1
j = next[j];

若 j == 0，说明已经没有可复用前缀，只能让主串继续后移：

1
2
i++;
j++;

5. KMP 复杂度

  • 求 next：O(m)
  • 匹配过程：O(n)

总复杂度：

1
O(m + n)

九、next 数组的手算与 nextval 优化

1. 手算 next 数组的核心方法

对王道写法，永远先写：

  • next[1] = 0
  • next[2] = 1

之后求 next[j] 时：

  1. 看 T[1...j-1]
  2. 找最长相等真前缀和真后缀
  3. 若长度为 k，则 next[j] = k + 1
  4. 若不存在，则 next[j] = 1

2. google 例子

旧文里给出的结果是：

1
2
3
位置j    1 2 3 4 5 6
模式串    g o o g l e
next[j]  0 1 1 1 2 1

这是典型手算题。

3. 为什么还要 nextval

有时 j = next[j] 后，下一次比较还会立刻再次失配，这样就浪费了一次比较。

若发现：

1
T[j] == T[next[j]]

则可以直接继续跳，得到优化后的 nextval。

4. nextval 规则

1
2
3
4
if (T.ch[j] == T.ch[next[j]])
    nextval[j] = nextval[next[j]];
else
    nextval[j] = next[j];

5. nextval 的意义

它进一步跳过了那些“跳过去也必然继续失配”的位置，从而减少无效比较。

6. KMP 为什么主串不回溯

设失配时：

1
S[i-j+1...i-1] = T[1...j-1]

也就是说主串前面那段内容已经完全确定，不需要再重新比较；真正需要调整的是模式串的对齐位置。

因此：

  • 主串指针 i 不回退
  • 模式串指针 j 通过 next 或 nextval 回跳

这就是 KMP 的本质。

十、图像化总览（Mermaid）

1. 二维数组拉平图

2. 特殊矩阵压缩图

3. BF 与 KMP 对比图

4. next / nextval 作用图

十一、易错点与易混淆点（详细版）

A. 易混淆点（A vs B）

  1. 行优先 vs 列优先

    • 行优先偏移含 i*N
    • 列优先偏移含 j*M
    • 判断口诀：谁在外层大块推进，谁乘“另一维长度”。

  2. 对称矩阵 vs 三角矩阵

    • 对称矩阵：上/下三角互为镜像
    • 三角矩阵：另一半是统一常量 c，不是镜像

  3. 空串 vs 空格串

    • 空串长度为 0
    • 空格串长度为若干空格个数

  4. 子串 vs 模式串

    • 子串一定在主串中存在
    • 模式串是“待匹配目标”，可能不存在

  5. next 的值 vs 公共前后缀长度

    • 公共前后缀长度是 k
    • 王道 1 基写法通常记录 k+1 作为继续比较位序

B. 易错点（为什么错 + 怎么改）

  1. 地址公式错一位

    • 错因：下标从 0/1 混用。
    • 正解：先统一下标体系，再代公式。

  2. 压缩映射只背公式不审题

    • 错因：没看“存上三角/下三角、行优先/列优先”。
    • 正解：先画 3x3 小图编号，再写通式。

  3. BF 失配回退位置写错

    • 错因：把 i=i-j+2 当死记，场景一变就错。
    • 正解：先求当前候选起点 k=i-j+1，下一起点 k+1 推导即可。

  4. KMP 中 j==0 处理漏写

    • 错因：只记 j=next[j]。
    • 正解：j==0 表示模式串已退无可退，必须 i++、j++。

  5. nextval 误以为改变正确性

    • 错因：把优化看成“另一个算法”。
    • 正解：nextval 只减少无效比较，不改变匹配结果。

C. 本章做题顺序建议

1
2
3
矩阵题：先审下标/存储方向 -> 再代映射公式
串匹配：先写 i,j 更新规则 -> 再写边界条件
KMP题 ：先求 next -> 再跑匹配过程

十二、书签级思维导图复现（第四章，Mermaid）

十三、PDF 例题与知识点补充（数组、矩阵、串）

例题 1：二维数组行优先地址

题目：已知 b[M][N]、首地址 LOC、元素大小 s，求 b[i][j] 地址（0基）。

答案：LOC + (i*N + j) * s。

详细解析：

  1. 行优先表示先按行连续存储。
  2. 第 i 行前面有 i*N 个元素。
  3. 再偏移第 j 列，得到总偏移 i*N+j。
  4. 地址 = 首地址 + 偏移 * 元素大小。

例题 2：二维数组列优先地址

题目：同一数组在列优先下，b[i][j] 地址公式是什么？

答案：LOC + (j*M + i) * s。

详细解析：

  1. 列优先表示先按列连续存储。
  2. 第 j 列前面有 j*M 个元素。
  3. 列内再偏移 i，总偏移 j*M+i。

例题 3：对称矩阵压缩存储量

题目：n 阶对称矩阵仅存下三角（含主对角）需要多少单元？

答案：n(n+1)/2。

详细解析：

  1. 第 k 行（1基）下三角有效元素有 k 个。
  2. 总数是 1+2+...+n。
  3. 求和得 n(n+1)/2。

例题 4：下三角矩阵映射（1基）

题目：下三角（含主对角）按行压缩时，a[i][j] (i>=j) 的映射下标是多少？

答案：k = i(i-1)/2 + j - 1。

详细解析：

  1. 第 i 行前共有 1+...+(i-1)=i(i-1)/2 个元素。
  2. 行内第 j 个元素再加偏移 j-1。

例题 5：三角矩阵常量区

题目：若上三角（或下三角）全为常量 c，压缩时如何处理？

答案：常量区通常只用 1 个额外单元保存 c。

详细解析：

  1. 常量区所有值相同，无需重复存储。
  2. 访问到常量区坐标时直接返回该单元值即可。

例题 6：三对角矩阵有效元素个数

题目：n 阶三对角矩阵有效元素个数是多少？

答案：3n-2。

详细解析：

  1. 主对角有 n 个。
  2. 上下对角各 n-1 个。
  3. 总数 n + (n-1) + (n-1) = 3n-2。

例题 7：稀疏矩阵何时选三元组

题目：稀疏矩阵场景下，什么时候优先三元组表？

答案：非零项较少且以静态查询、遍历为主时。

详细解析：

  1. 三元组结构简单，空间紧凑。
  2. 适合“建好后主要读，不频繁改”。

例题 8：稀疏矩阵何时选十字链表

题目：什么时候优先十字链表？

答案：非零项需要频繁插入、删除时。

详细解析：

  1. 十字链表按行列都可快速挂接。
  2. 动态更新时比三元组重排更高效。

例题 9：空串与空格串

题目："" 与 " " 是否等价？

答案：不等价。

详细解析：

  1. 空串长度是 0。
  2. 空格串长度是空格数量（本题为 3）。
  3. 长度和内容都不同。

例题 10：BF 失配回退

题目：BF 算法 1 基写法失配后常用回退公式是什么？

答案：i = i - j + 2, j = 1。

详细解析：

  1. 当前比较失败时，当前匹配起点为 i-j+1。
  2. 下一候选起点应为其后一个，即 i-j+2。
  3. 模式串重置到首位比较。

例题 11：KMP 核心优化

题目：KMP 比 BF 的核心优化是什么？

答案：主串指针 i 不回退，模式串指针 j 按 next 回跳。

详细解析：

  1. BF 失配会回退主串，导致重复比较。
  2. KMP 利用模式串自身前后缀信息跳过无效比较。

例题 12：KMP 边界 j==0

题目：KMP 中当 j==0 时如何处理？

答案：执行 i++, j++。

详细解析：

  1. j==0 表示模式串已无可回退位置。
  2. 只能把主串后移一位，模式串从头重新尝试。

例题 13：next 数组定义（王道口径）

题目：王道口径下 next 的关键定义是什么？

答案：next[1]=0，next[j] 表示失配后模式串应跳到的位置。

详细解析：

  1. next 本质记录“可复用的最长前后缀信息”。
  2. 失配后无需回主串，直接据 next 调整 j。

例题 14：nextval 的意义

题目：nextval 相比 next 的意义是什么？

答案：进一步跳过“跳过去也会失配”的位置。

详细解析：

  1. 某些字符重复场景下，next 仍会造成重复比较。
  2. nextval 在构造时做二次压缩，减少比较次数。

例题 15：复杂度结论

题目：BF 与 KMP 的复杂度分别是什么？

答案：

  1. BF 最坏 O(nm)。
  2. KMP 匹配 O(n)，连同预处理整体 O(n+m)。

详细解析：

  1. BF 最坏情况下每次失配都几乎重头比较。
  2. KMP 中 i 单调前进，j 虽回退但总体受线性约束。

十四、第四章必背核对表

  1. 行优先/列优先地址公式必须会写。
  2. 对称/三角/三对角的存储量与映射条件要分清。
  3. 稀疏矩阵结构选择看“静态查询 vs 动态更新”。
  4. 空串不等于空格串。
  5. BF 回退公式和 KMP 回跳规则不能混。
  6. KMP 中 j==0 的处理必须会写。
  7. next 与 nextval 的语义差异要清晰。

总结

第四章的核心可以压缩成两句话：

  1. 数组和矩阵部分教你如何利用结构规律节省存储空间
  2. 串和模式匹配部分教你如何利用模式串自身结构减少重复比较

真正必须掌握的内容有：

  • 行优先 / 列优先寻址
  • 对称矩阵、三角矩阵、三对角矩阵的映射公式
  • 稀疏矩阵的三元组表与十字链表
  • 串的定义、基本操作与存储方式
  • 朴素模式匹配
  • KMP、next、nextval 的含义与手算方法

把这些内容真正吃透，第四章就不会再是“公式堆”和“死记硬背题”，而会变成一套很清晰的规律题。

作者：[Austoin]
参考来源：基于现有旧文章整理