Module 02

第二阶段：数据结构

数据结构不是一组需要背诵的类名，而是对数据组织方式和操作代价的选择。本模块从一个问题开始：程序反复对数据做什么操作？ 先确定操作，再选择能以合适代价完成操作的结构。

一、先建立统一模型

任何数据结构都可以从四个问题开始：数据放在哪里，结构维护什么不变量，向外提供哪些操作，操作的时间和空间代价是什么。先回答这四个问题，才能看懂代码为什么需要数组、指针、哈希或树。

存储模型

连续槽位：数组、动态数组、堆、矩阵
节点与指针：链表、树、Trie
槽位与哈希：HashMap、Set
关系与邻居：图
代表元与父指针：并查集
区间摘要：Fenwick、Segment Tree

存储模型决定了能否按下标访问、插入时是否需要搬移、访问是否具有缓存局部性，以及结构需要维护多少额外索引。

不变量

不变量是每次公开操作完成后都必须成立的事实。例如堆顶保持全局最小值，链表的 next 连接方向正确，二叉搜索树左子树值小于根，Trie 的路径对应字符前缀，并查集的父指针最终到达代表元。

写代码前先写不变量；调试时先检查不变量。一个操作如果只在样例上产生正确输出，却破坏了不变量，后面的操作迟早会失败。

接口契约

接口不只是函数名，还包括结果、是否原地修改、空结构行为、重复元素策略、非法输入处理和复杂度口径。教程中的每篇结构都应明确：

二、按操作需求选择结构

不要从“我记得哪些结构”开始，而要从题目中的重复操作开始。下面的表是选择的起点，复杂度仍需结合具体实现和输入约束确认。

选择时再问三个问题

第一，操作是在线到达还是可以先整体预处理？第二，是否需要输出完整有序结果，还是只需一个极值、存在性或聚合值？第三，数据规模、更新频率和内存限制是否允许更复杂的索引？

例如，求一次数组最大值不需要堆；如果元素不断加入且每次都要取最大值，堆才体现优势。需要区间最小值但更新很少时，前缀或稀疏表可能比线段树简单；更新频繁时才考虑动态区间结构。

三、沿一条学习路径推进

模块按依赖关系分为五段。每段先学习最小模型，再学习实现和题型，后一段会复用前一段的概念。

第一段：连续数据和端点顺序

1. 数组与字符串：连续存储、索引、扩容、双指针、前缀和与滑动窗口。
2. 链表：节点连接、虚拟头节点、插入删除和快慢指针。
3. 栈与队列：后进先出、先进先出、双端队列和单调结构。

这一段建立“访问位置”和“维护顺序”的基础。栈、队列和很多图遍历、解析、滑动窗口算法都从这里出发。

第二段：按 key 和优先级组织数据

1. 哈希表：哈希、冲突、扩容、去重、计数和分组。
2. 堆：堆序不变量、优先队列、Top K、多路归并和动态中位数。

哈希表优化的是按 key 找到对象，堆优化的是反复取得当前极值。两者都不是“万能快速结构”，都依赖明确的接口和复杂度前提。

第三段：从局部连接到任意关系

1. 树与二叉树：递归结构、遍历、二叉搜索树、构造和序列化。
2. 图：边列表、邻接表、邻接矩阵、遍历、路径和带权关系。

树是有层级的关系，图允许任意关系。树遍历中的栈和队列、图遍历中的邻接结构，都建立在前面线性结构的接口之上。

第四段：专用索引和连通性

1. 字典树：把字符串的公共前缀共享为节点路径。
2. 并查集：用代表元维护动态等价关系、连通分量和合并。

Trie 适合前缀约束，并查集适合只关心“是否属于同一组”的场景。它们都用额外状态换取特定操作的低复杂度。

第五段：区间与题面构造

1. 树状数组、线段树与位集合：处理动态区间查询、更新、位运算和坐标压缩。
2. ACM 模式构造数据结构：从文本输入构造数组、链表、树、图和操作序列。

进阶结构要在明确操作和约束后再学。ACM 构造贯穿所有前置结构，解决的是“怎样从题面得到正确内存对象”的工程问题。

四、每篇文章都按同一顺序阅读

为了避免章节之间风格跳跃，每篇教程统一遵循以下主线：

具体问题
  → 朴素方案的代价
  → 存储模型
  → 不变量
  → 核心操作的状态变化
  → 最小实现
  → 典型应用
  → 复杂度与边界
  → 实验、练习和面试表达

如果文章把 API、实现、题型和面试问答交叉在一起，读者会不断切换阅读目标。API 先作为接口契约出现，代码随后验证不变量，题型最后从不变量自然推导出来。

五、复杂度要写清前提

看到 O(1)、O(log n) 或 O(n) 时，继续追问它属于哪种口径：

• 最坏复杂度：任何输入都不超过的上界。
• 平均复杂度：依赖输入分布、哈希均匀等假设。
• 均摊复杂度：一串操作的总成本平均到每次，例如动态数组扩容。
• 输出敏感复杂度：结果本身很大时，至少要支付输出成本。

例如哈希表平均 O(1) 依赖冲突控制；普通二叉搜索树查找是 O(h)，不平衡时高度可能达到 n；动态数组追加均摊 O(1)，扩容瞬间仍需 O(n)；输出所有前缀匹配单词时，输出长度不能从复杂度中隐去。

六、统一处理边界条件

每篇文章至少覆盖空结构、单元素、重复元素、最大规模、越界和非法输入。对于题目保证合法的场景，要明确这是题目条件，不是通用 API 的承诺。

还要说明对象所有权：切片通常创建新容器，链表删除可能复用节点，图的邻接表可能共享边对象。没有所有权说明，调用者无法判断修改返回值是否会影响原结构。

七、学完每篇应该留下什么

每学完一个结构，保留四样东西：一张存储布局图、一份最小实现、一张接口与复杂度表，以及一组覆盖边界的测试。测试不只验证样例，还要验证不变量在每次操作后仍成立。

建议使用下面的复盘卡：

八、模块级练习

1. 用数组实现栈，再用两个栈实现队列。
2. 用堆和排序分别求 Top K，比较时间、空间和输出顺序。
3. 用邻接表和并查集分别处理无向图连通性，说明两者能回答的问题有什么不同。
4. 用 Trie 实现前缀计数和自动补全，明确重复单词和删除行为。
5. 用树状数组和线段树处理动态区间和，比较实现复杂度和适用范围。
6. 为链表、树和图设计一套 ACM 序列化与反序列化格式。

九、完成标准

读完本模块后，你应该能从题目中的操作反推出结构，而不是从结构名称反推题目。你能画出数组、节点、哈希桶、树、图和区间摘要的内存模型，写出最小接口，说明不变量、边界和复杂度，并用测试证明实现没有破坏契约。

当题目继续追问“为什么这样设计”“换一种结构行不行”或“极端输入会怎样”时，回到同一条主线：操作需求、存储模型、不变量、代价和边界。数据结构的系统认知就建立在这几个稳定问题上，而不是建立在零散的记忆点上。

十、从一个操作追到一个结构

下面用几个小场景练习推导过程。

场景一：实时读取最小任务

任务不断到达，每次处理当前优先级最低的任务。数组能保存任务，却需要线性扫描；排序能一次得到顺序，却要在新任务到达后重新维护整体顺序。堆只要求父节点不大于子节点，于是堆顶就是下一项，插入和删除沿树高调整。

场景二：判断两个对象是否已连通

如果只需要回答“是否属于同一组”，并且关系不断合并，并不需要保留完整路径。并查集维护每个元素到代表元的父链，合并时连接两个代表，查询时沿父链找到代表并进行路径压缩。它的接口和图的邻接表不同，不能因为两者都谈连通性就互相替代。

场景三：查询某个前缀下的单词

哈希表适合完整 key 查询，却不能直接共享不同单词的公共前缀。Trie 把每个字符放到路径上，查询复杂度主要由字符串长度决定。若只需要精确查找，哈希表通常更简单；若要前缀计数、补全或词典遍历，Trie 的额外节点才有价值。

场景四：反复更新区间和

逐项修改和查询会重复扫描区间。前缀和能快速查询，却不适合频繁更新；树状数组用树状索引保存部分区间摘要，在线更新和查询都是对数级；线段树保存更灵活的区间节点，代价是实现、内存和边界更多。先明确更新和查询的比例，再决定是否需要复杂结构。

十一、阅读代码时的五个追问

看到一个新结构时，按顺序问：它的最小状态是什么？哪个字段表达不变量？一次操作先修改哪个字段？异常中途退出会留下什么状态？复杂度是否把复制、输出或重建成本算进去？

这五个问题适用于 Python 容器，也适用于手写节点结构和 ACM 构造。回答不出来时，先画状态变化图，不要马上背模板代码。

十二、术语回顾

• 接口：调用者可以依赖的操作和行为约定。
• 实现：在内存中保存状态并完成接口的具体方法。
• 不变量：公开操作结束后必须成立的事实。
• 均摊复杂度：把偶发的大成本分摊到一系列操作。
• 局部性：近期或相邻数据更可能再次访问的性质。
• 别名：两个变量引用同一个对象或节点。
• 单位元：区间聚合中与运算结合后不改变结果的值。

这些词会在各篇教程中反复出现。先掌握它们之间的关系，再记每种结构的特殊名词。

十三、从基础到进阶的复习节奏

第一次学习时，只要求能画模型、说不变量、写最小操作；第二次学习时，再补复杂度、实现优化和边界；第三次复习时，使用题型和实验验证是否能在新题面中迁移。不要在第一次阅读时同时记住所有变体，否则细节会遮住主线。

每次复习都回到同一个起点：题目反复做什么操作？结构维护了什么事实？如果换一种输入或规模，哪个代价会先成为瓶颈？

十四、模块入口

按照上述路径开始阅读：数组与字符串。读完线性结构后进入哈希表和堆，再进入树、图、Trie、并查集，最后学习区间结构和 ACM 构造。每篇文章内部都沿用同一套“问题—模型—不变量—操作—应用—边界”顺序。

十五、遇到不会的题怎么办

不要从答案代码反向记忆。先把题目改写成操作表：需要按位置、按 key、按优先级、按前缀、按连通性，还是按区间聚合？再列出数据是否动态、是否在线、是否要求原地修改。操作表通常会排除大多数不合适的结构。

如果仍无法选择，先使用最简单能表达不变量的结构写出正确版本，再用规模约束和性能测量决定是否升级。正确性、边界和接口先于微优化；结构越复杂，越需要测试不变量和所有权。

十六、最后的自检

读者完成本模块后，应能从空结构开始描述初始化，再跟踪一次插入、查询和删除的状态变化；应能说明异常输入如何处理，指出复杂度依赖的前提，并给出一个会暴露错误不变量的测试。达到这个标准，数据结构才从零散 API 变成可以迁移的系统知识。

这套方法也适用于尚未收录的新结构：先描述问题，再选择表示，写出不变量，验证操作，最后比较代价。目录会继续扩展，但阅读和推导的主线保持不变。

复习时可以把每章的核心模型画在同一张纸上，比较结构如何用不同存储方式换取不同操作代价。这样新题出现时，先识别操作，再调用已有模型。

最终目标不是记住更多名词，而是能解释每个选择的原因、代价和边界，并将这种解释迁移到新的题目和工程场景。

从这里开始阅读第一篇：数组与字符串。