13. A
## 13. A
在C语言中，数组N的下标从0开始。第一个元素 $m_{1,1}$ 对应存入 $n_0$，矩阵 $\mathbf{M}$ 的第一行有12个元素，第二行有11个，第三行有10个，第四行有9个，第五行有8个，所以 $m_{6,6}$ 是第 $12 + 11 + 10 + 9 + 8 + 1 = 51$ 个元素，下标应为50。
## 14. C
上三角矩阵按列优先存储，先存储只有1个元素的第一列，再存储有2个元素的第二列，以此类推。$m_{7,2}$ 位于左下角，对应右上角的元素为 $m_{2,7}$，在 $m_{2,7}$ 之前存有
第1列：1
第2列：2
……
第6列：6
第7列：1
前面共存储有 $1 + 2 + 3 + 4 + 5 + 6 + 1 = 22$ 个元素（数组下标范围为 $0 \sim 21$），注意数组下标从0开始，所以 $m_{2,7}$ 在数组N中的下标为22，即 $m_{7,2}$ 在数组N中的下标为22。
## 15. B
二维数组A按行优先存储，每个元素占用1个存储单元，由A[0][0]和A[3][3]的存储地址可知，A[3][3]是二维数组A中的第121个元素，假设二维数组A的每行有 $n$ 个元素，则 $n \times 3 + 4 = 121$，求得 $n = 39$，所以元素A[5][5]的存储地址为 $100 + 39 \times 5 + 6 - 1 = 300$。
## 16. A
用三元组表存储结构存储稀疏矩阵 $M$ 时，每个非零元素都由三元组（行标、列标、关键字值）组成。但是，仅通过三元组表中的元素无法判断稀疏矩阵 $M$ 的大小，因此还要保存 $M$ 的行数和列数。此外，还可以保存 $M$ 的非零元素个数。例如，右图所示的两个稀疏矩阵的三元组表是相同的，若不保存行数和列数，则无法判断两个稀疏矩阵的大小。
| 0 | 2 | 0 | 0 |
| --- | --- | --- | --- |
| 0 | 0 | 5 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 2 | 0 |
| --- | --- | --- |
| 0 | 0 | 5 |
| 0 | 0 | 0 |
<!-- page: 120 -->
2027年数据结构考研复习指导
# 归纳总结
本章所介绍的几种数据结构是线性表的应用与推广，考试中主要以选择题形式考查，但栈和队列仍可能出现在算法设计题中。不少读者看到教材中列出大量操作函数时容易产生畏难情绪：如果考试中出现了栈或队列相关的算法大题，是否需要完整写出每个操作函数？
其实，在算法设计题中，栈和队列通常作为辅助工具用于解决其他问题，无须严格按照模块化方式分函数实现。我们完全可以将其声明和核心操作写得简洁明了。以顺序栈为例：
（1）声明并初始化栈：
（2）入栈操作：
（3）出栈操作：
对于链式栈，同样只需定义一个结构体，然后根据需要从常规操作中摘取关键语句，直接嵌入到自己的解题代码中即可，无须完整实现所有接口。此外，在考研真题中，链式栈出现的概率远低于顺序栈，因此大家应有所侧重，多训练与顺序栈相关的题目。
# 思维拓展
设计一个栈，使它可以在 $O(1)$ 的时间复杂度内实现 Push、Pop 和 min 操作。所谓 min 操作，是指得到栈中最小的元素。
# 提示
使用双栈，两个栈是同步关系。主栈是普通栈，用来实现栈的基本操作 Push 和 Pop；辅助栈用来记录同步的最小值 min，例如元素 x 入栈，则辅助栈 stack_min[top++] = (x<min)?x:min；即在每次 Push 中，都将当前最小元素放到 stack_min 的栈顶。在主栈中 Pop 最小元素 y 时，stack_min 栈中相同位置的最小元素 y 也会随着 top--而出栈。因此 stack_min 的栈顶元素必然是 y 之前入栈的最小元素。本题是典型的以空间换时间的算法。
# 购买王道书，就上
# 王道官方考研书店
wangdao.taobao.com
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 121 --> 第4章 申 【考纲内容】 字符串模式匹配 【知识框架】
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
视频讲解
【复习提示】
本章为统考大纲第6章内容，根据读者建议单独成章。大纲仅要求掌握字符串模式匹配，重点是理解KMP算法的原理、next数组和nextval数组的推导过程。手工计算next数组时，可先求出部分匹配值表再进行转换，也可直接依据递推公式求解。
*4.1 串的定义和实现①
字符串简称串，计算机中非数值处理的对象基本上都是字符串数据。常见的信息检索系统（如搜索引擎）、文本编辑程序（如Word）、问答系统、自然语言翻译系统等，均以字符串作为核心处理对象。本章将详细介绍字符串的存储结构及其相关操作。
4.1.1 串的定义
串（string）是由零个或多个字符组成的有限序列，通常记为
$$
S = ^ {\prime} a _ {1} a _ {2} \dots a _ {n} ^ {\prime} \quad (n \geqslant 0)
$$
其中， $S$ 是串名，单引号括起的字符序列是串的值；每个 $a_{i}$ 可以是字母、数字或其他字符；串中字符的个数 $n$ 称为串的长度。当 $n = 0$ 时，该串称为空串（用 $\varnothing$ 表示）。
串中任意多个连续字符组成的子序列称为该串的子串，而包含该子串的串称为主串。某个字符在串中的序号称为该字符在串中的位置；子串在主串中的位置以其第1个字符在主串中的位
<!-- page: 122 -->
2027年数据结构考研复习指导
置来标识。当两个串长度相等，且对应位置上的字符完全相同时，称这两个串相等。
例如，设串A='China Beijing'，B='Beijing'，C='China'，则它们的长度分别为13、7和5。其中，B和C都是A的子串，B在A中的位置为7，C在A中的位置为1。
需注意，由一个或多个空格（空格是一种特殊字符）组成的串称为空格串，空格串不是空串，其长度等于其中空格字符的个数。
串的逻辑结构与线性表极为相似，区别仅在于串的数据对象被限定为字符集。但在基本操作上，二者有显著差异：线性表的基本操作通常以单个元素为单位，如查找、插入或删除某个元素；而串的基本操作一般以子串为单位，如查找、插入或删除一个子串等。
## 4.1.2 串的基本操作
- StrAssign(&T, chars)：赋值操作。将串 T 赋值为 chars。
- StrCopy(&T, S)：复制操作。将串 S 复制给串 T。
- StrEmpty(S)：判空操作。若 S 为空串，则返回 TRUE，否则返回 FALSE。
- StrCompare(S, T)：比较操作。若 S > T，返回值 > 0；若 S = T，返回值 = 0；若 S < T，返回值 < 0。
- StrLength(S)：求串长操作。返回串 S 中字符的个数。
- SubString(&Sub, S, pos, len)：求子串操作。用 Sub 返回串 S 中从第 pos 个字符起、长度为 len 的子串。
- Concat(&T, S1, S2)：串联接操作。用 T 返回由 S1 和 S2 联接而成的新串。
- Index(S, T)：定位操作。若主串 S 中存在与串 T 值相同的子串，则返回其在 S 中首次出现的位置；否则返回 0。
- ClearString(&S)：清空操作。将串 S 置为空串。
- DestroyString(&S)：销毁操作。将串 S 销毁。
不同的高级语言对串的基本操作集可能有不同的定义方式。在上述操作中，StrAssign（赋值）、StrCompare（比较）、StrLength（求长）、Concat（联接）和SubString（求子串）这五种操作构成了串类型的最小操作子集：它们无法通过其他串操作实现；而其余串操作（除ClearString和DestroyString外）均可基于该最小操作子集实现。
## 4.1.3 串的存储结构
### 1. 定长顺序存储表示
类似于线性表的顺序存储结构，串的定长顺序存储使用一组地址连续的存储单元来存放串值的字符序列。系统为每个串变量预先分配一个固定长度的数组。
串的实际长度不得超过 MAXLEN，若超出，则多余部分被舍弃，称为截断。串长有两种表示方式：一种是如上述结构所示，用一个独立的整型变量 len 显式记录串的长度；另一种是在串值末尾添加一个不计入串长的结束标记符 '\0'，此时串长为隐含值，需要通过遍历计算得出。
执行插入、联接等操作时，若结果串长度超过 MAXLEN，则通常按“截断”处理。要从根本上避免这一限制，需要取消对串长上限的硬性规定，转而采用动态分配的存储方式。
<!-- page: 123 -->
第4章 串
111
## 2. 增分配存储表示
堆分配存储仍以地址连续的存储单元存放串值字符序列，但其存储空间在程序运行过程中动态串请获得。
在 C 语言中，存在一个称为堆的自由存储区。可通过调用 malloc() 为新生成的串动态分配一块大小等于串长的连续存储空间：若分配成功，返回指向该空间起始地址的指针，作为串的基地址（由指针 ch 指示）：若分配失败，则返回 NULL。已分配的空间可通过 free() 释放。
上述两种存储方式被大多数高级程序设计语言所采用。块链存储表示仅做简单介绍。
## 3. 块链存储表示
类似于线性表的链式存储结构，串也可采用链表形式存储。考虑到串的特殊性（每个元素仅为单个字符），实际实现中，每个链表结点可存放一个或多个字符。每个结点称为一个块，整个链表称为块链结构。图 4.1(a) 显示了块大小为 4 的链表（每个结点存放 4 个字符），最后一块占不满时通常用“#”补齐；图 4.1(b) 则为块大小为 1 的链表（每个结点仅存 1 个字符）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 4.1 串值的链式存储方式 ## 4.2 串的模式匹配 ### 4.2.1 简单的模式匹配算法 模式匹配是指在主串中查找与模式串（待搜索的字符串）完全相同的子串，并返回其首次出现的位置。本节基于定长顺序存储结构，介绍一种不依赖其他串操作的暴力匹配算法。 在该算法中，计数指针 i 和 j 分别指示主串 S 和模式串 T 中当前待比较的字符位置。其基本思想是：从主串 S 的第一个字符开始，与模式串 T 的首字符比较。若相等，则继续比较后续字符；否则，将主串的比较起点后移一位，并重新从 T 的首字符开始比较；重复此过程，直至模式 <!-- page: 124 --> 2027年数据结构考研复习指导 串 $\mathrm{T}$ 的所有字符依次与主串 $\mathrm{S}$ 中某段连续字符完全匹配，则称匹配成功，函数返回该子串在主串中的起始位置；若遍历完主串仍未找到匹配，则返回 0，表示匹配失败。 图4.2显示了模式串 $\mathrm{T} = \text{'abcac'}$ 和主串S中的匹配过程。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图4.2 简单模式匹配算法举例
在简单模式匹配算法中，设主串和模式串的长度分别为 $n$ 和 $m$（$n \gg m$），则最多需进行 $n - m + 1$ 趟匹配，每趟最多比较 $m$ 次，因此最坏时间复杂度为 $O(nm)$。例如，当模式串为'0000001'，而主串为'00000000000000000000000000000000000000000000000000000'时，由于模式串前6个字符均为'0'，而主串前45个字符也全为'0'，导致每趟匹配都直到模式串的最后一个字符才发现不匹配。整个过程中，主串指针i需回溯39次，总比较次数达 $40 \times 7 = 280$ 次。
## 4.2.2 串的模式匹配算法——KMP算法
在图4.2的第三趟匹配过程中，当 $i = 7$、$j = 5$ 位置字符不相等时，通常会从 $i = 4$、$j = 1$ 重新开始比较。然而，观察发现，$i = 4$ 和 $j = 1$、$i = 5$ 和 $j = 1$ 以及 $i = 6$ 和 $j = 1$ 这三次比较都是不必要的。因为从第三趟部分匹配的结果可知，主串的第4、5、6个字符（'b'、'c'、'a'），与模式串的第2、3、4个字符相同，而模式串的首字符为'a'，故这些重复比较是多余的。只需将模式串向右滑动三个字符的位置，然后从 $i = 7$、$j = 2$ 继续比较即可。
在简单模式匹配中，每次匹配失败后都会将模式串向右滑动一位并从头开始比较。但是，某次已匹配成功的序列实际上是模式串的某个前缀，通过分析模式串本身的结构，若已匹配成功的序列中有后缀正好是模式串的前缀，则可直接将模式串右滑到与这些字符对齐的位置，而无须回溯主串指针i，从而提高效率。这种优化策略正是KMP算法的核心。
<!-- page: 125 -->
第4章 串
113
# 1. KMP算法的原理
要理解模式串的结构，首先需明确几个概念：前缀、后缀和部分匹配值。前缀是指除最后一个字符外，字符串的所有头部子串；后缀是指除第一个字符外，字符串的所有尾部子串；部分匹配值则是指字符串的前缀和后缀的最长相等前后缀长度。下面以'ababa'为例进行说明：
- 'a'的前缀和后缀均为空集，最长相等前后缀长度为0。
- 'ab'的前缀为{a}，后缀为{b}，{a}∩{b}=∅，最长相等前后缀长度为0。
- 'aba'的前缀{a,ab}∩后缀{a,ba}={a}，最长相等前后缀长度为1。
- 'abab'的前缀{a,ab,aba}∩后缀{b,ab,bab}={ab}，最长相等前后缀长度为2。
- 'ababa'的前缀{a,ab,aba,abab}∩后缀{a,ba,aba,baba}={a,aba}，交集有两个，最长相等前后缀长度为3。
因此，模式串'ababa'的部分匹配值为00123。
那么，这个部分匹配值有何作用？
回到最初的问题，主串为'ababcabcacbab'，模式串为'abcac'。
利用上述方法容易求得模式串'abcac'的部分匹配值为00010，将部分匹配值组织成数组的形式，即构成部分匹配值表（Partial Match Table，PM表）。
| 编号 | 1 | 2 | 3 | 4 | 5 |
| --- | --- | --- | --- | --- | --- |
| S | a | b | c | a | c |
| PM | 0 | 0 | 0 | 1 | 0 |
下面利用 PM 表进行字符串匹配：
主串 a b a b c a b c a c b a b
模式串 a b c
# 第一趟匹配：
在第3位发生失配（c≠a），此前已匹配2个字符'ab'。查表可知，最后一个匹配字符b对应的部分匹配值为0，按照下面的公式计算模式串需要右滑的位数：
右滑位数 = 已匹配字符数 - 对应的部分匹配值
由于 $2 - 0 = 2$，将模式串向右滑动2位，进行第二趟匹配。
主串 a b a b c a b c a c b a b
模式串 a b c a c
# 第二趟匹配：
在第5位发生失配（c≠b），此前已匹配4个字符'abca'。查表可知，最后一个匹配字符a对应的部分匹配值为1，$4 - 1 = 3$，将模式串向右滑动3位，进行第三趟匹配。
主串 a b a b c a b c a c b a b
模式串 a b c a c
# 第三趟匹配：
模式串全部字符匹配成功。
可见，部分匹配值的核心价值在于指导模式串在失配后的最优右移距离。整个过程中，主串指针始终未回溯，这使得KMP算法的时间复杂度稳定为 $O(n + m)$。
某趟匹配失败时：若已匹配序列中不存在相等的前后缀（PM值为0），则滑动位数最大，直接将模式串首字符对齐到主串当前失配位置；若存在最长相等前后缀（可理解为首尾重合），则将模式串向右滑动至与主串中该相等后缀对齐的位置，从而跳过已知相等的部分，避免重复比较。两种情形下，模式串右滑位数均为“已匹配字符数－对应的部分匹配值”。
<!-- page: 126 -->
2027年数据结构考研复习指导
还有一种特殊情况：若模式串的第一个字符即与主串当前字符失配，则已匹配字符数为 0，按规则将模式串整体右移一位，并从主串下一个位置开始新一轮匹配。
## 2. next 数组的手算方法
在实际匹配过程中，模式串在内存中的存储位置是固定的，并不会真正“滑动”；发生变化的只是指针。前文通过模拟滑动的方式，是为了直观地帮助读者理解KMP算法的匹配逻辑。
**中点击右键）** KMP算法中指针变化/比较次数的分析（2015、2019）
KMP算法的核心特性是：每趟匹配失败时，主串指针 i 不回溯，仅模式串指针 j 调整。为此，可定义一个 next 数组，next[j] 的含义是：当模式串的第 j 个字符失配时，下一轮应从模式串的第 next[j] 个位置继续与主串当前字符比较。
下面介绍一种手算 next 数组的方法，仍以模式串 'abcac' 为例。
第 1 个字符失配时：令 next[1] = 0，然后指针 i 加 1，指针 j 重置为 1，即下一轮将模式串的第 1 个位置与主串当前位置的下一位置进行比较（注意，图中下标为字符编号）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
第 2 个字符失配时：令 next[2] = 1，模式串下次的比较位置为 1，相当于向右滑动 1 位（注，next[1] = 0、next[2] = 1 是固定规则）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
在后续的手算过程中，可在失配位置前画一条分界线，尝试将模式串向右移动，直到分界线左侧的部分能够首尾对齐（存在相等的前后缀），或模式串完全跨过分界线为止。 第 3 个字符失配时：模式串下次的比较位置为 1，即 next[3] = 1，相当于向右滑动 2 位。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
第 4 个字符失配时：模式串下次的比较位置为 1，即 next[4] = 1，相当于向右滑动 3 位。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
第 5 个字符失配时：模式串下次的比较位置为 2，即 next[5] = 2，相当于向右滑动 3 位。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 127 -->
第4章 串
115
next 数组和 PM 表的关系是怎样的？
通过上述举例，可推导出 next 数组和 PM 表之间的关系：
$$
\begin{array}{l}
\text{next}[j] = j - \text{右滑位数} = j - (\text{已匹配的字符数}^{\oplus} - \text{对应的部分匹配值}) \\
= j - [(j-1) - \text{PM}[j-1]] \\
= \text{PM}[j-1] + 1
\end{array}
$$
因此，next 数组等于将 PM 表右移一位，再整体加 1。经验证，该结论与手算结果一致。
| 编号 | 1 | 2 | 3 | 4 | 5 |
| --- | --- | --- | --- | --- | --- |
| S | a | b | c | a | c |
| next | 0 | 1 | 1 | 1 | 2 |
我们注意到：
1) PM 表右移后空出的第一个位置补 0，因为若模式串首字符失配，算法规定 next[j] = 0，表示将主串和模式串同步右移一位。
2) PM 表最后一个元素右移后移出，因为原来的模式串中，最后一个字符的部分匹配值是供其下一个字符使用的，但显然其没有下一个字符，所以可以舍去。
**注意**
以上讨论均假设串的编号从 1 开始；若串的编号从 0 开始，则 next 数组需要整体减 1。
*3. next 数组的推理公式
如何推理 next 数组的一般公式？设主串为 's₁s₂⋯sₙ'，模式串为 'p₁p₂⋯pₙ'。当主串的第 i 个字符与模式串的第 j 个字符失配时，应将主串当前位置与模式串的哪个字符进行比较？
假设此时应与模式串的第 k（k<j）个字符比较，则模式串的前 k-1 个字符的子串必须满足以下条件，且不存在更大的 k'>k 满足条件：
$$
'p_1p_2 \cdots p_{k-1}' = 'p_{j-k+1}p_{j-k+2} \cdots p_{j-1}'
$$
若存在满足上述条件的子串，则发生失配时，仅需将模式串的第 k 个字符与主串的第 i 个字符对齐。此时，模式串的前 k-1 个字符必然与主串中第 i 个字符之前的 k-1 个字符相等，因此，可直接从模式串的第 k 个字符开始，与主串的第 i 个字符继续比较，如图 4.3 所示。
| 主串 | s₁ | — | — | — | — | — | s₁-k+1 | — | s₁-1 | s₂ | — | — | — | — | sₙ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 子串 | | | p₁ | — | pₖ-₁ | — | p₁-k+1 | — | p₁-1 | p₂ | — | pₙ | | | |
| 右滑 | | | | | | | p₁ | — | pₖ-1 | pₖ | — | — | pₙ | | |
图 4.3 模式串右滑到合适位置（阴影对齐部分表示上下字符相等）
若在已匹配的序列中不存在满足上述条件的相等前后缀（可视为 k=1），则应让主串的第 i 个字符与模式串的第 1 个字符重新比较。
特别地，当模式串的第 1 个字符（j=1）与主串失配时，规定 next[1] = 0。
通过上述分析可得出 next 函数的公式：
$$
\text{next}[j] = \begin{cases}
0, & j = 1 \\
\max\{k \mid 1 < k < j \text{且 'p}_1 \cdots p_{k-1}' = 'p_{j-k+1} \cdots p_{j-1}' \}, & \text{当此集合不为空时} \\
1, & \text{其他情况}
\end{cases}
$$
要用代码来实现，貌似难度不小，下面尝试推理求解的科学步骤。
① 注意，当模式串匹配到位置 j 失配时，已匹配成功的字符数为 j-1。</j）个字符比较，则模式串的新的字符相等。
<!-- page: 128 -->
2027年数据结构考研复习指导
首先由公式可知
$$
\text{next}[1] = 0
$$
设 $\text{next}[j] = k$，此时 $k$ 应满足的条件在上文中已描述。
此时 $\text{next}[j+1] = ?$ 可能有两种情况：
（1）若 $p_k = p_j$，则表明在模式串中
$$
'p_1 \cdots p_{k-1} p_k' = 'p_{j-k+1} \cdots p_{j-1} p_j'
$$
且不可能存在 $k' > k$ 满足上述条件，此时 $\text{next}[j+1] = k+1$，即
$$
\text{next}[j+1] = \text{next}[j] + 1
$$
（2）若 $p_k \neq p_j$，则表明在模式串中
$$
'p_1 \cdots p_{k-1} p_k' \neq 'p_{j-k+1} \cdots p_{j-1} p_j'
$$
此时可将求 next 函数值的问题视为一个模式匹配问题。用前缀 $p_1 \cdots p_k$ 去与后缀 $p_{j-k+1} \cdots p_j$ 匹配，当 $p_k \neq p_j$ 时，应将 $p_1 \cdots p_k$ 向右滑动至用第 $\text{next}[k]$ 个字符与 $p_j$ 进行比较，若 $p_{\text{next}[k]}$ 与 $p_j$ 仍不匹配，则需寻找长度更短的相等前后缀，下一步继续用 $P_{\text{next}[\text{next}[k]]}$ 与 $p_j$ 进行较，以此类推，直到找到某个更小的 $k' = \text{next}[\text{next} \cdots [k]]$（$1 < k' < k < j$），满足条件
$$
'p_1 \cdots p_{k'}' = 'p_{j-k'+1} \cdots p_j'
$$
则 $\text{next}[j+1] = k' + 1$。
也可能不存在任何 $k'$ 满足上述条件，即不存在长度更短的相等前后缀，令 $\text{next}[j+1] = 1$。
理解起来可能有点抽象？下面通过一个具体例子说明。
图 4.4 的模式串已求得 6 个字符的 next 值，现求 $\text{next}[7]$，因为 $\text{next}[6] = 3$，又 $p_6 \neq p_3$，所以需比较 $p_6$ 与 $p_1$（因 $\text{next}[3] = 1$），$p_6 \neq p_1$，而 $\text{next}[1] = 0$，故 $\text{next}[7] = 1$：求 $\text{next}[8]$，因为 $p_7 = p_1$，所以 $\text{next}[8] = \text{next}[7] + 1 = 2$：求 $\text{next}[9]$，因为 $p_8 = p_2$，所以 $\text{next}[9] = 3$。
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 模式串 | a | b | a | a | b | c | a | b | a |
| next[j] | 0 | 1 | 1 | 2 | 2 | 3 | ? | ? | ? |
图 4.4 求模式串的 next 值