数据结构
CHAPTER 01 · 基石与复杂度

绪论:三要素与 ADT

一句话总览:数据结构 = 逻辑结构 + 存储结构 + 数据的运算三要素;逻辑结构说「元素之间是什么关系」,存储结构说「在内存里怎么摆」,两者相互独立——同一种关系可以有不同的摆法。
📚
生活化类比
把数据想成一座图书馆:书的分类体系(文学→小说→科幻)是逻辑结构;书在书架上是连续摆放还是散放加索引卡,是存储结构;借书/还书/查书的规则是运算。ADT 就是贴在门口的「服务承诺」——只告诉你能办什么业务,不告诉你书怎么摆。类比的边界:图书馆换摆法不影响借书规则(接口不变),但找书速度会变——程序里也一样,换存储结构不改接口,却直接改变运算的时间复杂度。

1.1 逻辑结构:元素之间的「关系图谱」

按元素间关系分四大类,与计算机怎么存完全无关:

四种逻辑结构:关系从「无」到「多对多」
逻辑结构只看「关系」,不看内存 集合 同属一堆,别无关系 线性结构(1 : 1) 每个元素最多一个前驱、一个后继 树形结构(1 : N) 一个前驱、多个后继,层次分明 图状结构(M : N) 任意两个元素都可能相关
线性表、栈、队列、串都是「线性」;树与二叉树是「树形」;图最自由,也最难算。

1.2 存储结构:同一关系,不同摆法

同一个线性表:顺序存储 vs 链式存储
顺序存储:地址连续 a0a1a2a3a4a5 100010041008101210161020 LOC(ai) = LOC(a0) + i × sizeof(元素) 一次乘加直达 → 随机存取 O(1) 代价:插入/删除要挪动一片元素 链式存储:地址随意,指针缝合 a0a1a2a3 nextnextnext∧ 每个结点 = 数据域 + 指针域,散布在内存各处 找第 i 个? 从头走 O(n)
逻辑上都是 a0→a1→a2→a3,物理上一个「连排柜」、一个「散落+指路条」——存取性能因此天差地别。
存储结构思路优点代价
顺序存储逻辑相邻 → 物理相邻(数组)随机存取 O(1),无额外指针开销插删挪动多,容量要预估/扩容
链式存储指针记录后继关系(链表)插删改指针即可,容量灵活只能顺序访问,指针占空间
索引存储另建索引表:关键字 → 地址检索快,适合大数据索引表本身占空间、要维护
散列存储由关键字直接算出地址(哈希)增删查都接近 O(1)有冲突,不支持范围/顺序查询

1.3 抽象数据类型(ADT):只承诺,不泄底

ADT = 数据对象 + 数据关系 + 基本运算的定义,与实现无关。调用方只看接口,实现可以从数组换成链表而调用代码一行不改——这就是「封装」的思想源头。

ADT List(接口定义,C 风格)
// 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 随堂自测

QUIZ 1
关于「线性表」,下列说法正确的是?
线性表描述的是「1 对 1 的前驱后继关系」,属于逻辑结构;顺序表和链表是它的两种存储实现。元素类型任意,与是不是整数无关。
QUIZ 2
抽象数据类型(ADT)的核心思想是?
ADT 只定义「是什么、能做什么」,刻意隐藏「怎么做」。C 语言照样能写 ADT;内存布局恰恰是 ADT 要隐藏的部分;效率取决于具体实现,不是 ADT 本身的承诺。
CHAPTER 02 · 基石与复杂度

复杂度分析:大 O 与摊还

一句话总览:复杂度衡量的是「n 变大时,代价增长的量级」——只留最高阶、去掉系数;大 O 是最坏上界,摊还分析则把「偶尔很贵」的操作平摊到整个序列上。
🚗
生活化类比
估通勤时间:你说「上班大约 40 分钟」,不会精确到「今天红灯多等 90 秒」。路程翻倍 → 时间大约翻倍,这是量级(O(n));红灯、天气是系数和低阶项,估量级时忽略。类比的边界:路程只有 500 米时,等一个红灯反而占大头——n 很小时系数不可忽略,所以小数组上插入排序常常跑赢快速排序。

2.1 增长量级:一张图看懂谁先爆炸

常见复杂度的增长曲线(横轴 n,纵轴代价)
n → 代价 O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ) n 翻倍:O(n) 代价×2,O(n²) ×4,O(2ⁿ) 直接平方级爆炸 —— 量级决定「能不能算完」
n = 10⁶ 时,O(n log n) 约两千万次操作能秒级跑完,O(n²) 是万亿级——今天就不用等了。
复杂度名称典型例子n = 10⁶ 时的体感
O(1)常数数组下标访问、哈希查找(理想)瞬间
O(log n)对数二分查找、平衡树查找约 20 步,瞬间
O(n)线性遍历、顺序查找毫秒级
O(n log n)线性对数快排(平均)、归并、堆排几十毫秒~秒级
O(n²)平方冒泡、插入、选择排序小时级,基本不可用
O(2ⁿ) / O(n!)指数 / 阶乘朴素递归斐波那契 / 全排列枚举n≈40 就算到宇宙尽头

2.2 数出来的复杂度:看循环变量怎么变

count.cpp — 四种典型循环
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²)!
⚠ 高频陷阱:见两层 for 就写 O(n²)
错误写法:数循环层数定复杂度 → 把上面的 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)(二分)。

ℹ 空间复杂度只算「额外」空间
输入本身占的空间不计。原地算法(冒泡、堆排)O(1);归并要辅助数组 O(n);递归快排平均栈深 O(log n)、最坏 O(n)。递归深度过大 → 栈溢出崩溃,这是空间复杂度的现实后果。

2.4 摊还分析:偶尔很贵 ≠ 每次很贵

push_back.cpp — 动态数组扩容
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)
✓ 记忆锚点
加法取最大,乘法叠起来;折半是 log,翻倍是指数;留最高阶,系数全丢掉。

2.5 随堂自测

QUIZ 1
for (int i = 1; i <= n; i *= 2) s++; 的时间复杂度是?
i 取 1,2,4,…,2ᵏ,直到 2ᵏ > n 停止,共约 log₂n 次。循环变量「乘除变化」是对数级的标志;「加减变化」才是线性级。
QUIZ 2
对初始为空的动态数组连续 push_back n 次(每次满则容量翻倍),总时间复杂度是?
扩容虽发生 log n 次,但每次搬家量翻倍递增,总和小于 2n,故总代价 O(n)、摊还每次 O(1)。A 把「单次最坏」错乘了 n 次;D 混淆了单次与总量。
CHAPTER 03 · 线性结构

顺序表与链表

一句话总览:顺序表用「地址连续」换来 O(1) 随机存取,链表用「指针缝合」换来 O(1) 插删(已定位时);选结构就是选「你让哪个操作快」,没有全赢的摆法。
🅿️
生活化类比
顺序表是编号停车场:报编号 i 直接算出车位位置(随机存取);想在中间插一辆车,后面整排车都得挪(O(n))。链表是寻宝线索链:每张线索写着下一张的藏匿点,中间加一张只需改两张线索的指向;但找第 5 张必须从头顺藤摸瓜。类比的边界:停车场可以扩建,但扩建要整体搬家(扩容拷贝);线索随便藏(不要求连续内存),代价是每张线索多花纸写地址(指针空间开销)。

3.1 顺序表:插入删除的代价是「挪动」

seq_insert.cpp — 顺序表插入
// 在第 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 章已推导)。下面亲手点一点:

HANDS-ON DEMO
动态数组扩容模拟器
连续点「尾插」:多数时候只是占一格;容量满的那一次会「申请 2 倍空间 + 整体搬家」。盯着累计搬家量与操作次数的比值,体会什么叫摊还 O(1)。

3.2 单链表:改指针的艺术

link_build.cpp — 头结点 + 头插法
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
}
删除结点 q 的两步指针手术:先绕路,再释放
第①步 p->next = q->next —— 让 p 绕过 q 直接牵住 c abc nextnext∧ p q(待删除) p->next 改指 c(新链接) 第②步 free(q) —— 此时才安全释放 b ac 已释放 ✕ 顺序反了 = 先 free(q) 再读 q->next → 访问已释放内存(use-after-free),崩溃或读到脏数据
插入同理反着来:先让新结点接住后继,再让前驱接住新结点——任何一步先断旧链,后继就永远丢了。
⚠ 高频陷阱:边遍历边释放 / 先断链后接线
错误写法:p = p->next; free(p);(释放的是新 p,且旧结点泄漏)或插入时先 p->next = s 再给 s->next 赋值 → 原后继整段丢失(内存泄漏 + 数据静默丢失)。正确姿势:删除前先用临时指针存住目标;一切改链操作遵循「先接新、后断旧」。

3.3 链表家族与选型

形态结构特点解决什么问题
单链表一个 next 指向后继最基本的动态线性表
双链表prior + next 两个指针O(1) 找前驱,删除自身不用从头找
循环单/双链表尾结点指回头部(成环)从任一结点出发可达全表;轮转调度
静态链表数组存结点,next 是「下标」无指针语言/定长内存池场景
✓ 记忆锚点
插入「新人先接后继,前驱再接新人」;删除「先绕过、后释放」。头结点不是第一个数据结点,它是为了让「第一个位置」和「其他位置」的操作长得一样。

3.4 随堂自测

QUIZ 1
长度为 n 的顺序表,等概率地在任意合法位置插入一个元素,平均需要移动多少个元素?
合法插入位置有 n+1 个,移动量从 n(插最前)到 0(插最后),平均 (0+1+…+n)/(n+1) = n/2。C 是链表已定位时的插删代价,别混。
QUIZ 2
带头结点的单链表,引入「头结点」的主要目的是?
头结点让「在第一个数据结点前插入/删除」与中间位置写法一致,空表时 head->next==nullptr 也无需特判 head 本身。它多占一个结点(A 错),不改变查找方式(B、C 错)。
CHAPTER 04 · 线性结构

栈与队列

一句话总览:栈和队列都是「操作受限的线性表」——栈只在一端进出(LIFO),队列一端进另一端出(FIFO);循环队列用取模把数组弯成环,根治「假溢出」。
🍽️
生活化类比
栈是食堂的一摞盘子:最后摞上去的最先被拿走(LIFO);队列是奶茶店排队:先来先点单(FIFO)。循环队列像圆桌转盘上的座位:编号转一圈又回到 0,队尾追着队头跑。类比的边界:现实中你能从盘子摞中间抽一个、排队的人会插队——程序里的普通栈/队列严禁这些操作,正是「受限」才让行为可预测、实现能做到 O(1)。

4.1 两种「受限」的方向

栈:同一端进出;队列:两端各司其职
栈(LIFO) abc push 入栈 pop 出栈 栈顶 top:唯一开口,c 最后进最先出 队列(FIFO) cba 队尾 rear 入队 队头 front 出队 a 最先进队,也最先离开 —— 公平排队
受限不是缺陷而是契约:栈保证「最近的先处理」(递归/撤销),队列保证「先来的先处理」(调度/缓冲)。

栈的经典应用:括号匹配、表达式求值(中缀转后缀)、递归调用栈、进制转换;队列的经典应用:CPU 调度、消息缓冲、BFS、打印机任务。双端队列(deque)两端都可进出,是栈与队列的超集。

match.cpp — 栈做括号匹配
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();   // 栈空 = 全部配对;非空 = 左括号多了
}   // "([)]" 会在配对时失败 —— 嵌套必须最近优先,正是 LIFO

4.2 循环队列:取模把数组弯成环

循环队列(M=8):rear 越过 7 号位后回到 0
下标回绕:(i + 1) % 8 10203040 01234567 front = 2(队头元素) rear = 6(下一个空位) 入队:data[rear]=x; rear=(rear+1)%M 出队:x=data[front]; front=(front+1)%M 元素个数 = (rear-front+M)%M = 4 队满 = (rear+1)%M == front(牺牲一格)
front/rear 永远只增不回退,靠 %M 回绕——前面出队腾出的格子能被后面复用,这就是根治假溢出。
cqueue.cpp — 循环队列核心
#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 顶到数组尾就报满——前面明明有空位(假溢出)→ 用循环队列。② 若不牺牲一格,队满和队空都满足 front == rear,无法区分(静默逻辑错误)→ 三种解法:牺牲一个存储格(最常用)、增设 size 计数、增设 tag 标志。
ℹ 竞赛与工程里的两个变形
单调栈:栈内保持单调,用于「下一个更大元素」「柱状图最大矩形」,每个元素进出各一次 O(n)。单调队列:双端队列维护窗口最值,滑动窗口最大值 O(n)。它们不是新结构,是「栈/队列 + 一条维护规则」。
✓ 记忆锚点
栈是摞盘子,队是排奶茶;满空分不清,就牺牲一格;下标要回绕,全靠 %M。

4.3 随堂自测

QUIZ 1
循环队列容量 M=10(牺牲一格方案),当前 front=8、rear=3,队列中的元素个数是?
(rear − front + M) % M = (3 − 8 + 10) % 10 = 5。元素占 8、9、0、1、2 共 5 格。直接减得 −5 说明忘了加 M 再取模——这正是回绕的意义。
QUIZ 2
入栈序列为 1,2,3,4(入栈出栈可交替进行),下列哪个是不可能的出栈序列?
3 先出栈说明 1、2 已压入且仍在栈中,此时栈顶是 2——1 被 2 压着,不可能抢在 2 前面出来。A 全压后连弹,B 压 1,2,3 弹 3,2 再压 4 弹 4,1,D 压一个弹一个,都合法。
CHAPTER 05 · 线性结构

串与 KMP 模式匹配

一句话总览:BF 暴力匹配失配就把主串指针拉回去重来(O(n·m));KMP 预先算出模式串的「最长相等前后缀」,失配时主串指针永不回头,只让模式串滑到重叠处,整体 O(n+m)。
🧩
生活化类比
用花边模板「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] 的「最长相等真前缀与真后缀」的长度(真 = 不含自身)。它回答:失配时,已经匹配上的这段里,有多少可以「废物利用」。

逐位推导 P = "ababc" 的 π 数组
蓝 = 前缀,绿 = 后缀;两者相等才计数,且不能取整个子串 P[0..0] "a"P[0..1] "ab"P[0..2] "aba"P[0..3] "abab"P[0..4] "ababc" a ab aba abab ababc 单字符没有「真」前后缀 → π[0] = 0 前缀 a ≠ 后缀 b → π[1] = 0 前缀 "a" = 后缀 "a" → π[2] = 1 前缀 "ab" = 后缀 "ab" → π[3] = 2 结尾 c 谁也配不上 → π[4] = 0 π = [0, 0, 1, 2, 0]
π 只跟模式串自己有关,与主串无关——所以能一次预处理,反复使用。

5.3 失配时怎么滑:主串永不回头

KMP 匹配 T="abababc":失配后模式串右滑 2 格,i 停在原地
主串 T abababc i=0123i=456 第一趟 a✓b✓a✓b✓c✗ j=4 失配:已匹配 "abab",π[3]=2 j ← π[j-1] = 2,模式滑 4-2=2 格 i 不动! 第二趟 aba✓b✓c✓ 虚线两格 = π 保证必然匹配,直接跳过比对 j 走完 → 命中,起点 i-j+1 = 2
BF 会把 i 拉回 1 重头再来;KMP 的 i 只进不退——省下的正是「已经知道答案」的重复比较。
kmp.cpp — π 数组 + 匹配主循环
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-based)的 next[1]=0, next[2]=1,其值 = 最长相等前后缀长度+1;竞赛/工程(0-based)的 π 就是长度本身。混用会整体错一位:轻则漏匹配,重则 j 回退到错误位置死循环。正确姿势:动笔前先钉死一套约定;换算关系 next[j] = π[j-1] + 1。另外求「所有出现位置」时,命中后要 j = π[j-1] 继续,否则漏掉重叠匹配。
✓ 记忆锚点
主串不回头,模式靠重叠;重叠多长,π 说了算。

5.4 随堂自测

QUIZ 1
P = "abab",按「最长相等真前后缀长度」定义(0-based),π 数组是?
"a"→0;"ab" 前缀 a≠后缀 b→0;"aba" 首尾都是 a→1;"abab" 前缀 ab=后缀 ab→2。B 是教材 +1 约定的 next 值,D 忘了「真前后缀不含自身」。
QUIZ 2
KMP 总复杂度能达到 O(n+m) 的关键原因是?
i 只增不减共 n 步;j 每次 +1 都伴随 i 前进,而回退只会减少 j,故回退总量 ≤ 增长总量 ≤ n——摊还线性。KMP 与哈希、排序无关,也不依赖 m 很小。
CHAPTER 06 · 线性结构

数组、压缩存储与广义表

一句话总览:多维数组本质是「按映射公式摊平的一维内存」;压缩存储 = 只存有规律矩阵的「有效部分」,其余靠公式换算;广义表则是元素还可以是子表的线性表——递归定义的开端。
🏢
生活化类比
公寓房号就是二维→一维映射:「M 层 N 号」换算成全局编号 = (M−1)×每层户数 + N,一层一层数过去就是行优先。对称矩阵压缩像「夫妻共用一个储物柜」——a[i][j] 和 a[j][i] 值相同,存一份就够。广义表是俄罗斯套娃:盒子里既可以放小球(原子),也可以放更小的盒子(子表)。类比的边界:真实房号会跳 4、13 层(不规则),而数组映射必须严格规则——所以只有对称/三角/带状这类规律矩阵才能用公式压缩,零散分布的稀疏矩阵只能老实登记「哪行哪列有啥」。

6.1 行优先:二维是怎么摊平的

3×4 矩阵按行优先摊进一维内存(0-based)
逻辑视图:3 行 4 列 a00a01a02a03 a10a11a12a13 a20a21a22a23 行优先:第 0 行整行排完,才轮到第 1 行 k = i × 4 + j (列数 n = 4) 列优先(Fortran/MATLAB):k = j × 3 + i 同一个 a[i][j],两种语言算出的地址不同! 物理视图:一段连续内存 a00a01a02a03a10a11a12a13a20a21a22a23 k=0k=4k=8k=11 按行遍历贴着内存走(缓存友好);按列遍历到处跳 —— 大矩阵性能差数倍的原因
「多维」只是给人看的视图,内存永远一维;映射公式就是视图与内存之间的翻译官。

6.2 对称矩阵:只存下三角

4×4 对称矩阵压缩:16 格 → 10 格
a00a10a11a20a21a22a30a31a32a33 k0k1k2k3k4k5k6k7k8k9 不存不存不存不存不存不存 a[i][j] = a[j][i],上三角是下三角的镜像 i ≥ j:k = i(i+1)/2 + j i < j:交换 i、j 再套上面的公式 前 i 行共 1+2+…+i = i(i+1)/2 个元素, 本行再走 j 步 —— 公式就是「数格子数出来的」 a00a10a11a20a21a22a30a31a32a33 一维数组 sa[10] 装下整个 4×4 对称矩阵:n 阶只需 n(n+1)/2 格
压缩不是魔法,是「用一次乘加换一半内存」——访问仍是 O(1),只是公式多一步。
特殊矩阵(n 阶)压缩方案存储量
对称矩阵下三角(含对角线)按行存n(n+1)/2
三角矩阵有效三角 + 常数区 1 格n(n+1)/2 + 1
三对角(带状)三条对角线按行交错存3n − 2
稀疏矩阵(t 个非零)三元组 (行,列,值) / 十字链表3t(另存行列数)

6.3 稀疏矩阵:登记制代替铺满制

triple.cpp — 三元组顺序表
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。

⚠ 高频陷阱:把表尾当成「最后一个元素」
错误写法:GetTail((a,b,c)) 答成 c 或 (b,c) 丢掉外层括号 → 后续 GetHead/GetTail 连锁全错。正确姿势:GetTail((a,b,c)) = (b,c)——尾巴是「剩下的整段表」,必须带括号;空表的表尾无定义。取 b 的正确姿势:GetHead(GetHead(GetTail(LS))),一层层剥。
⚠ 下标约定先钉死
本章公式全部 0-based。教材常用 1-based:行优先 k=(i−1)×n+j−1、对称 k=i(i−1)/2+j(i≥j)。考试先看下标从几开始,再套对应公式——差一位就是全错。
✓ 记忆锚点
行优先一行行数;对称存一半;稀疏三元组;广义表——头可为娃,尾必是盒。

6.5 随堂自测

QUIZ 1
10 阶对称矩阵按下三角(含对角线)压缩存储,一维数组至少需要多少个存储单元?
n(n+1)/2 = 10×11/2 = 55。45 是不含对角线的 n(n−1)/2;100 是没压缩的全量。对角线上 a[i][i] 只出现一次,必须存。
QUIZ 2
广义表 LS = (a, (b, c), d),GetTail(LS) 的结果是?
表尾 = 去掉表头 a 后,其余元素组成的表:((b,c), d)。A 是第二个元素(一个子表),B 是最后一个元素,D 非法拆开了子表 (b,c)——子表是不可拆的整体元素。
CHAPTER 07 · 树形结构

二叉树与遍历

一句话总览:二叉树每结点最多两个孩子且左右不可交换;四种遍历的区别只是「根在什么时机被访问」;完全二叉树能直接塞进数组,父子关系变成下标公式。
🏛️
生活化类比
把二叉树想成「每人最多两名直属下级」的组织架构,遍历就是巡视顺序:先序 = 先见领导再下基层(根左右);中序 = 左部门→领导→右部门(左根右);后序 = 基层全见完才见领导(左右根)——适合「先汇总下属再处理自己」(算目录大小、释放内存);层序 = 一层一层扫楼。类比的边界:真实组织一人可带 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⌋。
同一棵树,四种巡视路线
ABCDEF ← C 只有左孩子 F 先序(根左右):A B D E C F 中序(左根右):D B E A F C 后序(左右根):D E B F C A 层序(逐层):A B C D E F 递归代码只有一份,visit 放的位置 决定它是先序 / 中序 / 后序
遍历序列是「树的一维投影」;投影 + 中序(左右分界信息)才能还原立体结构。

7.2 遍历代码:一份递归 + 一个队列

traverse.cpp
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(最宽一层)
完全二叉树 ↔ 数组:父子关系 = 下标算术
0123456 left(i) = 2i + 1 right(i) = 2i + 2 parent(i) = (i - 1) / 2 i=0 无父亲;2i+1 ≥ n 即无左孩子 最后一个非叶子下标 = n/2 - 1 a[0]a[1]a[2]a[3]a[4]a[5]a[6] 层序编号直接当下标,零指针开销
只有「完全」形态才配得上数组存储——中间缺一个结点,下标公式就全乱了。堆正是吃这个红利。

7.3 重构、线索与森林

重构二叉树:先序/后序/层序提供「谁是根」,中序提供「左右子树的分界」——所以 先序+中序、后序+中序、层序+中序都能唯一重构;先序+后序不行(单孩子分不清左右)。

ℹ 线索二叉树 & 左孩子右兄弟
线索化:n 个结点的二叉链表有 n+1 个空指针,浪费!把空左链指向「中序前驱」、空右链指向「中序后继」(加标志位区分),即可不用栈/递归做中序遍历。树/森林转二叉树:左指针 = 第一个孩子,右指针 = 下一个兄弟(「左孩子右兄弟」);森林的后根遍历对应二叉树的中序。
⚠ 高频陷阱:完全二叉树的判定
错误写法:只检查「最后一层靠左」却忘了中间层必须满 → 把缺了中间结点的树误判为完全树,堆的下标公式随之全错。正确姿势:层序遍历(空孩子也入队),遇到第一个空结点后,队列里不允许再出现任何非空结点——出现即非完全。
✓ 记忆锚点
先序根先行,中序根居中,后序根收尾;重构必带中序;叶子永远比双分支结点多一个。

7.4 随堂自测

QUIZ 1
一棵二叉树中度为 2 的结点有 5 个,则叶子结点有几个?
n₀ = n₂ + 1 = 6,与度为 1 的结点无关。推导:总边数 = n−1 = n₁ + 2n₂,又 n = n₀+n₁+n₂,联立消元即得——D 正是没推过公式的直觉误区。
QUIZ 2
下列哪组遍历序列不能唯一确定一棵二叉树?
先序给根、后序也给根,但两者都无法区分「唯一的孩子是左还是右」——如先序 AB、后序 BA,B 挂左挂右都成立。中序的价值就是提供左右分界,缺它不唯一。
CHAPTER 08 · 树形结构

二叉排序树与 AVL 树

一句话总览:BST 靠「左 < 根 < 右」让查找每次砍掉一半,中序遍历天然有序;但插入顺序能让它退化成链 O(n)——AVL 用「平衡因子 ≤1 + 旋转」把高度强行摁回 O(log n)。
⚖️
生活化类比
BST 查找就是猜数字游戏:「大了往左、小了往右」,每问一次淘汰一半候选。可如果插入的是有序序列 1,2,3,4,5,树长成一条右斜链——相当于每次只猜「大 1」,一次只淘汰一个。AVL 是自动配平的书架:哪边沉了就做一次局部「旋转重排」,始终两边大致等高。类比的边界:旋转本身只是 O(1) 改几个指针,但每次插入删除都可能触发——这正是后来红黑树用「宽松平衡」换「更少旋转」的动机。

8.1 BST:查找与插入

bst.cpp
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)
BST 删除的三种情况:越删越要保住「左小右大」
① 删叶子:直接摘 201030✕ 父结点相应指针置空即可 ② 只有一个孩子:孩子顶位 40✕3532 35 整体上移 独生子继承位置,子树关系不变 ③ 两个孩子:找「中序后继」替身 50✕30706080 右子树最小值 60 复制到根,再删掉原 60 (后继必无左孩子 → 化归情况①②)
中序后继 = 右子树最左结点,它是「比根大的最小值」——顶上来不破坏任何大小关系。

8.2 AVL:失衡就旋转

平衡因子 BF = 左子树高 − 右子树高,AVL 要求每个结点 |BF| ≤ 1。插入后从新结点向上找到最小失衡子树,按「失衡方向」做四种旋转之一:

LL 型失衡 → 一次右旋:B 上位,C 的左子树过继给 A
旋转前:C 的 BF = +2(左左沉) CBT4AT2 BF=+2 BF=+1 右旋 C 旋转后:B 当根,全员 |BF| ≤ 1 BACT2T4 中序仍是 A B T2 C T4 —— 旋转不改 BST 有序性,只改高度
旋转的本质:把「中间大小」的结点提为根——T2 从 B 的右子过继成 C 的左子,大小关系毫发无损。
失衡类型特征(最小失衡结点 → 孩子)修复动作
LLBF=+2,左孩子 BF=+1(左左沉)对失衡结点右旋一次
RRBF=−2,右孩子 BF=−1对失衡结点左旋一次
LRBF=+2,左孩子 BF=−1(拐角沉)先左旋左孩子,再右旋自己
RLBF=−2,右孩子 BF=+1先右旋右孩子,再左旋自己
⚠ 高频陷阱:双孩子删除直接「右子树整体上位」
错误写法:删 50 时把 70 整棵提上来、30 挂到某处随手一接 → 60 可能落到 70 的右边,BST 性质被静默破坏,后续查找结果时对时错,极难排查。正确姿势:用中序后继(右子树最左)的值覆盖被删结点,再去右子树里删那个后继——它必无左孩子,问题化归为情况①②。
⚠ LR/RL 别转反
「拐角型」失衡单旋无效(转完还是歪的)。口诀:先把孩子转成直线型,再对自己转。LR = 左孩子的右侧沉 → 先左旋孩子变 LL,再右旋自己。
✓ 记忆锚点
BST 中序即有序;删除找后继;LL 右、RR 左,LR/RL 先转娃再转爹。

8.3 随堂自测

QUIZ 1
把 1,2,3,4,5 依次插入初始为空的 BST(不做平衡),查找任一元素的复杂度是?
有序插入让每个新结点都成为上一个的右孩子,树高 = n,查找等价于链表顺序扫描。这正是 AVL/红黑树存在的理由:平衡不能靠插入数据的运气。
QUIZ 2
AVL 插入后,最小失衡结点 BF=+2,其左孩子 BF=−1,应做哪种调整?
父 +2(左沉)而左孩子 −1(它的右侧沉)= LR 拐角型,单旋会把歪斜换个方向继续歪。先把左孩子左旋成 LL 直线型,再右旋自己。C 是镜像的 RL,方向全反。
CHAPTER 09 · 树形结构

堆与优先队列

一句话总览:堆是「只保证父 ≥ 子(或父 ≤ 子)」的完全二叉树:根就是全局最值,数组存储零指针;插入上浮、删顶下沉各 O(log n),Floyd 自底向上建堆只要 O(n)——堆排序与优先队列都靠它。
🏢
生活化类比
堆是一家「上级永远比直属下级强」的公司:找全公司最强的人一眼即得(根);新人入职先放最底层,比直属上级强就换位置上浮(sift-up);最强的人离职,让最后一名员工暂代岗位,再一层层跟更强的下级换位下沉(sift-down)。类比的边界:堆只约束「父子」,兄弟之间、堂兄弟之间毫无排序——所以堆的中序遍历不是有序序列,查任意元素仍要 O(n) 全扫;它不是查找树,是「最值提取机」。

9.1 堆的形态:树的脸,数组的身

大根堆 [90,70,80,40,50,60,20]:父子有序,兄弟无关
90708040506020 根 = 全局最大,O(1) 直达 ✓ 每个父亲 ≥ 两个孩子 ✗ 70 < 80?兄弟不排序,合法! ✗ 中序 40,70,50,90,60,80,20 无序 查任意值 / 找第 k 大以外的元素:O(n) i 的孩子 2i+1、2i+2;父亲 (i-1)/2 90708040506020 层序编号 = 数组下标(第 7 章公式)
堆用「放弃兄弟排序」换来「维护成本极低」——只要最值、不要全序的场景,它是性价比之王。
HANDS-ON DEMO
大根堆调整模拟器
插入随机值后点「单步调整」看它逐层上浮;弹出堆顶后看「末尾元素补位 → 逐层下沉」。琥珀色 = 正在调整的结点,绿色 = 刚完成交换。

9.2 下沉调整与 O(n) 建堆

heap.cpp — siftDown + Floyd 建堆
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);               // 自底向上,叶子天然成堆
}
Floyd 建堆:从 n/2−1 号开始,自底向上逐个下沉
i=2i=1i=0 i=3i=4i=5i=6 第①个调第②个调第③个调(根最后) 叶子无孩子,天然满足堆性质,跳过 为什么是 O(n) 而不是 O(n log n)? 结点越多越靠底层,可下沉的高度越小: Σ 每层结点数 × 层高 ≈ 2n 一半结点是叶子(0 步),1/4 只沉 1 层… 逐个 insert 上浮建堆才是 O(n log n): 一半结点在底层,却要向上爬满全程
下沉建堆让「人多的底层少干活」;上浮建堆让「人多的底层多干活」——方向一反,量级就差一个 log。

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 即得前缀编码(任何码不是别人的前缀,解码无歧义)。

字符权(频率)哈夫曼编码码长
f4501
c121003
d131013
e161113
a511004
b911014

合并顺序: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,保证「调某结点时它的子树已是堆」。
✓ 记忆锚点
插入上浮、删顶下沉;建堆 n/2−1 起步向上走;堆只保父子、不保兄弟;哈夫曼——权大离根近。

9.5 随堂自测

QUIZ 1
Floyd 自底向上建堆的复杂度是 O(n) 而非 O(n log n),根本原因是?
单个结点最坏仍可沉 log n 层(A 错),但这样的结点极少:第 h 层只有约 n/2^(h+1) 个结点、最多沉 h 层,级数求和收敛到 2n。建堆是原地算法(C 错),叶子不调但非叶子全要调(D 错)。
QUIZ 2
堆排序中,把堆顶与当前末尾交换、堆规模减 1 之后,下一步必须做的是?
换上来的是原末尾的小元素,只有「根」这一处可能违反堆性质,两棵子树仍是完好堆——一次 siftDown(0) 即可,O(log n)。重新建堆浪费(A),上浮方向反了(B)。
CHAPTER 10 · 树形结构

红黑树与 B/B+ 树

一句话总览:红黑树用 5 条染色规则实现「近似平衡」(最长路径 ≤ 2×最短),拿更少旋转换稳定 O(log n);B/B+ 树用「多路」把树高压到 3~4 层,让磁盘查找只需 3~4 次 IO——数据库与文件系统的基石。
📖
生活化类比
AVL 是精密天平:稍歪就调,查得快但挪书勤;红黑树是「大体水平」的书架:允许有点歪,但数学保证歪不过一倍,挪书次数少。B+ 树是图书馆的多级目录卡:大厅目录(内部结点)只写「往几楼几区走」,书(数据)全在叶子层,书架之间还有连廊(叶子链表)——借一批连号的书 = 定位起点后沿连廊顺着拿。类比的边界:红黑树的「大体」有严格下界(黑高平衡),不是随便乱放;B+ 树的目录卡一页能写几百条,这才压得低楼层数。

10.1 红黑树:五条规则撑起「近似平衡」

  • ① 结点非红即黑;② 根是黑;③ 叶结点(NIL 空结点)是黑;
  • ④ 红结点的孩子必黑(不存在连续红);
  • ⑤ 任一结点到其所有叶子的路径上,黑结点数相同(黑高 bh 一致)。

推论:最短路径全黑(长 bh),最长路径红黑相间(长 2bh)→ 最长 ≤ 2×最短,树高 ≤ 2log₂(n+1),查找/插入/删除都是 O(log n)。插入默认染红(不破坏⑤),再靠「变色 + 旋转」修复④。

一棵合法红黑树:黑高处处为 2,最长路 ≤ 2×最短路
1381711115252227 最长路:13→17→25→22 黑红黑红 = 4 个结点 最短路:13→8→1→NIL 黑红黑 = 3 个结点 4 ≤ 2×3 ✓ 每条到 NIL 的路径 黑结点数都是 2(含 NIL) 红 8 的孩子 1、11 全黑 ✓ 红 25?不,25 黑 其红孩子 22、27 下面是 NIL(黑)✓ 图中省略 NIL 叶(规则③里的黑色空结点);它同时仍是 BST:中序 1,8,11,13,15,17,22,25,27 有序
红黑树 = BST + 染色约束;「黑高一致」是灵魂,红结点只是允许存在的弹性缓冲。
维度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+ 树:内部结点只指路,数据沉底,叶子手拉手
2040 根页 内部结点只有「键 + 页指针」 一页 16KB 能装几百个键 → 树极矮 <20 20~39 ≥40 51218 222835 445060 数据数据数据数据数据数据数据数据数据 叶子有序链表:WHERE k BETWEEN 12 AND 44 → 定位 12 后沿链顺扫,顺序 IO 任何查找都走到叶子 → 路径等长,性能稳定;3 层 B+ 树(每页几百键)可索引千万级记录,点查仅 3 次页 IO 对比二叉树:log₂(10⁷) ≈ 24 层 = 最坏 24 次磁盘 IO —— 这就是数据库不选二叉树的算术原因
B+ 树的每个设计都对着磁盘的脾气:页要装满(多路)、层高要矮、范围要顺扫(叶链)。
bplus.cpp — 结点即磁盘页
// 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
// 插入:叶子满 → 分裂成两页,中间键上提给父亲(可能连锁到根)
⚠ 高频陷阱:把 B+ 树当 B 树分析
错误认知:「B+ 树内部结点也存数据,查到键就能返回」→ 树高、IO 次数、范围查询分析全错(面试高频翻车点)。正确姿势:B 树数据散布全树、命中即停;B+ 树数据只在叶子,任何查找都必须走到叶子层,内部结点纯索引。顺带:B- 树就是 B 树(横杠是连字符,不是「B 减树」)。
⚠ 红黑树不是严格平衡
别拿 AVL 的 |BF|≤1 去套红黑树——它允许一侧比另一侧长一倍。分析题里「红黑树高度 ≈ log n」要写成「≤ 2log₂(n+1)」,量级相同但常数不同。
✓ 记忆锚点
红黑保黑高,最长不过双倍;B+ 数据沉叶子,叶链范围扫得快;树矮一层,磁盘少读一次。

10.3 随堂自测

QUIZ 1
数据库索引普遍选 B+ 树而不是红黑树,最核心的原因是?
两者查找都是 O(log n),但红黑树是二叉的,千万数据约 24 层 ≈ 24 次页 IO;B+ 树几百路、3~4 层 ≈ 3~4 次 IO,且范围查询沿叶链顺序读。B、C、D 均为事实性错误。
QUIZ 2
红黑树中,根到某叶子路径上有 3 个黑结点(不计 NIL),则根到任何其他叶子的路径上黑结点数是?
性质⑤「黑高一致」:任一结点到其全部叶子的路径黑结点数相同。红结点数量可以不同(这正是路径长度差异的来源),但黑数被钉死——这是红黑树全部平衡保证的根。
CHAPTER 11 · 集合与图

哈希表

一句话总览:哈希 = 用「一次函数计算」直接算出存储地址,把查找从「比较」变成「计算」,平均 O(1);但冲突不可避免(鸽笼原理),工程重点是冲突处理 + 装填因子控制。
📮
生活化类比
快递柜按手机号尾号算柜号:报尾号直接开柜,不用一排排找(计算代替比较)。两人尾号相同 = 冲突:拉链法像柜门上挂一串小钩子,同号包裹全挂这串上;开放定址像「此柜被占,按规则看下一个柜」。装填因子 = 柜子占用率,太满了找空柜要试很久。类比的边界:快递柜可以随便加柜,哈希表扩容却必须全体重新算地址(rehash)——柜号公式里的模数变了,老包裹的柜号全作废。

11.1 哈希函数与冲突

常用除留余数法 H(key) = key % p,p 取不大于表长 M 的质数(减少规律性撞车);还有直接定址、数字分析、平方取中等。好函数两条标准:算得快 + 散得匀。关键字空间远大于地址空间 → 冲突只能管理,不能消灭。

拉链法:同义词挂同一条链(H(k)=k%7)
0123456 桶数组(M=7),每格是一条链的头指针 9 16 9%7=16%7=2 → ∧ 12 12%7=5 → ∧ 查 16:算 H=2 → 沿链比较 2 次命中 平均比较 ≈ 1 + α/2 α = n/M 可以大于 1 删除 = 摘链结点,干净利落
拉链法把「冲突」变成「短链表顺序查找」——链短时依旧近似 O(1),Java HashMap 链过长还会升级成红黑树。
开放定址·线性探测:占位就顺延,堆积会传染
M=10,H(k)=k%10;已存 22、32、42(同义词挤成一片) 22324212? 0123456789 H(12)=2 被占 → 探 3 被占 → 探 4 被占 → 落 5,比较 4 次 一次堆积(primary clustering):同义词片越长,新元素越容易砸进片里,片越长——恶性循环 缓解:二次探测(±1²,±2²…跳着找)、双散列(步长由第二个哈希函数决定)、控制 α ≤ 0.7
开放定址所有元素都住在表内:查找失败的判定是「探到空位」——所以删除绝不能把格子清空。

11.2 装填因子与 rehash

α = 已存元素数 n / 表长 M。拉链法 α 可 > 1(链变长而已);开放定址必须 α < 1,工程上到 0.7~0.75 就扩容 rehash:申请约 2 倍新表,所有元素按新模数重新落位——单次 O(n),摊还到每次插入仍是 O(1)(与动态数组同款分析)。

hash.cpp — 拉链法最小实现
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+ 树 / 平衡树
⚠ 高频陷阱:开放定址直接物理删除
错误写法:删 32 时把 3 号格清空 → 之后查 42:H=2 被占,探 3 遇空位,按规则判「不存在」——42 明明在表里却查不到(静默错误,最阴险的一类 bug)。正确姿势:打墓碑标记(deleted):查找跳过墓碑继续探,插入可复用墓碑位;墓碑多了再整体 rehash 清理。拉链法无此问题,可直接摘链。
⚠ 除留余数的 p 别乱取
p 取偶数或 2 的幂时,地址只由低位决定,奇偶/规律数据会严重偏斜(Java HashMap 用 2 的幂但先做高低位异或扰动,就是为此)。考试默认:p 取 ≤ M 的最大质数。
✓ 记忆锚点
哈希用计算换查找;冲突天注定,拉链或探测;开放删除留墓碑;α 一大就搬家。

11.3 随堂自测

QUIZ 1
开放定址(线性探测)哈希表中,删除元素为什么不能直接清空该槽位?
查找失败的终止条件是「探到空槽」。把中间槽清空,等于在探测路径上挖了个假终点——链后段的元素全部「失踪」。所以要留墓碑:查找跳过、插入可占。
QUIZ 2
拉链法哈希表表长 M=7,已存 14 个元素,装填因子 α 是?
α = n/M = 14/7 = 2。拉链法允许 α > 1(平均链长 2,查找仍近似常数);开放定址的 α 必须小于 1——这是两种冲突方案的本质差别之一。
CHAPTER 12 · 集合与图

并查集

一句话总览:并查集用一个 parent 数组森林回答「谁和谁同伙」:Find 找代表元(根),Union 合并两棵树;按秩/大小合并 + 路径压缩双优化后,单次操作摊还 O(α(n))——逆阿克曼函数,宇宙范围内 ≤ 4,近似常数。
🏢
生活化类比
每人只记「我的直属上级是谁」。问「你的大老板是谁」就沿上级链一路问到顶(Find);两家公司合并 = 一家的大老板认另一家大老板当上级(Union,合并的是老板不是员工)。路径压缩:问过一次后,链上所有人直接把上级改成大老板——下次一步到位;按大小合并:小公司并入大公司,避免链条越接越长。类比的边界:并查集只支持「合并」不支持「分家」——拆集合要换离线删边倒序、可持久化等高级玩法。

12.1 两个操作与两个优化

路径压缩:find(4) 之后,全链直挂根
压缩前:find(4) 要爬 3 层 1234 根(代表元) fa[4]=3, fa[3]=2, fa[2]=1 find(4) 递归回程时 顺手 fa[x]=根 压缩后:下次 find 一步到根 1234 树被拍扁成「一层星形」,之后每次 find 都是 O(1) 压缩的成本摊进本次 find —— 不额外收费
路径压缩是「问路顺便修路」:本次多走的路,变成以后所有人少走的路。
按大小合并:小的挂大的,树高不涨
✓ 小树根挂大树根:高度不变 size 1 → 挂到 size 4 大树高度 3,小树高度 1:合并后仍是 3 ✗ 反着挂:大树塞进小树,高度 +1 反复「大挂小」 可退化成 n 长链 按秩(高度)或按大小二选一即可,配合压缩都是 O(α(n))
两个优化各管一头:按秩合并防「越接越长」,路径压缩防「越查越深」——合体后近似常数。
dsu.cpp — 竞赛标准写法
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 判环、朋友圈/等价类、网格连通块
⚠ 高频陷阱:unite 直接 fa[a]=b
错误写法:不 find 根就把 a 挂到 b 下 → a 原来的整棵子树跟着改姓,但 b 若还有上级,集合关系看似对实则树越接越深;更糟的是把「根挂到非根」接出环,find 无限递归栈溢出。正确姿势:永远 a=find(a); b=find(b); 之后只动根指针。
⚠ 压缩与「按秩」的小别扭
路径压缩会改树高,「秩」就不再是真实高度,只是上界估计——不影响复杂度结论。想省心就按大小合并(size 不受压缩影响),本书代码即此写法。
✓ 记忆锚点
Find 找根顺手压,Union 并根小随大;只合不分,近似常数。

12.2 随堂自测

QUIZ 1
unite(a, b) 的正确做法是?
并查集的合并单位是「树根(代表元)」。A 可能把根挂到非根下,接出深链甚至环;C、D 完全不是并查集的操作语义。
QUIZ 2
同时使用路径压缩 + 按秩合并后,m 次操作的总复杂度是?
双优化的摊还界是 O(α(n)),α 在任何可想象的 n 下 ≤ 4。注意是「摊还近似常数」而非「单次最坏常数」——某次 find 仍可能爬几层,D 的说法过强。
CHAPTER 13 · 集合与图

图的存储与遍历

一句话总览:图 = 顶点 + 边,表达任意 M:N 关系;邻接矩阵用二维数组记「有没有边」,邻接表用链表记「邻居是谁」;DFS 一条道走到黑(栈/递归),BFS 一圈一圈扩(队列)。
🚇
生活化类比
地铁线网图:站点 = 顶点,轨道 = 边。邻接矩阵是一张「任意两站是否直达」的大表格:查任意两站一眼出结果,但 n² 个格子绝大多数是 0,浪费;邻接表是每个站口贴的「相邻站点清单」:省纸,但查「A 和 B 直达吗」得翻 A 的清单。DFS 像探险:能换乘就一直换,走不动才回头;BFS 像水波纹:先逛完 1 站直达圈,再逛 2 站圈。类比的边界:地铁轨道双向通行(无向图),单行道是有向图;换乘有远近票价(带权图/网)。

13.1 术语速览与两种存储

无向图边数 e ≤ n(n−1)/2(取等 = 完全图);有向图看入度/出度。无向图任意两点可达 = 连通;有向图双向都可达 = 强连通。带权图叫网。存储除矩阵/邻接表外,还有有向图的十字链表、无向图的邻接多重表(边只存一份,便于删边)。

同一个无向图:邻接矩阵 vs 邻接表
ABCDE 邻接矩阵:对称,0/1 各半 ABCDE ABCDE 01100 10010 10010 01101 00010 空间 O(n²),查边 O(1) 稀疏图 90% 是 0 → 浪费 邻接表:每顶点一条邻居链 A →B →C →D →E → BC AD AD BCE D 空间 O(n+e),遍历邻居高效;查「A-B 有边吗」要扫链 稀疏图默认选它;稠密图 / 频繁查边选矩阵
无向图矩阵必对称(可压缩存一半);第 i 行 1 的个数 = 顶点 i 的度。有向图则行和 = 出度、列和 = 入度。

13.2 DFS 与 BFS:两套模板

graph.cpp — 邻接表 + 双遍历
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
// 调用次数 = 连通分量个数
HANDS-ON DEMO
BFS 广度优先遍历模拟器
从 A 出发,每点一次「单步」= 出队一个顶点并把它未访问的邻居入队。灰色 = 未访问,琥珀 = 在队列中,绿色 = 已出队访问。注意 D、E 之间有边——看 visited 如何拦住重复入队。

13.3 复杂度与用途对照

维度DFSBFS
数据结构栈(递归即系统栈)队列
时间(邻接表 / 矩阵)O(n+e) / O(n²)O(n+e) / O(n²)
空间O(最深递归深度)O(最宽一层)
擅长连通性、环检测、拓扑排序、路径枚举无权图最短路、层数/距离、最少步数
⚠ 高频陷阱:BFS 出队时才标记 visited
错误写法:出队才置 vis → 同一顶点被多个邻居重复入队,队列膨胀、重复访问,稠密图上直接退化成指数级冗余(静默性能灾难)。正确姿势:入队瞬间就标记——队列里的每个顶点都是「已预约」,别人再来直接跳过。DFS 同理:进递归就标记,别等回溯。
⚠ 别忘了外层循环
图可能不连通:只从 0 号点跑一次遍历,其他连通分量全漏。标准写法是 for (u : 所有顶点) if (!vis[u]) bfs(u);——顺带数出连通分量个数。
✓ 记忆锚点
稠密矩阵稀疏表;DFS 栈、BFS 队;BFS 入队即标记;无权最短路,层数即答案。

13.4 随堂自测

QUIZ 1
n 个顶点、e 条边的图用邻接表存储,BFS 的时间复杂度是?
每个顶点进出队一次(O(n)),每条边在其端点出队时被检查(无向图两次,O(e))。O(n²) 是邻接矩阵版本的复杂度——存储结构决定遍历成本。
QUIZ 2
BFS 能求「无权图单源最短路」的根本原因是?
第 k 层出队的顶点,恰好是「最少 k 条边可达」的顶点——更短的路若存在,早在更浅的层就访问过它了。BFS 用普通队列、不排序、非递归;带权图最短路要交给 Dijkstra(第 14 章)。
CHAPTER 14 · 集合与图

最小生成树与最短路

一句话总览:最小生成树用 n−1 条边连通全部顶点且总权最小——Prim「长顶点」适合稠密图,Kruskal「挑边 + 并查集」适合稀疏图;最短路里 Dijkstra 贪心锁定(禁负权),Floyd 三重循环 DP 一次算出所有点对。
🔌
生活化类比
给 n 个小区铺光纤,要求全连通且线材最省 = MST。Kruskal:把线材按价格从便宜到贵试铺,两端已在同一张网里就跳过(否则成环浪费)——「是否同网」正是并查集的拿手戏。Prim:从一个小区起家,每次把「离现有网络最近的未入网小区」拉进来。最短路像导航:Dijkstra 每次锁定「当前最近的未锁定路口」,再去更新它邻居的预估距离(松弛)。类比的边界:若存在「负过路费」(负权边),已锁定的路口可能事后更便宜——贪心的「锁定即最优」前提崩塌,得换 Bellman-Ford。

14.1 Prim vs Kruskal:同一棵树,两种长法

同一张网:Prim 从 A 生长 / Kruskal 按边权挑(MST 总权 = 9)
Prim:顶点集合逐步扩张(O(n²),稠密图) ABCDE 2①1②4③2④ 356 每轮选「一端在网内、一端在网外」的最小边:2→1→4→2 Kruskal:边排序 + 并查集判环(O(e log e),稀疏图) ABCDE 2✓1✓4✓2✓ 3✗环5(停)6(停) 按权试边 1,2,2,3,4…:A-C 两端已连通 → 弃;凑满 n−1=4 条即停
两种贪心殊途同归:总权都是 9。边权互异时 MST 唯一;有相等边权时树形可能不同,但最小总权唯一。

14.2 Dijkstra:锁定 + 松弛

Dijkstra 从 S 出发:每轮锁定最小 dist,再松弛邻居
SABCT 251623 dist=0 🔒2 🔒3 🔒(5→3)5 🔒(8→5)8 🔒(12→8) 锁定顺序:S(0)→A(2)→B(3)→C(5)→T(8) 松弛:dist[v] = min(dist[v], dist[u] + w(u,v)) B 原估 5,经 A 只要 2+1=3 → 改 C 原估 8,经 B 只要 3+2=5 → 改 前提:边权非负! 否则「锁定即最优」不成立 朴素版 O(n²);堆优化 O((n+e)log n)
Dijkstra = BFS 的带权推广:BFS 用队列按「边数」分层,Dijkstra 用最小 dist 按「距离」分层。
dijkstra.cpp — 朴素 O(n²) 版
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:所有点对,三层循环

floyd.cpp — 中转点 DP
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 行,多源首选
⚠ 高频陷阱:Floyd 把 k 写进内层
错误写法:for i → for j → for k → 算出来的只是「直达或一步中转」的局部最优,多跳路径永远松弛不出来,结果静默偏大(样例小时还看不出)。正确姿势:k 是 DP 的「阶段」,必须最外层——先允许借道 0,再允许借道 0,1……逐阶段放开。
⚠ Dijkstra 遇负权必翻车
负权边会让「已锁定」的点事后更便宜,而 Dijkstra 永不反悔 → 答案错误。负权单源用 Bellman-Ford(O(n·e),还能检测负环);口诀:Dijkstra 贪心不回头,负权请绕道。
✓ 记忆锚点
Prim 长点、Kruskal 挑边(并查集判环);Dijkstra 每轮锁最近;Floyd 的 k 在最外;负权不贪心。

14.4 随堂自测

QUIZ 1
Kruskal 算法判断「加入这条边会不会成环」,最高效的配套结构是?
「两端是否已连通」正是并查集的定义域操作,双优化后近似 O(1)。用 DFS 每次判环要 O(n+e),整体退化——这就是第 12 章并查集的头号实战场景。
QUIZ 2
Dijkstra 不能处理负权边的根本原因是?
非负权保证「绕远路不会更便宜」,锁定才安全;负权让后走的路可能反超,而 Dijkstra 不反悔。负权与环无必然关系,队列也照常存负数——错的是贪心前提,不是实现细节。
CHAPTER 15 · 集合与图

拓扑排序与关键路径

一句话总览:拓扑排序把 AOV 图排成「所有前驱都排在前面」的线性序列(有环则排不出);关键路径在 AOE 网上找「决定总工期的最长链」——拖它一天,整个项目晚一天。
🎓
生活化类比
大学培养方案就是 AOV 图:先修高数才能修数据结构。拓扑排序 = 排一张四年课表,保证每门课开课时先修课都已修完;没有依赖的课(体育、选修)随时可插——所以合法课表不止一份。关键路径像装修流程:水电→泥工→油漆一环扣一环,最长的那条工序链决定交房日期;给不关键的工序加人手,交房日期纹丝不动。类比的边界:课表允许并行上课(多个入度 0 同时可选),关键路径也可能不止一条。

15.1 拓扑排序:入度表剥离法(Kahn)

Kahn:反复摘「入度 0」的点,摘不动还有剩 = 有环
C1C2C3C4C5C6 入度0入度02112 一种合法拓扑序:C1 C2 C3 C4 C5 C6(C1/C2、C4/C5 可互换 → 不唯一) 轮次 摘出  剩余入度变化 ①  C1,C2 C3: 2→0 ②  C3   C4: 1→0, C5: 1→0 ③  C4,C5 C6: 2→0 ④  C6   全部摘完 ✓ 无环 若某轮无入度 0 可摘、仍有点剩: 剩下的点互相等待 → 存在环 DFS 版:后序遍历结果逆序即拓扑序
拓扑排序 = 不断「解锁没有前置任务的任务」;它同时是最便宜的有向图判环器。
topo.cpp — 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 的活动是关键活动,串起来就是关键路径(源到汇的最长路,长度 = 总工期)。

AOE 网:红色关键路径 V1→V3→V4→V5,总工期 9
V1V2V3V4V5 ve/vl=0/03/42/26/69/9 a1=3a2=2a3=2a4=4a5=3a6=3 活动 e l l−e(余量) a1  0 1 1 a2  0 0 0 ← 关键 a3  3 4 1 a4  2 2 0 ← 关键 a5  6 6 0 ← 关键 a6  3 6 3 ve 正向取 max:V4 = max(3+2, 2+4) = 6 vl 逆向取 min:V2 = min(6−2, 9−3) = 4 关键路径 = 最长路(2+4+3=9):a2、a4、a5 零余量,拖一天全局晚一天;a1 有 1 天缓冲
「最短工期」由「最长路径」决定——因为所有分支都必须完成,慢的那支说了算。
⚠ 高频陷阱:以为压缩任何活动都能提前完工
错误决策:给余量 3 天的 a6 加人赶工 → 总工期纹丝不动(白花钱);更隐蔽的是:把关键活动 a4 压缩 2 天后,关键路径可能换人——原来的次长链变成新关键链,继续压 a4 又白干。正确姿势:只压关键活动,且每压一步重算关键路径;多条关键路径并存时要同时压。
⚠ 拓扑序不唯一 ≠ 有环
同一轮有多个入度 0 的点,选谁先出都合法(队列换优先队列可得字典序最小)。判环的唯一标准:输出顶点数 < n。另外拓扑排序只对有向图有意义,无向图有边即「环」。
✓ 记忆锚点
拓扑:入度 0 逐个剥,剥不完必有环;关键路径是最长链,零余量才关键;ve 正向 max,vl 逆向 min。

15.3 随堂自测

QUIZ 1
Kahn 拓扑排序结束后,输出的顶点数少于 n,说明?
环上的每个点都在等环内前驱,入度永远减不到 0,谁也进不了队——这正是拓扑排序兼职判环的原理。不连通、多源点都不影响「全部输出」。
QUIZ 2
关于 AOE 网的关键路径,正确的是?
所有分支都要完工,总工期由最慢的链(最长路)决定;只有零余量的关键活动影响工期,且关键路径可以并列多条。A 把最长记成最短,B 忽略余量,D 忽略并列。
CHAPTER 16 · 查找排序与进阶

查找算法总览

一句话总览:查找的成本取决于「数据被组织成什么样」:无序只能顺序 O(n);有序 + 顺序存储才能折半 O(log n);分块是折中与索引思想;树表/哈希则是把「组织」做到极致。
📖
生活化类比
查字典:顺序查找 = 从第一页翻起;二分查找 = 翻中间,目标拼音更靠前就撕掉后半本再翻中间——字典「按拼音排好 + 能直接翻到任意页」正是二分的两个前提。分块查找 = 先看侧面的字母凸标(块间有序),定位到区块后块内逐页翻(块内无序)。类比的边界:换成「卷轴」就翻不了中间——链表定位中点要顺着爬,二分立刻失效;字典若没排序,翻中间毫无信息量。

16.1 二分查找:区间折半的艺术

在 11 个有序数中找 31:每轮砍掉一半候选
a = [3, 9, 15, 22, 31, 47, 58, 66, 79, 88, 95],闭区间写法 [lo, hi] 第1轮第2轮第3轮第4轮 39152231475866798895 39152231 2231 31✓ lo=0 hi=10 mid=5:47>31 → hi=4 lo=0 hi=4 mid=2:15<31 → lo=3 lo=3 hi=4 mid=3:22<31 → lo=4 lo=4 hi=4 mid=4:命中!共 4 次比较 ≈ log₂11 虚线 = 已被排除的候选(每轮至少砍一半)
二分的本质是「每次比较排除一半」——前提是数据有序且能 O(1) 跳到中点。
bsearch.cpp — 两种区间约定
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) / 2
错误写法:lo、hi 都接近 int 上限时,lo+hi 溢出变负数 → 数组负下标越界,崩溃或读脏数据(Java 官方库曾潜伏此 bug 二十年)。正确姿势:mid = lo + (hi - lo) / 2,数学等价但永不溢出。另一坑:区间约定 [lo,hi] 与 [lo,hi) 的循环条件、收缩写法必须从一而终,混搭 = 死循环或漏解。
✓ 记忆锚点
二分三前提:有序、顺序存、随机访问;mid 用减法防溢出;区间约定从一而终。

16.3 随堂自测

QUIZ 1
二分查找无法高效用于「有序单链表」,原因是?
二分 = 每轮 O(1) 跳中点 + 一次比较。链表跳中点要爬半条链,总复杂度退化回 O(n)。有序性、可比较性链表都有;表长也无需是 2 的幂。
QUIZ 2
把 mid = (lo + hi) / 2 改写成 mid = lo + (hi - lo) / 2 的主要目的是?
两式数学等价(都向下取整),但前者在大下标时加法溢出变负,后者先做差永远安全。速度与取整方向不变,升降序由比较方向决定,与此无关。
CHAPTER 17 · 查找排序与进阶

内部排序全景

一句话总览:八大排序分五族——插入、交换、选择、归并、分配;背下「复杂度 + 稳定性」总表,吃透快排划分与归并合并两个核心动作,其余都是变体。
🃏
生活化类比
整理一手扑克:插入排序 = 每摸一张,插进左手已理好的牌里(摸牌即排序);选择排序 = 每次从乱牌堆里挑最小的放到末尾;快排 = 抽一张当基准,小的甩左边大的甩右边,两堆各自递归;归并 = 先把小堆理好,再「两堆顶牌比大小,小的先出」合成大堆。稳定性 = 两张同点数的牌保持原来的先后——多关键字排序(先按点数、再按花色排)全靠它。类比的边界:手牌少时插入最快(n 小系数说了算),这正是快排小区间切插入的原因。

17.1 快排:一趟划分定一个「最终位」

挖坑法划分:pivot=42,一趟之后 42 落到最终位置
初始 [42, 17, 88, 6, 55, 31, 73],pivot 挖出,坑在左端;j 从右找小,i 从左找大 坑17886553173 pivot = 42 j 左移遇 31<42 → 填左坑;i 右移遇 88>42 → 填右坑;再遇 6<42 → 填坑;i==j 收工 一趟结束:pivot 归位,左 ≤ 42 ≤ 右 3117642558873 42 已在最终位置(下标 3);左右两段各自递归 —— 平均 log n 层 × 每层 O(n) = O(n log n)
快排的「快」来自每趟把 pivot 送到最终位并大致对半分;「险」来自划分可能极度不均(见陷阱)。
quick.cpp — 挖坑法快排
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 归并:两个有序段的拉链合并

2-路归并:顶牌比大小,小的先出(≤ 保稳定)
左段已排序 [17, 42, 88],右段已排序 [6, 31, 55, 73] 1742886315573 i→17 与 j→6 比:6 小先出;再比 17 与 31:17 出;再比 42 与 31:31 出 … 6173142557388 合并一趟 O(n),共分治 log n 层 → 稳定 O(n log n);代价:O(n) 辅助数组 关键细节:a[i] ≤ a[j] 时先取左边 —— 相等元素左段在前,稳定性就靠这个 ≤
归并把「排序」拆成「分治到单元素 + 层层拉链合并」,每层都是线性扫描,量级稳稳 n log n。
merge.cpp — 合并两个有序段
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 后面。

⚠ 高频陷阱:固定首元素 pivot 遇上有序输入
错误配置:pivot 恒取 a[lo] 且输入已升序 → 每趟划分出 0 与 n−1 的极端偏斜,退化成 O(n²),递归深度 n 直接栈溢出(实测大数组有序数据是快排杀手)。正确姿势:随机 pivot / 三数取中;小区间(n<16)切插入排序;内省排序(introsort)再兜底:递归深度超限转堆排(C++ std::sort 的做法)。
✓ 记忆锚点
不稳定四兄弟「快选希堆」;n log n 三剑客「快堆归」;基本有序用插入,要稳定用归并,磁盘排序用归并的多路版。

17.4 随堂自测

QUIZ 1
下列哪组排序全部不稳定?
口诀「快选希堆」不稳定:它们的长距离交换/筛选会打乱相等元素的原始次序。冒泡、插入、归并、基数都稳定——A、C 全稳定,D 混进了稳定的归并和冒泡。
QUIZ 2
输入已经升序,pivot 固定取首元素时,哪个算法反而退化到 O(n²)?
有序输入让固定首 pivot 每趟只剥离一个元素,划分 0 : n−1,递归 n 层 → O(n²)。插入排序遇有序反而是 O(n) 最好情况;归并、堆对输入顺序不敏感,恒 O(n log n)。
CHAPTER 18 · 查找排序与进阶

进阶结构与外部排序

一句话总览:Trie 用「共享前缀」换 O(串长) 查询,线段树把区间统计压到 O(log n),跳表用「多级索引」让链表跑出平衡树速度,布隆过滤器用位数组回答「一定不在 / 可能在」;数据装不进内存时,外部归并排序的胜负手是磁盘 IO 次数。
🚄
生活化类比
跳表是地铁的快慢车系统:普通链表是站站停的慢车,架几层「快车线」就能大段跨越,坐过站再降层换慢车精确定位——期望 O(log n)。布隆过滤器是门卫的「黑名单印象」:他说「没见过你」→ 你肯定不在名单上;他说「好像见过」→ 可能认错人(多人特征叠在同一格)。类比的边界:门卫不能「忘掉一个人」——清掉某格特征会误伤共享这格的其他人,所以布隆不支持删除;快车线层数是抛硬币随机决定的,不是精密设计。

18.1 Trie:前缀的共享高速公路

Trie 存 {app, apple, api, to, top}:绿圈 = 单词终点
apple itop 根 app★le★ i★to★p★ 查 "apple":沿 a→p→p→l→e 走 5 步 复杂度 O(串长),与词库多大无关! "app" 是 "apple" 的前缀 → 共享前 3 结点 走到 p★ 但没到终点标记 → 只是前缀不是词 应用:搜索框自动补全、敏感词过滤、词频统计
Trie 把「比较关键字」换成「沿字符走路径」——哈希做不到的前缀查询,它天生就会。
trie.cpp — 26 叉字典树
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 跳表与线段树

跳表查 13:高层快车跨越,低层慢车精确定位
L2 L1 L0 19 1391317212531 1391317212531 红线:1 →(L2)→ 9 → 降层 →(L1)→ 13 命中,3 步;纯链表要 4 步,数据大时差距是 log n vs n 每结点层数抛硬币决定(p=1/2)→ 期望 O(log n);插入删除只改局部指针,无需旋转,并发友好(Redis zset)
跳表 = 链表 + 随机多级索引:用「概率平衡」替代「强制平衡」,实现简单一个量级。
ℹ 线段树 & 布隆过滤器速览
线段树:每个结点管一个区间 [l,r],存区间和/最值;单点修改与区间查询 O(log n),区间修改靠懒标记(先记账、查询路过时才下传)——区间统计问题的瑞士军刀。布隆过滤器:m 位 bit 数组 + k 个哈希函数,插入置 k 位,查询看 k 位是否全 1。说「不在」绝对准,说「在」可能误判(别人的位凑巧全被你撞上);不支持删除(计数版可解);用于缓存穿透拦截、爬虫 URL 去重、LSM-tree 减少无效磁盘读。

18.3 外部排序:IO 才是货币

数据远大于内存:① 分批读入内存排序,写出若干初始归并段(置换选择法可产出平均 2 倍内存长的段);② k 路归并:每轮从 k 个段头挑最小输出——用败者树选最小只需 O(log k) 次比较;③ 段太多就多趟归并,每趟都要读写全部数据一遍。所以优化目标是减少归并趟数:增大 k、用置换选择减少段数、按最佳归并树(哈夫曼思想:短段先合并)安排顺序。

⚠ 高频陷阱:拿布隆过滤器当「存在证明」
错误用法:布隆说「在」就直接放行 / 直接查库命中返回 → 误判率随元素增多悄悄上升,业务把「可能在」当「一定在」,出现幽灵命中;再有人手动清位「删除」→ 共享该位的其他元素被误判成「不在」(假阴性,布隆唯一的绝对承诺被破坏)。正确姿势:只用它做「一定不在」的快速拦截;「在」必须回源确认;删除用计数布隆或定期重建。
⚠ 跳表是「期望」不是「最坏」
层数随机,理论上存在全 1 层的极端(概率天文级小)。答题写「期望 O(log n)」;要最坏保证就选红黑树/AVL。工程上 Redis 选跳表正是看中:实现简单、范围查询顺链走、并发改造容易。
✓ 记忆锚点
Trie 走前缀,线段树管区间,跳表坐快车,布隆只敢说不;外排看 IO,败者树挑最小,短段先归并。

18.4 全书收官:选型速查

你的需求首选结构一句话理由
键值点查,不要顺序哈希表平均 O(1),计算换比较
有序 + 范围查询(内存)红黑树 / AVL中序有序,log n 保证
有序 + 范围查询(磁盘)B+ 树树矮 IO 少,叶链顺扫
前缀补全 / 词库TrieO(串长),与词量无关
区间统计 / 区间修改线段树log n 查询 + 懒标记
动态连通 / 判环并查集近似常数合并与查询
随时取最值 / Top-K堆(优先队列)根即最值,调整 log n
「是否存在」允许误报布隆过滤器位数组极省内存,只否认不肯定
内存装不下的排序外部归并 + 败者树趟数最少 = IO 最少
✓ 全书主线
逻辑结构定关系,存储结构定代价,运算频率定选型——没有最好的结构,只有最合身的权衡。恭喜你走完 18 章,数据结构的地基已经打牢。

18.5 随堂自测

QUIZ 1
布隆过滤器能给出的「绝对可靠」结论是?
k 个位只要有一个 0,说明从未被任何元素置过 → 必然没插入过(无假阴性)。反之 k 位全 1 可能是别人凑出来的(有假阳性);清位删除会误伤共享位,标准布隆不支持删除。
QUIZ 2
外部排序优化的首要目标是?
磁盘读写比内存比较慢几个数量级,每趟归并都要完整读写一遍数据——趟数才是成本大头。败者树省比较正是为了在同样 IO 下支撑更大的 k;稳定性与零内存都不是外排的优化目标。
渝ICP备2026024724号-1