字符串是字符组成的线性表，数组是按多维下标组织的元素集合。它们都不像栈和队列那样限制操作位置，但都有自己的存储约束与经典算法：字符串的匹配决定了文本处理的效率，数组的寻址决定了连续内存如何被高效利用。

本章定位

本章把线性表的思想扩展到两个常见的数据组织：串强调"内容比较与子串查找"，数组强调"多维下标到一维地址的映射"。串部分先建立抽象数据类型、字符编码与三种存储表示，再进入模式匹配：朴素匹配的复杂度分析暴露了指针回退的浪费，KMP 用最大长度表导出 next 数组，把匹配压到 $O(n+m)$，nextval 再消除必然失配的冗余比较；最后梳理串处理的工程陷阱。KMP 展示了最重要的思想——利用已经匹配的信息避免重复比较——这种思想在后面的字符串处理与模式匹配类问题中反复出现。

学习目标

完成本章后，你应该能够：

• 描述串的抽象数据类型与三种存储表示（定长、堆分配、块链）及各自的适用场景；
• 描述字符、字符集与编码的关系（ASCII、UTF-8、GBK），识别串处理中的常见陷阱；
• 实现朴素模式匹配并分析最好、一般、最坏复杂度，理解 KMP 如何避免指针回退；
• 由最大长度表手工推导 next 与 nextval 数组（约定 next[0] = -1），并论证 KMP 的复杂度为什么是 O(n + m)；
• 由多维数组的下标推导一维存储的寻址公式；
• 用压缩方式存储对称、三角矩阵和稀疏矩阵，并解释空间收益；
• 描述广义表的递归结构，正确计算表头、表尾、长度与深度。

四篇文章如何分工

学习问题	对应文章	完成后的可检查能力
字符串怎样定义、怎样编码、怎样存储？基本操作与代价如何？	3.1 字符串的定义、存储与编码	能说明字符编码与三种存储的取舍，实现基本串操作并分析复杂度
C 标准串函数有哪些？如何快速查找子串？串处理有哪些工程陷阱？	3.2 串的模式匹配与处理实践	能说明串函数库基础，由最大长度表手工推导 next/nextval 并论证 O(n + m)
多维数组怎样寻址？矩阵如何压缩？	3.3 数组寻址与特殊矩阵	能推导寻址公式，比较压缩方案的收益
广义表怎样递归定义、存储与操作？	3.4 广义表与递归算法	能区分表头表尾、求长度深度，并实现求深度等递归算法

推荐学习顺序

1. 先学习字符串的定义、存储与编码，建立串的模型与最小操作子集。
2. 再学习串的模式匹配与处理实践，这是本章的核心难点。
3. 然后学习数组寻址与特殊矩阵，难度相对平缓。
4. 最后学习广义表与递归算法，体会递归定义如何贯穿存储与算法。
5. 阅读后完成配套 Lab：先做 3.1 串基础与 3.2 模式匹配的选择题精练检验术语与存储，再依次完成 KMP、next 推导、比较次数、替换与 UTF-8 实验，最后用 Lab 03-14 工程题把本章串知识收口。

配套 Labs

• Lab 03-T-01：串的基础选择题精练（3.1）
• Lab 03-T-02：模式匹配选择题精练（3.2）
• Lab 03-T-03：数组与矩阵选择题精练（3.3）
• Lab 03-T-04：广义表选择题精练（3.4）
• Lab 03-E-01：KMP 模式匹配（首次出现位置）
• Lab 03-E-02：next 与 nextval 数组推导
• Lab 03-E-03：朴素匹配与 KMP 比较次数
• Lab 03-E-04：串的非重叠替换 Replace
• Lab 03-E-05：UTF-8 串长与字符数
• Lab 03-E-06：广义表的表头与表尾
• Lab 03-E-07：广义表的深度
• Lab 03-E-08：三对角矩阵压缩与取值
• Lab 03-E-09：多维数组行优先寻址
• Lab 03-P-01：串匹配与文本处理引擎（工程题）
• Lab 03-P-02：稀疏矩阵运算库（工程题）

学习建议

KMP 不要"背代码"

next 数组的递推第一次看容易绕。建议先用小模式串（如 ababc）手工走一遍匹配失败时主串指针不后退的过程，再对照最大长度表理解"为什么失配时跳到 next[j]"。能画出来，才算掌握。手工推导时还要注意 next 的三种约定差异（本教程采用 next[0] = -1 的 0-based 版，与 1-based 表数值整体平移 1 位），避免表值与代码对不上。

准备好后，从3.1 字符串的定义、存储与编码开始。