数据结构

Ch1-3 · 线性结构

1. 绪论 · 数据结构与算法
2. 时间 / 空间复杂度
3. 顺序表 ADT + 代码
4. 单链表 + 头插尾插
5. 双链表 / 循环链表
6. 链表经典算法
7. 栈 + 表达式求值
8. 队列 + 循环队列
9. 双端队列 / 优先队列
10. 串与 KMP
11. nextval 优化

Ch4-6 · 树与图

1. 数组 / 稀疏矩阵
2. 树的存储
3. 二叉树性质详细
4. 遍历（递归 + 非递归）
5. 由序列还原二叉树
6. 线索二叉树
7. 哈夫曼树与编码
8. BST 插入删除
9. AVL 完整算例
10. 红黑树性质
11. B 树 / B+ 树

Ch6-8 · 图查排

1. 图的存储 + 遍历
2. 最短路（Dijkstra/Floyd）
3. 最小生成树（Prim/Kruskal）
4. 拓扑 + 关键路径
5. 查找 + 散列 + ASL
6. 排序大全 + 代码
7. 外部排序
8. 知识地图

渐进复杂度只关心增长形状，机器无关。

大 O 的直觉（升序）

• O(1) 哈希查询、栈顶
• O(log n) 折半 / BST 平均
• O(n) 顺序扫描
• O(n log n) 归并 / 快排 / 堆排
• O(n²) 冒泡 / 选择 / 插入
• O(2ⁿ) 子集枚举
• O(n!) 全排列

// 动态顺序表定义
#define InitSize 100
typedef struct {
  ElemType *data;
  int MaxSize, length;
} SeqList;

// 初始化
void InitList(SeqList &L) {
  L.data = (ElemType*)malloc(
            sizeof(ElemType)*InitSize);
  L.length = 0;
  L.MaxSize = InitSize;
}

// 扩容 (倍增策略)
void IncreaseSize(SeqList &L, int len) {
  ElemType *p = L.data;
  L.data = (ElemType*)malloc(
            sizeof(ElemType)*(L.MaxSize+len));
  for(int i=0;i<L.length;i++)
    L.data[i] = p[i];
  L.MaxSize += len;
  free(p);
}

// 第 i 位插入元素 e (1 ≤ i ≤ length+1)
bool ListInsert(SeqList &L, int i, ElemType e) {
  if(i<1 || i>L.length+1) return false;
  if(L.length >= L.MaxSize) return false;
  for(int j=L.length; j>=i; j--)
    L.data[j] = L.data[j-1];       // 后移
  L.data[i-1] = e;
  L.length++;
  return true;
}

// 删除第 i 位
bool ListDelete(SeqList &L, int i, ElemType &e) {
  if(i<1 || i>L.length) return false;
  e = L.data[i-1];
  for(int j=i; j<L.length; j++)
    L.data[j-1] = L.data[j];
  L.length--;
  return true;
}

// 按值查找 → 下标 (失败返回 0)
int LocateElem(SeqList L, ElemType e) {
  for(int i=0;i<L.length;i++)
    if(L.data[i] == e) return i+1;
  return 0;
}

// 单链表结点
typedef struct LNode {
  ElemType data;
  struct LNode *next;
} LNode, *LinkList;

// 头插法 (逆序建立)
LinkList List_HeadInsert(LinkList &L) {
  L = (LNode*)malloc(sizeof(LNode));
  L->next = NULL;
  ElemType x;
  scanf("%d", &x);
  while(x != 9999) {
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = x;
    s->next = L->next;     // 新节点指向第一个
    L->next = s;            // 头指向新节点
    scanf("%d", &x);
  }
  return L;
}

头插法：每次插在表头之后，时间 O(1)，结果逆序。

// 尾插法 (顺序建立)
LinkList List_TailInsert(LinkList &L) {
  L = (LNode*)malloc(sizeof(LNode));
  LNode *r = L;                // 尾指针
  ElemType x;
  scanf("%d", &x);
  while(x != 9999) {
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = x;
    r->next = s;
    r = s;
    scanf("%d", &x);
  }
  r->next = NULL;
  return L;
}

// 按位查找第 i 个 (i >= 0, 0 即头结点)
LNode* GetElem(LinkList L, int i) {
  int j = 0;
  LNode *p = L;
  while(p && j<i) {
    p = p->next; j++;
  }
  return p;          // 失败返回 NULL
}

// 后插：在 p 之后插入 s (O(1))
bool InsertNextNode(LNode *p, ElemType e) {
  LNode *s = (LNode*)malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

① 逆置（原地）

LNode *p = L->next, *q, *prev = NULL;
L->next = NULL;
while(p) {
  q = p->next;
  p->next = L->next;
  L->next = p;     // 头插法
  p = q;
}

② 找环（Floyd 龟兔）

slow = fast = L->next;
while(fast && fast->next) {
  slow = slow->next;
  fast = fast->next->next;
  if(slow == fast) break;
}
if(!fast) return null;
// 求环入口：从头与相遇点同速前进
LNode *p = L->next;
while(p != slow) {
  p = p->next; slow = slow->next;
}
return p;

③ 合并两个有序链表 (非递归)

LNode *p = L1->next, *q = L2->next;
LNode *r = L1;        // 复用 L1 头
while(p && q) {
  if(p->data <= q->data) {
    r->next = p; r = p; p = p->next;
  } else {
    r->next = q; r = q; q = q->next;
  }
}
r->next = p ? p : q;
free(L2);

④ 倒数第 k 个（双指针）

LNode *fast = L, *slow = L;
for(int i=0; i<k; i++) fast = fast->next;
while(fast) {
  fast = fast->next; slow = slow->next;
}
return slow->next;   // 即倒数第 k 个

⑤ 判断回文（栈 / 快慢指针 + 翻转）

快慢指针定位中点，反转后半段，再与前半段逐节点比较。O(n) 时间、O(1) 空间。

顺序栈 vs 链栈

栈的卡特兰数

n 个不同元素入栈，可能的出栈序列数：
C(2n,n)/(n+1)（卡特兰数 1,2,5,14,42…）。

中缀 → 后缀

用栈计算后缀

遇数字进栈；遇运算符弹两个数 (注意顺序: 后弹的在前)，运算结果再入栈。栈底剩一即结果。

循环队列三种判空满

// 牺牲一格法
bool EnQueue(Q &q, ElemType x) {
  if((q.rear+1)%n == q.front) return false;
  q.data[q.rear] = x;
  q.rear = (q.rear+1) % n;
  return true;
}
bool DeQueue(Q &q, ElemType &x) {
  if(q.rear == q.front) return false;
  x = q.data[q.front];
  q.front = (q.front+1) % n;
  return true;
}

链队列

需要 front + rear 两个指针；带头节点更方便（出空时不用特判）。
不会"满"，只可能 malloc 失败。

队列的应用

• CPU 调度：就绪队列、阻塞队列
• 缓冲：键盘缓冲、打印队列
• BFS：图 / 树的层序遍历
• 层次模拟：操作系统页面置换 FIFO

两栈实现队列

// 双栈队列
push:  入 stack_in
pop:   stack_out 空时，
       把 in 全部倒入 out；
       否则直接出 out 栈顶

双端队列 Deque

两端都可以入出。受限的两类：

• 输入受限：只在一端入，两端都可出
• 输出受限：两端都可入，只在一端出

问"给定输入 1,2,3,4，输出 4,1,3,2 是否可能"是典型题。逐步模拟即可。

优先队列 / 堆

每次取出"优先级最高 / 最低"的元素。底层常用二叉堆。

大根堆 / 小根堆

• 大根堆：父 ≥ 子；堆顶 = 最大值
• 小根堆：父 ≤ 子；堆顶 = 最小值
• 用顺序存储：i 的父 ⌊i/2⌋，左 2i，右 2i+1（下标从 1 开始）

建堆 O(n)

从最后一个非叶 ⌊n/2⌋ 开始，逐个向下调整（siftDown）。每次插入 / 删除堆顶为 O(log n)。

应用：Top-K、Dijkstra、合并 K 个有序链表、任务调度。

朴素匹配：每次失配，主串指针 i 回退到本次起点 + 1，模式串指针 j 回到 0，最坏 O(nm)。

KMP 关键洞察：失配时主串不回退，只把 j 跳到合适位置，利用已知"前缀 == 后缀"的部分。

next 数组定义

next[j] = P[0..j-1] 的"最长真前缀 = 真后缀"长度
特别：next[0] = -1 (惯例)

手算 next 表步骤

1. next[0] = -1, next[1] = 0
2. 设当前 next[j] = k
3. 若 P[k] == P[j]: next[j+1] = k + 1
4. 否则 k = next[k]，回退继续比较
5. 若 k 退到 -1，next[j+1] = 0

完整 next 推导示例

P = "ababaca"

KMP 主匹配代码

int KMP(char *S, char *P, int *next) {
  int i=0, j=0;
  while(i<strlen(S) && j<(int)strlen(P)) {
    if(j == -1 || S[i] == P[j]) {
      i++; j++;
    } else {
      j = next[j];      // 主串 i 不回退！
    }
  }
  if(j == strlen(P)) return i - j;
  return -1;
}

复杂度：构造 next O(m) + 匹配 O(n) = O(n+m)。

问题：若 next[j] = k 而 P[j] == P[k]，则 j 跳到 k 后必然又失配，浪费一次比较。

nextval 定义

if(P[j] != P[next[j]])
  nextval[j] = next[j];
else
  nextval[j] = nextval[next[j]];   // 继续向上跳

对比示例

P = "aaaab"

若失配于 j=3 (P[3]='a')，next 会让 j 跳到 2 又比 'a'，再到 1 比 'a'，再到 0 比 'a'，再到 -1。
nextval 直接跳到 -1。

行优先 vs 列优先

m×n 数组 A，行优先元素 a[i][j] 的地址为：

LOC(a[i][j]) = LOC(a[0][0]) + (i·n + j)·k
// k 为每个元素字节数

C 语言、Python NumPy 默认行优先；Fortran、MATLAB 列优先。

对称矩阵的压缩

n 阶对称矩阵 a[i][j] = a[j][i]，仅存上 / 下三角，n(n+1)/2 个元素。

下三角行优先：k = i(i+1)/2 + j (i ≥ j)

三角 / 对角矩阵

• 三角矩阵：仅存非零部分 + 一个常数
• 三对角：仅存主对角线 ± 1 共 3n-2 个元素
• k 计算公式根据存储方向略不同，考试时手画下脚标

稀疏矩阵

非零元素远少于总元素：用三元组 (i, j, value) 存储。

必背 7 条

1. 第 i 层最多 2^(i-1) 个结点
2. 深度 h 的二叉树最多 2^h - 1 个结点
3. n 个节点的完全二叉树深度 = ⌊log₂n⌋ + 1
4. n 个节点的二叉树有 n + 1 个空指针
5. 叶子数 n₀ = n₂ + 1（度为 2 的节点 + 1）
6. 具有 n 个节点的不同二叉树形态数 = C(2n,n)/(n+1)（卡特兰）
7. 完全二叉树中，n 个节点，叶子数 = ⌈n/2⌉，单分支至多 1 个

三种特殊

完全二叉树编号关系

节点 i (从 1 开始)：
· 父亲 = ⌊i/2⌋
· 左孩子 = 2i
· 右孩子 = 2i+1
· 所在层 = ⌊log₂i⌋ + 1

证明 n₀ = n₂ + 1

总边数 = 总节点 - 1 = n - 1；又 = 0·n₀ + 1·n₁ + 2·n₂。
整理：n₀ + n₁ + n₂ - 1 = n₁ + 2n₂ → n₀ = n₂ + 1。

递归三件套

void preOrder(TreeNode *p) {
  if(!p) return;
  visit(p);
  preOrder(p->left);
  preOrder(p->right);
}
// 中序：换 visit 位置到中间
// 后序：换 visit 位置到最后

前序非递归 (栈)

stack<TreeNode*> st;
st.push(root);
while(!st.empty()) {
  p = st.top(); st.pop();
  visit(p);
  if(p->right) st.push(p->right);
  if(p->left) st.push(p->left);  // 后压先出
}

后序非递归（标记法）

stack<TreeNode*> st;
TreeNode *p = root, *r = NULL;   // r 记上次访问
while(p || !st.empty()) {
  while(p) {
    st.push(p);
    p = p->left;
  }
  p = st.top();
  if(p->right && p->right != r) {
    p = p->right;
  } else {
    visit(p);
    r = p;
    st.pop();
    p = NULL;
  }
}

层序遍历 (队列)

queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
  p = q.front(); q.pop();
  visit(p);
  if(p->left)  q.push(p->left);
  if(p->right) q.push(p->right);
}

哪两个序列能确定？

• ✅ 前 + 中
• ✅ 后 + 中
• ✅ 层 + 中
• ❌ 前 + 后（一般不能）
• ❌ 前 + 层（一般不能）

为什么必须有"中序"？

前/后/层都只告诉你"根在哪儿"，但中序是唯一把根的左、右子树分开的序列。两者结合才能递归切分。

前 + 中 还原步骤

动机

n 个节点共有 n+1 个空指针。利用它们存放"中序"或"前/后序"下的前驱后继，就能不用栈做遍历。

结构

typedef struct ThreadNode {
  ElemType data;
  struct ThreadNode *left, *right;
  int ltag, rtag;   // 0=孩子, 1=线索
} ThreadNode;

中序线索化算法

ThreadNode *pre = NULL;

void InThread(ThreadNode *p) {
  if(!p) return;
  InThread(p->left);

  if(!p->left)  { p->left = pre;  p->ltag = 1; }
  if(pre && !pre->right) {
    pre->right = p; pre->rtag = 1;
  }
  pre = p;

  InThread(p->right);
}

中序线索树的遍历（无栈）

// 中序后继：
// rtag=1 → right 直接是后继
// rtag=0 → 后继是右子树最左节点

ThreadNode* Next(ThreadNode *p) {
  if(p->rtag == 1) return p->right;
  p = p->right;
  while(p->ltag == 0) p = p->left;
  return p;
}

// 完整遍历
p = first(root);
while(p) {
  visit(p);
  p = Next(p);
}

前序 / 后序线索化

前序线索：left 空指前驱、right 空指后继；前驱的查找需父指针或额外栈。
后序线索：找后继较复杂（如果是右子树最末则需父指针）。

构造步骤

1. 把所有权值看作 n 棵单节点树
2. 取根权最小的两棵，合为新树（左小右大），权 = 两者之和
3. 将新树放回集合
4. 重复直到只剩一棵

性质

• 共 n 个叶子的哈夫曼树有 2n - 1 个节点
• 无度为 1 的节点（每次合并一定产生度 2）
• WPL = Σ wᵢ × Lᵢ（叶子权 × 路径长度）

完整例

权值 {7, 5, 4, 2}

哈夫曼编码

从根向左 = 0，向右 = 1。例：A=7→"0"、B=5→"10"、C=2→"110"、D=4→"111"。
前缀码：任何编码不是另一个的前缀，可唯一解码。

插入

bool BST_Insert(BSTNode *&T, ElemType e) {
  if(!T) {
    T = (BSTNode*)malloc(sizeof(BSTNode));
    T->data = e;
    T->left = T->right = NULL;
    return true;
  }
  if(e == T->data) return false;
  if(e < T->data) return BST_Insert(T->left, e);
  return BST_Insert(T->right, e);
}

逐次插入 {45, 24, 53, 12, 28} 得到的 BST，中序为 12, 24, 28, 45, 53。顺序不同形态不同。

删除（最难的情况）

1. 叶节点：直接删除。
2. 只有一个子树：用唯一子树代替自己。
3. 有两个子树：用中序后继（右子树的最左节点）或中序前驱替换 data，然后删除那个后继 / 前驱节点（递归回到情况 1 或 2）。

平均 / 最坏

随机插入：树高 O(log n)，操作 O(log n)。
有序插入：退化为单链表，O(n)。
→ 引出 AVL / 红黑树。

平衡因子 BF

BF(node) = h(左子树) - h(右子树) ∈ {-1, 0, 1}。插入后某节点 BF 变 ±2 即失衡。

四种失衡 + 调整

⚠️ 总是从最低失衡节点开始调整。调整后该子树高度不变 → 不会向上传播。

构造例：插入序列 {5, 4, 2, 8, 6, 9}

5 条性质

1. 每个节点不是红就是黑
2. 根是黑
3. 每个叶（NIL）都是黑
4. 红节点的子节点必为黑（不存在连续红）
5. 从任意节点到其所有叶的简单路径上，黑节点数相同

高度结论

n 个内节点的红黑树，
高度 h ≤ 2·log₂(n + 1)
→ 查找 / 插入 / 删除 O(log n)

AVL vs 红黑树

408 出题边界

大纲只要求"理解概念与性质"，不要求手画旋转或插入删除细节。看到红黑题，记住"性质 + 高度结论"即可。

m 阶 B 树定义

• 每个节点至多 m 个孩子（m-1 个关键字）
• 非根 至少 ⌈m/2⌉ 个孩子（⌈m/2⌉-1 个关键字）
• 根至少 2 个孩子（除非为叶）
• 所有叶在同一层（绝对平衡）
• 关键字升序排列；孩子 = 关键字 + 1

插入分裂

插入总是在叶层。若关键字数 = m，从中间分裂：左半留下、右半新建节点、中间关键字上提到父亲。父亲再满则递归上传。

删除

非叶节点关键字 → 用中序后继顶上（化为叶子删除）。叶节点关键字数不足 → 先向兄弟借（旋转），不能借则与兄弟合并，可能引起父亲递归不足。

B+ 树（数据库索引）

• 所有数据都在叶，内部节点只是索引
• 叶节点按横向链表连接 → 区间查询 O(log + k)
• 关键字数 = 孩子数（与 B 树差 1）
• 每次查找都要走到叶
• 对应应用：MySQL InnoDB、文件系统目录索引

B vs B+ 总览

邻接矩阵

typedef struct {
  VertexType vex[MaxN];
  EdgeType edge[MaxN][MaxN];
  int vexnum, arcnum;
} MGraph;

空间 O(V²)；判 (i,j) 有边 O(1)；列邻接 O(V)。
稠密图首选；不便处理稀疏。

邻接表

typedef struct ArcNode {
  int adjvex;
  struct ArcNode *next;
} ArcNode;
typedef struct VNode {
  VertexType data;
  ArcNode *first;
} VNode, AdjList[MaxN];

空间 O(V+E)；列邻接 O(度)；稀疏图首选。
有向图：出弧链 / 逆邻接表存入弧。

DFS（栈 / 递归）

bool visited[MaxN] = {false};
void DFS(Graph G, int v) {
  visit(v);
  visited[v] = true;
  for(w = FirstNeighbor(G, v); w >= 0;
       w = NextNeighbor(G, v, w))
    if(!visited[w]) DFS(G, w);
}
// 处理非连通图：
for(int i=0; i<G.vexnum; i++)
  if(!visited[i]) DFS(G, i);

BFS（队列）

void BFS(Graph G, int v) {
  visit(v); visited[v] = true;
  Q.push(v);
  while(!Q.empty()) {
    v = Q.pop();
    for(w = FirstNeighbor(G, v); w >= 0;
         w = NextNeighbor(G, v, w))
      if(!visited[w]) {
        visit(w); visited[w] = true;
        Q.push(w);
      }
  }
}

邻接表：O(V+E)；邻接矩阵：O(V²)。
BFS 在无权图中即最短路径算法（层数即距离）。

Dijkstra · 单源 · 非负权

1. 初始 dist[src]=0, 其他=∞，S = {src}
2. 取 dist 最小的未确定点 u 加入 S
3. 松弛 u 的所有邻居 v：if dist[v] > dist[u]+w(u,v) → 更新
4. 重复直到 S 覆盖所有点

O(V²) 朴素；O((V+E)log V) 二叉堆
O(V log V + E) 斐波那契堆

手算表格

Floyd · 多源

int D[V][V];     // 初始为权值
for k = 0..V-1:
  for i = 0..V-1:
    for j = 0..V-1:
      if(D[i][k]+D[k][j] < D[i][j])
        D[i][j] = D[i][k]+D[k][j];
        path[i][j] = k;

本质：动态规划。D⁽ᵏ⁾[i][j] = 只经过前 k 个顶点的最短路径。
O(V³) 时间、O(V²) 空间。能处理负权但不能有负环。

何时选谁？

• 只问一对点 / 单源 → Dijkstra（更快）
• 问所有对 → Floyd（写起来简单）
• 有负权 → Floyd 或 Bellman-Ford

Prim · 加点法

1. U = {任一起点 v₀}, V-U = 其余点
2. 找 (u∈U, v∈V-U) 中权最小的边 (u,v)
3. 把 v 加入 U，把 (u,v) 加入 MST
4. 重复 V-1 次

O(V²) 朴素 / 适合稠密图
O(E log V) 用堆

Kruskal · 加边法

1. 所有边按权升序排序
2. 依次取权最小、不构成环的边
3. 用并查集判环（合并两端点的代表元）
4. 选满 V-1 条边

O(E log E) 排序主导 / 适合稀疏图

并查集 Union-Find

int parent[N];
void init() {
  for(int i=0;i<N;i++) parent[i] = i;
}
int find(int x) {
  if(parent[x] == x) return x;
  return parent[x] = find(parent[x]);  // 路径压缩
}
void unite(int a, int b) {
  parent[find(a)] = find(b);
}

MST 的两条性质

• 切性质：横跨切的最小边一定在某棵 MST 中
• 环性质：任意环中权最大的边不在某棵 MST 中
• 所有边权互不相同时 MST 唯一

AOV 拓扑排序

1. 统计每个顶点的入度
2. 把入度为 0 的入队
3. 反复取队首 → 输出 → 把它的所有邻居入度 -1，新出现的 0 入队
4. 若输出节点数 < V，存在环

O(V+E)。拓扑序不唯一。

逆拓扑序（DFS）

DFS 中按"退栈"次序输出即得逆拓扑；其反过来即拓扑序。

AOE 关键路径 5 步

1. 正向遍历拓扑序，求每个事件最早发生 ve(v)
   ve(v₀)=0，ve(v)=max{ve(u) + w(u,v)}
2. 逆向遍历拓扑序，求每个事件最迟发生 vl(v)
   vl(终)=ve(终)，vl(u)=min{vl(v) - w(u,v)}
3. 每个活动 a=(u,v)：最早开始 e(a)=ve(u)，最迟开始 l(a)=vl(v)-w(u,v)
4. 机动时间 d(a) = l(a) - e(a)
5. d(a) = 0 的活动构成关键路径

折半判定树（11 个元素例）

分块查找

块内无序、块间有序。用索引表（每块的最大值 + 起始下标）。
ASL = L_I + L_S，L_I=⌈log₂(b+1)⌉ 用折半找块，L_S=(s+1)/2 块内顺序。

散列函数

• 直接定址：H(k) = a·k + b
• 除留余数：H(k) = k mod p（p 取不大于表长的质数）
• 数字分析、平方取中、折叠

冲突处理

• 开放定址
  · 线性探测 H_i = (H+i) mod m → 易堆积
  · 平方探测 H_i = (H + ±i²) mod m
  · 双散列 H_i = (H + i·H₂(k)) mod m
• 拉链法：每槽位是链表，删除安全

ASL 计算示例（除留 + 线性探测）

快排核心代码

int partition(int *a, int l, int r) {
  int pivot = a[l];
  while(l < r) {
    while(l < r && a[r] >= pivot) r--;
    a[l] = a[r];
    while(l < r && a[l] <= pivot) l++;
    a[r] = a[l];
  }
  a[l] = pivot;
  return l;
}
void quickSort(int *a, int l, int r) {
  if(l >= r) return;
  int p = partition(a, l, r);
  quickSort(a, l, p-1);
  quickSort(a, p+1, r);
}

记忆口诀

• 稳定五连：插入 / 冒泡 / 归并 / 基数 / 计数
• 原地 O(1) 空间：插入 / 希尔 / 冒泡 / 选择 / 堆
• 无关初始序：选择 / 归并 / 基数 / 堆
• 最坏退化：快速 O(n²)；其他多为最坏 = 平均

外部排序

归并段 + k 路败者树。读取磁盘块 → 内排序 → 归并写回。性能瓶颈：IO 次数。优化：增大归并段长度、增加归并路数。