第 10 章 基本数据结构 (Elementary Data Structures)
核心结论
-
动态集合 (Dynamic Set)：支持插入、删除、查询的对象集合——本章所有结构都是其实现；操作包括 SEARCH / INSERT / DELETE / MINIMUM / MAXIMUM / SUCCESSOR / PREDECESSOR。
-
栈 (Stack) 与队列 (Queue)：插入删除策略受限的动态集合——栈 LIFO、队列 FIFO；都能用数组 + top/head/tail 索引实现，全部操作 \(O(1)\)。
-
链表 (Linked List)：用 next/prev 指针组织线性顺序——插入删除 \(O(1)\)、查找 \(\Theta(n)\)；支持单/双、循环/非循环、排序/未排序多种变体。
-
哨兵 (Sentinel)：虚拟节点 L:nil 消除头尾边界条件——让代码更简洁，常数小幅优化。
-
指针/对象的数组实现：用数组下标当「指针」、多数组或单数组布局存对象；ALLOCATE-OBJECT / FREE-OBJECT 用自由表 (free list) 管理可重用对象。
-
有根树表示：二叉树用 left / right / parent 三指针；任意分支树用「左孩子右兄弟」表示仅需 two 指针。
|
本章主旨
本章是数据结构章节的入门——为后续 11-14 章的高级结构（散列表、二叉搜索树、红黑树、扩充结构）打基础。重点是「用指针实现动态集合」的不同模式：(1) 受限的删除策略（栈、队列）；(2) 通用线性结构（链表）；(3) 用数组模拟指针（多个数组、单数组 + 偏移、自由表管理）；(4) 一般化的树表示（左孩子右兄弟）。本章以「操作接口 + 实现细节 + 时间复杂度」三件套描绘每个结构。算法分析上，本章几乎都是 \(O(1)\) 或 \(\Theta(n)\)——不涉及复杂递归式。 |
一、核心概念
本章围绕 5 个核心概念展开：从受限的栈/队列接口开始，扩展到通用链表，再用数组模拟指针，最后给出树结构的紧凑表示。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
栈 (Stack) LIFO |
插入删除均在同端的动态集合；PUSH = 插入，POP = 删除最近元素；数组 + S.top 索引实现。 |
§10.1；S[1..S.top] 是有效区域；STACK-EMPTY 测试 S.top == 0；上溢 / 下溢处理。 |
队列 (Queue) FIFO |
插入在尾、删除在头的动态集合；ENQUEUE/DEQUEUE；数组 + Q.head/Q.tail 实现，「循环」避免浪费。 |
§10.1；Q.head = Q.tail 时空；Q.head = Q.tail + 1 时满；wrap-around 让 n-1 个元素可存于 n 大小的数组。 |
链表 (Linked List) |
用指针组织线性顺序的对象集合；元素有 key + next（+ prev）字段；支持单链/双链、循环/非循环、排序/未排序。 |
§10.2；LIST-SEARCH \(\Theta(n)\)、LIST-INSERT/DELETE \(O(1)\)；哨兵让边界条件统一。 |
指针与对象的数组实现 |
用数组下标代替指针——多数组（key/next/prev 各一）或单数组（连续子数组 + 偏移）；ALLOCATE/FREE 用 free list 管理。 |
§10.3；指针就是数组下标，NIL 用一个不可能的整数（如 0 或 -1）；free list 可服务多个链表。 |
有根树的表示 |
二叉树用 left/right/parent 三指针；任意分支树用「左孩子右兄弟」表示——只需两指针 + 父指针，访问所有孩子 \(O(c)\)（c = 孩子数）。 |
§10.4；第 6 章堆用「数组 + 上滤下滤」表示完全二叉树（特例）；第 21 章不相交集合森林只用父指针。 |
二、详细笔记
10.1 栈与队列
What：栈是 LIFO（last-in, first-out）的线性结构；队列是 FIFO（first-in, first-out）的线性结构；两者的元素组织策略被 DELETE 操作预先指定。
Why：栈与队列是「受限的动态集合」——简化接口让实现极其高效（数组 + 单索引）。实践中栈对应函数调用栈、表达式求值、撤销栈；队列对应任务调度、BFS、广度优先。
How：
-
栈（§10.1）：
\[\begin{array}{rl} & \textbf{STACK-EMPTY}(S) \\ 1 & \textbf{if } S.\text{top} == 0 \textbf{ return TRUE } \textbf{else return FALSE} \\ & \textbf{PUSH}(S, x) \\ 1 & S.\text{top} = S.\text{top} + 1 \\ 2 & S[S.\text{top}] = x \\ & \textbf{POP}(S) \\ 1 & \textbf{if } \textbf{STACK-EMPTY}(S) \textbf{ error “underflow”} \\ 2 & \textbf{else } S.\text{top} = S.\text{top} - 1 \\ 3 & \textbf{return } S[S.\text{top} + 1] \end{array}\]所有操作 \(O(1)\)。
-
队列（§10.1）：
\[\begin{array}{rl} & \textbf{ENQUEUE}(Q, x) \\ 1 & Q[Q.\text{tail}] = x \\ 2 & \textbf{if } Q.\text{tail} == Q.\text{length} \\ 3 & \quad Q.\text{tail} = 1 \\ 4 & \textbf{else } Q.\text{tail} = Q.\text{tail} + 1 \\ & \textbf{DEQUEUE}(Q) \\ 1 & x = Q[Q.\text{head}] \\ 2 & \textbf{if } Q.\text{head} == Q.\text{length} \\ 3 & \quad Q.\text{head} = 1 \\ 4 & \textbf{else } Q.\text{head} = Q.\text{head} + 1 \\ 5 & \textbf{return } x \end{array}\]关键：循环数组——tail 到 n 后回卷到 1；这样能存 n-1 个元素于 n 大小数组（少 1 个避免 head/tail 混淆「满 vs 空」）。
When： . 栈：函数调用 / 撤销栈 / 表达式求值。 . 队列：BFS / 任务调度 / 打印池。 . 双栈实现算法问题（练习 10.1-7）：栈模拟队列 amortized \(O(1)\)。 . 双队列实现栈：操作 amortized \(O(n)\)（用于消息系统）。
Example（栈）：初始 S = ⟨15, 6, 2, 9⟩（top=4），PUSH(S, 17) 后 S = ⟨15, 6, 2, 9, 17⟩（top=5），PUSH(S, 3) 后 S = ⟨15, 6, 2, 9, 17, 3⟩（top=6），POP() 返回 3 并 top=5。
Example（队列）：图 10.2——初始 Q = ⟨15, 6, 9, 8, 4⟩（head=7, tail=12），ENQUEUE(Q, 17) → tail=1（wrap）, ENQUEUE(Q, 3) → tail=2, ENQUEUE(Q, 5) → tail=3，DEQUEUE() 返回 15 并 head=8。
10.2 链表
What：链表是「每个对象包含指向下一个（或上一个）对象的指针」的线性数据结构；不要求连续存储，天然支持插入删除。
Why：动态集合的「最朴素」实现——比数组灵活（不需要预分配连续空间）；是后续树、散列等结构的基础。
How：
-
双链表示（图 10.3）：
\[\begin{array}{rl} & \textbf{LIST-SEARCH}(L, k) \\ 1 & x = L.\text{head} \\ 2 & \textbf{while } x \neq \text{NIL } \textbf{and } x.\text{key} \neq k \\ 3 & \quad x = x.\text{next} \\ 4 & \textbf{return } x \\ & \textbf{LIST-INSERT}(L, x) \\ 1 & x.\text{next} = L.\text{head} \\ 2 & \textbf{if } L.\text{head} \neq \text{NIL} \\ 3 & \quad L.\text{head}.\text{prev} = x \\ 4 & L.\text{head} = x \\ 5 & x.\text{prev} = \text{NIL} \\ & \textbf{LIST-DELETE}(L, x) \\ 1 & \textbf{if } x.\text{prev} \neq \text{NIL} \\ 2 & \quad x.\text{prev}.\text{next} = x.\text{next} \\ 3 & \textbf{else } L.\text{head} = x.\text{next} \\ 4 & \textbf{if } x.\text{next} \neq \text{NIL} \\ 5 & \quad x.\text{next}.\text{prev} = x.\text{prev} \end{array}\] -
操作复杂度：
-
LIST-SEARCH = \(\Theta(n)\)（最坏扫描到末尾）。
-
LIST-INSERT / LIST-DELETE（已有指针）= \(O(1)\)——这是链表优于数组的关键。
-
用关键字先 SEARCH 再 DELETE = \(\Theta(n)\)（因为 SEARCH）。
-
-
哨兵 / 哨位（Sentinel, §10.2）：
-
加一个 L:nil 节点代替 NIL 指针；所有节点 prev/next 默认指向 L:nil。
-
优势：消除头 / 尾边界条件，让 LIST-DELETE' 简化成 2 行（不需要「if prev != NIL」「if next != NIL」）。
-
-
链表变体对比：
变体 区别 适用 单链
仅 next 指针
节省空间、不需要反向遍历
双链
next + prev
可 O(1) 删除 + PREDECESSOR
循环
tail.next = head
简化「队」的实现
已排序
顺序 = 键序
可加速 SEARCH（线性 = 有序；可改造跳表 O(lg n)）
哨兵
头尾边界虚拟节点
简化代码、常数略小
When： . 频繁插入删除、不常按位访问 → 链表；否则用数组。 . 已排序 + 频繁查找 → 跳表 / BST 优于有序链表。 . 实现链表的链：树的子结构（第 12 章 BST）、散列的桶（第 11 章）、自由表（§10.3）。
Example：双链表 (1, 4, 9, 16) 表示为 { key: [9, 16, 4, 1], next: [2, 3, 4, NIL], prev: [NIL, 1, 2, 3], L.head = 1 }；LIST-INSERT(L, x) 在 x.key = 25 处插入后链表变 ⟨25, 1, 4, 9, 16⟩。
10.3 指针与对象的数组实现
What：在没有显式指针 / 对象类型的语言（如纯 Fortran 或某些教学语言）中，用「数组 + 下标」模拟指针与对象。
Why：很多语言（如 C、Java 有引用）天然支持指针；但在底层实现（操作系统内核、嵌入式）、教学（CLRS 的伪代码）和某些语言（如 JavaScript 早期无指针）中，需要数组实现。理解它对理解后续高级结构（堆、B 树）的内存布局很重要。
How：
-
多数组表示（图 10.5）：每个对象有 key、next、prev 三个字段，每个字段一个数组；下标 x 是「指向对象 x 的指针」。指针值是「整数下标」，NIL 用 0 或 -1。
-
单数组表示（图 10.6）：每个对象占据 A 的一段连续空间 A[j..k]；属性 = 偏移（key = offset 0, next = offset 1, prev = offset 2）；指向对象的指针 = j。允许异构对象（变长），但管理复杂。
-
自由表 (Free List)：已分配对象在用户链表中；未分配对象串成一个「自由链表」，头由全局变量 free 指向。
\[\begin{array}{rl} & \textbf{ALLOCATE-OBJECT}() \\ 1 & \textbf{if } \text{free} == \text{NIL} \\ 2 & \quad \textbf{error “out of space”} \\ 3 & \textbf{else } x = \text{free} \\ 4 & \quad \text{free} = x.\text{next} \\ 5 & \textbf{return } x \\ & \textbf{FREE-OBJECT}(x) \\ 1 & x.\text{next} = \text{free} \\ 2 & \text{free} = x \end{array}\]自由表操作 = 栈；ALLOCATE = POP, FREE = PUSH；复杂度 \(O(1)\)。
-
紧凑性练习 10.3-4：用「栈式存储」让链表尽量占用前 n 个位置——ALLOCATE 返回最低空闲位置；FREE 把空位入栈——访问局部性好（缓存友好）。
When： . 在受限环境实现动态集合 → 用数组 + 自由表。 . 实现堆（§6）+ 紧凑数组存储 → 章节 6 已用此技术。 . 实现带分配器的语言运行时 → 自由表是「slab allocator」的前身。
Example（多数组）：图 10.5 表示链表 (1, 4, 9, 16)：key = [7, 4, 1, 16, 9]，next = [3, 2, 5, NIL, 7]，prev = [NIL, 1, NIL, NIL, 2]（L = 1 指向 key=9 作为头）。
10.4 有根树的表示
What：树是层级结构，本节介绍三种指针表示：二叉树（left + right + parent）、有界分支（child[1..k]）、左孩子右兄弟（任意分支）。
Why：选择树的表示方式直接影响操作效率——二叉树适合 BST/堆、有界分支浪费存储、「左孩子右兄弟」紧凑且灵活（任意分支树仅需 O(n) 空间）。
How：
-
二叉树（图 10.9）：
-
每个节点：x.p（父）、x.left（左子）、x.right（右子）+ x.key。
-
T.root 指向根；空树 = T.root = NIL。
-
访问孩子 / 父亲 = \(O(1)\)。
-
-
有界分支树：若每个节点最多 k 个孩子，用 child[1..k] 数组代替 left/right。简单但当 k 大但实际孩子少时浪费空间。
-
左孩子右兄弟（Left-Child, Right-Sibling, 图 10.10）：
-
每个节点：x.p（父）、x.left-child（左起第一个孩子）、x.right-sibling（紧邻右兄弟）。
-
节省空间：n 节点占 O(n) 总指针数。
-
访问所有孩子 = 沿 right-sibling 链 O(c)（c = 孩子数）。
-
-
其他表示（§10.4 末）：
-
第 6 章堆：用「数组 + 上滤 / 下滤」表示完全二叉树——本质是「索引计算代替指针」。
-
第 21 章不相交集合森林：每个节点只有 parent 指针；向上走找根。
-
When： . 二叉树（章 12 BST、章 13 红黑树）→ left + right + parent。 . 任意分支树（章 21 不相交集合、章 19 斐波那契堆子结构）→ 左孩子右兄弟。 . 完全二叉树、堆 → 数组（最紧凑）。 . 仅需向上走（如 LCA、union-find）→ 仅 parent 指针。
Example（左孩子右兄弟）：一棵树根 A 有三个孩子 B/C/D，且 B 有两个子 E/F：表示 = {A: left=B, right=NIL, p=NIL}、{B: left=E, right=C, p=A}、{C: left=NIL, right=D, p=A}、{D: left=NIL, right=NIL, p=A}、{E: left=NIL, right=F, p=B}、{F: left=NIL, right=NIL, p=B}。访问 A 的所有孩子 = 沿 A.left = B → B.right = C → C.right = D → D.right = NIL，共 3 步 = O(3)。
三、关键图表
|
本章无独立编号图表
本章核心图（图 10.1-10.10）以「数组 + 下标 / 箭头」视觉形式展示栈、队列、链表、树等结构的物理布局。本笔记用伪代码 + 文字 + 表格描述；原书图见 CLRS 第 4 版第 233-247 页。 |
|
核心公式对照表
|
四、思维导图
mindmap
root((第 10 章 基本数据结构))
动态集合
操作接口
查询修改
栈队列
LIFO
FIFO
数组实现
循环wrap
链表
单链双链
循环
哨兵
O(1)插入
数组指针
多数组
单数组
自由表
紧凑存储
有根树
二叉
有界k
左子右兄
parent
总结
内存布局
操作接口
复杂度五、重点与易错点
-
栈的 STACK-EMPTY 必须先测 — 否则 POP 访问 S[0]（未定义）。
-
队列循环数组只存 n-1 个元素于 n 大小 — 留 1 个位置区分「满」（tail = head - 1）与「空」（tail = head）。
-
链表 LIST-DELETE 需要指针而非关键字 — 元素本身没有 L.head 之外的全局锚点；按关键字删必须先 SEARCH。
-
哨兵不是性能优化 — 简化代码、消除边界条件；常数小幅优化，不改变渐近复杂度（sentinels rarely reduce asymptotic time bounds）。
-
链表循环不漏 first 与 last — 双链表 head.prev = tail, tail.next = head（与 NIL 哨兵可结合：L:nil.next = head, L:nil.prev = tail）。
-
free list 是栈 — 后释放的先分配（LIFO）；这对缓存友好（刚释放的对象常在缓存中）。
-
free list 可服务多个链表 — 只要所有链表对象用同一属性做 next 指针（图 10.8）。
-
LEFT-CHILD, RIGHT-SIBLING 不需要 k 个孩子指针 — 而是用 sibling 链串接；空间 O(n) 总和。
-
LEFT-CHILD, RIGHT-SIBLING 访问父仍是 O(1) — 比纯链表多一个 parent；访问孩子 = O(c)，但总分支树遍历仍是 O(n)。
-
数组实现的「指针」是整数下标 — 通常 0 是 NIL（指针不可为 0 是约束）；某些实现用 -1。
-
紧凑链表的好处 — 在虚拟内存 / 分页系统中，密集存放降低 page fault；练习 10.3-4 用栈式分配实现。
-
「链表反转 O(n)」 — 练习 10.2-7 经典题；三指针迭代 vs 递归实现；三指针更省栈空间。
-
链表 vs 数组的选择：插入删除频繁 + 不按位访问 → 链表；按位访问 + 缓存敏感 → 数组。
-
二叉树 vs 一般树表示：当分支数有界时单独 child[1..k] 字段最简单；无界分支必用左孩子右兄弟。
-
「对象 + 指针」统一抽象 — 第 10.3 的多数组 / 单数组表示把「指针」抽象为「下标」+「属性映射」——这在所有后续章节（堆、B 树、图）中都用得上。
补充：与其他章节的衔接
-
第 6 章（堆）：堆就是「数组实现的完全二叉树」+「无显式指针」——本章数组指针技术的特例。
-
第 11 章（散列表）：散列表的「链接法」用链表做桶——本章链表用作子结构。
-
第 12 章（BST）/ 第 13 章（红黑树）：用 left + right + parent 表示树——本章三种指针表示的「二叉树」形式。
-
第 14 章（扩充数据结构）：在 BST / 红黑树节点上添加 size 等新字段——与本章「属性扩展」思想一脉相承。
-
第 19 章（斐波那契堆）/ 第 20 章（van Emde Boas 树）：用左孩子右兄弟 + 兄弟链变化维护结构。
-
第 21 章（不相交集合）：每个节点只有 parent 指针；本质是「向上走的树」。