第2章：信息结构（Information Structures）
一、导读
1.1 本章学习目标
第2章是 TAOCP 第一卷中最长也最核心的一章，Knuth 在此系统地讲解了基本数据结构：线性列表、栈、队列、树和链表。不同于现代教材直接给出高级语言实现，Knuth 从 MIX 汇编层面展示这些数据结构的内存布局和操作方法。
本章核心学习目标：
- 掌握线性列表的多种表示方法：连续存储（数组）和链接存储（链表）
- 理解栈和队列的抽象特性：LIFO 和 FIFO 的数学性质
- 掌握树的递归定义和遍历方法：前序、中序、后序遍历
- 理解链表操作的底层实现：插入、删除、合并的 MIX 汇编代码
- 学会分析数据结构操作的时间复杂度
1.2 为什么本章如此重要
数据结构是算法的基础。Knuth 在本章中不仅介绍了数据结构"是什么"，更深入分析了"为什么"——为什么选择链表而非数组？为什么树的遍历有这三种顺序？每种选择的代价和收益是什么？
1.3 核心问题引导
数组和链表在插入/删除/访问操作上的时间复杂度差异的根本原因是什么？
如何用数组模拟链表？这种表示方法有什么优势？
树的三种遍历顺序分别适合什么应用场景？
双向链表相比单向链表有什么优势和代价？
二、核心概念详解
2.1 线性列表
2.1.1 连续存储（数组）
数组的内存布局:
地址: 1000 1001 1002 1003 1004
内容: [a₀] [a₁] [a₂] [a₃] [a₄]
访问 a[i]: address = base + i × word_size
时间复杂度: O(1)
插入 a[k] 之前:
1. 将 a[k], a[k+1], ..., a[n-1] 向后移动一位
2. a[k] = new_element
时间复杂度: O(n-k) = O(n)
删除 a[k]:
1. 将 a[k+1], ..., a[n-1] 向前移动一位
时间复杂度: O(n-k) = O(n)2.1.2 链接存储（链表）
单向链表:
┌────┬────┐ ┌────┬────┐ ┌────┬────┐
│INFO│LINK│──→│INFO│LINK│──→│INFO│LINK│──→ Λ (空)
└────┴────┘ └────┴────┘ └────┴────┘
node1 node2 node3
每个节点: INFO 字段（数据）+ LINK 字段（指向下一节点的地址）
插入到 node1 之后:
1. P ← AVAIL (从可用空间分配新节点)
2. INFO(P) ← new_element
3. LINK(P) ← LINK(node1)
4. LINK(node1) ← P
时间复杂度: O(1) (已知插入位置)
删除 node1 之后的节点:
1. P ← LINK(node1)
2. LINK(node1) ← LINK(P)
3. AVAIL ← P (回收到可用空间)
时间复杂度: O(1)
查找第 k 个元素:
从头部开始遍历 k 步
时间复杂度: O(k)2.2 栈和队列
2.2.1 栈（Stack）
栈: LIFO (Last In, First Out)
操作:
PUSH(S, x): 将 x 压入栈 S 的顶部
POP(S): 删除并返回栈顶元素
TOP(S): 返回栈顶元素（不删除）
数组实现:
TOP 指针指向栈顶
PUSH: S[++TOP] = x
POP: return S[TOP--]
应用:
- 函数调用栈
- 表达式求值（中缀转后缀）
- 括号匹配
- 深度优先搜索2.2.2 队列（Queue）
队列: FIFO (First In, First Out)
操作:
ENQUEUE(Q, x): 将 x 加入队尾
DEQUEUE(Q): 删除并返回队首元素
循环数组实现:
FRONT 和 REAR 指针
ENQUEUE: Q[REAR] = x; REAR = (REAR + 1) mod M
DEQUEUE: x = Q[FRONT]; FRONT = (FRONT + 1) mod M
应用:
- 广度优先搜索
- 任务调度
- 缓冲区2.3 树
2.3.1 树的定义
树（Tree）的递归定义:
- 空集是树
- 如果 T₁, T₂, ..., Tₖ 是互不相交的树，则
T = {root} ∪ T₁ ∪ T₂ ∪ ... ∪ Tₖ 也是树
root 称为根，T₁, ..., Tₖ 称为子树
术语:
- 根（Root）: 没有父节点的节点
- 叶（Leaf）: 没有子节点的节点
- 度（Degree）: 子节点的数量
- 深度（Depth）: 从根到该节点的路径长度
- 高度（Height）: 从该节点到最深叶的路径长度
- 有序树: 子节点有顺序（长子、次子...）
- 二叉树: 每个节点最多有两个子节点（左、右）2.3.2 树的遍历
前序遍历（Preorder）: 根 → 左子树 → 右子树
中序遍历（Inorder）: 左子树 → 根 → 右子树
后序遍历（Postorder）: 左子树 → 右子树 → 根
示例树:
A
/ \
B C
/ \
D E
前序: A B D E C
中序: D B E A C
后序: D E B C A
应用:
- 前序: 复制树、序列化
- 中序: 二叉搜索树的有序遍历
- 后序: 删除树、表达式树求值2.4 树的存储表示
1. 子节点链表表示（最通用）:
每个节点: INFO, FIRST_CHILD, NEXT_SIBLING
A → B → C
↓ ↓
D → E
2. 左右子女表示（二叉树）:
每个节点: INFO, LEFT, RIGHT
A: LEFT=B, RIGHT=C
B: LEFT=D, RIGHT=E
3. 数组表示（完全二叉树）:
节点 i 的左子女: 2i
节点 i 的右子女: 2i+1
节点 i 的父节点: ⌊i/2⌋三、实战案例
3.1 案例一：MIX 实现链表插入
算法: 在有序链表中插入一个元素
输入: 链表头指针 HEAD，待插入值 X
输出: 插入后的链表
MIX 实现:
ENTA 0
STX INFO_NEW 新节点的 INFO = X
SEARCH LDA HEAD P ← HEAD
JAZ INSERT_FIRST 如果链表为空，插入到头部
LOOP LD1 0,1(0:2) 取 P 的 LINK
J1Z INSERT_END 如果 P 是最后一个节点
CMPA 0,1(3:5) 比较 X 和 INFO(P)
JG INSERT_HERE 如果 X > INFO(P)，在 P 之后插入
LD1 0,1(0:2) P ← LINK(P)
JMP LOOP
INSERT_HERE:
ENTA 0
ST1 LINK_NEW LINK(NEW) ← LINK(P)
STX 0,1(0:2) LINK(P) ← NEW (需要调整)
...3.2 案例二：二叉树遍历的 MIX 实现
前序遍历的 MIX 实现（递归）:
PREORDER STJ RET_ADDR 保存返回地址
LDA 0,1(3:5) 访问节点 INFO
... 处理节点
LD1 0,1(0:2) P ← LEFT
J1Z NO_LEFT
JSJ PREORDER 递归遍历左子树
NO_LEFT LD1 RIGHT_PTR P ← RIGHT
J1Z NO_RIGHT
JSJ PREORDER 递归遍历右子树
NO_RIGHT LDJ RET_ADDR
JMP 0,4 返回四、本章小结
线性列表有两种基本表示：连续存储（数组，O(1) 随机访问）和链接存储（链表，O(1) 插入/删除）
栈（LIFO）和队列（FIFO）是两种受限的线性结构，各自有广泛的应用
树是递归定义的非线性结构，前序/中序/后序遍历是基本操作
存储表示的选择取决于具体操作的需求——频繁随机访问选数组，频繁插入删除选链表
五、思考与练习
思考题
如何用两个栈实现一个队列？如何用一个队列实现一个栈？
给定一棵二叉树的前序遍历和中序遍历序列，能否唯一确定这棵树？如何构造？
循环链表相比普通链表有什么优势？
编程练习
用 MIX 汇编实现双向链表的插入和删除操作。
实现二叉树的层序遍历（使用队列）。
实现用数组表示的完全二叉树，支持插入和删除（堆操作）。