绪论:三要素与 ADT
把数据想成一座图书馆:书的分类体系(文学→小说→科幻)是逻辑结构;书在书架上是连续摆放还是散放加索引卡,是存储结构;借书/还书/查书的规则是运算。ADT 就是贴在门口的「服务承诺」——只告诉你能办什么业务,不告诉你书怎么摆。类比的边界:图书馆换摆法不影响借书规则(接口不变),但找书速度会变——程序里也一样,换存储结构不改接口,却直接改变运算的时间复杂度。
1.1 逻辑结构:元素之间的「关系图谱」
按元素间关系分四大类,与计算机怎么存完全无关:
1.2 存储结构:同一关系,不同摆法
| 存储结构 | 思路 | 优点 | 代价 |
|---|---|---|---|
| 顺序存储 | 逻辑相邻 → 物理相邻(数组) | 随机存取 O(1),无额外指针开销 | 插删挪动多,容量要预估/扩容 |
| 链式存储 | 指针记录后继关系(链表) | 插删改指针即可,容量灵活 | 只能顺序访问,指针占空间 |
| 索引存储 | 另建索引表:关键字 → 地址 | 检索快,适合大数据 | 索引表本身占空间、要维护 |
| 散列存储 | 由关键字直接算出地址(哈希) | 增删查都接近 O(1) | 有冲突,不支持范围/顺序查询 |
1.3 抽象数据类型(ADT):只承诺,不泄底
ADT = 数据对象 + 数据关系 + 基本运算的定义,与实现无关。调用方只看接口,实现可以从数组换成链表而调用代码一行不改——这就是「封装」的思想源头。
// ADT List:只承诺"能做什么",不规定"怎么实现"
struct List; // 数据对象:同类型的 n 个元素
List* create(); // 初始化:造一个空表
void destroy(List* L); // 销毁:归还全部资源
int length(const List* L); // 求表长
ElemType get(const List* L, int i); // 按位取:第 i 个元素
int locate(const List* L, ElemType x); // 按值查:返回位置
void insert(List* L, int i, ElemType x);// 在第 i 个位置插入
void remove(List* L, int i); // 删除第 i 个元素
// 同一份 ADT:数组实现 get 是 O(1),链表实现是 O(n)
// 接口不变,性能特征却不同 —— 选型时必须知道底层是谁get(i) 是 O(1),整道题复杂度全算错(考试/面试重灾区)。正确姿势:先分清题目说的是逻辑结构还是存储结构——线性表是逻辑概念,顺序表(数组)和链表都是它的实现。1.4 随堂自测
复杂度分析:大 O 与摊还
估通勤时间:你说「上班大约 40 分钟」,不会精确到「今天红灯多等 90 秒」。路程翻倍 → 时间大约翻倍,这是量级(O(n));红灯、天气是系数和低阶项,估量级时忽略。类比的边界:路程只有 500 米时,等一个红灯反而占大头——n 很小时系数不可忽略,所以小数组上插入排序常常跑赢快速排序。
2.1 增长量级:一张图看懂谁先爆炸
| 复杂度 | 名称 | 典型例子 | n = 10⁶ 时的体感 |
|---|---|---|---|
O(1) | 常数 | 数组下标访问、哈希查找(理想) | 瞬间 |
O(log n) | 对数 | 二分查找、平衡树查找 | 约 20 步,瞬间 |
O(n) | 线性 | 遍历、顺序查找 | 毫秒级 |
O(n log n) | 线性对数 | 快排(平均)、归并、堆排 | 几十毫秒~秒级 |
O(n²) | 平方 | 冒泡、插入、选择排序 | 小时级,基本不可用 |
O(2ⁿ) / O(n!) | 指数 / 阶乘 | 朴素递归斐波那契 / 全排列枚举 | n≈40 就算到宇宙尽头 |
2.2 数出来的复杂度:看循环变量怎么变
for (int i = 0; i < n; ++i) // 执行 n 次
s += a[i]; // O(n):单层线性扫描
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) // n × n 次
s += a[i] * a[j]; // O(n²):两层独立循环,乘法原理
for (int i = 1; i < n; i *= 2) // i = 1,2,4,8,... 共 log₂n 次
s += i; // O(log n):循环变量成倍增长
for (int i = 0; i < n; ++i)
for (int j = 1; j < n; j *= 2) // 外层 n × 内层 log n
s += j; // O(n log n):不是 O(n²)!j *= 2 增长,只跑 log n 次;按 j < i 增长则是 1+2+…+n = O(n²)。2.3 递归与空间复杂度
递归的时间 = 递归结点总数 × 每层非递归工作量;空间看递归深度(每层一个栈帧)。常用主定理速查:T(n)=2T(n/2)+O(n) → O(n log n)(归并);T(n)=2T(n/2)+O(1) → O(n)(遍历二叉树);T(n)=T(n/2)+O(1) → O(log n)(二分)。
2.4 摊还分析:偶尔很贵 ≠ 每次很贵
void push_back(int x) {
if (sz == cap) { // 满了:申请 2 倍新空间
int* p = new int[cap * 2];
for (int i = 0; i < sz; ++i) // 搬家:这一次是 O(n)
p[i] = data[i];
delete[] data; data = p; cap *= 2;
}
data[sz++] = x; // 绝大多数时候只走这一步 O(1)
}
// n 次尾插的搬家总量 = 1+2+4+...+n < 2n(等比级数)
// 总代价 O(n) → 摊到每次 = 摊还 O(1),尽管单次最坏 O(n)2.5 随堂自测
for (int i = 1; i <= n; i *= 2) s++; 的时间复杂度是?顺序表与链表
顺序表是编号停车场:报编号 i 直接算出车位位置(随机存取);想在中间插一辆车,后面整排车都得挪(O(n))。链表是寻宝线索链:每张线索写着下一张的藏匿点,中间加一张只需改两张线索的指向;但找第 5 张必须从头顺藤摸瓜。类比的边界:停车场可以扩建,但扩建要整体搬家(扩容拷贝);线索随便藏(不要求连续内存),代价是每张线索多花纸写地址(指针空间开销)。
3.1 顺序表:插入删除的代价是「挪动」
// 在第 i 个位置(1-based)插入 x:第 i 个起全部右移
bool insert(int a[], int* n, int cap, int i, int x) {
if (*n == cap || i < 1 || i > *n + 1) return false; // 满/非法
for (int j = *n; j >= i; --j) // 从后往前挪,防止覆盖
a[j] = a[j - 1];
a[i - 1] = x; // 数组下标 0-based
++(*n);
return true; // 插入平均挪 n/2 个,删除平均挪 (n-1)/2 → O(n)
}动态数组(如 vector)在顺序表之上加了「满则翻倍扩容」,把尾插做成摊还 O(1)(第 2 章已推导)。下面亲手点一点:
3.2 单链表:改指针的艺术
typedef struct Node {
int val;
struct Node* next; // 指针域:存后继的地址
} Node;
// 头插法:新结点总当第一个数据结点 → 建出的链与输入逆序
Node* build(int a[], int n) {
Node* head = new Node{0, nullptr}; // 头结点:不存数据
for (int i = 0; i < n; ++i) {
Node* s = new Node{a[i], head->next}; // ① 新人先接旧后继
head->next = s; // ② 前驱再接新人
}
return head; // 空表判断统一为 head->next == nullptr
}p = p->next; free(p);(释放的是新 p,且旧结点泄漏)或插入时先 p->next = s 再给 s->next 赋值 → 原后继整段丢失(内存泄漏 + 数据静默丢失)。正确姿势:删除前先用临时指针存住目标;一切改链操作遵循「先接新、后断旧」。3.3 链表家族与选型
| 形态 | 结构特点 | 解决什么问题 |
|---|---|---|
| 单链表 | 一个 next 指向后继 | 最基本的动态线性表 |
| 双链表 | prior + next 两个指针 | O(1) 找前驱,删除自身不用从头找 |
| 循环单/双链表 | 尾结点指回头部(成环) | 从任一结点出发可达全表;轮转调度 |
| 静态链表 | 数组存结点,next 是「下标」 | 无指针语言/定长内存池场景 |
3.4 随堂自测
栈与队列
栈是食堂的一摞盘子:最后摞上去的最先被拿走(LIFO);队列是奶茶店排队:先来先点单(FIFO)。循环队列像圆桌转盘上的座位:编号转一圈又回到 0,队尾追着队头跑。类比的边界:现实中你能从盘子摞中间抽一个、排队的人会插队——程序里的普通栈/队列严禁这些操作,正是「受限」才让行为可预测、实现能做到 O(1)。
4.1 两种「受限」的方向
栈的经典应用:括号匹配、表达式求值(中缀转后缀)、递归调用栈、进制转换;队列的经典应用:CPU 调度、消息缓冲、BFS、打印机任务。双端队列(deque)两端都可进出,是栈与队列的超集。
bool match(const string& s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[') st.push(c); // 左括号:压栈等待
else if (c == ')' || c == ']') {
if (st.empty()) return false; // 右括号多了
char t = st.top(); st.pop(); // 最近的左括号先配对
if (c == ')' && t != '(') return false;
if (c == ']' && t != '[') return false;
}
}
return st.empty(); // 栈空 = 全部配对;非空 = 左括号多了
} // "([)]" 会在配对时失败 —— 嵌套必须最近优先,正是 LIFO4.2 循环队列:取模把数组弯成环
#define M 8 // 容量 8,最多存 7 个(牺牲一格)
typedef struct {
int data[M];
int front, rear; // front→队头元素;rear→队尾下一个空位
} SqQueue;
void init(SqQueue* q) { q->front = q->rear = 0; }
bool enQueue(SqQueue* q, int x) {
if ((q->rear + 1) % M == q->front) return false; // 队满
q->data[q->rear] = x;
q->rear = (q->rear + 1) % M; // 回绕:7 → 0
return true;
}
bool deQueue(SqQueue* q, int* x) {
if (q->front == q->rear) return false; // 队空
*x = q->data[q->front];
q->front = (q->front + 1) % M;
return true;
}front == rear,无法区分(静默逻辑错误)→ 三种解法:牺牲一个存储格(最常用)、增设 size 计数、增设 tag 标志。4.3 随堂自测
串与 KMP 模式匹配
用花边模板「ABAB C」沿着布条印花:印到第 5 个字符发现对不上。笨办法是把模板挪回起点后一格、从头核对;聪明办法是发现已印好的「ABAB」尾部 AB 和模板开头 AB 一模一样——直接把模板滑过去对齐这段重叠,前面核对过的绝不重看。KMP 的 next/π 数组就是提前写好的「重叠说明书」。类比的边界:这招成立的前提是模板固定、值得预处理;如果每印一次就换一个模板,预处理本身也要算进成本。
5.1 串与暴力匹配
串是元素限定为字符的线性表;子串定位 Index(T, P) 是核心运算。存储可用定长数组、堆分配或块链。BF(Brute-Force):从主串每个起点逐字符比对,失配则主串指针回退到下一起点,最坏 O(n·m)(如 T="aaaa…ab",P="aaab")。
5.2 π 数组:模式串的自我认识
π[i] = 子串 P[0..i] 的「最长相等真前缀与真后缀」的长度(真 = 不含自身)。它回答:失配时,已经匹配上的这段里,有多少可以「废物利用」。
5.3 失配时怎么滑:主串永不回头
vector<int> buildPi(const string& p) { // O(m)
int m = p.size(); vector<int> pi(m, 0);
for (int i = 1, j = 0; i < m; ++i) {
while (j > 0 && p[i] != p[j]) j = pi[j - 1]; // 失配沿 π 回退
if (p[i] == p[j]) ++j; // 前后缀又能延长一格
pi[i] = j;
}
return pi;
}
int kmp(const string& t, const string& p) { // O(n)
auto pi = buildPi(p);
for (int i = 0, j = 0; i < (int)t.size(); ++i) {
while (j > 0 && t[i] != p[j]) j = pi[j - 1]; // 只回退 j
if (t[i] == p[j]) ++j;
if (j == (int)p.size()) return i - j + 1; // 命中起点
}
return -1; // i 全程不回头 → 总比较 O(n+m)
}next[1]=0, next[2]=1,其值 = 最长相等前后缀长度+1;竞赛/工程(0-based)的 π 就是长度本身。混用会整体错一位:轻则漏匹配,重则 j 回退到错误位置死循环。正确姿势:动笔前先钉死一套约定;换算关系 next[j] = π[j-1] + 1。另外求「所有出现位置」时,命中后要 j = π[j-1] 继续,否则漏掉重叠匹配。5.4 随堂自测
数组、压缩存储与广义表
公寓房号就是二维→一维映射:「M 层 N 号」换算成全局编号 = (M−1)×每层户数 + N,一层一层数过去就是行优先。对称矩阵压缩像「夫妻共用一个储物柜」——a[i][j] 和 a[j][i] 值相同,存一份就够。广义表是俄罗斯套娃:盒子里既可以放小球(原子),也可以放更小的盒子(子表)。类比的边界:真实房号会跳 4、13 层(不规则),而数组映射必须严格规则——所以只有对称/三角/带状这类规律矩阵才能用公式压缩,零散分布的稀疏矩阵只能老实登记「哪行哪列有啥」。
6.1 行优先:二维是怎么摊平的
6.2 对称矩阵:只存下三角
| 特殊矩阵(n 阶) | 压缩方案 | 存储量 |
|---|---|---|
| 对称矩阵 | 下三角(含对角线)按行存 | n(n+1)/2 |
| 三角矩阵 | 有效三角 + 常数区 1 格 | n(n+1)/2 + 1 |
| 三对角(带状) | 三条对角线按行交错存 | 3n − 2 |
| 稀疏矩阵(t 个非零) | 三元组 (行,列,值) / 十字链表 | 3t(另存行列数) |
6.3 稀疏矩阵:登记制代替铺满制
typedef struct { int i, j, v; } Triple; // 行、列、值
typedef struct {
Triple data[MAX]; // 非零元,按「行优先」排好序
int mu, nu, tu; // 总行数、总列数、非零元个数
} TSMatrix;
// 普通转置:对每一列 col,扫全部三元组找 j==col 的,交换 i,j
// → O(nu × tu),列多时很慢
// 快速转置:先统计每列个数 → 前缀和算出每列在新表中的起始位
// 再扫一遍直接对号入座 → O(nu + tu)
// 十字链表:每个非零元同时挂在「行链」和「列链」上,
// 适合非零元个数频繁变化的场景(增删不挪动)6.4 广义表:套娃式线性表
广义表 LS = (a₁, a₂, …, aₙ),元素可以是原子或子表。两个基本运算:GetHead 取第一个元素(原子或子表都可能);GetTail 取「除头以外其余元素组成的表」——永远是表。深度 = 括号最大嵌套层数。例:LS = (a, (b, c), d),深度 2。
6.5 随堂自测
二叉树与遍历
把二叉树想成「每人最多两名直属下级」的组织架构,遍历就是巡视顺序:先序 = 先见领导再下基层(根左右);中序 = 左部门→领导→右部门(左根右);后序 = 基层全见完才见领导(左右根)——适合「先汇总下属再处理自己」(算目录大小、释放内存);层序 = 一层一层扫楼。类比的边界:真实组织一人可带 N 个下级(那是普通树),二叉树硬性限 2,而且只有一个下级时也要说明是左是右——左右子树交换后就是另一棵二叉树。
7.1 必背性质与两种特殊形态
- 第 i 层最多 2^(i−1) 个结点;深度 h 的树最多 2^h − 1 个结点。
- n₀ = n₂ + 1:叶子数 = 度为 2 的结点数 + 1(由「边数 = 结点数 − 1」推出)。
- 满二叉树:每层都塞满;完全二叉树:只允许最后一层缺右侧若干——编号与满树前 n 个一一对应。
- n 个结点的完全二叉树深度 = ⌊log₂n⌋ + 1;结点 i(0-based)的孩子是 2i+1、2i+2,父亲是 ⌊(i−1)/2⌋。
7.2 遍历代码:一份递归 + 一个队列
void inorder(TreeNode* t) { // 中序:左 → 根 → 右
if (!t) return;
inorder(t->left);
visit(t); // 挪到最前=先序,最后=后序
inorder(t->right);
}
void levelOrder(TreeNode* root) { // 层序:队列驱动,非递归
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
auto t = q.front(); q.pop();
visit(t); // 出队即访问
if (t->left) q.push(t->left); // 下一层排队
if (t->right) q.push(t->right);
}
} // 两者都是 O(n);递归空间 O(树高),层序空间 O(最宽一层)7.3 重构、线索与森林
重构二叉树:先序/后序/层序提供「谁是根」,中序提供「左右子树的分界」——所以 先序+中序、后序+中序、层序+中序都能唯一重构;先序+后序不行(单孩子分不清左右)。
7.4 随堂自测
二叉排序树与 AVL 树
BST 查找就是猜数字游戏:「大了往左、小了往右」,每问一次淘汰一半候选。可如果插入的是有序序列 1,2,3,4,5,树长成一条右斜链——相当于每次只猜「大 1」,一次只淘汰一个。AVL 是自动配平的书架:哪边沉了就做一次局部「旋转重排」,始终两边大致等高。类比的边界:旋转本身只是 O(1) 改几个指针,但每次插入删除都可能触发——这正是后来红黑树用「宽松平衡」换「更少旋转」的动机。
8.1 BST:查找与插入
TreeNode* search(TreeNode* t, int x) {
if (!t || t->val == x) return t; // 空或命中
return x < t->val ? search(t->left, x) // 小 → 左半区
: search(t->right, x); // 大 → 右半区
}
TreeNode* insert(TreeNode* t, int x) {
if (!t) return new TreeNode{x}; // 走到空位,落座
if (x < t->val) t->left = insert(t->left, x);
else if (x > t->val) t->right = insert(t->right, x);
return t; // 相等不插:BST 默认不存重复键
} // 查找/插入都是 O(树高):平衡 O(log n),退化成链 O(n)8.2 AVL:失衡就旋转
平衡因子 BF = 左子树高 − 右子树高,AVL 要求每个结点 |BF| ≤ 1。插入后从新结点向上找到最小失衡子树,按「失衡方向」做四种旋转之一:
| 失衡类型 | 特征(最小失衡结点 → 孩子) | 修复动作 |
|---|---|---|
| LL | BF=+2,左孩子 BF=+1(左左沉) | 对失衡结点右旋一次 |
| RR | BF=−2,右孩子 BF=−1 | 对失衡结点左旋一次 |
| LR | BF=+2,左孩子 BF=−1(拐角沉) | 先左旋左孩子,再右旋自己 |
| RL | BF=−2,右孩子 BF=+1 | 先右旋右孩子,再左旋自己 |
8.3 随堂自测
堆与优先队列
堆是一家「上级永远比直属下级强」的公司:找全公司最强的人一眼即得(根);新人入职先放最底层,比直属上级强就换位置上浮(sift-up);最强的人离职,让最后一名员工暂代岗位,再一层层跟更强的下级换位下沉(sift-down)。类比的边界:堆只约束「父子」,兄弟之间、堂兄弟之间毫无排序——所以堆的中序遍历不是有序序列,查任意元素仍要 O(n) 全扫;它不是查找树,是「最值提取机」。
9.1 堆的形态:树的脸,数组的身
9.2 下沉调整与 O(n) 建堆
void siftDown(int a[], int n, int i) { // 把 a[i] 压到该在的位置
while (2 * i + 1 < n) { // 还有孩子就继续
int c = 2 * i + 1; // 左孩子
if (c + 1 < n && a[c + 1] > a[c]) ++c; // 挑更大的孩子
if (a[i] >= a[c]) break; // 已 ≥ 两个孩子:到位
swap(a[i], a[c]); // 与大孩子换位,继续下沉
i = c;
}
}
void buildHeap(int a[], int n) { // Floyd 建堆 O(n)
for (int i = n / 2 - 1; i >= 0; --i) // 最后一个非叶子 → 根
siftDown(a, n, i); // 自底向上,叶子天然成堆
}9.3 堆排序与优先队列
堆排序:建堆 O(n) → 循环 n−1 次「堆顶与末尾交换、堆缩小 1、新顶下沉 O(log n)」→ 总 O(n log n),原地、不稳定。升序用大根堆(最大的先甩到尾部)。优先队列:只暴露 push / pop / top 的堆封装,C++ 的 priority_queue<int> 默认大根堆,小根堆写 priority_queue<int, vector<int>, greater<int>>。Dijkstra、Huffman、任务调度、Top-K 全是它的主场。
9.4 应用:哈夫曼树与最优前缀编码
带权路径长度 WPL = Σ 叶子权 × 路径长。哈夫曼算法:每次用优先队列取权最小的两棵树合并成新树(新根权 = 两者之和)放回,重复 n−1 次。结果:没有度为 1 的结点,n 个叶子共 2n−1 个结点;权越大离根越近。左 0 右 1 即得前缀编码(任何码不是别人的前缀,解码无歧义)。
| 字符 | 权(频率) | 哈夫曼编码 | 码长 |
|---|---|---|---|
| f | 45 | 0 | 1 |
| c | 12 | 100 | 3 |
| d | 13 | 101 | 3 |
| e | 16 | 111 | 3 |
| a | 5 | 1100 | 4 |
| b | 9 | 1101 | 4 |
合并顺序:5+9=14 → 12+13=25 → 14+16=30 → 25+30=55 → 45+55=100。WPL = 45×1 + (12+13+16)×3 + (5+9)×4 = 224,比等长 3 位编码(100×3=300)省 25%——这就是压缩软件的底层原理之一。
for (i = 0; i < n; ++i) siftDown(...) → 调上层时下面的子树还不是堆,之后调下层又会把上层刚理顺的关系打乱——结果静默地不是堆,堆顶不是最值,排序输出错乱。正确姿势:从 n/2 − 1 递减到 0,保证「调某结点时它的子树已是堆」。9.5 随堂自测
红黑树与 B/B+ 树
AVL 是精密天平:稍歪就调,查得快但挪书勤;红黑树是「大体水平」的书架:允许有点歪,但数学保证歪不过一倍,挪书次数少。B+ 树是图书馆的多级目录卡:大厅目录(内部结点)只写「往几楼几区走」,书(数据)全在叶子层,书架之间还有连廊(叶子链表)——借一批连号的书 = 定位起点后沿连廊顺着拿。类比的边界:红黑树的「大体」有严格下界(黑高平衡),不是随便乱放;B+ 树的目录卡一页能写几百条,这才压得低楼层数。
10.1 红黑树:五条规则撑起「近似平衡」
- ① 结点非红即黑;② 根是黑;③ 叶结点(NIL 空结点)是黑;
- ④ 红结点的孩子必黑(不存在连续红);
- ⑤ 任一结点到其所有叶子的路径上,黑结点数相同(黑高 bh 一致)。
推论:最短路径全黑(长 bh),最长路径红黑相间(长 2bh)→ 最长 ≤ 2×最短,树高 ≤ 2log₂(n+1),查找/插入/删除都是 O(log n)。插入默认染红(不破坏⑤),再靠「变色 + 旋转」修复④。
| 维度 | AVL | 红黑树 | B+ 树 |
|---|---|---|---|
| 平衡标准 | 严格:|BF| ≤ 1 | 宽松:最长 ≤ 2×最短 | 绝对:所有叶同层 |
| 树高 | ≈ 1.44 log n | ≤ 2 log(n+1) | log_m n(m 数百,通常 3~4 层) |
| 插删维护 | 旋转较多 | 变色为主,旋转 ≤ 2~3 次 | 结点分裂 / 借位 / 合并 |
| 典型应用 | 读多写少的内存查找 | map/set、epoll、CFS 调度 | MySQL InnoDB 索引、文件系统 |
10.2 B 树与 B+ 树:为磁盘而生
m 阶 B 树:每结点最多 m 个孩子、m−1 个关键字;根(非叶)至少 2 个孩子,其余非根结点至少 ⌈m/2⌉ 个孩子;所有叶同层。关键字满了就分裂,太空就借位或合并。B 树的数据可存在任何结点;B+ 树进一步:内部结点只当「路标」,数据全在叶子,叶子间拉一条有序链表。
// B+ 树结点 = 一个磁盘页(InnoDB 默认 16KB)
struct BPlusNode {
bool isLeaf;
int keys[M - 1]; // 键:导航路标(内部结点只有它)
BPlusNode* child[M]; // 内部结点:子页指针
Record* rec[M - 1]; // 叶子结点:数据记录指针
BPlusNode* next; // 叶子结点:下一片叶子(范围走廊)
};
// 点查:页内二分选分支 → 读子页(1 次磁盘 IO)→ … → 叶子
// 范围 [a,b]:点查定位 a 所在叶子 → 沿 next 顺扫到 b
// 插入:叶子满 → 分裂成两页,中间键上提给父亲(可能连锁到根)10.3 随堂自测
哈希表
快递柜按手机号尾号算柜号:报尾号直接开柜,不用一排排找(计算代替比较)。两人尾号相同 = 冲突:拉链法像柜门上挂一串小钩子,同号包裹全挂这串上;开放定址像「此柜被占,按规则看下一个柜」。装填因子 = 柜子占用率,太满了找空柜要试很久。类比的边界:快递柜可以随便加柜,哈希表扩容却必须全体重新算地址(rehash)——柜号公式里的模数变了,老包裹的柜号全作废。
11.1 哈希函数与冲突
常用除留余数法 H(key) = key % p,p 取不大于表长 M 的质数(减少规律性撞车);还有直接定址、数字分析、平方取中等。好函数两条标准:算得快 + 散得匀。关键字空间远大于地址空间 → 冲突只能管理,不能消灭。
11.2 装填因子与 rehash
α = 已存元素数 n / 表长 M。拉链法 α 可 > 1(链变长而已);开放定址必须 α < 1,工程上到 0.7~0.75 就扩容 rehash:申请约 2 倍新表,所有元素按新模数重新落位——单次 O(n),摊还到每次插入仍是 O(1)(与动态数组同款分析)。
struct HashTable {
vector<list<pair<int,int>>> buckets; // key → value
HashTable(int m) : buckets(m) {}
int& operator[](int key) {
auto& chain = buckets[key % buckets.size()]; // 算地址
for (auto& kv : chain)
if (kv.first == key) return kv.second; // 链上命中
chain.push_back({key, 0}); // 冲突:挂到链尾
return chain.back().second;
}
};
// 查找/插入平均 O(1+α);最坏全撞一条链 O(n)
// 哈希表不保序:范围查询、按序遍历请找 B+ 树 / 平衡树11.3 随堂自测
并查集
每人只记「我的直属上级是谁」。问「你的大老板是谁」就沿上级链一路问到顶(Find);两家公司合并 = 一家的大老板认另一家大老板当上级(Union,合并的是老板不是员工)。路径压缩:问过一次后,链上所有人直接把上级改成大老板——下次一步到位;按大小合并:小公司并入大公司,避免链条越接越长。类比的边界:并查集只支持「合并」不支持「分家」——拆集合要换离线删边倒序、可持久化等高级玩法。
12.1 两个操作与两个优化
int fa[N], sz[N];
void init(int n) {
for (int i = 0; i < n; ++i) fa[i] = i, sz[i] = 1; // 各自为王
}
int find(int x) {
if (fa[x] != x) fa[x] = find(fa[x]); // 回程压缩:直挂根
return fa[x];
}
void unite(int a, int b) {
a = find(a); b = find(b); // 先找根!合并的是根
if (a == b) return; // 本就同集合
if (sz[a] < sz[b]) swap(a, b); // 按大小:小并入大
fa[b] = a; sz[a] += sz[b];
}
// 连通块数 = 满足 fa[i]==i 的 i 的个数
// 应用:Kruskal 判环、朋友圈/等价类、网格连通块a=find(a); b=find(b); 之后只动根指针。12.2 随堂自测
图的存储与遍历
地铁线网图:站点 = 顶点,轨道 = 边。邻接矩阵是一张「任意两站是否直达」的大表格:查任意两站一眼出结果,但 n² 个格子绝大多数是 0,浪费;邻接表是每个站口贴的「相邻站点清单」:省纸,但查「A 和 B 直达吗」得翻 A 的清单。DFS 像探险:能换乘就一直换,走不动才回头;BFS 像水波纹:先逛完 1 站直达圈,再逛 2 站圈。类比的边界:地铁轨道双向通行(无向图),单行道是有向图;换乘有远近票价(带权图/网)。
13.1 术语速览与两种存储
无向图边数 e ≤ n(n−1)/2(取等 = 完全图);有向图看入度/出度。无向图任意两点可达 = 连通;有向图双向都可达 = 强连通。带权图叫网。存储除矩阵/邻接表外,还有有向图的十字链表、无向图的邻接多重表(边只存一份,便于删边)。
13.2 DFS 与 BFS:两套模板
vector<int> g[N]; bool vis[N]; // g[u] = u 的邻居们
void dfs(int u) {
vis[u] = true; visit(u); // 进门就标记
for (int v : g[u])
if (!vis[v]) dfs(v); // 一路深入,死路自动回溯
}
void bfs(int s) {
queue<int> q;
vis[s] = true; q.push(s); // 入队时标记!防重复入队
while (!q.empty()) {
int u = q.front(); q.pop(); visit(u);
for (int v : g[u])
if (!vis[v]) { vis[v] = true; q.push(v); }
}
}
// 非连通图:外层 for 每个未访问顶点再调一次 dfs/bfs
// 调用次数 = 连通分量个数13.3 复杂度与用途对照
| 维度 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈(递归即系统栈) | 队列 |
| 时间(邻接表 / 矩阵) | O(n+e) / O(n²) | O(n+e) / O(n²) |
| 空间 | O(最深递归深度) | O(最宽一层) |
| 擅长 | 连通性、环检测、拓扑排序、路径枚举 | 无权图最短路、层数/距离、最少步数 |
for (u : 所有顶点) if (!vis[u]) bfs(u);——顺带数出连通分量个数。13.4 随堂自测
最小生成树与最短路
给 n 个小区铺光纤,要求全连通且线材最省 = MST。Kruskal:把线材按价格从便宜到贵试铺,两端已在同一张网里就跳过(否则成环浪费)——「是否同网」正是并查集的拿手戏。Prim:从一个小区起家,每次把「离现有网络最近的未入网小区」拉进来。最短路像导航:Dijkstra 每次锁定「当前最近的未锁定路口」,再去更新它邻居的预估距离(松弛)。类比的边界:若存在「负过路费」(负权边),已锁定的路口可能事后更便宜——贪心的「锁定即最优」前提崩塌,得换 Bellman-Ford。
14.1 Prim vs Kruskal:同一棵树,两种长法
14.2 Dijkstra:锁定 + 松弛
void dijkstra(int g[][N], int n, int s) {
vector<int> dist(n, INT_MAX); vector<bool> done(n, false);
dist[s] = 0;
for (int k = 0; k < n; ++k) {
int u = -1;
for (int i = 0; i < n; ++i) // 选未锁定中 dist 最小者
if (!done[i] && (u == -1 || dist[i] < dist[u])) u = i;
if (u == -1 || dist[u] == INT_MAX) break; // 剩余不可达
done[u] = true; // 锁定:此后不再变
for (int v = 0; v < n; ++v) // 松弛 u 的所有邻居
if (g[u][v] && dist[u] + g[u][v] < dist[v])
dist[v] = dist[u] + g[u][v];
}
}14.3 Floyd:所有点对,三层循环
for (int k = 0; k < n; ++k) // 中转点 k 必须在最外层!
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
// 含义:d[i][j] = 只允许用 0..k 号点中转时 i→j 的最短路
// 第 k 轮回答「借道 k 会不会更近」—— 阶段维度,不能挪进内层
// O(n³);允许负权边(不能有负权环);代码 5 行,多源首选for i → for j → for k → 算出来的只是「直达或一步中转」的局部最优,多跳路径永远松弛不出来,结果静默偏大(样例小时还看不出)。正确姿势:k 是 DP 的「阶段」,必须最外层——先允许借道 0,再允许借道 0,1……逐阶段放开。14.4 随堂自测
拓扑排序与关键路径
大学培养方案就是 AOV 图:先修高数才能修数据结构。拓扑排序 = 排一张四年课表,保证每门课开课时先修课都已修完;没有依赖的课(体育、选修)随时可插——所以合法课表不止一份。关键路径像装修流程:水电→泥工→油漆一环扣一环,最长的那条工序链决定交房日期;给不关键的工序加人手,交房日期纹丝不动。类比的边界:课表允许并行上课(多个入度 0 同时可选),关键路径也可能不止一条。
15.1 拓扑排序:入度表剥离法(Kahn)
vector<int> topo(int n, vector<int> g[], int indeg[]) {
queue<int> q;
for (int i = 0; i < n; ++i)
if (indeg[i] == 0) q.push(i); // 无前置的先入队
vector<int> order;
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u); // u 的前置已全部完成
for (int v : g[u])
if (--indeg[v] == 0) q.push(v); // 拆掉一条依赖
}
return order; // order.size() < n → 有环,排不出!
} // O(n+e);用优先队列取最小可得「字典序最小」拓扑序15.2 AOE 网与关键路径
AOE 网:顶点 = 事件(里程碑),边 = 活动(带工期)。四个量:事件最早 ve(源点起正向取 max)、事件最晚 vl(汇点起逆向取 min);活动最早 e = ve(尾),活动最晚 l = vl(头) − 工期。l − e = 0 的活动是关键活动,串起来就是关键路径(源到汇的最长路,长度 = 总工期)。
15.3 随堂自测
查找算法总览
查字典:顺序查找 = 从第一页翻起;二分查找 = 翻中间,目标拼音更靠前就撕掉后半本再翻中间——字典「按拼音排好 + 能直接翻到任意页」正是二分的两个前提。分块查找 = 先看侧面的字母凸标(块间有序),定位到区块后块内逐页翻(块内无序)。类比的边界:换成「卷轴」就翻不了中间——链表定位中点要顺着爬,二分立刻失效;字典若没排序,翻中间毫无信息量。
16.1 二分查找:区间折半的艺术
int bsearch(int a[], int n, int x) { // 闭区间 [lo, hi]
int lo = 0, hi = n - 1;
while (lo <= hi) { // 区间非空就继续
int mid = lo + (hi - lo) / 2; // 防 lo+hi 溢出!
if (a[mid] == x) return mid;
if (a[mid] < x) lo = mid + 1; // mid 已排除,+1
else hi = mid - 1;
}
return -1;
}
int lower_bound(int a[], int n, int x) { // 半开 [lo, hi):首个 ≥x
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < x) lo = mid + 1;
else hi = mid; // mid 可能是答案,保留
}
return lo; // 两种约定都对,混用必错(死循环/漏解)
}16.2 分块查找与全家福
分块(索引顺序)查找:块间有序(第 i 块所有关键字 < 第 i+1 块)、块内无序。先查索引表定块(可二分),再块内顺序扫。块长取 √n 时 ASL ≈ √n——介于顺序与折半之间,适合「整体懒得全排、局部频繁增删」的数据。
| 查找结构 | 平均查找 | 增删 | 保序/范围 | 适用场景 |
|---|---|---|---|---|
| 有序顺序表 + 二分 | O(log n) | O(n) 挪动 | ✓ | 静态/少改的表 |
| BST(随机数据) | O(log n) | O(log n) | ✓ | 教学与轻量场景 |
| AVL / 红黑树 | O(log n) 保证 | O(log n) | ✓ | 内存有序映射 map/set |
| B+ 树 | O(log_m n) 次页 IO | 分裂/合并 | ✓✓ | 磁盘数据库索引 |
| 哈希表 | O(1) | O(1) | ✗ | 纯键值点查 unordered_map |
| 跳表 | 期望 O(log n) | 期望 O(log n) | ✓ | 并发友好(Redis zset) |
mid = lo + (hi - lo) / 2,数学等价但永不溢出。另一坑:区间约定 [lo,hi] 与 [lo,hi) 的循环条件、收缩写法必须从一而终,混搭 = 死循环或漏解。16.3 随堂自测
内部排序全景
整理一手扑克:插入排序 = 每摸一张,插进左手已理好的牌里(摸牌即排序);选择排序 = 每次从乱牌堆里挑最小的放到末尾;快排 = 抽一张当基准,小的甩左边大的甩右边,两堆各自递归;归并 = 先把小堆理好,再「两堆顶牌比大小,小的先出」合成大堆。稳定性 = 两张同点数的牌保持原来的先后——多关键字排序(先按点数、再按花色排)全靠它。类比的边界:手牌少时插入最快(n 小系数说了算),这正是快排小区间切插入的原因。
17.1 快排:一趟划分定一个「最终位」
void quickSort(int a[], int lo, int hi) {
if (lo >= hi) return;
int p = a[lo], i = lo, j = hi; // pivot 挖出,坑在 i
while (i < j) {
while (i < j && a[j] >= p) --j; // 右找小
a[i] = a[j]; // 填左坑,坑移到 j
while (i < j && a[i] <= p) ++i; // 左找大
a[j] = a[i]; // 填右坑,坑移到 i
}
a[i] = p; // pivot 落最终位
quickSort(a, lo, i - 1);
quickSort(a, i + 1, hi);
} // 平均 O(n log n);最坏 O(n²);递归栈平均 O(log n)17.2 归并:两个有序段的拉链合并
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // ≤ 保稳定
while (i <= mid) tmp[k++] = a[i++]; // 左段收尾
while (j <= hi) tmp[k++] = a[j++]; // 右段收尾
for (int t = lo; t <= hi; ++t) a[t] = tmp[t];
}
// mergeSort:递归分半 → 回溯时 merge;T(n)=2T(n/2)+O(n)
// → O(n log n) 最坏也成立;外部排序的「多路归并」是它的磁盘版17.3 八大排序总表(必背)
| 算法 | 平均 | 最坏 | 最好 | 额外空间 | 稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) 已有序 | O(1) | ✓ |
| 直接插入 | O(n²) | O(n²) | O(n) 已有序 | O(1) | ✓ |
| 希尔排序 | ≈O(n^1.3) | O(n²) | O(n) | O(1) | ✗ |
| 快速排序 | O(n log n) | O(n²) 划分偏斜 | O(n log n) | O(log n) 栈 | ✗ |
| 简单选择 | O(n²) | O(n²) | O(n²) | O(1) | ✗ |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ✗ |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | ✓ |
基数排序不比较:按「个位→十位→百位」(LSD)逐位分配 + 收集,每轮必须稳定,d 是位数、r 是基数。选择排序不稳定例:[5a, 5b, 2] 第一轮 5a 与 2 交换 → 5a 跑到 5b 后面。
17.4 随堂自测
进阶结构与外部排序
跳表是地铁的快慢车系统:普通链表是站站停的慢车,架几层「快车线」就能大段跨越,坐过站再降层换慢车精确定位——期望 O(log n)。布隆过滤器是门卫的「黑名单印象」:他说「没见过你」→ 你肯定不在名单上;他说「好像见过」→ 可能认错人(多人特征叠在同一格)。类比的边界:门卫不能「忘掉一个人」——清掉某格特征会误伤共享这格的其他人,所以布隆不支持删除;快车线层数是抛硬币随机决定的,不是精密设计。
18.1 Trie:前缀的共享高速公路
struct Trie {
Trie* ch[26] = {}; // 每个字符一条岔路
bool end = false; // 单词终点标记
void insert(const string& s) {
Trie* u = this;
for (char c : s) {
int k = c - 'a';
if (!u->ch[k]) u->ch[k] = new Trie(); // 没路修路
u = u->ch[k];
}
u->end = true;
}
bool search(const string& s) {
Trie* u = this;
for (char c : s) {
u = u->ch[c - 'a'];
if (!u) return false; // 路断了:不存在
}
return u->end; // 有路但无终点标记 = 只是前缀
}
};18.2 跳表与线段树
18.3 外部排序:IO 才是货币
数据远大于内存:① 分批读入内存排序,写出若干初始归并段(置换选择法可产出平均 2 倍内存长的段);② k 路归并:每轮从 k 个段头挑最小输出——用败者树选最小只需 O(log k) 次比较;③ 段太多就多趟归并,每趟都要读写全部数据一遍。所以优化目标是减少归并趟数:增大 k、用置换选择减少段数、按最佳归并树(哈夫曼思想:短段先合并)安排顺序。
18.4 全书收官:选型速查
| 你的需求 | 首选结构 | 一句话理由 |
|---|---|---|
| 键值点查,不要顺序 | 哈希表 | 平均 O(1),计算换比较 |
| 有序 + 范围查询(内存) | 红黑树 / AVL | 中序有序,log n 保证 |
| 有序 + 范围查询(磁盘) | B+ 树 | 树矮 IO 少,叶链顺扫 |
| 前缀补全 / 词库 | Trie | O(串长),与词量无关 |
| 区间统计 / 区间修改 | 线段树 | log n 查询 + 懒标记 |
| 动态连通 / 判环 | 并查集 | 近似常数合并与查询 |
| 随时取最值 / Top-K | 堆(优先队列) | 根即最值,调整 log n |
| 「是否存在」允许误报 | 布隆过滤器 | 位数组极省内存,只否认不肯定 |
| 内存装不下的排序 | 外部归并 + 败者树 | 趟数最少 = IO 最少 |