第10章 基本数据结构 — 章节汇总

章节概览

本章是 Part III 数据结构的开篇，介绍了四种基本数据结构：栈（Stack）、队列（Queue）、链表（Linked List）和有根树（Rooted Tree）。这些数据结构是后续复杂数据结构（二叉搜索树、红黑树、B树等）的基础。栈和队列基于数组实现，提供 $O(1)$ 的基本操作；链表通过指针实现灵活的动态集合操作；有根树的表示方法为后续树结构算法奠定基础。

---

10.1 简单的基于数组的数据结构

小节	核心主题	关键结论
10.1 简单的基于数组的数据结构	数组、矩阵、栈、队列	数组 $O(1)$ 随机访问；栈/队列各操作 $O(1)$

核心思路：数组是连续内存存储的数据结构，支持 $O(1)$ 随机访问。栈是后进先出（LIFO）的数据结构，支持 PUSH/POP 操作。队列是先进先出（FIFO）的数据结构，支持 ENQUEUE/DEQUEUE 操作。栈和队列都可以用数组高效实现，各操作均为 $O(1)$。

---

10.2 链表

小节	核心主题	关键结论
10.2 链表	单/双链表、哨兵、循环链表	SEARCH $O(n)$；INSERT/DELETE $O(1)$（已知位置）

核心思路：链表通过指针将对象线性连接，顺序由指针而非数组索引决定。双链表的每个元素包含 next 和 prev 指针，支持双向遍历。哨兵（sentinel）是哑节点，可以简化边界条件处理，消除空链表的特判。循环链表的尾节点指向头节点，实现环形结构。

---

10.3 有根树的表示

小节	核心主题	关键结论
10.3 有根树的表示	二叉树、left-child/right-sibling	每个节点固定2个指针；$O(n)$ 空间

核心思路：二叉树每个节点包含 left、right、parent 三个指针。对于任意多叉树，使用 left-child/right-sibling（LCRS）表示法：每个节点包含 left-child（最左子节点）和 right-sibling（右兄弟）两个指针，将多叉树统一为二叉树表示。LCRS 表示法空间效率高（每个节点固定 2 个指针），是后续树算法的标准表示。

---

本章核心知识点

关键数据结构对比

数据结构	访问	搜索	插入	删除	空间
数组	$O(1)$	$O(n)$	$O(n)$	$O(n)$	$O(n)$
栈	$O(1)$ 顶	$O(n)$	$O(1)$ 顶	$O(1)$ 顶	$O(n)$
队列	$O(1)$ 首/尾	$O(n)$	$O(1)$ 尾	$O(1)$ 首	$O(n)$
双链表	$O(n)$	$O(n)$	$O(1)$	$O(1)$	$O(n)$
二叉树	—	$O(n)$	$O(h)$	$O(h)$	$O(n)$

核心操作复杂度

操作	栈	队列	双链表
插入	PUSH $O(1)$	ENQUEUE $O(1)$	LIST-INSERT $O(1)$
删除	POP $O(1)$	DEQUEUE $O(1)$	LIST-DELETE $O(1)$
搜索	—	—	LIST-SEARCH $O(n)$

---

与前序章节的知识关联

前序章节	关联方式
第2章 入门	栈用于递归（2.3节分治法）；数组是插入排序/归并排序的基础
第6章 堆排序	堆是用数组表示的二叉树（6.1节），与10.3节的树表示互补
第7章 快速排序	栈用于快速排序的迭代版本（尾递归优化）
第3章 运行时间	RAM模型假设数组访问 $O(1)$（10.1节的基础）

---

学习路线

第10章学习路径：
  10.1 简单的基于数组的数据结构（数组→栈→队列）
    → 10.2 链表（指针→双链表→哨兵→循环链表）
      → 10.3 有根树的表示（二叉树→LCRS表示）

学习建议

本章是数据结构的基础，内容相对直观但细节重要。10.1 的栈和队列是后续算法（DFS、BFS、表达式求值）的核心工具。10.2 的链表操作（尤其是哨兵优化）需要仔细理解指针操作的正确性。10.3 的 LCRS 表示法是后续第12章（二叉搜索树）和第13章（红黑树）的基础，务必掌握其与原始多叉树的对应关系。

基本数据结构