# 《数据结构》知识点全解

> AI生成｜2026年10月28日｜codebuddy｜原书：韩桂华 程桂卿主编《数据结构》，华中科技大学出版社，2013-09-01
> **我的阅读**：进度 100%｜累计 9小时54分钟｜开始 2017-07-24｜最近 2024-05-15｜读完 2020-06-19

**一句话总结**：这本书研究数据元素之间的关系、在计算机中的存储方式以及相应操作的实现，核心是学会用时间、空间和实现复杂度做结构选型。

**适合谁 / 前置知识**：适合计算机相关专业的本科生、准备考研或面试的自学者，以及需要补数据结构基础的开发者。需要具备一门编程语言的基础，理解变量、数组、函数、指针或引用、基本递归；完全不熟悉编程的人应先补语言基础。它偏向应用型本科教材，重实用和操作，不深入算法正确性证明、摊还分析或大规模工程优化；若要做算法研究，需再读更理论化的教材。

## 一、全书地图

| 章 | 主题 | 核心问题 | 在全书中位置 |
|---|---|---|---|
| 第1章 | 绪论 | 数据结构、算法、复杂度是什么 | 建立语言与评价标准 |
| 第2章 | 线性表 | 一对一关系如何顺序或链式存储 | 最基础的结构，后续结构的构件 |
| 第3章 | 栈和队列 | 受限线性表如何解决特定顺序问题 | 线性表的操作受限变体 |
| 第4章 | 串 | 文本如何存储与模式匹配 | 线性表的字符特化 |
| 第5章 | 矩阵与广义表 | 多维、稀疏、嵌套数据如何压缩表示 | 从线性结构过渡到层次结构 |
| 第6章 | 树 | 一对多关系如何表示与遍历 | 第一个典型非线性结构 |
| 第7章 | 图 | 多对多关系如何表示、遍历与优化 | 最一般的关系结构 |
| 第8章 | 查找 | 如何按关键字高效定位记录 | 静态/动态查找表的组织 |
| 第9章 | 内排序 | 如何在内存中把记录排成有序序列 | 与查找相互依赖 |
| 第10章 | 文件 | 外存中的记录如何组织与检索 | 把结构思想扩展到磁盘环境 |

全书的主线是“逻辑结构 → 存储结构 → 基本运算 → 复杂度评价”。第2至5章处理线性或可线性化的数据；第6、7章进入树与图；第8、9章把存储结构与“查找、排序”两类高频操作结合；第10章把内存中的组织方式延伸到外存。读的时候应始终追问：数据关系是什么、用什么物理方式存、关键操作代价多大。

## 二、核心知识点

**1. 数据结构三要素与抽象数据类型**
- **是什么**：数据结构包含逻辑结构、存储结构和数据运算。逻辑结构分集合、线性、树、图；存储结构分顺序、链式、索引、散列；抽象数据类型（ADT）只描述“能做什么”，不暴露“怎么做”。
- **为什么重要**：先确定逻辑关系，再选物理存储，最后实现操作，能避免一上来就写代码导致结构错配。
- **怎么用**：设计“通讯录”时，先判定记录是一对一线性关系，再在数组和链表中按查询/插入频率选择。
- **常见误区**：把逻辑结构与存储结构混为一谈；认为链表一定比数组高级。

**2. 算法与复杂度**
- **是什么**：算法是有限、确定、可执行的求解步骤；时间复杂度描述输入规模增大时基本操作的增长率，空间复杂度描述额外空间。
- **为什么重要**：同一问题可有多种实现，复杂度决定数据量增大后是否还能用。
- **怎么用**：顺序查找为 O(n)，二分查找为 O(log n)；快排平均 O(n log n)，最坏 O(n²)。比较时同时看最好、平均、最坏情况。
- **常见误区**：把 O(1) 理解为“只执行一次”；忽略常数、缓存局部性和实际数据分布；只看平均情况而不看最坏情况。

**3. 顺序表与链表**
- **是什么**：顺序表用连续空间存元素，支持下标随机访问；链表用结点和指针表示逻辑相邻，物理位置可分散。
- **为什么重要**：这是“连续存储 vs 离散存储”的基本权衡，决定了插入、删除、查找的成本。
- **怎么用**：频繁按下标读、尾部追加，选顺序表；频繁在已知位置插入删除、长度变化大，选链表。顺序表插入平均移动约 n/2 个元素，链表定位仍需 O(n)。
- **常见误区**：说“链表插入删除一定 O(1)”却漏掉查找前驱的 O(n)；忽略链表指针的额外空间和较差的缓存局部性。

**4. 单链表的建立与维护**
- **是什么**：单链表由数据域和指针域组成，常见操作有头插法、尾插法、查找、插入、删除和逆置。
- **为什么重要**：链式思想是栈链、邻接表、树的孩子表示等结构的基础。
- **怎么用**：头插法会逆序，尾插法保持输入顺序；插入时先让新结点指向后继，再改前驱指针；逆置可用三个指针逐步改向。
- **常见误区**：先改前驱指针导致后继丢失；删除头结点或尾结点时未更新头指针/尾指针；遍历时提前移动指针。

**5. 栈**
- **是什么**：栈是只允许在一端插入和删除的线性表，遵循后进先出（LIFO）。
- **为什么重要**：它把“最近未完成的事情”组织起来，是表达式求值、括号匹配、递归和深度优先搜索的底层机制。
- **怎么用**：顺序栈用 top 标记栈顶；链栈用链表头作为栈顶。遇到左括号入栈，右括号与栈顶匹配；递归调用可理解为系统栈的压入与弹出。
- **常见误区**：空栈弹出、满栈压入未检查；把栈的“先进后出”与队列的“先进先出”混淆。

**6. 队列与循环队列**
- **是什么**：队列只允许队尾插入、队头删除，遵循先进先出（FIFO）。循环队列用取模把数组首尾相接。
- **为什么重要**：它保证按到达顺序处理任务，是广度优先搜索、打印调度、缓冲区的常用结构。
- **怎么用**：常见约定为 front 指向队头、rear 指向队尾下一位置；牺牲一个单元时，`(rear+1)%m==front` 判满，`front==rear` 判空。也可用元素个数或标志位区分空满。
- **常见误区**：普通数组队列反复出队后出现“假溢出”；不同教材对 front/rear 的定义不同，混用公式导致空满判断错误。

**7. 串与模式匹配**
- **是什么**：串是字符的有限序列；模式匹配是在主串中寻找模式串的位置。
- **为什么重要**：文本编辑、检索、日志过滤都依赖它；BF 与 KMP 展示了“利用已匹配信息”的优化思路。
- **怎么用**：BF 逐位比较，失配后主串回退，最坏 O(nm)；KMP 预处理 next 数组，失配时只移动模式串，整体 O(n+m)。next 的核心是模式串前缀与后缀的最长公共长度。
- **常见误区**：下标从 0 还是 1 开始、next[0] 还是 next[1] 起用，各教材约定不同，必须与代码统一；会把 KMP 的“不回退主串”误解为“永不比较”。

**8. 矩阵的压缩存储**
- **是什么**：二维数组可按行优先或列优先映射到一维空间；对称矩阵、三角矩阵可只存一半；稀疏矩阵可存三元组（行、列、值）。
- **为什么重要**：科学计算和图像数据常含大量重复零，压缩能显著节省空间。
- **怎么用**：对称矩阵只存下三角，按行映射到一维数组；稀疏矩阵用三元组表或十字链表，转置时可用“按列收集”或快速转置。
- **常见误区**：压缩公式的行列下标基准不统一；稀疏矩阵“压缩后一定更快”，实际上三元组检索可能更慢，需按操作选择。

**9. 广义表**
- **是什么**：广义表是元素可为原子或子表的递归结构，如 `LS=(a,(b,c))`。
- **为什么重要**：它能表示嵌套、层次化、可变长的数据，是树与递归思想的前奏。
- **怎么用**：`head` 取第一个元素，`tail` 取除首元素外其余元素组成的表；上例长度为 2，深度为 2，tail 为 `((b,c))`。
- **常见误区**：把 tail 当成“最后一个元素”；忘记 tail 的结果仍然是表；计算深度时只数括号层数而不看嵌套结构。

**10. 树与二叉树**
- **是什么**：树是除根外每个结点只有一个前驱、可有多个后继的层次结构；二叉树每个结点至多两个子树，且有左右之分。
- **为什么重要**：树能高效表达层次关系，二叉树更是查找树、堆、哈夫曼树和表达式树的基础。
- **怎么用**：常用性质有 `n0=n2+1`（叶子数等于度为 2 的结点数加 1）；完全二叉树适合顺序存储；前序、中序、后序、层序遍历是基本操作。已知“前序+中序”或“后序+中序”可唯一还原二叉树。
- **常见误区**：把“满二叉树”和“完全二叉树”混同；认为“前序+后序”也能唯一还原；遍历时把访问结点与递归子树的顺序写反。

**11. 树、森林与哈夫曼树**
- **是什么**：树可用双亲表示、孩子表示或孩子兄弟表示；森林可转化为二叉树。哈夫曼树是带权路径长度（WPL）最小的二叉树。
- **为什么重要**：孩子兄弟表示把多叉树统一成二叉树；哈夫曼编码用不等长前缀码压缩数据。
- **怎么用**：每次从森林中取两个权值最小的树合并，重复到只剩一棵；左分支记 0、右分支记 1 可得前缀编码。
- **常见误区**：认为哈夫曼树唯一——形态和编码可能不唯一，但最小 WPL 一致；合并时未使用最小堆，导致实现低效或选错结点。

**12. 图**
- **是什么**：图由顶点集和边集组成，分有向/无向、带权/无权；存储常用邻接矩阵和邻接表。
- **为什么重要**：图能表达网络、依赖、路径和关系，是社交网络、地图导航、任务调度的模型基础。
- **怎么用**：邻接矩阵适合稠密图，邻接表适合稀疏图；DFS/BFS 都要用 visited 标记。最小生成树可用 Prim（稠密图）或 Kruskal（稀疏图）；最短路可用 Dijkstra（非负权）或 Floyd；拓扑排序只适用于有向无环图。
- **常见误区**：对负权边使用 Dijkstra；遍历时不标记访问导致重复或死循环；把最小生成树当成任意两点最短路。

**13. 查找**
- **是什么**：查找是在查找表中按关键字定位记录，常见方法有顺序、二分、分块、二叉排序树、平衡树、B 树/B+ 树和散列。
- **为什么重要**：查找往往是系统最频繁的操作，组织结构直接决定响应速度。
- **怎么用**：二分查找要求有序且可随机访问，O(log n)；二叉排序树平均 O(log n)、最坏退化为 O(n)，AVL 通过旋转保持平衡；散列平均 O(1)，需处理冲突并控制装填因子。
- **常见误区**：在链表上做二分查找；认为散列最坏也是 O(1)；开放定址法删除时直接置空，破坏后续探测链。

**14. 内排序**
- **是什么**：内排序在内存中完成，常见有插入、希尔、冒泡、快速、选择、堆、归并和基数排序。
- **为什么重要**：排序是查找、去重、统计和很多算法预处理的基础；不同排序在时间、空间、稳定性上各有取舍。
- **怎么用**：小规模或基本有序可用插入排序；平均性能选快排，最坏可控选堆排或归并；要求稳定选归并、插入、冒泡、基数排序。基于比较的排序，最坏情况有 Ω(n log n) 下界。
- **常见误区**：认为快排任何情况都最快——有序且基准选择不当时会退化到 O(n²)；忽略归并排序的 O(n) 辅助空间；把“稳定”误解为“时间复杂度固定”。

**15. 文件**
- **是什么**：文件是存储在外存上的记录集合，组织方式有顺序文件、索引文件、索引顺序文件、倒排文件和直接文件。
- **为什么重要**：外存访问以块为单位，一次 I/O 的成本远高于内存运算，文件结构的目标是减少磁盘访问次数。
- **怎么用**：顺序文件适合批量顺序处理；索引顺序文件（如 ISAM 思想）兼顾顺序与随机；B+ 树适合动态索引；散列文件适合按关键字直接定位。
- **常见误区**：用内存结构的复杂度直接推断外存性能；混淆逻辑记录与物理块；忽略块因子、溢出区和索引维护成本。

## 三、关键概念速查表

| 概念 | 一句话解释 | 用在哪儿 |
|---|---|---|
| 逻辑结构 | 数据元素之间的抽象关系 | 选型第一步 |
| 存储结构 | 逻辑关系在内存中的物理实现 | 数组、链表、邻接表 |
| 时间复杂度 | 基本操作次数随规模增长的阶 | 比较算法优劣 |
| 顺序表 | 连续空间 + 下标访问 | 频繁随机读 |
| 链表 | 结点 + 指针表示相邻关系 | 频繁插入删除 |
| 栈 | 后进先出的受限线性表 | 括号匹配、递归、DFS |
| 队列 | 先进先出的受限线性表 | BFS、调度、缓冲 |
| 循环队列 | 用取模复用数组空间 | 固定容量缓冲 |
| KMP | 利用前缀函数避免主串回退 | 文本模式匹配 |
| 稀疏矩阵 | 只存非零元及其位置 | 大规模稀疏数据 |
| 广义表 | 原子或子表构成的递归表 | 嵌套结构表示 |
| 二叉树 | 每结点至多两棵有序子树 | 查找、堆、编码 |
| 哈夫曼编码 | 按频率构造的最优前缀码 | 数据压缩 |
| 邻接表 | 每个顶点挂一条边链表 | 稀疏图存储 |
| 最小生成树 | 连接所有顶点且总权最小的树 | 网络布线 |
| 拓扑排序 | 把有向无环图排成线性次序 | 任务依赖 |
| 二叉排序树 | 左小右大的动态查找树 | 动态查找 |
| 散列表 | 由关键字直接计算存储位置 | 平均 O(1) 查找 |
| 稳定性 | 相等关键字记录相对次序不变 | 多关键字排序 |
| 块因子 | 一个物理块容纳的记录数 | 外存文件设计 |

## 四、可复用的方法/框架

**结构选型五步法**
1. **定关系**：数据是一对一、一对多还是多对多？先画逻辑草图，不急着写代码。
2. **列操作**：统计查找、插入、删除、遍历、排序各自的频率，找出主操作。
3. **选存储**：主操作是随机访问就优先连续存储；主操作是已知位置增删就考虑链式；图先看稠密程度。
4. **算代价**：写出主操作的平均与最坏复杂度，同时估算额外空间。
5. **验边界**：用空表、单元素、头尾位置、满/空、重复关键字、非连通图等用例检查。

**算法实现四问**
- 输入规模和数据分布是什么？
- 是否需要稳定、是否需要原地？
- 最坏情况能否接受？
- 边界条件和失败路径是否明确？

**调试检查清单**
- 空结构能否正常操作？
- 头结点、尾结点、根结点是否特殊处理？
- 指针修改顺序是否安全？
- 循环队列的空满条件是否统一？
- 图遍历是否重置 visited？
- 排序后相等元素次序是否符合预期？

## 五、我的阅读轨迹

| 进度 | 累计阅读 | 开始阅读 | 最近阅读 | 读完时间 |
|---|---|---|---|---|
| 100% | 9小时54分钟 | 2017-07-24 | 2024-05-15 | 2020-06-19 |

全书已读完，没有未读章节。建议按“1 周—1 月—3 月”的间隔做三轮复习：第一轮复述第2至5章的存储与操作；第二轮重点攻第6、7章的遍历、还原、最短路和生成树；第三轮用第8、9章的查找与排序做综合题，并整理复杂度对照表。最近一次阅读距读完时间较久，优先复习树、图、KMP、散列和排序稳定性这些易混点。

## 六、行动清单

- 画一张“逻辑结构—存储结构—典型操作—复杂度”总表，合上书默写。
- 手写顺序表、单链表、循环队列的插入、删除、判空、判满代码。
- 用三个指针实现单链表逆置，并画出每一步的指针变化。
- 对同一组数据分别做前序、中序、后序、层序遍历，再用两种序列还原二叉树。
- 实现 Dijkstra 和拓扑排序，各构造一个反例验证边界。
- 把八种内排序按时间、空间、稳定性、适用场景做成对照表。
- 建立错题本，只记录“错因 + 正确判断 + 反例”，每周复盘一次。

## 七、延伸阅读

1. **《大话数据结构》**：语言更轻松、图示更多，适合在本书之前或并行阅读，用来补直觉；先建立结构图像，再回到本书做严谨练习。
2. **《算法（第4版）》**：在本书之后读，重点看如何把数据结构落到可运行代码，并加强算法分析与实现能力。
3. **《算法导论》**：最后读，理论性和数学性更强，适合系统补正确性证明、渐进分析和更深入的算法设计。

说明：章节名称以本书目录为准；不同教材对 KMP 的 next 定义、循环队列的 front/rear 约定可能不同，落地代码时需与所用版本核对。