CS106B 编程抽象：C++ 实现与算法图解

资料基础：斯坦福 CS106B 官方课程网站（2026 夏季学期，8 周压缩学期，共 28 讲）全部公开页面——课程主页、Syllabus、讲座页（含各讲文字讲义与公开附件）、作业页等。完整调研记录见同目录 00_research_inventory.md（及 lecture_data_records.json 数据记录）。 版权与用途声明：官方材料 © Stanford University，受保护、不得擅自传播。本文档是自学整理笔记：将 28 讲公开内容按主题重组成 17 章，讲解均为原创中文表述，未逐字转载任何官方讲义；全部代码为本笔记撰写的教学示例（现代 C++17、仅用标准库），并非课程作业提交物。 学习建议：每章先读“概述”，再看“核心概念与算法原理”里的图示/步骤分解，然后亲手把代码敲一遍并运行，最后用“思考题”自测。链表、二叉树、堆、图这几章强烈建议边读边在纸上画内存/结构图。

课程概览

这门课是什么？

CS106B（Programming Abstractions，编程抽象）是斯坦福入门编程序列的第二门课。先修 CS106A 用 Python 建立了编程方法论与问题求解基础；CS106B 在此基础上做三件大事：

1. 学一门新语言：C++（类型系统、函数、字符串、类、指针与动态内存）；
2. 掌握编程抽象：认识“抽象数据类型”(ADT)——把“用什么”与“怎么实现”分开，先会用（客户端视角），再自己实现（实现者视角）；
3. 吃透经典数据结构与算法：线性表、栈、队列、集合/映射、树、堆、哈希表、图，以及递归、回溯、分治、贪心（Dijkstra、霍夫曼）、复杂度分析（大 O）。

官方 syllabus 给的主题推进顺序（“近似顺序”）正是本文档 17 章的骨架：

C++ 基础 → 数据抽象与经典 ADT → 递归与回溯 → 类与面向对象 → 指针与动态内存 → 链式数据结构 → 进阶算法

与 CS106A 的衔接

• CS106A 结业水平 = 能写多函数程序、会用循环/条件/列表/字典、理解基础测试。CS106B 不重复教编程入门，而是以“你会写程序”为前提，快速补 C++ 语法差异后直接进入抽象与算法。
• Python 经验迁移要点：列表→std::vector、字典→std::map/std::unordered_map、集合→std::set/std::unordered_set、字符串 API 差异大（C++ 字符串可原地修改）、一切传参默认按值拷贝（要显式写 & 引用）。这些差异会在 Lecture 1–3 反复强调。

官方课程要点（摘自 syllabus，概括）

• 教学团队：讲师 Sean（Szumlanski）、Head TA Butch、14 名 section leaders；小班讨论每周一次、占 5%。
• 节奏与考核：8 周、28 讲（MTWTh 13:30–14:45，NVIDIA Auditorium）；作业 25% + 期中 27.5% + 期末 37.5% + 小班 5% + 讲座小测 4% + Quiz0 1%；期中 7/17、期末 8/14（纸笔）。
• 作业（8 个，约每周一个，10–20 小时/个）： | # | 名称 | 覆盖主题（对应章节） | |—|—|—| | 0 | Welcome to CS106B! | 环境与工具 | | 1 | Getting Your C++ Legs | C++ 基础、字符串（L1） | | 2 | Fun with Collections | 栈/队列/集合/映射等 ADT（L2–L3） | | 3 | Recursion Etudes | 递归（含分形）（L5） | | 4 | Recursive Backtracking | 回溯（L6） | | 5 | Tone Matrix | 类/数组/动态内存（L8–L9） | | 6 | Listy Things | 链表与树（L11–L12） | | 7 | Huffman Coding（选做🌱） | 霍夫曼编码（L13） |
• 工具：Qt Creator（编辑器+编译器）+ Stanford C++ Library（课程专用容器库，文档公开：web.stanford.edu/dept/cs_edu/resources/cslib_docs/）。本文档代码一律用标准库 std:: 容器（等价关系见文末速查表），保证你能在任何现代 C++ 环境编译运行。
• 教科书：Eric Roberts, Programming Abstractions in C++（第 5 版），ISBN 978-0133454840。
• 学习目标（概括）：乐于用编程解决现实问题；识别常见抽象；理解日常技术背后的程序化概念；能用递归/算法推理拆分复杂问题；能评估数据结构与算法的设计取舍。

学习路线：真实 28 讲 ↔ 本文 17 章

官方 2026 夏季学期 28 讲实际顺序如下。本文档按官方教学顺序把它重组成 17 章主题笔记（每章开头标注“对应真实讲座 Lxx–Lyy”），数字编号即学习顺序：

（L28 Wrap 为期末回顾，无新主题。）

笔记约定

• 每章统一结构：概述 → 核心概念与算法原理 → 代码示例与实现详解（代码做什么 / 实现机制解说）→ 复杂度分析 → 关键要点 → 常见陷阱与注意事项 → 思考题（带答案）。
• ASCII 图一律放在 text 代码块中；cpp 代码块可直接复制编译。
• 术语采用“中文（English）”或“English（中文）”双语标注，方便对照原版材料。

Lecture 1: C++ 基础回顾与 STL 容器入门（C++ Fundamentals & STL Containers：Syntax, Functions, std::string, Vector & Grid, Testing）（对应课程真实讲座 L01–L04）

概述

本讲是 CS106B 的“开机课”：把大家从 CS106A 的 Python 世界平稳地接进 C++，先讲清一门语言的两副面孔——语法与语义——再讲程序从源码到运行的全过程，然后系统复习变量、循环、分支、函数、字符串等基础构件，最后引入第一批“抽象数据类型（Abstract Data Type，ADT）”容器 Vector 与 Grid，并介绍函数分解与单元测试的思想。全讲为后续栈、队列、集合、映射等容器铺好语言地基。 对应官方 L01（6/22，Welcome!）、L02（6/23，C++ Fundamentals）、L03（6/24，C++ Strings）、L04（6/25，Testing, Vectors, and Grids）四讲。

核心概念与算法原理

1. 语法 vs 语义、编译与执行

问题定义：新手学 C++ 常把“编译器报不报错”和“程序对不对”混为一谈，需要先分清两个层面。 直观解释：语法（syntax）是“怎么说才合规矩”，语义（semantics）是“这句话到底什么意思”。就像中文句子“把书放上书架”语法正确，但语义上我们明白说的是“放上书架的那本书”，而不是“放一个书架上坐着的人”。官方在第 2 讲正是用这种自然语言的例子引入这对术语。 步骤分解：写代码时先满足语法（编译器才肯放行），再保证语义（程序才做对的事）。语法错误在编译期被揪出来；语义错误往往要等到运行期甚至悄悄潜伏。

问题定义：C++ 源码是如何变成可运行程序的？ 直观解释：编译器（compiler）是一个“翻译程序”：把整份 C++ 源码一次性翻译成机器能执行的指令；这与 Python 的解释器（interpreter）逐行边翻译边执行的方式不同（官方第 2 讲对比过这一点）。

hello.cpp(源码,人写的)
   │  ① 预处理:展开 #include
   ▼
   │  ② 编译(compiler):逐行检查语法,翻译成机器指令
   ▼
可执行文件(机器指令,0 和 1)
   │  ③ 操作系统加载它,并从 main() 开始执行
   ▼
屏幕输出:Hello, world!

操作要点：编译期错误（compile-time error，多为语法/类型问题）在点“运行”之前就会被报告；运行期错误（runtime error，如越界崩溃）则发生在程序真正跑起来之后。

2. main、注释、#include、命名空间、cout/endl

• 问题定义：每个 C++ 程序都需要一个统一的“入口”和一套“打招呼”的仪式。
• 直观解释：main() 是唯一特殊的函数——程序一启动就自动调用它，无需任何人手动调用；一个没有 main() 的程序无法通过编译（官方第 2 讲强调“main is special”）。main() 最后 return 0; 表示“零错误”，这个值会交还给操作系统。
• 步骤分解：#include <库名>（标准库用尖括号）把别人写好的库“搬”进来；using namespace std; 让我们不必在每个标准库名字前敲 std::；cout << 内容 << endl; 向屏幕输出，endl 负责换行。注释分两种：// 单行注释与 /* ... */ 块注释，注释是写给人的，编译器完全忽略。
• 一句话注明：课程官方在 L01/L02 使用 #include "console.h" 弹出课程专用终端，其输出机制等价于标准库 <iostream> 的 std::cout。

3. 变量与数据类型、未初始化陷阱

问题定义：C++ 是强类型语言——每个变量必须先声明、带一个固定类型，之后不能改类型。 直观解释：变量像贴了标签的储物盒，标签（类型）决定盒子里能放什么形状的东西。常用类型：int（整数）、double（浮点数）、char（单字符，单引号）、bool（真假）、string（字符串，双引号）。 步骤分解：int a = 5; 声明并初始化；之后改值只需 a = 7; 而不能再写 int a = 7;（那是重复声明，报错）。 关键陷阱（官方第 2 讲专门点名）：基本类型变量若不初始化，里面装的是“垃圾值”（garbage）——C++ 不会自动帮你清零；唯一的例外是 string，默认自动初始化为空串 ""。大多数编译器会放行未初始化代码，但结果是不可预测的，务必养成“声明即初始化”的习惯。

4. 循环：while / for / range-for

问题定义：如何反复执行同一段逻辑？ 步骤分解：

• while (条件) { ... }：先判断再执行，条件为假就退出；记得在循环体里推进条件，否则死循环。
• for (int i = 0; i < n; i++) { ... }：把“初始化、条件、步进”收拢到一行，适合“按次数/按下标”遍历。i++ 是 i = i + 1 的简写。
• range-based for（又称 for-each）：for (char ch : s) { ... } 直接“逐个掏出元素”，无需下标。适合 vector、string、set 等容器；代价是拿不到当前下标。

5. 分支与布尔逻辑、短路求值

问题定义：如何让程序“看情况行事”？ 步骤分解：if (条件) ... else if (条件) ... else ...。比较运算符 == != < <= > >=；布尔运算符 &&（且）、||（或）、!（非）。 机制要点（短路 short-circuiting）：&& 左侧为假时右侧根本不会执行；|| 左侧为真时右侧也不会执行。这个特性常被用来“先安检再动手”，例如先检查下标合法再访问数组：if (i >= 0 && i < v.size() && v[i] > 0)——若 i 越界，后面的 v[i] 压根不会被访问，从而避免崩溃。官方第 2 讲还提醒过常见笔误 if (numCupcakes == 1 || 2)，这里的 2 恒为真，条件永远成立。

6. 函数：原型、传值 vs 传引用

问题定义：把一段逻辑命名并复用，同时明确它“吃什么（参数）、吐什么（返回值）”。 直观解释：C++ 编译器从上往下逐行看代码，所以调用一个“还没见过”的函数会报错。两种解法（官方第 3 讲）：把函数定义挪到 main() 之前；或在其上方放一个函数原型（prototype）——即“函数签名 + 分号”，例如 int square(int x);，相当于提前告诉编译器“这个函数长什么样，具体实现稍后见”。 关键区分（传值 vs 传引用）：默认是传值（pass-by-value）——调用时把实参拷贝一份给形参，函数里改的是副本，外面的变量毫发无损；若形参写作 int& n（传引用，pass-by-reference），形参就成了指向实参的“虫洞/传送门”，函数里动它等于直接动调用者的变量。传引用还有第二个动机：容器可能很大，逐元素拷贝既费时又费内存，引用只花几十比特建立“纽带”。官方第 3 讲用“倒空海盗宝藏”的比喻演示了两种传参的天壤之别（传值清空不了原宝藏，传引用可以）。

内存示意（左侧传值、右侧传引用）：

传值:                       传引用:
main() 的 n [ 3 ]           main() 的 n [ 4 ]
foo() 的 n  [ 3→4 ](副本)    foo() 的 n ──虫洞──► main() 的 n

7. std::string：对象、成员函数与逐字符处理

问题定义：文本处理是编程日常，需要一套趁手的字符串工具。 直观解释：C++ 的 string 不是基本类型而是对象：它内部是一块连续存放字符的内存（本质是字符数组），同时“随身携带”一批现成函数，用点号 . 调用，称为成员函数（member function）。它与 Python/Java 的一大不同是可修改（mutable）：s[0] = 'Y' 能直接改掉第 0 个字符。 常用成员函数：s.length()（字符个数）、s[i]（按下标读写字符）、s += "xx" 或 s + t（拼接）、s.substr(起点, 长度)（截子串）、s.find(子串)（返回首次出现下标，找不到返回 string::npos）、s.insert(位置, 文本)、s.erase(位置, 长度)、s.replace(位置, 长度, 新文本)。

字符串 "hello" 的内存布局(数组本质):
+----+----+----+----+----+
|'h' |'e' |'l' |'l' |'o' |
+----+----+----+----+----+
  0    1    2    3    4     ← 下标从 0 到 length()-1

逐字符遍历：用普通 for 按下标 s[i] 访问（可改），或 range-for 取出每个 char 副本（只读遍历更简洁，但拿不到下标、也改不了原串）。

8. 字符处理：ASCII 与 cctype、类型转换

问题定义：字符在计算机里只是数字，需要一套“字符—数字”对照表和现成的判断函数。 直观解释：char 背后就是整数——'A' 是 65，'a' 是 97，'0' 是 48（这就是 ASCII 标准）。所以字符可以比较大小、做算术，也可以用函数式类型转换 int(ch) 把它“现出原形”。 步骤分解：<cctype> 库提供一族的 isXxx(ch) 判断函数：isalpha（字母）、isdigit（数字）、isupper/islower（大小写）、isspace（空白）等，以及转换函数 toupper(ch)/tolower(ch)（注意它们是传值：返回新字符，不改原变量）。 风格要点（官方第 3 讲）：别把 96、65 这类“魔数（magic number）”直接写死在代码里——int(ch) - ('a' - 1) 比 int(ch) - 96 自解释得多。能用 isalpha 等库函数表达意图时，就不要再手写 ch >= 'a' && ch <= 'z' 这种比较。

9. Vector：顺序容器、扩容、add vs insert(0,·)

问题定义：需要一个能自动伸缩、按下标快速访问的“列表”。 直观解释：Vector 是“同质、有序、按下标 0..n-1 索引”的容器，底层是连续内存数组——可以类比浏览器的标签页：有先后顺序，能增能减。课程官方使用 Stanford 的 Vector<T>，与标准库 std::vector<T> 等价（官方第 4 讲特意提醒两者大小写不同；本笔记一律用 std 版本）。 常用操作对照：v.push_back(x)（官方 add，末尾追加）、v.insert(v.begin()+i, x)（官方 insert(i,x)，在 i 前插入并右移后续元素）、v.erase(v.begin()+i)（官方 remove(i)，删除并左移）、v.size()、v.empty()（官方 isEmpty）、v[i] 下标访问、v.clear()。

push_back(末尾追加,快):              insert(0,x)(头部插入,慢):
[15][20][18]     加 33             [15][20][18][33]    插入 90
[15][20][18][33]                   [ ][15][20][18][33] ← 先把 4 个元素整体右移
                                   [90][15][20][18][33] ← 再写新值

运行时对比（官方第 4 讲核心实验）：add 只是往末尾“放一个”，偶尔后台扩容一次；insert(0, x) 则每次都要把已有的每一个元素往右挪一格。官方在课上用计时工具实测：规模 5 万时 insert 版比 add 版慢约 17 倍，规模到 50 万时差距膨胀到三百多倍。规模每翻倍，insert 版的工作量也翻倍式增长——这正是下一讲“大 O 记号”要量化的现象。这里的“扩容”概念先记住：vector 满了会申请一块更大的内存并把所有元素拷过去（偶尔发生，均摊后 add 仍是 O(1)），细节留待第 4 讲与实现篇展开。

10. 二维容器：Grid（用 vector<vector> 表示）

问题定义：表格、棋盘、像素图……都需要“行列”二维数据。 直观解释：官方 Grid<T>(行, 列) 就是矩形网格，元素按 g[r][c] 访问（行在前的“row-major”，记忆口诀：row 是“major（主要）”，所以行号永远先写）。用标准库表示就是“vector 的 vector”：std::vector<std::vector<int>> g(rows, vector<int>(cols, 0))——外层是行、内层是列。官方 numRows()/numCols() 对应 g.size() 与 g[0].size()。 遍历方式：双层 for（外层行、内层列）打印；range-for 会按 row-major 顺序把所有元素平铺输出（拿不到行列号）。适用场景：井字棋棋盘、图像像素、乘法表等。

11. 函数分解与测试理念；ADT 概念引入

问题定义：怎么让一段正确但“又长又乱”的代码变得可读、可测、可维护？ 直观解释（官方第 4 讲）：把大任务拆成“各司其职”的小函数叫函数分解（functional decomposition）；函数名用动词短语，变量名有意义，注释只解释“为什么/怎么做”，而不是把代码逐行翻译成英文。好的副产品是：每个小函数都能被独立、严格地测试。 测试理念：官方在 L04 引入 SimpleTest 框架（STUDENT_TEST 写用例、EXPECT_EQUAL 断言、runSimpleTests 批量跑），并展示了为 extractAlpha 设计的“边界场景清单”：全是字母/没有字母/字母在头中尾/空串/长度 1、2、3/超长串……本笔记不引入任何 Stanford 库，用自写的迷你断言函数（见示例 3 附近说明）演示同一思想：对边界条件穷举、断言期望值、一次运行全量验证。 ADT 是什么：抽象数据类型 = “数据 + 允许的操作”打包成的契约。使用者只需知道“能 push 什么、pop 得到什么”，不必关心内部是数组还是链表——这正是官方第 4 讲“先从客户端视角使用、后几讲再亲手实现”的教学路线。

代码示例与实现详解

示例 1：一门 C++ 程序的“骨架课”——变量、三种循环、分支与短路

// 文件: basics_demo.cpp
// 演示: 注释、变量类型、cout/endl、while/for/range-for、if 与短路求值
#include <iostream>   // 标准库用尖括号: 提供 cout/endl
#include <string>     // 提供 std::string(写全可不加,<iostream> 常间接引入,但显式更稳)
using namespace std;  // 免写 std:: 前缀(std = standard 命名空间)

int main()            // 程序的唯一入口,操作系统自动调用它
{
    // (1) 变量: 声明即初始化,类型一旦定下不可更改
    int    age   = 20;        // 整数
    double pi    = 3.14159;   // 浮点数
    char   grade = 'A';       // 单字符必须单引号
    string name  = "Ada";     // 字符串必须双引号
    bool   likesCS = true;    // 布尔

    // (2) cout 输出 << endl 换行(不写 endl 所有输出会黏在一起)
    cout << "Hello, " << name << "!" << endl;
    cout << "age=" << age << ", grade=" << grade << ", pi=" << pi << endl;

    // (3) while: 先判断再执行
    int i = 1;
    while (i <= 3) {
        cout << "count " << i << endl;
        i++;                  // 推进条件,否则死循环
    }

    // (4) for: 初始化/条件/步进三合一;循环变量 j 只在循环内有效
    int sum = 0;
    for (int j = 0; j < 5; j++) {
        sum += j;             // 0+1+2+3+4
    }
    cout << "0..4 之和 = " << sum << endl;

    // (5) range-based for: 逐字符掏出,拿不到下标
    for (char ch : name) {
        cout << "[" << ch << "]";
    }
    cout << endl;

    // (6) if + 短路: age>=18 为假时,&& 右边根本不会执行
    if (age >= 18 && likesCS) {
        cout << "成年,且热爱计算机科学。" << endl;
    } else {
        cout << "条件不满足。" << endl;
    }
    return 0;   // main 返回 0 = "零错误",交还操作系统
}

【代码做什么】：(1) 声明五种常见类型的变量并输出；(2) 用 while 数 1 到 3；(3) 用 for 求 0..4 的和；(4) 用 range-for 把名字逐字打上括号；(5) 用 && 组合两个条件。整体把本讲的“骨架语法”在一份可运行程序里串了一遍。

【实现机制解说】：注意 for (int j = 0; j < 5; j++) 里 j 的作用域只在循环内——出了右花括号 j 就不存在，这是 C++ 的块作用域规则。sum += j 是 sum = sum + j 的简写。age >= 18 && likesCS 演示短路：若 age >= 18 为假，整个表达式立即为假，右侧 likesCS 不再求值——若右侧是 v[i] > 0 这类可能越界的访问，短路正好保护它不被执行。

示例 2：字符串、字符与函数——成员函数、原型、传值 vs 传引用

// 文件: string_func_demo.cpp
// 演示: string 成员函数、逐字符处理、cctype、函数原型、传值与传引用
#include <cctype>    // isspace / toupper 等字符判断与转换
#include <iostream>
#include <string>
using namespace std;

// —— 函数原型区: 放在 main 之前,让编译器先“认识”这些函数 ——
string makeAcronym(const string& phrase); // 取每个单词首字母拼缩写(大写)
int    asciiSum(const string& s);         // 求字符串各字符 ASCII 码之和
void   toUpperInPlace(string& s);         // 引用参数: 就地改成大写

int main()
{
    // (1) string 成员函数: length()/[]/substr()/+= (字符串是可改对象)
    string phrase = "abstract data type";
    cout << "长度: " << phrase.length() << endl;            // 18
    cout << "第 0 个字符: " << phrase[0] << endl;           // 'a'
    cout << "substr(0,3): " << phrase.substr(0, 3) << endl; // "abs"

    // (2) 传 const 引用: 省拷贝且保证不被改动(想改也改不了)
    string acr = makeAcronym(phrase);
    cout << "缩写: " << acr << endl;                        // "ADT"
    cout << "ASCII 码和: " << asciiSum(acr) << endl;        // A=65 D=68 T=84 → 217

    // (3) 传引用: 函数内改动会“穿透”到 main 里的 acr
    toUpperInPlace(acr);   // acr 已是 "ADT",再转一次不变(留作观察点)
    string lower = "hello";
    toUpperInPlace(lower);
    cout << "toUpperInPlace 后: " << lower << endl;         // "HELLO"
    return 0;
}

// —— 函数定义区 ——
string makeAcronym(const string& phrase)
{
    string result;
    bool newWord = true;                 // 下一个字符是否是单词首字母
    for (char ch : phrase) {
        if (isspace(ch)) {
            newWord = true;              // 遇到空白 → 下一个非空白是词首
        } else if (newWord) {
            result += toupper(ch);       // 首字母转大写并拼接(注意: 需 string 打底)
            newWord = false;
        }
    }
    return result;                       // 返回新串,phrase 本身未动
}

int asciiSum(const string& s)
{
    int total = 0;
    for (char ch : s) {
        total += int(ch);                // 类型转换: char 露出 int 真身
    }
    return total;
}

void toUpperInPlace(string& s)           // & 表示引用: 形参是实参的别名
{
    for (int i = 0; i < (int)s.length(); i++) {
        s[i] = toupper(s[i]);            // 逐个字符原地改写(字符串可修改)
    }
}

【代码做什么】：makeAcronym 把 “abstract data type” 缩成 “ADT”（体会逐字符扫描 + 词首判断）；asciiSum 用 int(ch) 累加字符的 ASCII 码；toUpperInPlace 借引用形参原地把字符串改成大写。main 里依次展示 length/下标/substr、传值式库函数（toupper 返回新字符）与引用式自定义函数。

【实现机制解说】：result += toupper(ch) 这一行有两个细节：(a) result 是 string，+= 把右侧 char 拼到末尾，这就是“字符串可原地增长”；(b) 若写成 result = result + toupper(ch) 也等价，但若两边都是裸字符串字面量（如 "abc" + "xyz"）则编译不过——C++ 里双引号字面量是 C 风格字符串，必须至少一边是 C++ 的 string。再看传参：makeAcronym(const string& phrase) 的 const & 是“只读借用”，既省去整串拷贝（若 1GB 文本按值传就要再拷 1GB），又由编译器保证函数内改不了它；toUpperInPlace(string& s) 没有 const，函数内 s[i] = ... 会直接改到调用者的变量——这正是“传值 vs 传引用”的分界线：有 & 是虫洞，没 & 是复印件。另外 s.length() 返回无符号类型，与 int 比较时建议先 (int) 强转，避免有符号/无符号比较的隐形坑（官方第 3 讲练习也提醒这类细节）。

示例 3：std::vector 与二维 vector——“add vs insert(0,·)”计时 + Grid 表示

// 文件: vector_grid_demo.cpp
// 演示: vector 常用操作、add vs insert(0,·) 运行时对比、二维容器表示 Grid
#include <chrono>    // 计时
#include <iostream>
#include <vector>
using namespace std;

double timeAdd(int n);        // 原型: n 次 push_back 耗时(毫秒)
double timeInsertHead(int n); // 原型: n 次 insert(begin()) 耗时(毫秒)

int main()
{
    // (1) 常用操作(std 版; 官方 Stanford Vector 的 add/insert/remove 同名不同拼)
    vector<int> v = {15, 20, 18};   // 初始化列表
    v.push_back(33);                // 对应 add(33)   → {15,20,18,33}
    v.insert(v.begin() + 2, 90);    // 对应 insert(2,90) → {15,20,90,18,33}
    v.erase(v.begin());             // 对应 remove(0) → {20,90,18,33}
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " ";
    cout << endl;

    // (2) 计时对比: 规模翻倍时,add 版近似线性,insert 头部版近似“翻倍再翻倍”
    cout << "n        push_back    insert(begin)" << endl;
    for (int n : {5000, 10000, 20000, 40000}) {
        double tAdd = timeAdd(n);
        double tIns = timeInsertHead(n);
        cout << n << "    " << tAdd << " ms      " << tIns << " ms"
             << "   (慢 " << tIns / tAdd << " 倍)" << endl;
    }

    // (3) 二维 vector 模拟 Grid: 3 行 4 列,row-major(行先列后)
    const int ROWS = 3, COLS = 4;
    vector<vector<int>> g(ROWS, vector<int>(COLS, 0));  // 全部初始化为 0
    g[2][3] = 18;                                       // 第 2 行第 3 列
    for (int r = 0; r < (int)g.size(); r++) {           // 外层行
        for (int c = 0; c < (int)g[r].size(); c++) {    // 内层列
            cout << g[r][c];
            if (c + 1 < (int)g[r].size()) cout << ", ";
        }
        cout << endl;
    }
    return 0;
}

double timeAdd(int n)
{
    vector<int> v;
    auto t0 = chrono::steady_clock::now();
    for (int i = 0; i < n; i++) v.push_back(i);   // 每次只写末尾一个位置
    auto t1 = chrono::steady_clock::now();
    return chrono::duration<double, milli>(t1 - t0).count();
}

double timeInsertHead(int n)
{
    vector<int> v;
    auto t0 = chrono::steady_clock::now();
    for (int i = 0; i < n; i++) v.insert(v.begin(), i); // 每次都要把所有元素右移
    auto t1 = chrono::steady_clock::now();
    return chrono::duration<double, milli>(t1 - t0).count();
}

【代码做什么】：(1) 用 std 容器复刻官方 Vector 的 add/insert/remove 三连操作并打印；(2) 用 <chrono> 对“n 次末尾追加”和“n 次头部插入”分别计时，规模从 5000 翻倍到 40000，观察两者差距如何被拉大（官方 L04 用 SimpleTest 的 TIME_OPERATION 做过同款实验，规模到 50 万时差距达数百倍）；(3) 用 vector<vector<int>> 造一张 3×4 网格并 row-major 打印——这就是官方 Grid 类的标准库替身。

【实现机制解说】：v.insert(v.begin(), i) 每执行一次，要把当前所有元素整体右移一格腾出第 0 位，因此第 i 次插入要搬 i 个元素，n 次总共约搬 1+2+…+n ≈ n²/2 次——规模翻倍，搬移次数约翻 4 倍，计时结果会直观地“翻倍再翻倍”。push_back 则不同：末尾有空位时只写一个位置；只有当容量（capacity）耗尽，vector 才会“扩容”——申请一块更大的连续内存、把旧元素全部拷过去再释放旧的（这就是示例说明里提到的后台扩容），因为扩容不常发生，均摊下来 add 仍接近 O(1)。这正是官方 L04 强调“insert(0,·) 危险地慢、add 相当快”的底层原因。网格部分：vector<vector<int>> g(ROWS, vector<int>(COLS, 0)) 先造好 3 个“行”，每行是一个长度为 4 的全 0 列向量；g[2][3] = 18 先取第 2 行的 vector（引用语义），再改其第 3 个元素——两层下标 [][] 与官方 g[r][c] 一一对应。

复杂度分析

关键要点

• 先语法后语义：编译器只把关“合不合规矩”，程序“对不对”永远靠你自己想清楚，再靠测试验证。
• 声明即初始化：C++ 不会替你清零基本类型变量，未初始化的 int 里装的是垃圾值。
• 想改实参就用引用 &，只想省拷贝就用 const &；大容器一律不要按值传。
• 字符串与容器都从 0 开始编号、都可用 range-for 遍历；先想清要不要下标、要不要修改，再选 for 还是 for-each。
• add（末尾追加）均摊 O(1) 快到飞起，insert(0,·) 每回都要“全体右移”慢得吓人——以后写循环优先往末尾堆数据。

常见陷阱与注意事项

• 未初始化变量：int a; cout << a; 打印垃圾值。规避：声明时立刻给初值。
• 越界访问：s[10]（字符串长度 5）可能打印乱码甚至段错误崩溃，v[v.size()] 同理。规避：始终让下标落在 [0, size)，必要时先判断再访问。
• 引号用错：字符用单引号 'A'，字符串用双引号 "A"，混用会导致编译错误或歧义。
• 类型不可变：int a = 5; string a = "hi"; 是重复声明；改值只写 a = 7;。
• == 写成 =：if (a = 5) 是赋值而非比较，条件恒真。规避：条件里坚持用 ==。
• 短路误用/漏用：if (x || y) 若 x 恒真则 y 永不执行；反之访问数组前不检查边界可能崩。规避：把“安检”放在 && 左侧。
• 魔数：int(ch) - 96 让人看不懂。规避：用 ('a' - 1) 或 isalpha/toupper 这类自解释写法。
• 注释废话：// 打印 hello 这种把代码翻译成中文的注释是噪音。规避：注释只写“为什么/整体在干嘛”，函数名取动词短语。
• 循环里改 size：for (int i = 0; i < v.size(); i++) 若循环体里 push_back 会越跑越多。规避：先缓存原始大小或改用 while + 明确退出条件。

思考题（带答案）

问题 1：string s = "hello"; for (char ch : s) { ch = toupper(ch); } cout << s; 输出是什么？为什么？ 答案：输出 hello。range-for 里的 ch 是每个字符的拷贝，改 ch 只改副本，原字符串不受影响；想真正修改要写成 for (int i = 0; i < s.length(); i++) s[i] = toupper(s[i]);（即示例 2 的 toUpperInPlace 思路）。

问题 2：声明 void mystery(int& b, int c) 后调用 int x = 5; mystery(x, x);，函数内 b++、c++，回到 main 后 x 是多少？为什么？ 答案：x 变成 6。b 是引用，b++ 直接改 main 里的 x；c 是传值，c++ 只改函数内副本，与 x 无关。要点：同名实参传给引用和值两个形参时，只有引用那一路会“穿透”。

问题 3：手头有一个很大的 vector<string>，只想统计里面有多少个元素，函数签名写成 int countAll(vector<string> v) 有什么问题？怎么改最好？ 答案：按值传参会把整个 vector 逐元素拷贝一遍，时间 O(n)、内存翻倍，纯属浪费。改成 int countAll(const vector<string>& v)：const 表明只读不改，& 避免拷贝，调用方与函数语义都不变，开销降为 O(1)。

Lecture 2: 栈与队列（Stacks & Queues：LIFO/FIFO 与 ADT 客户端视角）（对应课程真实讲座 L05）

概述

本讲介绍两种最简单的“有序容器”：栈（stack）与队列（queue）。它们不提供任意位置读写，只各开一个口子，却因此换来了极简、极快的操作，并能优雅地解决反转、配对、任务排队等一大批问题。本讲延续“客户端视角”：只关心“能做什么、语义是什么”，暂不深究内部实现；同时会用容器按引用传递、取模运算符 %、break 语句等配套语法，并完整实现一个经典应用——后缀表达式（postfix）求值。 对应官方 L05（6/29，Stacks and Queues）一讲；官方还随讲附赠 StackViz / QueueViz 两个可视化小程序帮助直观感受进出顺序。

核心概念与算法原理

1. ADT 的“客户端视角”（Client-Side Approach）

问题定义：学了 Vector/Grid 之后，如何又快又稳地搭建新工具，而不必先懂内部实现？ 直观解释：课程采取“先当用户、后当制造者”的策略：先学会使用 ADT（调用它的操作、相信它的语义），实现细节（数组？链表？）留到讲完指针与动态内存之后再揭开。官方在 L04 与 L05 反复强调这一点：作为客户端，我们享受的是“契约”——只要按文档调用，内部怎么折腾我们不必操心。 步骤分解：使用一个 ADT 的标准流程 = ① 决定需要什么语义（后进先出还是先进先出）→ ② 选对容器（Stack 或 Queue）→ ③ 只通过其公开操作读写（不越权访问内部）→ ④ 按文档假设复杂度与行为。官方用 StackViz/QueueViz 动画直观演示入栈出栈、入队出队的每一步，建议下载摆弄一遍。

2. Stack：LIFO，后进先出

问题定义：有些任务要求“最后放进去的最先被处理”——比如撤销、后退。 直观解释：栈像一摞盘子：你永远只能从最上面取放（官方 L05 称其为 LIFO：last-in, first-out）。它只开一个口（栈顶 top），开口少反而让它行为确定、几乎不可能误操作。 操作/步骤分解（官方 Stack 与 std::stack 对照）：

栈的抽象视图(只从顶部进出):
        ┌─────┐
        │ 12  │ ← top: peek/pop 都在这
        ├─────┤
        │ 15  │
        ├─────┤
        │ 20  │
        ├─────┤
        │ 10  │ ← 最先 push 的,沉在最底
        └─────┘
 push(7) → 7 落在 12 之上; pop() → 移走 12

注意：C++ 标准库的 stack::pop() 返回值是 void——必须先 top() 看一眼再 pop() 移走，两步完成“取出”。官方 Stanford 的 pop() 一步到位返回元素，这是两者最易踩的差异。 现实应用（官方列举）：① 反转任何序列（后进先出天然倒序）；② 程序本身的“调用栈 call stack”记录函数调用顺序与返回地址；③ 浏览器“后退”按钮按访问历史回退；④ 文本编辑器撤销（undo）操作栈。官方还预告：图论里的深度优先搜索（DFS）本质上也能用栈实现，课程后段会再见面。

3. Queue：FIFO，先进先出

问题定义：另一些任务讲究“先来先服务”的公平排队。 直观解释：队列像排队买票：新来的排到队尾，服务完的从队首离开——FIFO（first-in, first-out）。只开两个口：队首（front，出）与队尾（back，入）。 操作/步骤分解：

队列的抽象视图(队尾进,队首出):
  enqueue(7)                     dequeue()
      │                              │
      ▼                              ▼
[ 尾 ] [ 4 ][ 3 ][ 2 ][ 1 ] [ 首 ] → 移走 1,其余前移

现实应用：打印店的打印任务队列、演唱会购票排队、游戏登录排队、LaIR 答疑排队（官方 L05 全数点名）；图论中的广度优先搜索（BFS）用队列逐层扩散。广度式处理的通用模式是：先把“起点/初始任务”入队，然后循环“出队一个 → 处理 → 把它的后继任务入队”，直到队列空。 清空/遍历的标准句式：队列没有下标、不能用 range-for（std 的 stack/queue 都是“只露一头的适配器”），想遍历就只能一边出队一边处理：while (!q.empty()) { 处理 q.front(); q.pop(); }。官方 L05 特意演示了错误写法 for (int i = 0; i < q.size(); i++)——每出队一次 size 就变小，循环会提前结束，只处理掉一半任务。

4. 配套工具：容器按引用传递、%、break

问题定义：写操作这些容器的函数时，有什么约定俗成的规矩？

• 容器一律按引用传：队列/栈可能装大量数据，按值传等于整份拷贝（时间 O(n)、内存翻倍）；写 void f(queue<int>& q) 只建立 O(1) 的“纽带”。即使函数不打算改动容器，也应写 const queue<int>& 以省拷贝（官方 L05 把它列为“top take-away”）。
• 取模 %：返回整除的余数：17 % 3 == 2（17÷3=5 余 2），5 % 2 == 1。高频用途：奇偶判断（x % 2）、每 N 次做某事（次数 % N == 0）、环形下标前进 (i + 1) % n。
• break：立即跳出当前所在的那一层循环，跳到循环后第一行继续。常配合 while (true) 做“满足条件就收手”的中断。
• range-for 与输出流：std 的 stack/queue 不能 range-for、也不能直接 cout << s（官方 Stanford 版支持打印与 == 比较，这是课程库的贴心之处）；本笔记统一用“边出边处理”的方式展示内容。

5. 用 Vector 充当 Stack——抽象的力量

问题定义：栈和 vector 有什么关系？为什么有了 vector 还要 Stack？ 直观解释：官方 L05 演示：push/pop 完全可以用 vector 的“末尾增删”模拟——v.push_back(x) 当 push、v.pop_back() 当 pop。但两者不可同日而语：写 stack 版本时语义一眼可见、无下标可算、几乎不可能出错；写 vector 版本要自己小心“该从哪头删”，一不留神就出界或删错端。这就是抽象的价值：把“只能从顶部操作”的约束内建进类型，错误在编译与设计层面就被挡掉了。std::vector 提供 push_back/pop_back/back() 恰好可作此用，而 std::stack 则把这一约束固化成了专用类型。

6. 经典应用：后缀表达式（postfix）求值

问题定义：人习惯中缀（infix）写法 3 + 5 * 2，但解析它要处理优先级与括号、多次扫描；如何让程序一次从左到右扫完就算出结果？ 直观解释：后缀表达式（也叫逆波兰记法 RPN）把运算符放到两个操作数之后：3 5 2 * + 表示“3 与 (5×2) 相加”。它完全不需要括号和优先级规则，天然适合计算机从左到右单遍处理（官方 L05 补充说明里完整推导过）。谁在帮我们算？ 一台只认得“数就压、符就取二合一”的栈机器。 步骤分解（算法）：准备一个空栈；从左到右读每个 token：

1. 读到数字 → 压栈；
2. 读到运算符（+ - * /）→ 先 pop 出右操作数，再 pop 出左操作数（顺序关键！减法和除法左右颠倒结果就错），算完把结果压回栈；
3. 全部读完 → 栈顶唯一剩下的数字就是答案。

走查 3 5 2 * + 12 2 3 * / -（对应中缀 3 + 5*2 − 12/(2*3)）：

token   动作               栈(自底向上)
3       数字,压栈           [3]
5       数字,压栈           [3,5]
2       数字,压栈           [3,5,2]
*       取 5*2=10,压栈      [3,10]
+       取 3+10=13,压栈     [13]
12      数字,压栈           [13,12]
2       数字,压栈           [13,12,2]
3       数字,压栈           [13,12,2,3]
*       取 2*3=6,压栈       [13,12,6]
/       取 12/6=2,压栈      [13,2]
-       取 13-2=11,压栈     [11]
结束    pop → 答案 11

健壮性检查：非法表达式会露出马脚——运算符出现时栈里不足 2 个数（操作数不够）、除数为 0、token 既非数字也非运算符、结束时栈里不是恰好 1 个数（说明多/少了操作数）。一个完整的 processPostfix 实现见下方示例 3，返回 bool 表示成功与否，失败时保持结果参数原值。

代码示例与实现详解

示例 1：用 std::stack 反转字符串 + 模拟浏览器“后退”（含 break）

// 文件: stack_demo.cpp
// 演示: push/top/pop、清空栈的 while 句式、LIFO 反转、“后退”应用与 break
#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 用栈反转字符串: 后进先出 = 天然倒序
string reverseViaStack(const string& text)
{
    stack<char> s;
    for (char ch : text) {
        s.push(ch);              // 逐个压栈
    }
    string out;
    while (!s.empty()) {         // 清空栈的标准句式
        out += s.top();          // 先 top() 看一眼栈顶
        s.pop();                 // 再 pop() 移走(标准库 pop 不返回值!)
    }
    return out;
}

int main()
{
    string word = "stressed";
    cout << "stressed 反转: " << reverseViaStack(word) << endl;  // desserts

    // 浏览器“后退”按钮: 历史记录就是一个栈,越新访问的越先被退回
    stack<string> history;
    history.push("首页");
    history.push("课程主页");
    history.push("L05 讲义页");

    cout << "开始点击后退…" << endl;
    while (!history.empty()) {
        string current = history.top();   // 当前停在哪一页
        history.pop();                    // 后退 = 弹出当前页
        cout << "离开: " << current << endl;
        if (current == "课程主页") {       // 回到课程主页就收手
            cout << "已回到课程主页,停止回退。" << endl;
            break;                        // break: 跳出最近的 while
        }
    }
    return 0;
}

【代码做什么】：reverseViaStack 把 “stressed” 每个字符压栈再全部弹出，得到 “desserts”——LIFO 的反转威力一目了然；main 里用 stack<string> 存放访问历史，模拟浏览器后退：循环里“看栈顶 → pop 离开该页”，一旦弹出的是 “课程主页” 就 break 退出循环。

【实现机制解说】：栈的操作全在“顶”上发生，因此每个操作都是 O(1)。s.pop() 不返回被移除的元素是 C++ 标准库与官方 Stanford 版最大的差异：官方 Stack::pop() 直接返回栈顶，而 std 版必须 top() + pop() 两步走——若直接 s.pop() 后想用返回值，会拿到垃圾甚至编译错误。break 只作用于它所在的最近一层循环：本例它在 while 内部，因此触发后直接跳到循环右花括号之后。注意 while (!s.empty()) 是“排空容器”的通用句式：任何循环里若一边遍历一边改变容器大小，千万别把 s.empty() 换成循环次数上限之类的固定值——那正是官方 L05 演示的队列遍历翻车点。

示例 2：用 std::queue 模拟打印任务队列（FIFO + % + 引用传递）

// 文件: queue_demo.cpp
// 演示: push/front/pop、FIFO 打印队列、% 运算符、容器按引用传递
#include <iostream>
#include <queue>
#include <string>
using namespace std;

// 处理整个打印队列。参数必须是引用: 传值会把整支队伍拷贝一份(费时费内存)
void runPrinter(queue<int>& jobs)
{
    int done = 0;
    while (!jobs.empty()) {           // 边出队边处理,直到队列空
        int job = jobs.front();       // peek: 看队首(最早提交的任务)
        jobs.pop();                   // dequeue: 移走队首
        done++;
        cout << "打印完成: 任务 #" << job << endl;
        if (done % 3 == 0) {          // % 取模: 每完成 3 个汇报一次
            cout << "   —— 已累计完成 " << done << " 个任务" << endl;
        }
    }
    cout << "队列已空,打印机待机。" << endl;
}

int main()
{
    queue<int> printer;               // 打印任务按提交顺序排队(FIFO)
    for (int job = 1; job <= 6; job++) {
        printer.push(job);            // enqueue: 依次进队尾
    }
    cout << "队首(最先打印)任务: #" << printer.front() << endl;  // 1
    cout << "队尾任务: #" << printer.back() << endl;             // 6

    runPrinter(printer);              // 先进先出: 1,2,3,4,5,6

    // % 的另两个常见用法: 奇偶判断 与 环形下标
    for (int i = 1; i <= 5; i++) {
        if (i % 2 == 0) cout << i << " 是偶数, ";
    }
    cout << endl;
    cout << "环形下标: 6 个槽(编号 0..5)里, 槽 5 的下一个是槽 "
         << (5 + 1) % 6 << "  ← 公式 (i+1) % 总槽数" << endl;
    return 0;
}

【代码做什么】：任务 1..6 按序入队，front()/back() 分别展示队首队尾，随后 runPrinter 用“看队首 → pop”的句式按 FIFO 顺序打印全部任务（输出 1 到 6，证明先来先服务），并用 done % 3 == 0 每三个任务汇报一次进度；结尾顺带展示 % 的奇偶判断与环形下标两种常见用法。

【实现机制解说】：runPrinter(queue<int>& jobs) 用引用而非值——若写 queue<int> jobs，函数入口就要把整支队伍逐元素拷贝（O(n) 时间 + 双倍内存），函数里清空的也只是一份副本，调用方的队列原封不动。这是官方 L05 反复强调的规矩：容器进函数一律走引用；不打算改就加 const。打印顺序 1→6 恰好验证 FIFO：push 全在队尾、pop 全在队首，新任务永远不可能插队。% 的实质是“整除的余数”，done % 3 == 0 在 done=3、6 时为真——“每 N 次触发一次”是它的招牌用法；环形下标 (i+1) % n 让下标在 0..n-1 间循环打转，是轮询调度（round-robin）的基础。

示例 3：后缀表达式求值器（完整健壮版）

// 文件: postfix_demo.cpp
// 演示: 用 std::stack 单遍求值后缀表达式,含非法输入检测
#include <iostream>
#include <sstream>   // istringstream: 按空白切分字符串
#include <stack>
#include <string>
using namespace std;

// 求值后缀表达式 expr; 成功返回 true 并把答案写进 result;
// 失败(非法表达式/除零)返回 false 且 result 保持原值不变。
bool processPostfix(const string& expr, int& result)
{
    stack<int> s;
    istringstream iss(expr);
    string token;
    while (iss >> token) {                       // 逐个取 token(按空格切)
        if (token == "+" || token == "-" ||
            token == "*" || token == "/") {
            if (s.size() < 2) return false;      // 操作数不够 → 非法
            int rhs = s.top(); s.pop();          // 先弹出的是右操作数!
            int lhs = s.top(); s.pop();          // 再弹出的是左操作数
            if (token == "+")      s.push(lhs + rhs);
            else if (token == "-") s.push(lhs - rhs);
            else if (token == "*") s.push(lhs * rhs);
            else {                               // 除法: 防除零
                if (rhs == 0) return false;
                s.push(lhs / rhs);
            }
        } else {                                 // 既非四则符 → 尝试当整数
            try {
                s.push(stoi(token));
            } catch (...) {
                return false;                    // 既非运算符又非整数 → 非法
            }
        }
    }
    if (s.size() != 1) return false;             // 栈应恰好只剩最终答案
    result = s.top();
    return true;
}

int main()
{
    const string exprs[] = {
        "3 5 2 * + 12 2 3 * / -",   // 等价于 3+5*2-12/(2*3) = 11
        "5 10 +",                   // 15
        "10 12 + 5 -",              // 17
        "2 3 + 4 5 + *",            // 45
        "5 10 + +",                 // 非法: 第二个 + 缺操作数
        "10 + 20",                  // 非法: 开头两个数没到就先遇运算符
        "4 0 /",                    // 非法: 除零
        "3 x 2 +",                  // 非法: x 不是数字也不是运算符
        ""                          // 非法: 空串
    };
    for (const string& e : exprs) {
        int result = 0;                            // 每次重置,便于观察“失败不改值”
        if (processPostfix(e, result)) {
            cout << "\"" << e << "\" = " << result << endl;
        } else {
            cout << "\"" << e << "\" → 非法表达式(结果仍为 " << result << ")" << endl;
        }
    }
    return 0;
}

【代码做什么】：processPostfix 从左到右单遍扫描：数字压栈，运算符则弹两个操作数（先弹右、后弹左）计算后压回；结束时若栈里恰好剩一个数即为答案。main 用 9 个用例覆盖：4 个合法表达式（含官方 L05 的经典式 3 5 2 * + 12 2 3 * / - = 11）与 5 类非法输入（缺操作数、数字不足、除零、乱 token、空串）。

【实现机制解说】：算法成立的关键是栈暂存子结果：遇到运算符时，栈顶两个数正是它该吃的“最近两个数”，算完压回后它们以单个结果的身份继续参与外层运算——这恰好是表达式树的后序遍历求值，因此无需括号与优先级。弹栈顺序必须“先右后左”：- 与 / 不满足交换律，10 12 + 5 - 若先弹左会算出 7 而非 17。istringstream >> token 自动按任意空白切词，比手写 split 简洁。错误处理走“早退原则”：任一环节发现非法立即 return false，且绝不动 result——官方练习强调用“失败不改参数”来测试，防止调用者误以为失败会写入哨兵值。该函数与官方 L05 课后练习 bool processPostfix(string expr, int& result) 同款签名，这里用纯标准库实现。

复杂度分析

要点：栈与队列把“能做的事”刻意收窄，换来的是所有核心操作都是 O(1)，且语义无歧义、几乎不可能误用。std 默认用 deque 兜底（stack 也可指定 vector），两种底层都不影响客户端看到的复杂度。

关键要点

• 栈是 LIFO：只能碰栈顶，push 进去、pop 出来，天然反转一切“后来居上”的序列。
• 队列是 FIFO：队尾进、队首出，“先来先服务”，是公平排队的代名词。
• 清空/遍历栈与队列只有一种标准句式：while (!空) { 取顶/首; 弹出; }，绝不要用固定循环次数。
• 容器进出函数一律传引用（不修改就 const &），按值传等于白拷一份 O(n) 的数据。
• 后缀表达式求值 = “数字压栈、运算符取二合一”的栈机器，单遍扫描即可，先弹右操作数再弹左操作数。

常见陷阱与注意事项

• std::stack::pop() 不返回元素：直接 int x = s.pop(); 编译报错。规避：先 top() 取值再 pop()。
• 循环条件随出队变小：for (i = 0; i < q.size(); i++) { q.pop(); } 只处理一半。规避：一律 while (!q.empty())。
• 空容器上操作：对空栈 top()/pop()、空队列 front()/pop() 是未定义行为，可能崩溃。规避：操作前先判空。
• 弹栈顺序弄反：后缀求值里 -、/ 先弹右操作数，反了结果错。规避：把“先弹右、后弹左”写进注释并自测减法/除法用例。
• 按值传容器：void f(queue<int> q) 隐式整队拷贝。规避：写成 queue<int>& 或 const queue<int>&。
• 误以为栈/队列可随机访问或可 range-for：下标、迭代器一概没有。规避：想“翻看”全部内容就先想清楚是否需要排队/栈语义，或改用 vector。
• % 与 / 混淆：17 % 3 是余数 2，17 / 3 是商 5。规避：默念“% 是取余”。

思考题（带答案）

问题 1：依次 push(1), push(2), pop(), push(3), pop(), pop() 后栈为空。问每次 pop() 各返回什么？若换成队列（push 当 enqueue、pop 当 dequeue）结果又如何？ 答案：栈是 LIFO，三次 pop 依次返回 2、3、1（每次 pop 的都是当时的栈顶）。队列是 FIFO，三次 pop 依次返回 1、2、3（每次 pop 的都是最早的队首）。同一组操作、两种容器、完全相反的输出顺序——这正是 LIFO 与 FIFO 语义差异的最佳记忆点。

问题 2：为什么官方 L05 说“用 vector 也能当栈用，但我们还是推荐 Stack”？举一个用 vector 模拟栈时容易犯的错。 答案：vector 的 push_back/pop_back 确实能模拟栈，但 vector 同时暴露了下标、insert、erase 等“多余能力”，使用者要时刻自律“只能动尾巴”，容易下标算错、从错误的端删除、甚至越界。Stack 把“只能从顶部进出”固化为类型约束，犯错空间被设计层面抹掉——这就是抽象的力量：用更受限的接口换更低的出错率。

问题 3：给出后缀式 2 3 4 * + 5 + 的求值过程（写出每一步后的栈）。 答案：2 压栈 [2]；3 压栈 [2,3]；4 压栈 [2,3,4]；* 取 3×4=12 压回 [2,12]；+ 取 2+12=14 压回 [14]；5 压栈 [14,5]；+ 取 14+5=19 压回 [19]；结束，答案 19。（可对照官方 L05 练习用例 "2 3 4 * + 5 +" == 19。）

Lecture 3: 集合与映射（Set & Map：去重、词频统计与基于树的有序容器）（对应课程真实讲座 L06）

概述

本讲解决两个高频需求：去重（同一批数据里只保留每种元素一份）与关联查询（按某个键快速找到对应的值）。为此引入两个新 ADT：集合 Set（元素的“成员关系”容器）与映射 Map（键→值的查表容器）。两者都建立在“有序结构”之上：元素/键始终按序排列，插入与查找都快得惊人（O(log n)），与课堂上之后才讲的哈希版本（HashSet/HashMap，平均 O(1)）形成对照。本讲用一个“去重挑战题”开场，并实现词频统计经典应用。 对应官方 L06（6/30，Sets and Maps）一讲；官方课上用《德古拉》全文做过词频统计演示。

核心概念与算法原理

1. 挑战题：去重（De-Dupe）

问题定义：写一个函数，输入一串字符串，把其中每种字符串恰好打印一次。例如 {"unicorn", "starfish", "hummingbird", "starfish", "unicorn", "unicorn"} 应打印 unicorn、starfish、hummingbird 各一次。 直观解释：官方 L06 开场先给“笨办法”：对每个元素回看它之前有没有出现过（双重循环），再进阶成“用一个辅助函数查区间”。两种做法都能对，但要么 O(n²) 慢、要么代码绕。直到把元素“扔进一个 Set”——重复项被容器自动吸收——一行核心逻辑解决问题，课堂的用意就是让大家先体会“没有好工具的痛”，再享受 ADT 的甜。 朴素法步骤分解：对第 i 个元素，向前扫描 0..i-1 检查是否重复，无重复才打印——最坏要两两比较 n²/2 次。Set 法：见示例 1。

2. Set：无重复的“成员判断机”

问题定义：需要一种容器回答“某元素在不在里面”，并且保证绝不存两份。 直观解释：数学集合的数据结构版。两个铁律（官方 L06 原话拆解）：① 不允许重复——同一元素插 100 次也只留 1 份；② 不保存插入顺序、也没有下标。所以 Set 的本质是“二元成员判断装置”：一个元素要么是成员，要么不是。 操作/步骤分解（官方 Set ↔ std::set）：

“有序性”与内部机制：打印或遍历 Set 时元素总是按序出现（官方 L06 点名：按 ASCII 序排列——大写字母排在小写前，因为 'A'=65 < 'a'=97）。这不是巧合：官方 Stanford Set 由平衡二叉搜索树（balanced BST）支撑，元素按键有序存放，从而插入、查找、删除都只要 O(log n)。C++ 标准库的 std::set 同样是平衡 BST（红黑树），行为完全一致——本笔记一律用 std 版，与课程的 Set 一一对应。

std::set<string> 内部是二叉搜索树(红黑树), 插入 "starfish" 已存在 → 直接忽略:
           hummingbird
          /            \
      dragon          starfish
                          \
                        unicorn
  遍历(中序)= dragon, hummingbird, starfish, unicorn  ← 天然有序

步骤分解（插入）：从根开始，与当前节点比较大小：小走左、大走右、相等说明重复直接返回——一路下行到空位即挂上新节点。树高约 log₂n，故每次比较 O(log n)。遍历：中序遍历（左—根—右）即得升序序列。

3. Set 的应用：去重与查重

• 全量去重：把 vector 元素全部 insert 进 set，重复被自动吸收；要回 vector 就遍历 set 倒回去（代价：排序后的顺序与原顺序无关）。
• 保留首次出现顺序的去重：set 只当“查重台账”——遍历原 vector，若 count(w)==0 就打印并登记。
• 找重复项：登记“已见过”，第二次见到就报“重复”；再套一个 set 可保证每个重复项只报一次（官方 L06 有整套变体练习）。
• “Set 很快”：官方 L06 强调 Set 操作远比“反复扫 vector 查重”快——后者最坏 O(n²)，Set 版每个元素只花 O(log n) 的树查找，总耗时 O(n log n)。

4. Map：键 → 值 的“活字典”

问题定义：要按“键”快速检索“值”：学号→姓名、ISBN→书名、单词→出现次数。 直观解释：Map 是关联式（associative）结构：每个键唯一、恰好映射一个值。官方 L06 的直观例子：把全班的社保号映射到姓名；喂进一个社保号，吐出一个名字。键集合本身就是一个 Set（键互不相同、按序排列），值是它“名下”挂的东西。 操作/步骤分解：

“探键”行为——官方 L06 的招牌知识点：

1. 查询不存在的键时返回该值类型的默认值（int 得 0、string 得空串）；
2. 用 m[key] 语法查询不存在的键时，map 会把该键加进去并配上默认值——副作用！官方演示：map["Sonia"] 查完，map 里多出一个 “Sonia: 空串”。get(key) 则只返回默认值、不插入。

C++ 标准库忠实复刻了这一对行为：std::map 的 operator[] 找不到键就插入默认值；at(key) 找不到则抛异常（相当于“无副作用查询”，但要小心异常）；count(key) 只回答“在不在”。惯用法：先 count 探键、再 [] 取值，避免误插与异常。 键不可变语义：给已有键赋新值 = 覆盖旧映射（官方：m["Julie"] = "Zelenski" 之后再 m["Julie"] = "Stanford"，旧值被覆盖，size 不变）。 多值关联（键 → 容器）：一个键只能映射一个值，但那个值可以是整个容器！map<string, vector<string>> 让“同名（键）→ 多个姓氏（值容器）”成为可能。官方 L06 强调：取出容器后必须用引用接收（vector<string>& v = m["Julie"]），否则拿到的是拷贝，往里 add 等于白干（练习 2 专门考这一点）。

5. 词频统计与“出现最多的词”

问题定义：给一段文本，统计每个词出现几次；进一步找出出现次数最多的词。 直观解释：官方 L06 用《德古拉》全文演示：map<string,int> 键为单词、值为次数，一行 counts[word]++ 完成“没见过就记 1、见过就加 1”的完整逻辑——因为 [] 对不存在的键先补 0 再自增。要按频率找最热词，遍历键值对维护最大值即可（示例 2）。 命名约定（官方 L06 提及）：map 变量名建议写成“键To值”式，如 wordToFrequency、isbnToTitle，把键值关系直接写进名字；词频表常见命名 counts。

6. 有序 vs 无序：Set/Map 与 HashSet/HashMap 的取舍

问题定义：既然要“超快查找”，为什么课程先教“有序版”而非哈希版？ 直观解释：官方 L06 预告：课程库里同时存在 HashSet/HashMap（无序、基于哈希表，平均 O(1)）与 Set/Map（有序、基于平衡 BST，O(log n)）。四个容器的查找都快到在日常数据上几乎无感；差别在于：有序版保证遍历有序、支持“找前驱/后继、区间”等操作，代价是每次 O(log n)；无序版更快但顺序随机。官方明确“本期只需知道概念差异，哈希实现细节到第 24 讲”。 对照表：

同样插入 {"starfish","unicorn","hummingbird","dragon"}:
  std::set 遍历:    dragon → hummingbird → starfish → unicorn   (有序)
  std::unordered_set 遍历:  顺序随机,每次运行都可能不同

代码示例与实现详解

示例 1：Set 去重——挑战题的标准解法与“保序”变体

// 文件: set_dedupe_demo.cpp
// 演示: std::set 去重(有序输出) 与 保留首次出现顺序的去重
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

// 解法 A: 把元素全扔进 set,重复项自动被吸收; 遍历即得有序去重结果
void printUniqueSorted(const vector<string>& words)
{
    set<string> uniqueSet;                  // 空集合
    for (const string& w : words) {
        uniqueSet.insert(w);                // 重复插入被静默忽略
    }
    for (const string& w : uniqueSet) {     // 按键升序遍历
        cout << w << endl;
    }
}

// 解法 B: 用 set 当“查重台账”,保持元素在原 vector 里的首次出现顺序
void printUniqueInOrder(const vector<string>& words)
{
    set<string> seen;                       // 记录“已见过的词”
    for (const string& w : words) {
        if (seen.count(w) == 0) {           // 首次出现才打印 (count 返回 0 或 1)
            cout << w << endl;
            seen.insert(w);                 // 登记,防止下次再打印
        }
    }
}

int main()
{
    vector<string> creatures = {"unicorn", "starfish", "hummingbird",
                                "starfish", "unicorn", "unicorn"};
    cout << "== 解法 A: 有序去重输出 ==" << endl;
    printUniqueSorted(creatures);           // hummingbird / starfish / unicorn
    cout << "== 解法 B: 保留首次出现顺序 ==" << endl;
    printUniqueInOrder(creatures);          // unicorn / starfish / hummingbird
    return 0;
}

【代码做什么】：解法 A 一字排开地 insert，由 set 自己吞掉重复，遍历输出即升序去重结果；解法 B 用 seen.count(w) == 0 判断“从没见过”，头一回见到才打印并登记。main 用官方 L06 的独角兽/海星/蜂鸟数据验证两种输出的顺序差异。

【实现机制解说】：set::insert 返回 pair<迭代器, bool>，bool 位告知“这次是否真的插入了”（已存在时为 false）——官方练习里“只打印重复项一次”等变体可借它实现。count(w) 对 set 只会返回 0 或 1，因为集合语义禁止重复，用它判断成员关系最直白。复杂度对比：若用 vector 的双重循环去重，最坏 O(n²) 次比较；这里每个词一次树查找 O(log n)，总 O(n log n)。遍历 set 得到的是升序而非插入序，所以解法 A 与解法 B 输出顺序不同——想保序就自己维护“首次出现”逻辑，想让容器代劳排序就接受字典序。

示例 2：Map 词频统计——找“出现最多的词”

// 文件: word_freq_demo.cpp
// 演示: std::map 词频统计、按键序遍历、查找最高频词(官方用《德古拉》全文,
//       这里用内嵌小文本代替文件输入,逻辑完全一致)
#include <iostream>
#include <map>
#include <sstream>   // istringstream: 自动按空白切词
#include <string>
using namespace std;

int main()
{
    // 一段模拟课文(可想象成官方课上打开的 poem.txt / dracula.txt)
    const string text =
        "roses are red butterflies are beautiful "
        "red roses are lovely beautiful butterflies";

    map<string, int> wordToFreq;        // 命名约定: 键To值
    istringstream iss(text);
    string word;
    while (iss >> word) {
        wordToFreq[word]++;             // 探键: 新词自动补 0,再自增
    }

    // (1) 遍历: std::map 的 range-for 每次给出 pair<const 键, 值>
    cout << "== 词频表(按键升序) ==" << endl;
    for (const auto& kv : wordToFreq) {
        cout << kv.first << ": " << kv.second << endl;
    }

    // (2) 找出现次数最多的词(遍历一遍,维护当前冠军)
    string topWord;
    int topFreq = -1;
    for (const auto& kv : wordToFreq) {
        if (kv.second > topFreq) {      // 严格大于: 平手时保留先遇到的
            topWord = kv.first;
            topFreq = kv.second;
        }
    }
    cout << "出现最多的词: \"" << topWord << "\", 共 " << topFreq << " 次" << endl;

    // (3) 探键行为演示: operator[] 会“顺手”插入默认值
    cout << "查不在表里的词 zzz 的次数: " << wordToFreq["zzz"] << endl;
    cout << "副作用? zzz 被插进表了: " << wordToFreq.count("zzz") << " (1=是)" << endl;
    cout << "用 count 探键(无副作用): " << wordToFreq.count("qix") << endl;
    return 0;
}

【代码做什么】：istringstream 按空白把课文切成单词，wordToFreq[word]++ 一行完成“首次出现记 1、再次出现加 1”；随后按键升序打印词频表，再单遍扫描找出最高频词；最后演示 operator[] 探键会插入默认值、count() 无副作用。

【实现机制解说】：词频统计的“魔法”全在 wordToFreq[word]++ 的求值顺序：operator[] 找不到键时先构造 {word, 0} 插入并返回其引用，++ 再把它加到 1；找得到则直接对旧值自增——两行 if/else 压缩成一行。这与官方 Stanford Map 的 m[word]++ 行为一致（官方特别注明 get(word)++ 会编译失败，因为 get 返回的是临时值不可自增）。const auto& kv 中 kv.first 是键、kv.second 是值；auto& 引用遍历避免复制整个 pair。找最高频词是线性扫描：map 已按键排好序，但“最大频率”与键序无关，必须逐对比较——复杂度 O(n)。最后一个知识点是副作用：查 “zzz” 之后表里真的多了 zzz:0；需要“只查不改”就用 count/find（或 at，但要注意它找不到会抛异常）。官方课上跑通《德古拉》全文后还加了“打印出现超过 100 次的词”的阈值筛选，道理与这里完全相同。

示例 3：Map 的多值关联——键 → 容器，以及引用陷阱

// 文件: multivalue_map_demo.cpp
// 演示: map<string, vector<string>> 让一个键关联多个值(值本身是个容器)
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

int main()
{
    // 课程 → 选课学生名单 (键唯一, 值是一个可增长的 vector)
    map<string, vector<string>> courseToStudents;

    // 关键: 用【引用】接收返回值! 否则拿到拷贝, push_back 改的是副本
    vector<string>& cs106b = courseToStudents["CS106B"];
    cs106b.push_back("Ada");
    cs106b.push_back("Alan");

    // 也可以不建中间变量, 直接链式操作(每次返回的都是同一份引用)
    courseToStudents["CS103"].push_back("Grace");
    courseToStudents["CS103"].push_back("Edsger");

    // 遍历: 键升序; 每个键名下再遍历其 vector
    cout << "== 选课名单(按键升序) ==" << endl;
    for (const auto& kv : courseToStudents) {
        cout << kv.first << ": ";
        for (const string& name : kv.second) {
            cout << name << " ";
        }
        cout << endl;
    }

    // 对照: 若忘记引用, 会发生什么?
    vector<string> copy = courseToStudents["CS106B"];   // 整份拷贝!
    copy.push_back("Linus");                            // 只改了副本
    cout << "CS106B 名单末尾是否多了 Linus? "
         << (courseToStudents["CS106B"].back() == "Linus" ? "是" : "否(拷贝被丢弃)")
         << endl;
    return 0;
}

【代码做什么】：以“课程→学生名单”演示键到容器的映射：用引用接收 operator[] 的返回值后 push_back，真正把学生加进 map 内的 vector；遍历打印时外层按键升序、内层逐个输出名字；最后故意演示“忘写引用”的后果——改动只落在副本上，被悄悄丢弃。

【实现机制解说】：map 的值类型是 vector<string> 时，m[key] 的返回类型是 vector<string>&（引用）。写成 vector<string> v = m["CS106B"] 会触发拷贝构造——复制整条名单；对 v 的任何修改都与 map 无关，函数结束副本销毁，改动蒸发。官方 L06 练习 2 正是这个坑：没写 & 时打印出的名单全是空的。这也是“值语义”的体现：C++ 里普通赋值默认拷贝，想“拿到并操作原件”必须显式用引用或指针。此外注意 kv.second 遍历 vector 时用 const string& name 只读引用，避免每轮复制一个字符串。

复杂度分析

要点：有序容器把“保持有序”内建进每次操作，换来可预期的升序遍历；无序容器放弃顺序换平均常数时间。两者都远快于“在 vector 里线性扫描查重”的 O(n²)。n 不大时差距无所谓，选型口诀：要顺序输出用 set/map，只求快不求序用 unordered 版（官方 L06 亦如此建议）。

关键要点

• Set 是“二元成员机”：同一元素永远只存一份，回答只有“在/不在”，遍历天然升序。
• 有序的代价与回报对称：set/map 每次 O(log n)，换来排序遍历；由平衡 BST（红黑树）支撑。
• map[key] 会“探键即插入”：查不存在的键会顺手塞进一个默认值；只查不改用 count/find。
• 键要“挂”多个值：让值本身成为容器（如 map<string, vector<string>>），且取出时务必用引用接收。
• 词频统计一行流：counts[word]++ = “没见过记 1、见过加 1”；变量命名用 “键To值”，如 wordToFreq。

常见陷阱与注意事项

• 误以为 set 保插入序：set 遍历永远是升序。规避：要保序就去重时自己维护“首次出现”判断。
• map[key] 查询的副作用：读一下不存在的键就污染了表。规避：先 count(key) 再决定是否 [] 取值。
• 拿 map 的容器值时不写引用：vector<string> v = m[k] 是拷贝，改动无效。规避：写 auto& v = m[k]。
• 对 set 用下标：set 没有下标、没有 []。规避：用 count/find 判断成员、range-for 遍历。
• 值覆盖的误判：m[k] = v2 不会新增一对，而是覆盖旧值。规避：先想清楚“覆盖 vs 新增”的语义，必要时先 count。
• 给元素排序的依据想当然：字符串按 ASCII 序排，大写全在小写之前（"Apple" < "banana"）。规避：要“正常字典序”先统一小写再入 set/map。
• 遍历时修改容器：range-for 遍历 set/map 时插入或删除元素会使迭代器失效。规避：先收集要删的键，遍历结束后再删。

思考题（带答案）

问题 1：vector<string> v = {"a","b","a","c","b"}，想把 v 变成无重复版本（顺序随意），代码怎么写？复杂度多少？ 答案：set<string> s(v.begin(), v.end()); v.assign(s.begin(), s.end());——构造 set 自动去重并排序，再倒回 vector。复杂度 O(n log n)（n 次插入 × log n）。要保留原顺序则改为：遍历 v，用 set<string> seen 判重，首次见到的元素 push_back 进新 vector。

问题 2：为什么官方 L06 说 Set/Map 的插入查找“很快”，比“反复扫 vector”快？请给出数量级对比。 答案：vector 里线性查重 n 个元素最坏 O(n²) 次比较；set 每次插入沿树下行 O(log n)，共 O(n log n)。对 n=100 万，前者约 10¹² 次比较（不可行），后者约 2×10⁷ 次（瞬间完成）。树高 log₂n 意味着“规模翻倍只多 1 层比较”——这就是 O(log n) 的威力（下一讲用大 O 记号正式刻画）。

问题 3：写出用 map 统计字符频次的代码片段：给定 string s，统计每个字母出现次数并输出次数最多的字母。 答案：map<char,int> freq; for (char ch : s) freq[ch]++; 然后单遍扫描找最大：char best; int mx=-1; for (auto& kv : freq) if (kv.second > mx) { mx = kv.second; best = kv.first; }。若要忽略大小写/只统计字母，可先 tolower 并用 isalpha 过滤（把示例 2 的“词”换成“字符”即可）。

Lecture 4: 算法分析：大 O 记号与运行时间估算（Big-O & Algorithmic Analysis）（对应课程真实讲座 L07）

概述

本讲回答一个贯穿全课程的问题：“这个算法到底快不快？”先论证两种直觉方案都不可靠——用秒表计时受机器与负载干扰，逐条数指令又繁琐且无意义；随后引入大 O 记号（Big-O）：用“输入变大时工作量如何增长”来刻画算法的本质快慢。接着建立常见增长函数族的直觉（常数、对数、线性、n log n、二次、指数……），推导求和恒等式 1+2+…+n = n(n+1)/2，并据此解释为何 add 均摊很快而 insert(0,·) 慢到爆炸，最后学会根据增长阶数估算可处理的问题规模。 对应官方 L07（7/1，Big-O and Algorithmic Analysis）一讲；官方随讲给出 Prezi 与“对数运行时的推导”补充视频。

核心概念与算法原理

1. 为什么“墙钟计时”与“数指令”都不靠谱

问题定义：如何公平地比较两个解决同一问题的算法谁快？ 直观解释：官方 L07 先泼两盆冷水。方案一：直接掐秒表（墙钟时间）——同一程序在不同机器、不同负载下时间天差地别；后台开个浏览器都能干扰结果；测试用例大小不公平，结论就失真。方案二：数代码执行了多少条“操作”（赋值、比较、算术、函数调用……）——听起来更“公平”，但很容易数漏（i++ 其实含一次算术+一次赋值，v[i] 背后藏着一乘一加的内存寻址……），而且不同指令在 CPU 上的时钟周期不同，编译器还会优化改写你的代码——数出来的 4n+4 这种数字基本没有意义（官方原话：这是“傻瓜的差事”）。 结论：我们真正该关心的是增长率——当输入规模 n 增大时，工作量以什么“形态”增长：是翻倍就翻倍（线性），还是翻倍就变四倍（二次）？大 O 记号就是描述这种形态的语言。

2. Big-O 的直觉与（非正式）定义

问题定义：给运行时间函数 T(n) 找一个最简“成长形状”来描述它。 直观解释：设输入规模为 n（数组长度、字符串长度、某个整数等）。Big-O 回答：“当 n 变得足够大时，T(n) 大致像什么函数在长？”它只关心“最高阶项”，忽略常数系数与低阶项——因为这些在 n 巨大时才是决定命运的。 严谨定义（了解即可）：称 T(n) = O(f(n))，若存在常数 c 与 n₀，使得对所有 n ≥ n₀ 都有 T(n) ≤ c·f(n)。意思是：从某个足够大的 n 开始，T(n) 的曲线总被 c·f(n) 压住。 化简法则（官方 L07 三步流程）：

1. 假设输入任意大；
2. 找到执行次数最多的语句，统计它跑了多少次（机器无关的近似）；
3. 扔掉常数系数、只留最高阶项 → 大 O 结果。 例如 T(n) = 4n + 4 → O(n)；T(n) = (1/6)n² + 1000n → O(n²)；T(n) = 6n + 2ⁿ → O(2ⁿ)（指数项吞掉一切多项式）。

3. 常见增长函数族与直觉

工作量(操作数)
  ^
  |                            2ⁿ :每加 1 输入就翻倍,爆炸式
  |                          ╱
  |                      n² ╱   :n 翻倍 → 工作量 ×4
  |                    ╱
  |              n·log n     :排序类算法的典型
  |            ╱
  |        n ╱   :n 翻倍 → 工作量 ×2(线性)
  |      ╱
  |  log n :n 翻倍只多 1 步,几乎贴着地面
  | 1 ─────  :常数,与 n 无关
  +───────────────────────────────────► n(输入规模)

增长顺序铁律（n 巨大时）：1 < log n < n < n log n < n² < 2ⁿ < n!。前两名几乎贴地、后两名都是“灾难级”，中间的差距也动辄千万倍。官方 L07 特别提醒一个常见误解：不要把 O(log n) 看成“O(1) 与 O(n) 之间的一半”——对数增长极其接近常数：输入从 1 涨到 10 亿，log₂ 只从 0 涨到 30。

4. 求和恒等式：1+2+…+n = n(n+1)/2

问题定义：insert(0,·) 连续 n 次总共搬移 1+2+…+n 个元素，这串和到底等于什么？ 推导（官方 L07 同款手法）：设 S = 1 + 2 + … + (n−1) + n，把它倒过来再写一遍，两式相加：

  S =   1   +   2   + … + (n−1) +   n
+ S =   n   + (n−1) + … +   2   +   1
--------------------------------------
 2S = (n+1) + (n+1) + … + (n+1) + (n+1)      ← 共 n 个 (n+1)
 2S = n(n+1)
  S = n(n+1)/2

关键结论（官方点名要记住）：1+2+…+n = n(n+1)/2，它的数量级是 O(n²)（因为 (n²+n)/2 的最高阶是 n²）。凡是在循环里看到“第 i 次做 i 件事”，总工作量多半就是这条恒等式。

5. 幕后：v.add 的“均摊 O(1)” vs v.insert(0,·) 的 O(n)

问题定义：官方文档说 add 是 O(1)、insert(0,·) 可达 O(n)，两者差在哪？ add 的均摊机制：vector 底层是一块连续数组。末尾有空位时，add 只写一个新元素（O(1)）；当容量（capacity）恰好用尽，vector 会扩容：申请一块更大的内存（常见策略是翻倍）、把 n 个旧元素全部拷过去、释放旧块——单看这一次是 O(n)。但因为容量翻倍，这次 O(n) 之后要再等 n 次 O(1) 的 add 才会再次扩容：

容量=4,已满:   [1][2][3][4]        ← push_back(5): 放不下!
扩容到 8:     [1][2][3][4][ ][ ][ ][ ]   ← O(n)=4 次拷贝,腾出 4 个空位
再写 5:       [1][2][3][4][5][ ][ ][ ]
   —— 接下来 3 次 add 都只需写 1 个位置,把刚才的 O(n) 摊薄

n 次 add 的总成本 ≈ n 次 O(1) + 少数几次 O(n) 扩容 ≈ O(n)，平均每次 O(1)——这就是“均摊（amortized）O(1)”的含义：单次可能贵，长期平均便宜。 insert(0,·) 为什么是 O(n)：在开头插一个元素，必须把现有的每一个元素都右移一格腾位置；第 i 次插入要搬 i 个元素，n 次共搬 1+2+…+n = n(n+1)/2 ≈ O(n²)。官方在 L04/L07 的课上实测（TIME_OPERATION，规模 5 万→50 万）：add 版耗时从毫秒级缓慢爬升，insert 头部版则爆炸式增长，两版差距从十几倍扩大到数百倍。中间位置插入同理要搬一半元素（O(n)），只有紧贴末尾插入才接近 O(1)（写的元素数 = size − index + 1）。

6. 由增长阶数估算运行时间（规模估算）

问题定义：已知某 O(f(n)) 函数在 n₀ 时耗时 t₀，如何预测 n₁ 时的耗时？ 方法：运行时间按“输入规模比值的 f 次方”放大。设 k = n₁/n₀：

• 线性 O(n)：耗时 ×k。例：n=50 用 100ms → n=100 用 200ms。
• 二次 O(n²)：耗时 ×k²。例：n=50 用 100ms → n=100 用 400ms；若 n 冲到 100 万，放大 (10⁶/50)² = 4×10⁸ 倍 → 100ms × 4×10⁸ = 4×10¹⁰ ms ≈ 463 天！
• 指数 O(2ⁿ)：耗时 ×2^(n₁−n₀)。例：n=5 用 100ms → n=30，放大 2²⁵ ≈ 3355 万倍 → 约 38.8 天。官方提醒：n 只加了 25，就从 0.1 秒变一个多月——输入每 +1，运行时间翻倍，这是识别 O(2ⁿ) 的“指纹”。
• 对数 O(log n)：n 翻倍只多 1 步。n=10 亿时 log₂n ≈ 30——只需约 30 步就能处理 10 亿规模（因为 2³⁰ ≈ 10 亿），这正是二分查找等对数算法的“可怕之处”（官方 L07 称之为 logarithmic runtimes 的震撼）。

判断口诀：n 翻倍 → 时间翻倍 = 线性；变 4 倍 = 二次；只加常数 = 对数；直接翻倍翻倍再翻倍 = 指数。O(n²) 函数不一定“慢”，O(n) 函数也不一定“快”——大 O 只描述增长趋势，不承诺具体秒数（官方 L07 特别指出这一点，并举例自己实测过 n=1 万仅 14ms 的 O(n²) 函数）。

代码示例与实现详解

示例 1：亲手测量 O(n) 与 O(n²)——翻倍实验

// 文件: growth_demo.cpp
// 演示: 规模翻倍时, push_back 总耗时近似翻倍(线性), 头部插入总耗时近似 ×4(二次)
#include <chrono>
#include <iostream>
#include <vector>
using namespace std;

double timeAppend(int n) {                // n 次在末尾追加(push_back)
    vector<int> v;
    auto t0 = chrono::steady_clock::now();
    for (int i = 0; i < n; i++) v.push_back(i);
    auto t1 = chrono::steady_clock::now();
    return chrono::duration<double, milli>(t1 - t0).count();
}

double timePrepend(int n) {               // n 次在头部插入(insert(begin()))
    vector<int> v;
    auto t0 = chrono::steady_clock::now();
    for (int i = 0; i < n; i++) v.insert(v.begin(), i);
    auto t1 = chrono::steady_clock::now();
    return chrono::duration<double, milli>(t1 - t0).count();
}

int main()
{
    cout << "n       push_back(ms)   insert(begin)(ms)   头部/末尾" << endl;
    double prevP = -1;
    for (int n = 2000; n <= 32000; n *= 2) {     // 规模每次翻倍
        double tA = timeAppend(n);
        double tP = timePrepend(n);
        cout << n << "    " << tA << "    " << tP << "     " << tP / tA;
        if (prevP > 0) {                         // 与上一档头部耗时比
            cout << "   (头部较上一档 ×" << tP / prevP << ")";
        }
        cout << endl;
        prevP = tP;
    }
    return 0;
}

【代码做什么】：对 n = 2000、4000、…、32000 逐档测量“n 次末尾追加”与“n 次头部插入”的总耗时，打印两列及比值。预期：push_back 档间近似 ×2（线性）；insert(begin) 档间近似 ×4（二次），两列差距越拉越大。

【实现机制解说】：为什么头部插入档间是 ×4？第 i 次 insert(begin()) 要搬 i 个元素，n 次共搬 1+2+…+n ≈ n²/2 次——n 翻倍 → 总搬移 ×4，这就是求和恒等式的活教材（O(n²) 的来源）。push_back 则每次几乎只写一个位置，偶尔触发一次 O(n) 扩容，均摊后总 O(n)，所以翻倍 → 总时间约 ×2。注意两次测量都在同一进程内进行、用 steady_clock 取墙钟差，量级上足以看清增长形态；若机器抖动较大，可把档位起点调大或每档重复几次取平均——但不要用绝对毫秒数跨机器比较，这正是本讲开头“墙钟不可靠”的教训。

示例 2：用“操作计数器”实证三种增长形态 + 验证求和恒等式

// 文件: opcount_demo.cpp
// 演示: 用计数器亲眼看到 线性 / 二次 / 对数 的执行次数; 验证 1+…+n = n(n+1)/2
#include <iostream>
using namespace std;

long countLinear(int n) {                 // 线性: 循环 n 次
    long ops = 0;
    for (int i = 0; i < n; i++) ops++;
    return ops;                            // 恒等于 n
}

long countNested(int n) {                 // 二次: 双层循环, 恰好执行 n×n 次
    long ops = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) ops++;
    return ops;
}

long countHalving(int n) {                // 对数: 反复减半, 次数 ≈ log2(n)+1
    long ops = 0;
    while (n > 0) { n /= 2; ops++; }
    return ops;
}

int main()
{
    cout << "== 表 A: 线性 vs 减半(对数) ==" << endl;
    cout << "  n         线性次数   减半次数" << endl;
    for (int n : {1000, 1000000, 100000000}) {
        cout << "  " << n << "   " << countLinear(n) << "   "
             << countHalving(n) << endl;
    }
    cout << "  (若 n=10 亿: 线性要 10 亿步, 减半只需 30 步, 因为 2^30≈10^9)" << endl;

    cout << "== 表 B: 双层循环实际次数 == n² ==" << endl;
    cout << "  n     实际次数      n×n" << endl;
    for (int n : {500, 1000, 2000, 4000}) {
        cout << "  " << n << "   " << countNested(n) << "    " << (long)n * n << endl;
    }

    // 求和恒等式: 循环累加 vs 闭式公式, n=1..100000 全量核对
    long long check = 0;
    bool ok = true;
    for (long long n = 1; n <= 100000; n++) {
        check += n;
        long long formula = n * (n + 1) / 2;
        if (check != formula) { ok = false; break; }
    }
    cout << (ok ? "恒等式成立: 1+2+…+100000 = " : "恒等式出错!")
         << check << " = 100000×100001/2" << endl;
    return 0;
}

【代码做什么】：用真实的计数器展示三种增长：线性计数器等于 n；减半计数器在 n=1000/10⁶/10⁸ 时只从 10 涨到 27；双层循环计数器恰等于 n²（表 B 三列一致，眼见 O(n²) 的来源）；最后把 1 累加到 10 万，与 n(n+1)/2 公式逐项核对，验证恒等式。

【实现机制解说】：三个计数器函数就是三种复杂度的“活体标本”。countHalving 揭示 O(log n) 的模式——每轮把输入除以 2，且每轮只做 O(1) 工作，则总轮数 ≈ log₂n：n=10⁸ 只跑 27 轮，n=10⁹ 也才 30 轮（2³⁰ ≈ 10 亿，官方 L07 引用的震撼数字）。countNested 内层循环独立执行 n 次、外层又套 n 次，总执行恰好 n² 次——这是 O(n²) 最直白的来源。恒等式验证采用“暴力求和 vs 闭式公式”对拍：C++ 里 n * (n + 1) 若 n 是 int 可能溢出，故这里用 long long 并先乘后除——顺带复习了类型宽度与运算顺序的坑（除以 2 放最后才能保证 (n+1) 为奇数时也整除）。

示例 3：规模估算器——把“n 翻倍会怎样”变成数字

// 文件: estimate_demo.cpp
// 演示: 由基准 (n0, t0) 预测 n1 的耗时(线性/二次/指数三种增长)
#include <iostream>
using namespace std;

// 多项式增长: power=1 → 线性(×k), power=2 → 二次(×k²)
double predictMs(int n0, double t0ms, int n1, int power)
{
    double k = (double)n1 / n0;          // 输入规模放大倍数
    double factor = 1.0;
    for (int i = 0; i < power; i++) factor *= k;
    return t0ms * factor;
}

// 指数增长: 每多 1 输入翻一倍 → 放大 2^(n1-n0) 倍
double predictExpMs(int n0, double t0ms, int n1)
{
    double factor = 1.0;
    for (int k = n0; k < n1; k++) factor *= 2;
    return t0ms * factor;
}

int main()
{
    cout << "官方同款例题(基准: n=50 用 100ms):" << endl;
    cout << "  线性 n=100:   " << predictMs(50, 100, 100, 1) << " ms" << endl;   // 200
    cout << "  二次 n=100:   " << predictMs(50, 100, 100, 2) << " ms" << endl;   // 400
    cout << "  二次 n=1e6:   " << predictMs(50, 100, 1000000, 2)
         << " ms = " << predictMs(50, 100, 1000000, 2) / 1000.0 / 3600 / 24
         << " 天" << endl;                                                       // ≈463 天
    cout << "  指数 n=5→30:  " << predictExpMs(5, 100, 30)
         << " ms = " << predictExpMs(5, 100, 30) / 1000.0 / 3600 / 24
         << " 天" << endl;                                                       // ≈38.8 天
    return 0;
}

【代码做什么】：把“规模估算”做成函数：给定基准点 (n₀, t₀) 与目标 n₁，线性增长按 ×(n₁/n₀) 放大、二次按平方放大、指数按 2 的差次方放大；main 直接复算官方 L07 的三道例题并换算成“天”，让数字自己说话。

【实现机制解说】：估算的本质是比例推理——我们从不预测绝对秒数，只预测“相对基准放大了多少倍”，因此与机器、语言无关，这正是大 O 的价值。指数分支里 for (k = n0; k < n1; k++) factor *= 2 累乘 n₁−n₀ 次，避开浮点溢出地算出 2^(n₁−n₀)；二次分支的 for 循环等价于 factor = k * k，写循环是为了与“幂次可扩展”的教学语义一致。结果对照官方数字：二次在 n=10⁶ 时约 463 天、指数在 n=30 时约 38.8 天——注意这些预测都锚定在 n=50 用 100ms 这个假设基准上；官方 L07 强调，换一个基准点（例如实测 n=10⁴ 只要 14ms 的 O(n²) 函数）绝对数字会完全不同，但增长形态不变。这也解释了为何不要拿别人的秒数吓自己：该警惕的是增长阶数，不是某个绝对值。

复杂度分析

附：空间复杂度同规则——只关心“随 n 增长的内存形态”，例如 vector 扩容临时占 O(n) 额外空间、树与哈希表存 n 个元素占 O(n)。

关键要点

• 别用秒表比算法：机器、负载、用例都会污染结论；大 O 只谈增长形态。
• 化简法则：扔常数、留最高阶——4n+4 → O(n)，(1/6)n²+1000n → O(n²)。
• 记住增长链条 1 < log n < n < n log n < n² < 2ⁿ，以及“对数≈贴着常数、指数≈灾难”。
• 求和恒等式 1+2+…+n = n(n+1)/2 = O(n²)：见到“第 i 次做 i 件事”就想起它。
• 判断指纹：输入翻倍，时间翻倍=线性、×4=二次、只加常数=对数、整体再爆炸=指数。

常见陷阱与注意事项

• 用墙钟秒数跨机器比较：同一程序两台机器差 10 倍很正常。规避：只比较同一环境下的相对增长，或干脆用操作计数/大 O 表述。
• 拿“单个 O(n) 函数慢”下结论：大 O 不承诺常数大小——O(n) 里藏着 1000n 也可能比 O(n²) 的 0.001n² 在中小规模更慢。规避：大 O 用于讨论 n 很大时的趋势。
• 把 O(log n) 当“介于常数与线性之间的一半”：对 10 亿输入 log 只需 30 步，它贴着常数跑。规避：背下“2³⁰≈10⁹”这个数感锚点。
• 忘记均摊：说“push_back 是 O(n)”不完全错但会误导——单次可能 O(n)，长期平均 O(1)。规避：描述为“均摊 O(1)”。
• 溢出破坏估算/求和：n*(n+1)/2 中 int 相乘可能溢出；2^n 也别真算。规避：用 long long，指数估算用对数或累乘。
• 把双层循环一律当 O(n²)：内层若与 n 无关（如固定 100 次）则整体仍是 O(n)。规避：数清内外层各自的迭代次数再相乘。
• 规模估算忘了基准：所有“预测天数”都锚定在某个假设基准上，基准不同绝对数字全变。规避：先明确“什么规模、多少时间”的基准再外推。

思考题（带答案）

问题 1：函数 A 对 n 个元素做两遍单层扫描，函数 B 对同样输入做一层嵌套循环。分别求大 O，并说明“A 一定比 B 快吗”。 答案：A 是 2n 次操作 → O(n)；B 是 n² 次 → O(n²)。大 O 上 A 优于 B，但不保证 A 在每个具体 n 都快——若 A 的单步代价很高而 B 极简，小规模时可能反超；不过 n 足够大后 O(n) 必然碾压 O(n²)。这正是大 O 只谈趋势、不谈常数的含义。

问题 2：某算法在输入 n=10 时耗时 1ms，在 n=20 时耗时 4ms，在 n=40 时耗时 16ms。它大致是什么复杂度？n=160 时预计多久？ 答案：n 翻倍 → 时间 ×4，符合二次 O(n²)。从 40 到 160 是两轮翻倍（40→80→160），时间 ×16：16ms × 16 = 256ms。（也可直接按比例 (160/40)² = 16 计算。）

问题 3：为什么说“在 vector 开头反复 insert 的总成本是 O(n²)”，用求和恒等式解释，并给出 n=10⁵ 时的搬移次数量级。 答案：第 i 次在开头插入要右移 i 个元素，n 次总搬移 = 1+2+…+n = n(n+1)/2 ≈ n²/2，最高阶 n² → O(n²)。n=10⁵ 时约搬 5×10⁹ 个元素，即便每秒搬 10⁹ 个也要约 5 秒；而同样的 n 次 push_back 均摊总成本只有 O(n)。这就是为什么“优先往末尾堆数据”是铁律。

Lecture 5: 递归：原理、策略与递归式思维（Recursion: Principles & Strategies）（对应课程真实讲座 L08–L10）

概述

本讲正式引入”递归（recursion）”：让函数调用自己，把一个大问题不断拆成同构（形状相同、规模更小）的子问题，直到某个最小问题能直接给出答案。我们会从阶乘、回文这类”热身”例子中吃透递归三要素与调用栈机制，再实现递归二分查找、字符串逆序打印和全排列枚举——这些技巧是后续回溯、分治（归并/快排）与树遍历的共同地基。 （对应官方 2026 夏季 CS106B：L08 Monday, July 6 “Introduction to Recursion”；L09 Tuesday, July 7 “More Recursion”；L10 Wednesday, July 8 “Recursive Problem Solving”。官方在第 8 讲开篇就让大家 DON’T PANIC——递归第一次出现在代码里觉得”玄、晕、难”完全正常，多练习就会变成第二天性。）

核心概念与算法原理

1. 什么是递归：函数调用自己

• 问题定义：要解决问题 P(输入 x)，先把 x 拆成一个或多个”更小的 x’“，然后调用正在写的这个函数自己去解决 P(x’)，最后把子问题的答案拼成 P(x) 的答案。
• 直观解释：俄罗斯套娃——打开最大的娃娃，里面是一个小一号的娃娃，再打开又是一个更小的；大自然里 Koch 雪花、罗马花椰菜都呈现这种”整体里嵌套同形局部”的自相似（self-similar）结构。
• 官方在第 8 讲给出递归函数的两大关键组件，也就是常说的三要素：
  1. 基准情形（base case）：对某些”显然能答”的规范输入直接返回结果，不再调用自己——这是递归的终止条件；
  2. 递归步骤（recursive case）：把当前输入分解成子问题，其中至少一个交给函数自身处理；
  3. 向基准靠拢（progress toward base case）：每次递归调用传入的输入必须比当前更”小”，保证迟早撞上基准情形——而不是朝反方向无限增长。

2. 调用栈：先”递”下去，再”归”回来 程序运行时，每调用一次函数，系统就在内存的”程序栈（call stack）”上压入一个栈帧（stack frame），记录参数、局部变量和返回地址；函数返回时该帧弹出。递归 = 不断压栈（”递”的过程），撞到基准后逐层弹出（”归”的过程），每层带着返回值回到上一层继续未完成的计算。以阶乘为例（本讲第一个正式程序），factorial(5) 的栈是这样长高又变矮的：

factorial(5) 的调用栈（框越往上越"新"；栈顶是最深的那一层调用）

“递”的途中：一帧一帧压栈
┌────────────────────────────────┐
│ factorial(0)   基准情形 return 1│ ← 栈顶（最深）
├────────────────────────────────┤
│ factorial(1)   等待 1 × ____    │
├────────────────────────────────┤
│ factorial(2)   等待 2 × ____    │
├────────────────────────────────┤
│ factorial(3)   等待 3 × ____    │
├────────────────────────────────┤
│ factorial(4)   等待 4 × ____    │
├────────────────────────────────┤
│ factorial(5)   等待 5 × ____    │
├────────────────────────────────┤
│ main()                         │
└────────────────────────────────┘

“归”的途中：帧从栈顶依次弹出，返回值逐层回传、就地完成乘法：
factorial(1) = 1 × 1   = 1
factorial(2) = 2 × 1   = 2
factorial(3) = 3 × 2   = 6
factorial(4) = 4 × 6   = 24
factorial(5) = 5 × 24  = 120   ← 最终答案交回给 main()

3. 无限递归与栈溢出（stack overflow） 如果函数没有基准情形、或递归调用不向基准靠拢，栈帧会无穷无尽地堆积，最终占满栈空间导致程序崩溃（官方在第 8 讲用 foo(){ foo(); } 演示，崩溃前能压入约二十六万个帧）。规避方法只有一个：动笔写递归体之前，先问自己”最小输入是什么？答案是什么？参数怎么变小？”

4. 递归 vs 迭代 官方在第 8 讲直言：今天大部分例子用 for 循环也能写，我们偏要用递归，是为了用温和的题目建立递归直觉。两者的取舍大致是：

5. 信任飞跃（leap of faith） 写递归最常见的心理障碍是想把每一层调用都追踪一遍。官方反复鼓励的姿势恰恰相反：假设”对更小输入的递归调用已经正确返回了”，你只需负责当前这一层如何利用子结果、以及基准情形是否正确。好比接力赛中你相信前一棒会把棒交到你手里，你只操心自己这一段怎么跑。

6. 包装函数（wrapper function）与函数重载（overloading） 递归函数往往需要额外参数（如二分查找的 lo、hi），但调用者不想关心这些。于是写一个”门面”包装函数：只接收用户想传的参数，内部负责初始化并调用真正的递归函数；若两函数同名（仅参数不同），就叫函数重载，C++ 会根据实参个数与类型自动选择调用哪一个——这比 xxxHelper 式的命名更清爽（官方在第 9 讲的二分查找里就用了两个同名 binarySearch）。

7. 语句顺序决定输出顺序：打印 vs 递归 递归调用前后各放一句代码，执行时机完全不同：调用之前的语句在”递”的途中执行（自顶向下）；调用之后的语句要等子调用全部返回才执行，即”归”的途中执行（自底向上）。正序打印字符串，就是先打印再递归；逆序打印只需把两句对调——栈天然替我们把顺序反转了：

#include <iostream>
#include <string>
using namespace std;

// 先打印、后递归：顺着"递"的路径输出 → 正序
void printForward(const string& s, int k) {
    if (k == (int)s.length()) { cout << endl; return; }
    cout << s[k];
    printForward(s, k + 1);
}
// 先递归、后打印：顺着"归"的路径输出 → 逆序
void printBackward(const string& s, int k) {
    if (k == (int)s.length()) { return; }
    printBackward(s, k + 1);
    cout << s[k];
}

注意逆序版里换行若放在基准情形，会打印在整串之前（基准最先执行），正确做法是把换行交给包装函数收尾——这就是”包装函数负责 setup/tear-down”的典型用途（官方第 8 讲的教训）。

8. 从线性查找到递归二分查找（binary search）

• 线性查找（linear search）：从下标 0 逐个比到末尾，找到即停。它不要求数据有序，但最坏要扫 n 个元素。
• 二分查找：前提是容器已按非降序排好。每次取当前搜索区间 [lo, hi] 的中点 mid 与 key 比较：key 小则 key 只可能落在左半 [lo, mid-1]，key 大则只可能在右半 [mid+1, hi]——无论哪种，都一次性丢掉一半搜索空间。官方在第 9 讲强调：每步 O(1) 的比较把空间减半，正是第 7 讲讲的”对数运行时”：1 亿（约 2³⁰）个元素也只需约 30 次比较。
• 中点公式的溢出陷阱（官方第 9 讲补充）：int 最大值约 21.47 亿。若 lo、hi 都很大，(lo + hi) / 2 的加法本身可能溢出成负数，得到非法下标导致程序崩溃（如 lo = 1,000,000,001、hi = 2,000,000,001，lo + hi 溢出为 −1,294,967,294）。改用代数等价但永不溢出的 lo + (hi - lo) / 2——中间量最大只到 hi。这个细节常出现在技术面试里。

9. 递归枚举与分形的”预览” 硬币序列（每次抛 H/T，n 次共 2ⁿ 种）、骰子序列（6ⁿ 种）、全排列（n! 种）都属于递归枚举：每层递归在一个”决策点”上尝试所有候选并深入。官方在第 9–10 讲用递归树/Prezi 演示：coinFlip 只是两处递归调用，dice 把两次调用改成 for 循环六次，permutation 则在 for 里逐一挑”下一个字符”。这类问题迭代写非常痛苦、递归写却只有几行，是下一讲”回溯”的直接前奏。分形（Koch 雪花、谢尔宾斯基三角形）则是递归的图形化表达：官方动画特别提醒，代码里四个子段是按深度优先依次画完的（先把最左分支一路画到底再回头），并非并行绘制——递归调用的书写顺序决定图形呈现顺序。

代码示例与实现详解

下面 4 个示例全部只依赖 C++17 标准库、可独立编译运行。

示例 1：递归阶乘——三要素与”递/归”全景

#include <iostream>
using namespace std;

// n! = n × (n-1)!，0! = 1
int factorial(int n) {
    if (n == 0) {          // ① 基准情形：0! 直接给答案
        return 1;
    }
    return n * factorial(n - 1);   // ② 递归步骤 ③ 参数 n-1 朝 0 靠拢
}

int main() {
    for (int n = 0; n <= 10; ++n) {
        cout << n << "! = " << factorial(n) << endl;
    }
    return 0;
}

【代码做什么】：factorial 把 n! 的定义直接翻译成代码：n! = n × (n−1)!。主函数打印 0! 到 10! 验证结果。若把基准情形注释掉或参数写成 n + 1，程序将因栈溢出而崩溃——这是理解递归的第一块试金石。

【实现机制解说】：调用 factorial(5) 时，第 2 节的栈帧图精确描述了全过程：递——五个 factorial 帧层层压栈，每帧都”冻结”在自己那行 return n * factorial(n-1) 上，等待子调用返回值填空；最深处的 factorial(0) 命中基准，直接返回 1，不再压栈；归——从 factorial(1) 起每帧依次弹出并完成自己的乘法，答案如多米诺骨牌般回传。理解”乘法发生在归途、而非递途”是看懂一切递归计算的关键：递途只负责把问题拆到最小，真正的计算在回卷时完成。

示例 2：回文判断——剥皮法递归

#include <iostream>
#include <string>
using namespace std;

// 回文：正着读反着读都一样，如 racecar
bool isPalindrome(const string& s) {
    if (s.length() <= 1) {          // 基准：空串与单字符都是回文
        return true;
    }
    if (s.front() != s.back()) {    // 首尾不等 → 直接判否
        return false;
    }
    // 首尾相同 → 剥掉它们，检查剩下的子串是否回文
    return isPalindrome(s.substr(1, s.length() - 2));
}

int main() {
    for (string t : {"racecar", "kayak", "hello", "a", "", "step on no pets"}) {
        cout << "\"" << t << "\" -> " << (isPalindrome(t) ? "是回文" : "非回文") << endl;
    }
    return 0;
}

【代码做什么】：isPalindrome("racecar") 先比较首 ‘r’ 与尾 ‘r’ 相同，于是递归检查剥皮后的 "aceca"；依次剥到长度 ≤ 1 时返回 true。对 "hello"，首 ‘h’ ≠ 尾 ‘o’，第一层就直接返回 false，不再深入。

【实现机制解说】：这里有两个关键设计。其一，递归调用必须发生在”首尾相等”这一检查之后——官方在第 8 讲的 Common Pitfall #3 指出：若忘了比较首尾就无脑递归，函数会对一切输入返回 true，而且如果你只写了”期望 true”的测试用例，这种坏函数会全部通过，让人毫无察觉。其二，用 substr 切片每次会复制约一半长度的新串（n 层累计约 O(n²) 时间）；若追求效率，可改用”传整个字符串的引用 + 两个下标 lo、hi 向中间靠拢”的写法，每层只做 O(1) 工作（这是官方面试风格的改进题，见思考题）。

示例 3：递归二分查找（含包装重载与防溢出中点）

#include <iostream>
#include <vector>
using namespace std;

// 在有序数组 v 的闭区间 [lo, hi] 内查找 key；找不到返回 -1
int binarySearch(const vector<int>& v, int key, int lo, int hi) {
    if (lo > hi) {                  // 基准：区间为空 → 不存在
        return -1;
    }
    int mid = lo + (hi - lo) / 2;   // 防溢出中点公式（勿写成 (lo+hi)/2）
    if (key < v[mid]) {
        return binarySearch(v, key, lo, mid - 1);   // 只搜左半
    }
    if (key > v[mid]) {
        return binarySearch(v, key, mid + 1, hi);   // 只搜右半
    }
    return mid;                     // key == v[mid]，命中
}

// 包装函数：与上面构成函数重载，调用者只需传数组和 key
int binarySearch(const vector<int>& v, int key) {
    return binarySearch(v, key, 0, (int)v.size() - 1);  // 空数组时 hi=-1 直接命中基准
}

int main() {
    vector<int> v = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    for (int key : {2, 38, 91, 99}) {
        cout << "在有序数组中查找 " << key << " -> 下标 "
             << binarySearch(v, key) << endl;
    }
    return 0;
}

【代码做什么】：每次比较 key 与 v[mid]，据此把搜索区间收缩为左半或右半并递归，直至区间为空（返回 −1）或命中（返回下标）。主函数对四个键演示查找：2 命中下标 0，38 命中下标 6，91 命中下标 9，99 不存在返回 −1。

【实现机制解说】：注意三点。第一，为什么能安全丢掉一半：数组有序，若 key < v[mid]，则 key 不可能出现在 mid 右侧任何位置，右半可以整体放弃——剪枝的正确性完全建立在有序性上，这也是本讲唯一”必须传引用而不传值”也成立的场景（传引用省去每次 O(n) 拷贝，官方在第 9 讲明确传值会变 O(n) 操作）。第二，基准情形 lo > hi：区间收缩到 lo 越过 hi 说明搜索空间已空，这正是”用递归把迭代终止条件表达出来”的典范；空数组经包装函数进入后 hi = −1，同样安全返回。第三，两个同名函数靠参数个数区分（3 参数版 + 2 参数版），这就是函数重载：编译器看到 binarySearch(v, key) 自动选 2 参数版，看到四参调用选 3 参数版。每层递归栈深 O(log n)，约 log₂(10) ≈ 4 层即可查完 10 个元素。

示例 4：递归生成全排列——枚举的雏形

#include <iostream>
#include <string>
using namespace std;

// soFar：已经确定的前缀；rest：还没安放位置的剩余字符
void permute(const string& soFar, const string& rest) {
    if (rest.empty()) {                 // 基准：没有剩余字符 → 得到一个完整排列
        cout << soFar << endl;
        return;
    }
    for (int i = 0; i < (int)rest.length(); ++i) {
        // 把 rest[i] 安到下一个位置，剩余字符 = 去掉 rest[i] 后的串
        string newRest = rest.substr(0, i) + rest.substr(i + 1);
        permute(soFar + rest[i], newRest);   // explore 每一个候选
    }
}

// 包装函数：从空前缀、完整字符串开始
void permute(const string& s) {
    permute("", s);
}

int main() {
    permute("cat");   // 应输出 6 个排列：cat cta act atc tca tac
    return 0;
}

【代码做什么】：permute("", "cat") 在每一层用 for 循环遍历 rest 里的每个字符，将其追加到 soFar 并递归处理剩余字符。当 rest 为空，说明所有字符都已就位，输出一个排列。共输出 3! = 6 行。

【实现机制解说】：这是”决策树”式递归的第一次正式登场：第 1 层有 3 个分支（c/a/t 谁打头），第 2 层每个分支又有 2 个选择，第 3 层 1 个，叶子总数 3×2×1 = 6。因为 soFar、rest 都是按值传递的新拷贝，父调用自身状态从未被改动，返回上一层时”天然撤销”了本层的选择——这个特性在下一讲的回溯里会与”共享状态需要显式撤销”形成鲜明对比。若把本函数改成硬币序列：for 循环换成两次固定递归 coinFlip(soFar+'H', n-1) 与 coinFlip(soFar+'T', n-1)，就得到 2ⁿ 个 H/T 序列（官方第 9 讲的 coinFlip 正是如此）——排列与序列共享同一套”递归枚举”骨架。注意按值传串有拷贝开销（总代价量级 O(n·n!)），面试改进版是传引用 + swap（官方第 10 讲展示过 swap 版排列，需在递归后把字符换回来，即”撤销”）。

复杂度分析

注意：”最好/最坏”永远指输入规模任意大时的差异（官方在第 9 讲强调：不能说”输入只有一个元素时最快”，那样任何函数都成 O(1) 了）；另外回文的 substr 切片版每层复制剩余串，最坏 O(n²)，用下标版可回到 O(n)。

关键要点

• 三要素缺一不可：先有能直接回答的基准情形，再写把输入缩小并调用自己的递归步骤——否则要么栈溢出，要么根本没在递归。
• 用信任飞跃写递归：先假设”更小输入的递归调用是对的”，只检查当前层如何拼装子结果；不要逐层手工追踪。
• 语句的位置决定时机：递归调用之前的代码在”递”时执行，之后的代码在”归”时执行——逆序打印的秘密就在这一行顺序里。
• 用包装函数 + 重载把”用户接口”和”递归细节”分开，让调用者只传最少的参数。
• 递归是”分而治之/自相似”的思维工具：二分把 O(n) 降到 O(log n)，枚举天然指数/阶乘级——能用递归几行说清的问题，往往迭代写起来又长又绕。

常见陷阱与注意事项

1. 忘基准情形或基准漏输入：如 factorial 只判 n == 1，调用 factorial(0) 会无限调用 factorial(-1)… 直至栈溢出（官方 Common Pitfall #2）。规避：把 0、空串这类”边界但合法”的输入都列出来测试；若参数改 unsigned，负数会下溢成巨大正数，同样死循环——类型替代不了基准设计。
2. int 函数漏 return：写下 n * factorial(n - 1); 却没写 return（官方 Common Pitfall #1），结果未定义。规避：编译加 -Wall，并把返回值直接写在 return 表达式里。
3. 回文忘了比较首尾：函数变成恒真，且全 true 的测试还发现不了（官方 Pitfall #3）。规避：测试集必须包含期望 false 的用例。
4. 递归调用不向基准靠拢（如 foo(n+1) 却以 n==0 为基准）。规避：写前先确认每层参数严格”变小”。
5. 改名后忘改函数体内的递归调用（官方 Pitfall #4，常见于复制粘贴）。规避：改名后全文搜索旧函数名。
6. 中点公式写成 (lo+hi)/2 导致大区间溢出崩溃。规避：一律 lo + (hi - lo) / 2。
7. 把换行/收尾语句放进逆序打印的基准情形：换行会出现在整串之前。规避：收尾工作交给包装函数。
8. 每层用 substr 造大拷贝：递归深、串长时浪费严重。规避：传引用 + 下标参数（如 printStringHelper 风格）。

思考题（带答案）

问题 1：把 factorial 的基准情形从 n == 0 改成 n == 1，然后调用 factorial(0) 会发生什么？为什么？ 答案：factorial(0) 不会命中基准（0 ≠ 1），于是调用 factorial(-1)、factorial(-2)……参数不但没向 1 靠拢反而越来越远，栈帧无限堆积，最终栈溢出崩溃。基准情形必须覆盖全部合法输入的边界，且递归方向必须朝向基准。 问题 2：用”信任飞跃”写递归二分查找时，你具体信任了什么？哪些细节可以完全不管？ 答案：信任 binarySearch(v, key, lo, mid-1) 与 binarySearch(v, key, mid+1, hi) 这两个”更小区间”的调用会各自返回正确下标或 −1——不必手工模拟这两次调用内部几十帧的执行。你只需要确保：区间确实在收缩（mid 两侧都严格小于原区间）、基准 lo > hi 正确、以及比较逻辑（小于走左、大于走右、相等命中）在当前层是对的。若这三件事成立，整体必然正确。 问题 3：为什么逆序打印字符串的 endl 不能放在基准情形里？正确的放置位置在哪？ 答案：基准情形是整条递归链最早执行的代码（它在”归”的起点），放在那里会让换行先于任何字符打印出来（输出变成先空一行再是反转串）。正确做法是把换行放在包装函数里：包装函数调用完递归主体后再补 endl，于是换行恰好出现在所有字符之后（官方第 8 讲 printStringReverse 的解法）。

Lecture 6: 递归回溯与枚举（Recursive Backtracking & Enumeration）（对应课程真实讲座 L11–L12）

概述

本讲在”枚举”（序列、排列、子集）的基础上引入递归回溯（recursive backtracking）：沿着决策点一步步尝试，撞上死胡同就退回上一个决策点换一条路，并把这一范式归纳为三字诀 choose–explore–unchoose（选择—探索—撤销）。我们会用生成子集、集合平分 isPartitionable、0-1 背包三个经典问题吃透回溯骨架与指数复杂度，为后面迷宫、数独等”迭代很难写”的问题储备通用武器。 （对应官方 2026 夏季 CS106B：L11 Thursday, July 9 “Recursive Backtracking and Enumeration”；L12 Monday, July 13 “More Recursive Backtracking”。官方用迷宫小人动画演示回溯：一路 Search…，碰壁就 Backtrack… 回到上一个岔路口换方向。）

核心概念与算法原理

1. 序列、排列、子集：三类枚举问题一家亲 官方在第 11 讲先做了小结：我们已能用递归生成三类结果——序列（抛 n 次硬币 2ⁿ 种、掷 n 次骰子 6ⁿ 种）、排列（”cat” 的 6 种重排）、子集（{a, c, t} 的 8 个子集，含空集）。它们都长在同一棵”决策树”上，区别只是每层的分支数（2、n、6…）与何时停止。子集问题里顺序无关，{b, a} 与 {a, b} 算同一个子集，所以决策树只需考虑”每个元素要 or 不要”，共 2ⁿ 个叶子。

2. 回溯是什么：碰壁就回头

• 问题定义：在多个连续决策构成的状态空间中搜索满足条件的解；当前路径走到头仍无解（死胡同 dead end）时，回到最近一个还有未试选项的决策点，改走另一条路，而不是从头重来。
• 直观解释：走迷宫——每个岔路口是一个决策点；走到死路就退回上一个岔路口选另一条走廊；再死路再退。官方动画里的小人正是这样”Searching… / Backtracking…”反复进退。若迷宫可绕圈，还需”撒面包屑”标记走过的地方，防止在两个格子间无限往返（即回溯骨架中的”查重状态”环节）。

3. 回溯的标准骨架：choose–explore–unchoose 把回溯算法解剖开，官方在第 11 讲给出如下通用结构（每步是否必需因问题而异）：

1. 基准情形（base case）：到达叶子。若当前状态是解 → 打印/计数/返回 true；
   否则返回"此路不通"的哨兵值（false / 0）。
2.（可选）查重：若进入过相同状态（如迷宫已撒过面包屑的格子）→ 直接返回。
3. 生成候选：用循环枚举本决策点的全部合法选择；非法选择跳过（剪枝）。
   对每个候选：
   a. 改变状态（choose）     —— 把选择付诸实施（放入容器/移动棋子/计入和）
   b. 递归深入（explore）    —— 带着新状态调用自己
   c. 处理返回值（可选）     —— 命中即停（return true）或累加计数
   d. 撤销状态（unchoose）   —— 把 a 的改动还原，供下一个候选使用

关键认识：什么情况下必须显式撤销？ 官方特别指出：若问题状态（容器/网格/字符串）是按值拷贝传下去的，父调用的拷贝从未被改动，函数返回即天然回到旧状态，”撤销”就自动完成了（上一讲的子集字符串版正是如此）；若状态是按引用共享的（vector、数组、网格），子调用对它的修改会永久残留，返回后必须手动撤销，否则兄弟分支看到的是一副被掏空/改坏的状态。本节三个例子里，子集用”按值”免撤销，平分与背包用”共享容器 + 显式撤销”。

4. 子集决策树与回溯撤销示意图

上半：子集 {a, b} 的决策树（每层决定“要/不要”一个元素；叶子 = 一个子集）
                       (soFar="", 待决策 a, b)
                    /                            \
           不要 a                               要 a
           /      \                            /      \
      不要 b      要 b                     不要 b     要 b
         |          |                        |          |
        {}         {b}                      {a}       {a,b}
     (计1)       (计1)                    (计1)      (计1)
    → 叶子共 4 = 2²：每个元素两种选择，路径即子集

下半：共享容器的 choose / unchoose 必须配对（isPartitionable 的 rest 容器，示例见后）
   深入（choose + explore）                        返回（unchoose）
   rest = {1,1,2,3,5}  取出 5 → 尝试放进某一组     把 5 放回 → rest 复原
   rest = {1,1,2,3}    取出 3 → …                 放回 3 → …
   rest = {1,1,2}      取出 2 → …                 放回 2 → …
        ……                                            如果不放回，回溯到兄弟分支时
                                                     rest 已被掏空，无物可选，
                                                     结果必错（见陷阱 1）

5. 把”打印”改成”计数/返回 bool”：三种返回风格 同一副骨架，只要改基准情形的返回值与返回语句的汇总方式，就能切换用途（官方在第 11 讲把 printSubsets 改成返回子集个数，并强调这种变形必须掌握）：叶子处 return 1（或解的值）、内部用 + 汇总 → 计数；叶子处 return 布尔条件、内部用 || 汇总 → 判断”是否存在解”。bool 版本还白得一个福利——短路求值（short-circuiting）：a || b 中 a 为 true 时 C++ 根本不会执行 b，于是”找到一个解就整棵树提前停止”不用写任何额外代码（官方第 11 讲用 isPartitionable 的两个版本对比了短路带来的巨大差异）。bool 函数收尾也建议直接 return sum1 == sum2; 而不是 if-else 绕弯。

6. isPartitionable：集合能否平分成两组

• 问题定义：能否把向量 V 的元素全部、恰好一次地分进两组 V₁、V₂，使两组元素和相等？例：{1,1,2,3,5} 可分（{1,5} 与 {1,2,3} 各为 6）；{1,4,5,6} 不可分。
• 思路：对每个元素做二选一（进组 1 / 进组 2），全部放完时检查两桶和是否相等。这是”子集”骨架的 bool 版本，且官方实现用了”从剩余容器取一个元素 + 递归后放回”的显式撤销写法。

7. 0-1 背包：struct 承载物品 + 剪枝

• 问题定义（官方第 12 讲）：背包容量 c，物品 i 有重量 wᵢ 与价值 vᵢ，每个物品只能整件拿或不拿（”0-1”即二选一），求不超过容量前提下的最大总价值。贪心（先拿最贵的，或按 v/w 比值拿）都不保证最优——官方给了反例：容量 10，物品 (w=8,v=160) 与三个 (3,58) 加一个 (1,2)：按比值贪心拿 8 号只能再拿 1 号得 162，而拿后四个共重 10 得 176。
• 剪枝（pruning）：某物品比剩余容量还重时，它不可能被拿，只能走”不拿”单分支——这比盲目二分少了半棵子树。官方原话是：背包问题里并非每个物品都面对二选一，”拿不动就被迫放弃”。
• C++ 配套知识——struct（结构体）：把重量与价值打包成一个新类型，避免两个平行 vector 错位（官方第 12 讲演示了 weights/values 分开存的风险）。定义写在函数外、右花括号后必须有分号；成员用 . 访问：Item i; i.weight = 4;。

8. 官方三种背包递归写法对照：为什么有的要撤销、有的不用？ 官方在第 12 讲一口气展示了三种等价写法，目的是让人看到”同题多解、各有权衡”，并强调考试不要求复刻某种写法、只要求正确可读。三者的本质差别是状态如何管理，而”要不要 unchoose”完全由此决定：

本节示例 3 采用”方案 2 + 剪枝”：既保有按引用传容器、避免按值拷贝整表的效率，又因为只用下标游走而完全免去 unchoose 簿记——是初学者最容易写对的一种。

代码示例与实现详解

下面 3 个示例只依赖 C++17 标准库，可独立编译运行。

示例 1：生成子集（打印版 + 计数版 + bool 判断版）

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 打印版：soFar=已选元素组成的子集，rest=尚未决策的元素
void printSubsets(const string& soFar, const string& rest) {
    if (rest.empty()) {                     // 全部元素决策完毕 → 打印一个子集
        cout << "{" << soFar << "}" << endl;
        return;
    }
    string newRest = rest.substr(1);        // 剥出当前元素 rest[0] 后的剩余
    printSubsets(soFar, newRest);           // 不要 rest[0]（exclude）
    printSubsets(soFar + rest[0], newRest); // 要 rest[0]（include）
}

// 计数版：把打印换成“每片叶子贡献 1”，内部用 + 汇总
int countSubsets(const string& soFar, const string& rest) {
    if (rest.empty()) {
        return 1;                           // 到达一个完整子集 → 计 1
    }
    string newRest = rest.substr(1);
    return countSubsets(soFar, newRest) +   // 不要
           countSubsets(soFar + rest[0], newRest);   // 要
}

// bool 版：是否存在某个子集，其元素和恰好等于 target？
// nums 只读，用下标 k 游走（无需撤销）；叶子直接给出“这条路成不成”
bool hasSubsetSum(const vector<int>& nums, int k, int sumSoFar, int target) {
    if (k == (int)nums.size()) {
        return sumSoFar == target;
    }
    // 不选 nums[k] 或 选 nums[k]；|| 短路 → 一旦找到 true 立即整树停止
    return hasSubsetSum(nums, k + 1, sumSoFar, target) ||
           hasSubsetSum(nums, k + 1, sumSoFar + nums[k], target);
}

int main() {
    printSubsets("", "ab");                 // 输出 {} {b} {a} {a,b}（顺序因先 exclude）
    cout << "子集总数: " << countSubsets("", "abc") << endl;   // 8 = 2³
    cout << "存在和为6的子集: " << hasSubsetSum({1, 2, 3, 7}, 0, 0, 6) << endl; // 1（1+2+3）
    return 0;
}

【代码做什么】：printSubsets("", "ab") 沿决策树下行：每个元素先试”不要”再试”要”，到叶子（rest 空）打印 soFar，共 4 行；countSubsets 结构完全相同，仅把叶子行为从打印改成 return 1、把两条递归路径用 + 相连，于是根调用返回 2³ = 8；hasSubsetSum 是第三个”bool 风格”函数：对 nums 里每个元素同样做”不选/选”的二选一，叶子用 sumSoFar == target 判定成败，主函数里 {1,2,3,7} 存在子集 {1,2,3} 和为 6，输出 1。

【实现机制解说】：soFar/rest 都是按值参数，每层调用拿到的是父状态的拷贝，因此不需要任何显式撤销——这就是第 3 节”按值天然撤销”的实例。三个函数演示了”打印 → 计数 → 判断”的返回风格切换：叶子处 return 1 并用 + 汇总得计数；叶子处返回布尔条件并用 || 汇总得判断，而 || 的短路让”找到解就整棵停止”零成本发生（官方在第 11 讲强调这种变形必须熟练掌握）。代价也要看清：递归调用数 2ⁿ 是指数级，若 n 大到 30+，即使每层 O(1) 也无法承受——官方提醒，对指数算法连”每层多一次 O(n) 的字符串拷贝”都会被放大成明显变慢，面试时往往要改成传引用 + 下标的高效版。

示例 2：isPartitionable——回溯 + 显式撤销 + 短路早停

#include <iostream>
#include <vector>
using namespace std;

// rest: 还没分配的元素（共享容器，按引用）；sum1/sum2: 两组当前总和
bool isPartitionable(vector<int>& rest, int sum1, int sum2) {
    if (rest.empty()) {                 // 基准：元素全部分完 → 两桶和相等即成功
        return sum1 == sum2;
    }
    int item = rest.back();             // 从末尾取（O(1)，比从 0 号取快）
    rest.pop_back();                    // ← choose：item 离开“待分配”容器
    // explore：两条路——给组1 或 给组2。|| 短路 → 组1 成功就不再探索组2
    bool ok = isPartitionable(rest, sum1 + item, sum2) ||
              isPartitionable(rest, sum1, sum2 + item);
    rest.push_back(item);               // ← unchoose：放回，供兄弟分支继续用
    return ok;
}

// 包装函数：两组初始和都是 0
bool isPartitionable(vector<int>& v) {
    return isPartitionable(v, 0, 0);
}

int main() {
    vector<int> a = {1, 1, 2, 3, 5};
    vector<int> b = {1, 4, 5, 6};
    cout << "可分: {1,1,2,3,5} -> " << isPartitionable(a) << endl;   // 1 (true)
    cout << "可分: {1,4,5,6}   -> " << isPartitionable(b) << endl;   // 0 (false)
    return 0;
}

【代码做什么】：isPartitionable 每次从 rest 末尾取一个元素，递归尝试把它放进组 1 或组 2；rest 空了就检查两组和。主函数验证两个官方用例：{1,1,2,3,5} 可分（如 {1,5} 与 {1,2,3}），{1,4,5,6} 不可分。

【实现机制解说】：这是”共享状态 + 显式撤销”的标准样板，请对照第 3 节骨架逐行读：pop_back 是 choose；两处递归是 explore；push_back 是 unchoose，它必须与 choose 一一配对，位置在返回值算完之后、return 之前。若删掉 push_back，第一分支把 rest 掏空后不还原，回溯到上层换走另一条分支时容器是空的，函数会在半途的某个 sum 组合上误判成功——官方演示过：删掉该行后 {1,4,5,6} 会错误地返回 true。另外两处细节：短路——若组 1 的分支已返回 true，|| 右侧的组 2 分支根本不执行，整棵搜索树立即收工；取末尾而非取开头——pop_back/push_back 都是 O(1)，而从下标 0 移除/插入是 O(n)，在指数递归里每一层省下的 O(n) 会放大成巨大差异（官方第 11 讲的 Exam Prep 专门点了这一点）。

示例 3：0-1 背包回溯版（struct Item + 剪枝）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {           // 注意：struct 定义在函数外；右花括号后要有分号！
    int weight;
    int value;
};

// 从下标 k 起的物品中挑，剩余容量 capacity，返回能获得的最大价值
int knapsack(const vector<Item>& items, int capacity, int k) {
    if (k == (int)items.size()) {       // 基准：没有物品可选了
        return 0;
    }
    const Item& it = items[k];
    int best = knapsack(items, capacity, k + 1);   // 不拿：作为基线
    if (it.weight <= capacity) {        // 剪枝：拿不动只能放弃（少走半棵子树）
        int take = it.value + knapsack(items, capacity - it.weight, k + 1);
        best = max(best, take);
    }
    return best;                        // 拿与不拿中取更优
}

// 包装函数：从第 0 号物品、满容量开始
int knapsack(const vector<Item>& items, int capacity) {
    return knapsack(items, capacity, 0);
}

int main() {
    vector<Item> items1 = {{4,6}, {2,4}, {3,5}, {1,3}, {6,9}, {4,7}};  // {w, v}
    vector<Item> items2 = {{8,160}, {3,58}, {3,58}, {3,58}, {1,2}};
    cout << "容量10 最优价值: " << knapsack(items1, 10) << endl;   // 19
    cout << "容量10 最优价值: " << knapsack(items2, 10) << endl;   // 176（贪心只有162）
    return 0;
}

【代码做什么】：对每个物品做”拿/不拿”决策。拿得动才尝试拿（剪枝），拿与不拿两个候选取 max；基准是没有物品可选时价值为 0。主函数复现官方两个测试：前者最优 19（拿 2、3、5 号与 (4,7) 号：重 10 值 19），后者最优 176——顺便戳穿贪心。

【实现机制解说】：这个版本采用官方的”下标 k 推进”写法：k 表示”前 k 件已决策、从第 k 件起待决策”，因此不需要修改任何共享容器，也就没有 unchoose 环节——撤销的缺失正是按引用传递但只用下标游走的红利（官方第 12 讲的方案 2/3 都属此类，方案 1 则需要显式把取出的物品放回）。再看复杂度与剪枝：最坏情形（每件都装得下）每个节点分裂成 2，是 O(2ⁿ)；最好情形（每件都超重）只剩”不拿”单分支，退化 O(n)。官方在第 12 讲坦率指出：这套朴素回溯不是最高效解法——同一条递归树里有大量重复子问题（如”还剩容量 3、还剩物品 3..n”会反复求解），后续课程会学 memoization（记忆化）与动态规划把它优化到多项式级，本章只要求掌握回溯骨架与指数本质。

复杂度分析

说明：三个问题的共同点是”决策树叶子数随 n 指数增长”，n 每加 1 工作量翻倍——这就是官方反复强调”指数运行时不可扩展”的原因：n = 30 的 2³⁰ ≈ 10 亿次调用已接近极限，n = 60 则彻底不可行。剪枝与短路只能砍掉明显无望的分支，不能改变指数本性。

关键要点

• 把回溯背成三字诀：choose（改状态）→ explore（递归）→ unchoose（还原），三步缺一不可、顺序不乱。
• 状态按值拷贝则返回即撤销；状态按引用共享则必须显式撤销，且撤销与选择严格配对——放回位置在递归返回之后、return 之前。
• 同骨架三种返回风格：叶子打印（void）、叶子 return 1 + 内部 + 汇总（计数）、叶子返回布尔条件 + 内部 || 汇总（判断）；bool 版用短路免费获得”找到即停”。
• 剪枝要趁早：在递归调用之前用约束检查砍掉不可能的分支（超重强制不拿），一行 if 常常省下半棵子树。
• 回溯解是”正确性优先”的暴力搜索：指数复杂度注定了它只适合小规模 n；看到大规模输入要立刻想到 memo/DP 这类优化方向。

常见陷阱与注意事项

1. 忘了 unchoose：共享容器（vector/数组）被上一层分支掏空或改坏，兄弟分支得到错误状态，结果可能”假阳性”（官方反例：删掉放回行后 {1,4,5,6} 误报可分）。规避：凡按引用修改状态，写完后立刻补还原语句，并用”两个分支都要正确”的用例测试。
2. 把 unchoose 写在 return 之后：那条语句永远不执行，等于没写。规避：还原必须发生在返回之前；若提前 return，先把还原语句复制到每个出口前面。
3. 短路被误用/漏用：a || b 只在 a 为 false 时才执行 b——若两个分支都有必须执行的”收尾动作”（如各放回一个元素），把它们都包在递归调用内部或先算出两个 bool 再合并。官方指出：先 bool r1 = f(); bool r2 = g(); 再 r1 || r2 会失去短路带来的早停。
4. 修改了按引用传入的调用方数据且不还原：即使算法正确，调用者的 vector 也被毁了。规避：要么只读 + 用下标游走，要么严格 choose/unchoose 配对。
5. 基准情形漏掉空输入/空容器：空集可分吗（两空桶和为 0 相等，答案是 true）？空物品的背包价值是 0？先想清楚边界再写代码。
6. 误用贪心代替搜索：0-1 背包按价值或 v/w 贪心都可能次优（官方两个反例）。规避：只要题目说”最大/最优 + 组合爆炸”，先按回溯枚举想，别默认贪心成立。
7. struct 定义细节：右花括号忘分号、定义在函数内部、成员名拼错。规避：struct 放函数外、}; 结尾、用 . 访问成员。
8. 在指数递归里埋 O(n) 操作（在开头删元素、每层复制整串）：n 稍大就慢到不可接受。规避：优先从容器末尾操作或改用下标参数。
9. 把”顺序无关”的子集当成”顺序有关”的排列去枚举：对 {a, b} 会同时生成 {a, b} 与 {b, a}，既重复又使规模从 2ⁿ 膨胀成 n! 量级。规避：子集决策树里元素顺序固定，每个元素只决策一次”要/不要”；只有真正讲究顺序的问题才用排列骨架。
10. 计数版基准情形 return 0 而不是 return 1：空子集也是合法子集，叶子应计 1；return 0 会让 countSubsets("") 输出 0（正确应为 1），并在更大集合上少算。规避：先在空输入上验证边界：countSubsets("") 应为 1、空集合的”子集存在和 target”问题要单独想清语义。

思考题（带答案）

问题 1：把示例 1 的 countSubsets 改成”bool 风格”：判断集合中是否存在某个子集，其元素之和等于给定目标值 target。只需要改动哪几处？ 答案：签名变为 bool subsetSumExists(const vector<int>& nums, int k, int sumSoFar, int target)：基准改为 if (k == nums.size()) return sumSoFar == target;；中间不再需要 + 计数，而是 return subsetSumExists(..., k+1, sumSoFar, target) || subsetSumExists(..., k+1, sumSoFar + nums[k], target);（分别对应不选/选当前元素）。|| 的短路保证一旦某分支凑出 target，其余分支立即停止——这是”打印→计数→判断”三种返回风格切换的标准示范。 问题 2：官方演示过：把示例 2 中 rest.push_back(item)（unchoose）那一行删掉，{1,4,5,6} 这个本应返回 false 的输入会错误地返回 true。请解释为什么。 答案：没有放回，第一分支（把元素逐个试放进组 1/组 2）递归到底把 rest 掏空后就再没还原过。返回上层尝试”另一个组”时，rest 仍是空的，函数立刻命中基准 rest.empty()，拿当时半途的 sum1、sum2 直接比较——某个中间状态下两桶和恰好相等，于是误报 true。可见 unchoose 不是风格问题而是正确性要求：它保证每个分支看到的 rest 都是”自己该决策的那批元素”。 问题 3：0-1 背包回溯的最坏复杂度 O(2ⁿ) 何时出现？”超重只能不拿”的剪枝为什么能让最好情形降到 O(n)？ 答案：最坏出现在每个物品都轻于或等于剩余容量、每个节点都分裂出”拿/不拿”两个递归调用，形成满二叉树 2ⁿ 片叶子；最好情形是每件物品都超重，每个节点只有”不拿”一条分支，递归变成一条直线 O(n)。剪枝的本质是：装不下的选择不可能成为最优解的一部分，提前砍掉它既不影响正确性，又避免探索一整棵注定无解的子树。

Lecture 7: 排序算法：选择、插入、归并与快速排序（Sorting: Selection, Insertion, Merge & Quicksort）（对应课程真实讲座 L13）

概述

本讲系统学习四类排序算法：先讲两个 O(n²) 的朴素算法——选择排序与插入排序，通过它们体会”比较多 vs 交换多”的工程权衡；再讲分治思想的代表归并排序 O(n log n)，最后简介快速排序。排序是无数上层算法（二分查找、去重、中位数、统计）的基石，官方称其在计算机科学中应用极广；学会从”最好/平均/最坏 + 空间”四个维度比较算法，是本讲真正的目的。 （对应官方 2026 夏季 CS106B：L13 Tuesday, July 14 “Sorting Algorithms”。官方配套发布了 sorting-stuff.zip 幻灯片与代码，并附有选择/插入/归并在不同规模随机向量上的实测耗时对比。）

核心概念与算法原理

先约定：本课程说”已排序（sorted）”默认指非降序（从小到大，允许相等），这比”严格递增”更精确（官方第 9 讲的定义）。下面所有算法都在原容器内就地排序，只依赖元素间的 < 比较，属于比较排序。

1. 选择排序（selection sort）——”多看少动”的等待型算法

• 问题定义：把数组从小到大排好序。
• 直观解释：像每次从一堆牌里挑出最小的一张放到最前面，再在剩下的牌里挑最小的放第二位……直到挑完。每轮只做一次交换，但为了确定”谁最小”要比较很多次——官方戏称它是”wait and see”算法，花大量时间比较，才决定把哪个元素换到目标位。
• 步骤分解：
  1. 维护前缀 [0, start) 已排好，start 从 0 开始；
  2. 在 [start, n) 里线性扫描找出最小值下标 minIdx（第一轮 n 次比较，第二轮 n−1 次……）；
  3. 把 v[start] 与 v[minIdx] 交换（每轮至多 1 次）；
  4. start++，重复直到只剩一个元素。
• 逐轮走查（竖线左边是已排序前缀）：

数组 [3 1 4 2]
第1轮 start=0：扫 [3 1 4 2] 最小=1 → 交换 → [1 | 3 4 2]
第2轮 start=1：扫 [3 4 2]  最小=2 → 交换 → [1 2 | 4 3]
第3轮 start=2：扫 [4 3]    最小=3 → 交换 → [1 2 3 | 4]
第4轮 只剩 4，结束。比较总次数 = 3+2+1 = n(n-1)/2，即 O(n²)

2. 插入排序（insertion sort）——”边走边停”的理牌算法

• 直观解释：像打扑克理牌：左手牌已排好，右手每次摸一张新牌，把它往左拖，一路与左边的牌比较，直到遇到比它小的牌就停，落位。官方戏称它是 “let’s gooooo!” 算法——每经过一个位置就交换/挪动一次，但一旦遇到更小的牌立即停止，因此比较次数可能远少于选择排序。
• 步骤分解：
  1. 前缀 [0, start) 已有序，start 从 1 开始；
  2. 取 key = v[start]（新摸的”牌”），在已排序前缀里从右向左把比 key 大的元素逐个右移一格（腾出空位）；
  3. 遇到 ≤ key 的元素或到达开头，把 key 填入空位；
  4. start++ 重复。
• 逐轮走查：

数组 [3 1 4 2]
第1轮 取1：3>1 → 3右移 [3 3 4 2]，1落位 → [1 3 4 2]
第2轮 取4：3<4 立即停，原位不动      → [1 3 4 2]
第3轮 取2：4>2右移、3>2右移、1<2停   → [1 2 3 4]
对“已有序输入”，每轮只比 1 次就停 → 总比较 n-1 次，O(n)！

3. 比较多 vs 交换多：工程权衡（官方第 13 讲重点） 选择排序比较多、交换少（O(n²) 次比较但最多 n−1 次交换）；插入排序交换/挪动可能多、比较可以少（遇到小牌提前停）。官方给的场景化例子很形象：

选择/插入的其他取舍：插入排序对”几乎有序”数据表现惊艳（官方建议：若应用里输入经常接近有序，选插入排序吃它的最好情形 O(n)）；而排序算法越简单越容易写对、容易调试——快速原型 vs 极致性能之间永远要权衡。

4. 归并排序（merge sort）——”先分后合”的分治算法

• 问题定义与思路：把数组从中间一分为二，递归把两半各自排好，再写一个”合并（merge）”过程把两个有序子数组合成一个有序数组。官方概括为”易分难合（easy split, hard join）“：拆是两行递归的事，难点全在合并。
• 步骤分解：
  1. 基准：区间只剩 0 或 1 个元素，天然有序，直接返回；
  2. 分：mid = lo + (hi - lo) / 2（防溢出公式，官方再次强调 (lo+hi)/2 会溢出），递归排 [lo, mid] 与 [mid+1, hi]；
  3. 合：用两个指针 i、j 分别指向左右两半开头，每次把较小者放入辅助数组 aux；某半耗尽后把另半剩余整体倒入；最后把 aux 拷回原区间。
• 递归树与复杂度图解（每层总工作量 O(n)，共约 log₂n 层）：

               [38 27 43 3 9 82 10]
              /                     \
      [38 27 43 3]              [9 82 10]
       /        \                /      \
   [38 27]    [43 3]         [9 82]    [10]
   /    \     /    \         /    \
 [38]  [27] [43]  [3]      [9]  [82]      ← 拆到单元素（分）
      ↑ 每层“合”的工作量加起来都是 O(n)，层数 O(log n) → 总 O(n log n)
   [27 38]  [3 43]        [9 82]    [10]
      \        /            \        /
   [3 27 38 43]            [9 10 82]
          \                    /
      [3 9 10 27 38 43 82]            ← 最终有序（合）

• 合并过程示例（左右各一指针，比较后取小者放入辅助区）：

左半 [3 27 38 43]   右半 [9 10 82]
i→3  vs  9 → 取3            aux: [3]
i→27 vs  9 → 取9            aux: [3 9]
i→27 vs 10 → 取10           aux: [3 9 10]
i→27 vs 82 → 取27           aux: [3 9 10 27]
……直至右半耗尽，左半剩余 [38 43] 整体倒入 → aux: [3 9 10 27 38 43 82]

• 缺点（官方明说）：① 合并需要 O(n) 辅助空间，内存吃紧时不合适；② 递归调用有压栈开销，对很小的数组（如 ≤100 个元素）选择/插入反而更快——官方实测：n=10 时三者都在毫秒级且插排略胜；n=100 时归并才开始反超；n=50,000 时差距拉大到 2.4 秒（选择）vs 1.4 秒（插入）vs 约 7 毫秒（归并）。

5. 快速排序（quicksort）——”难分易合”，实践中最快之一

• 官方把它与归并对比：归并是”易分难合”，快排是”难分易合（hard split, easy join）“——难点在 O(n) 的分区（partition），合并不需要（递归返回时数组已经就位，官方原话：join 是递归的自然结果）。
• 步骤分解：
  1. 选一个基准 pivot（示例取区间末尾元素）；
  2. 分区：一趟把数组重排为”≤ pivot 的元素都在左，pivot 居中，> pivot 都在右”，返回 pivot 最终下标 p——一趟 O(n)；
  3. 递归排序 pivot 左右两个子区间（都严格小于原区间）；
  4. 基准：区间 ≤ 1 个元素。
• 快排性质：平均 O(n log n)、最坏 O(n²)（见”最坏情形”：已有序输入 + 固定取尾做 pivot 时，每趟只切掉一个元素）；实践中因为原地交换、缓存友好，往往跑得比归并还快——这也是它名字的由来。官方说明快排会在后续作业与 CS161 中正式登场，本讲只要求理解分区思想。

代码示例与实现详解

下面 3 个示例只依赖 C++17 标准库、自包含可编译。

示例 1：选择排序与插入排序

#include <iostream>
#include <utility>      // std::swap
#include <vector>
using namespace std;

// 每轮找未排序区间的最小值，换到区间开头
void selectionSort(vector<int>& v) {
    for (int start = 0; start < (int)v.size() - 1; ++start) {
        int minIdx = start;                     // 假设当前位已是最小
        for (int j = start + 1; j < (int)v.size(); ++j) {
            if (v[j] < v[minIdx]) minIdx = j;   // 只更新下标，不急着交换
        }
        swap(v[start], v[minIdx]);              // 每轮至多一次交换
    }
}

// 每轮取未排序区第一个元素，往左拖到合适位置（比它大的整体右移）
void insertionSort(vector<int>& v) {
    for (int start = 1; start < (int)v.size(); ++start) {
        int key = v[start];                     // 新摸的“牌”
        int gap = start;                        // 空位从 start 开始向左找
        while (gap > 0 && key < v[gap - 1]) {   // 左邻更大 → 右移腾位
            v[gap] = v[gap - 1];
            --gap;
        }
        v[gap] = key;                           // key 落位
    }
}

void show(const vector<int>& v) {
    for (int x : v) cout << x << ' ';
    cout << endl;
}

int main() {
    vector<int> a = {3, 1, 4, 2};
    vector<int> b = a;
    selectionSort(a);   cout << "选择排序: "; show(a);
    insertionSort(b);   cout << "插入排序: "; show(b);
    return 0;
}

【代码做什么】：两个排序函数各就各位地对同一个输入演示。selectionSort 双层循环：外层固定”待安放位置”，内层找最小、外层结束后才交换一次；insertionSort 把新元素存进 key，用 gap 指针把比它大的元素一个个右移，最后把 key 写回空位（这就是”拖拽”的实现，官方代码里管这张牌叫 peach）。

【实现机制解说】：选择排序的交换必须放在内层循环之外——内层只是不断刷新 minIdx，找到最终目标才动手，否则每发现一个更小值就换一次，交换次数会从 O(n) 退化到 O(n²)（这正是”比较多 vs 交换多”取舍的代码体现）。插入排序的移动是整体平移而非两两交换：v[gap] = v[gap-1] 把大牌往右推一格，key 始终攥在手里，最后一次性落位，一趟的写次数等于”它左边比它大的元素个数”；而 while 的提前退出条件 key < v[gap-1] 一旦不成立（左邻 ≤ key）立即停止——对已排序输入，每轮只比较 1 次，整趟 O(n)，这就是插入排序最好情形的来源。两函数都就地修改、空间 O(1)。

示例 2：归并排序（递归 + 辅助 vector 归并）

#include <iostream>
#include <vector>
using namespace std;

// 归并排序 v[lo..hi]（闭区间）
void mergeSort(vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;                   // 基准：0 或 1 个元素，天然有序
    int mid = lo + (hi - lo) / 2;           // 防溢出中点（勿写 (lo+hi)/2）
    mergeSort(v, lo, mid);                  // 分：左半
    mergeSort(v, mid + 1, hi);              // 分：右半
    // 合：双指针归并两个有序子数组
    vector<int> aux;                        // O(n) 辅助空间（本算法最大“缺点”）
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi)             // 两边都还有货：取较小者
        aux.push_back(v[i] <= v[j] ? v[i++] : v[j++]);
    while (i <= mid) aux.push_back(v[i++]); // 左半剩余整体倒入
    while (j <= hi)  aux.push_back(v[j++]); // 右半剩余整体倒入
    for (int k = 0; k < (int)aux.size(); ++k)   // 拷回原区间
        v[lo + k] = aux[k];
}

void mergeSort(vector<int>& v) {            // 包装函数（重载）
    if (!v.empty()) mergeSort(v, 0, (int)v.size() - 1);
}

int main() {
    vector<int> v = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(v);
    for (int x : v) cout << x << ' ';
    cout << endl;                           // 3 9 10 27 38 43 82
    return 0;
}

【代码做什么】：mergeSort(v, lo, hi) 先递归排左右两半，再用辅助 vector aux 完成”合”：两个游标 i、j 分别走在左右半，谁小谁进 aux；某半耗尽就整体倒入另一半剩余；最后把 aux 的 lo..hi 段拷回原位。包装函数负责对外只暴露 mergeSort(v) 一个参数。

【实现机制解说】：结合第 4 节的递归树理解执行流：mergeSort(v,0,6) 先递归到最深——[38]、[27] 等单元素区间逐一返回（基准 lo >= hi），然后归途上自底向上合并：[27 38]、[3 43]、[9 82]，再合并成 [3 27 38 43] 与 [9 10 82]，最后合成整段有序——合并总是发生在左右都已有序之后，所以双指针比较取小必然正确。归并用 <= 取左半元素，相等元素保持左先右后的相对顺序，因此归并是稳定的。三个 while 一个都不能少：主循环结束后必有一半先耗尽，剩余元素必须整体续尾，否则会丢元素。中点公式在此与二分查找同样防溢出。空间上每层合成都新建一个 aux，栈深度 O(log n) 层，同层最多共存约 n 大小的辅助区，故总辅助空间 O(n)。

示例 3：快速排序（完整小实现，Lomuto 分区）

#include <iostream>
#include <utility>      // std::swap
#include <vector>
using namespace std;

// 一趟分区：以末尾元素为 pivot，返回 pivot 最终位置；
// 结束后 pivot 左侧都 ≤ pivot，右侧都 > pivot
int partition(vector<int>& v, int lo, int hi) {
    int pivot = v[hi];
    int i = lo;                             // i 左边都是已确认 ≤ pivot 的
    for (int j = lo; j < hi; ++j) {
        if (v[j] < pivot) {                 // 发现该去左边的元素
            swap(v[i], v[j]);               // 换到“小元素区”末尾
            ++i;
        }
    }
    swap(v[i], v[hi]);                      // pivot 归位
    return i;
}

void quickSort(vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;                   // 基准：0/1 个元素
    int p = partition(v, lo, hi);           // “难”的一步：O(n) 分区
    quickSort(v, lo, p - 1);                // 左边递归（比 pivot 小的）
    quickSort(v, p + 1, hi);                // 右边递归（比 pivot 大的）
}

void quickSort(vector<int>& v) {
    if (!v.empty()) quickSort(v, 0, (int)v.size() - 1);
}

int main() {
    vector<int> v = {7, 2, 9, 3, 6, 1, 8, 5, 4};
    quickSort(v);
    for (int x : v) cout << x << ' ';
    cout << endl;                           // 1 2 3 4 5 6 7 8 9
    return 0;
}

【代码做什么】：partition 选末元素为 pivot，用快慢两个下标 i、j 扫一遍：j 负责考察每个元素，凡小于 pivot 的都与 i 所指位置交换，使 i 左侧始终是”已确认 ≤ pivot”的区域；扫描结束把 pivot 换到 i 处并返回 i。quickSort 递归排 pivot 左右两侧。主函数对 9 个乱序整数排序验证。

【实现机制解说】：体会”难分易合”：partition 一趟 O(n) 完成重排后，pivot 已在其最终位置，左右两侧只需各自递归——没有合并步骤，因为”合”被分区天然完成了。为什么平均 O(n log n) 而最坏 O(n²)？若 pivot 每次都能把区间切成大致两半，递归树与归并一样深 O(log n)、每层 O(n)，总计 O(n log n)；但若输入已有序且 pivot 固定取末尾，每趟分区只把 pivot 挪走一个位置（一侧为空），递归树退化成一条长链，深度 O(n) → 总 O(n²)。实践中快排快的原因：完全原地（无辅助数组）、缓存局部性好；工程上还会用”随机选 pivot 或三数取中”来避免有序输入触发最坏情形。注意本实现用 < 而非 <= 比较，重复元素会偏向 pivot 右侧，功能正确但可进一步优化。

复杂度分析

官方实测参考（随机向量多次取平均）：n=10 时三者耗时都在 1 ms 上下（插排 0.000793 ms 甚至略快于归并 0.001027 ms）；n=1,000 时归并（约 0.10 ms）反超插排（0.56 ms）；n=50,000 时选择约 2.43 s、插入约 1.38 s、归并约 7.4 ms——印证两点：递归/辅助开销让小 n 时简单算法更优，而 n 一大 O(n log n) 对 O(n²) 就是数量级碾压。稳定性上：插入、归并（用 <= 取左）稳定；选择、快排的常见就地实现不稳定——若”相等元素保持原相对次序”重要，选稳定算法。

关键要点

• 选择排序”多看少动”：O(n²) 次比较但只有 O(n) 次交换；每轮只交换一次（交换放内层循环外）。
• 插入排序”边走边停”：遇到不比它大的牌立即停，因此几乎有序的输入接近 O(n)——判断数据形态后优先考虑它。
• 归并排序”先分后合”：O(n log n) 最坏也稳，代价是 O(n) 辅助空间与小数组时的递归开销——空间紧张或 n 很小就别用它。
• 快排”难分易合”：分区一趟 O(n)，平均 O(n log n)、原地且缓存友好；pivot 选得差（有序输入）会退化 O(n²)。
• 没有”万能最好”的排序：选算法先问四个问题——输入规模多大？是否接近有序？比较/交换谁更贵？内存够不够？

常见陷阱与注意事项

1. 选择排序把交换写进内层循环：每发现更小值就交换一次，交换次数退化为 O(n²)，丢掉”少交换”的优点。规避：内层只更新 minIdx，内层结束后交换一次。
2. 插入排序的循环边界写错：写成 gap >= 0 && key < v[gap] 会越界或漏比较。规避：用”空位在 gap、比较左邻 v[gap-1]”的写法：while (gap > 0 && key < v[gap-1])，落位写 v[gap] = key。
3. 归并基准写成 lo > hi（或忘处理 lo==hi）：单元素区间还会继续分裂，陷入不必要的递归甚至死循环。规避：基准用 lo >= hi。
4. 合并的三个 while 少写一个：主循环结束后必有一半还有剩余，不续尾就丢元素。规避：两个”整体倒入剩余”的 while 一个都不能删。
5. 中点公式 (lo+hi)/2 溢出：与二分查找同款陷阱（官方第 13 讲再次强调）。规避：lo + (hi-lo)/2。
6. 忘记把辅助数组拷回原数组：排完序却仍是无序原数组。规避：合并收尾用 v[lo+k] = aux[k] 回写。
7. 快排的有序输入最坏情形：固定取尾做 pivot + 输入已有序 → O(n²) 且可能栈深爆掉。规避：随机选 pivot、三数取中，或对小分区切换插入排序。
8. 混淆”比较次数”与”运行时间”：复杂度分析针对的是比较/交换这些基本操作的数量级，别用墙钟秒数直接下结论（机器、输入分布都影响实测）。

思考题（带答案）

问题 1：给你一个”基本有序”的 10 万元素数组（只有少量位置错乱），你会选插入排序还是归并排序？两者复杂度分别如何？ 答案：优先插入排序。它的最好情形 O(n) 恰好在”近乎有序”时出现：每个元素往左拖不了几步就停，总比较接近 O(n)；归并虽然最坏保证 O(n log n)，但对这种输入没有利用有序性的优势，还要付出 O(n) 辅助空间。这正体现”选算法要看输入形态”（官方讨论过：若应用里常见某种触发最好情形的输入，就该选那个算法）；工程上也常用”归并/快排 + 小分区切插入排序”的混合策略。 问题 2：归并排序的 O(n) 辅助空间具体花在哪？能否完全省掉？ 答案：花在”合”：每一层合并都要一个能容纳整个待合并区间的辅助数组 aux（两个有序子数组无法在不覆盖对方的情况下原地两两归并）。递归栈本身只占 O(log n)。完全原地归并在理论上可行但实现复杂、常数巨大，实践中几乎不用——所以内存敏感场景往往选择原地排序（如快排、堆排序，后者会在后续章节出现）。 问题 3：什么输入会让示例 3 的快排退化到 O(n²)？怎样缓解？ 答案：输入已经有序（升序或降序）且 pivot 固定取末尾时，每趟分区只会把 pivot 移到一端，另一侧为空，递归深度变成 n，总时间 O(n²)。缓解手段：①随机选 pivot（把最坏输入变成概率极低事件）；②三数取中（取 lo、mid、hi 三者的中位数做 pivot）；③遇到小区间切换插入排序并限制递归深度。

Lecture 8: 面向对象编程：类、对象与封装（OOP: Classes, Objects & Encapsulation）（对应课程真实讲座 L15）

概述

本讲是课程的重要转折：此前我们一直以”客户端”视角使用别人写好的 ADT（Vector、Stack 等），从这一讲开始第一次亲手”造”一个类，从使用者变成建造者。核心问题是：如何用类把”数据 + 操作数据的函数”打包成一个整体，并通过接口（.h）与实现（.cpp）分离、私有成员与 getter/setter 等手段划清抽象边界，让对象从生到死都处于合法状态。（官方对应：2026 夏季学期 L15，Monday, July 20 — Object-Oriented Programming，课上用一只只可爱的小袋鼠 Quokka 从零搭起一个类，本讲也是作业 5 Tone Matrix 的知识铺垫。）

核心概念与算法原理

1. 范式转变：从”操作数据”到”对象收发消息”

问题定义：在 C 这类过程式语言里，数据结构与操作它的函数是分离的，写出来往往是 goToFloor(elevator, 5) 这种”把对象塞给外部函数”的样子。OOP 要回答的问题是：能不能让”能力”长在”数据”身上，让电梯自己会”去 5 楼”？

直观解释：坐电梯时你不会想”把电梯交给一个外部函数处理”，而是直接按电梯里的按钮——按钮和电梯是一体的。OOP 把这个直觉搬进代码：我们对对象”发消息”（调用它的成员函数），对象自己决定如何改变自己的内部状态。官方称这是一次根本性的范式转变（paradigm shift）。

2. 类 = 蓝图/类型，对象 = 实例

它是什么：类是”图纸”，也等价于声明一种新的数据类型；对象是按图纸造出来的具体”房子”（变量）。官方特别指出：这一季用过的 Vector、Stack、Set、Map 全都是类——Vector<int> v; 中 Vector 是类型，v 就是 Vector 类的一个对象（实例，instance）。同一张蓝图可以造出无数座结构相同、内部各异的房子。

       Date 类（蓝图 / 模板）          ← 只画一次，定义一种"新类型"
  ┌───────────────────────────────────┐
  │ 成员变量（状态 state）: _year _month _day ... │
  │ 成员函数（行为 behavior）: 构造函数、printInfo() │
  └───────────────────────────────────┘
        │ 实例化 instantiation（按图施工，可造无数个）
   ┌────┼──────────┬─────────────┐
   ▼    ▼          ▼             ▼
┌─────┐┌─────┐  ┌─────┐      ┌─────┐
│ d1  ││ d2  │  │ d3  │      │ …   │   ← 每个对象各有自己的一份成员变量
└─────┘└─────┘  └─────┘      └─────┘   （给 d1 改值不影响 d2，如同在
                                        一间房子里放家具不会影响别的房子）

为什么要自己造类：官方给的理由是”扩充抽象词汇表”。把常用概念（如”日期”）封装成类型后，调用方不再需要盯着 v.remove(v.size()-1) 这类细节去猜意图，直接说”pop 一个”即可——抽象让代码更好读、更好交流、更难写错。

3. 接口（.h）与实现（.cpp）分离

问题定义：一个类有两类信息——外面的人需要知道”能调用哪些函数”（what）；而”具体怎么实现”（how）不必、也不应全部暴露。

它是什么：接口文件（.h，header）里放类声明：成员变量、成员函数原型，客户端 #include 它就够用了；实现文件（.cpp）里放每个成员函数的定义。官方把接口比作”从外面看到的类长什么样”，把实现比作”这些行为背后真正的代码”。

        .h（接口：what，对外合同）              .cpp（实现：how，幕后车间）
   ┌────────────────────────────┐      ┌────────────────────────────────┐
   │ #ifndef DATE_H             │      │ #include "date.h"             │
   │ class Date {               │      │ Date::Date(...) { ... }       │
   │ public:                    │      │ void Date::printInfo() {...}  │
   │   Date(...);               │      │ ... 每个函数定义都写 Date::    │
   │   void printInfo() const;  │      └────────────────────────────────┘
   │ private: ... };            │              编译时合体：
   │ #endif                     │      g++ -std=c++17 date.cpp main.cpp
   └────────────────────────────┘
        ▲ 客户端只看见这一半

头文件顶部的三行守卫 #ifndef DATE_H / #define DATE_H / … / #endif 叫 include guard，防止同一头文件被间接包含多次造成重复声明错误（官方在 L15 指出 Qt Creator 新建类时会自动生成）。

4. 构造函数与析构函数：对象的一生

它是什么：与类同名的函数叫构造函数，任何时刻创建对象都会自动调用它，最适合做初始化；参数不同可以写多个构造函数，这叫构造函数重载。名字为 ~类名 的函数叫析构函数，对象离开作用域死亡时自动调用。

对象的一生：局部对象在声明处出生（栈帧里分配空间 + 调构造函数），在函数返回或到达代码块末尾时死亡（自动调析构）。官方在 L15 用”会打印 R.I.P. 的析构函数”做了证明：createQuokka() 一返回，销毁信息立刻出现——局部变量确实随函数退出而消亡。这个”死亡”事实是下一讲（动态内存）的出发点。

5. 封装：private 成员与 getter/setter

问题定义：如果客户端能直接改内部数据，就可能把对象弄进”破损状态”。官方举例：假如 Vector 的 size 是公开变量，客户端写 v.size = 1;，底层明明还有 3 个元素却对外声称 1 个，遍历和删除全部错乱。

它是什么：把成员变量声明为 private（私有），只留受控的公共出入口：getter 只读返回某个私有成员的值；setter 是修改私有成员的唯一通道，可在里面加合法性校验。私有化不等于”锁死”，而是”所有改变都必须经过把门人”。官方归纳的理由：防止对象进入破损状态、能对写入值设限制、能保证对象一生状态可预期。

6. 匿名临时对象

有时我们不想给对象起名字（造出来立刻塞进容器或传给函数），可以直接调用构造函数，例如 Quokka("Muffinface", 5, "muffinface.jpg")——这种没有变量名的对象叫匿名临时对象，它只活在当前这一条语句里，语句结束随即析构（官方在 L15 演示了把 7 只匿名 Quokka 直接 add 进 Vector 的写法）。

代码示例与实现详解

示例 1：接口与实现分离的 Date 类（date.h + date.cpp + main.cpp 三文件项目）

这是官方推崇的工程组织方式：三个文件一起编译（g++ -std=c++17 date.cpp main.cpp -o date_demo）。注意头文件里全程使用 std:: 前缀而不写 using namespace std;——头文件会被任意客户端包含，把整个 std 命名空间”泄漏”给别人是很糟糕的做法。

// ================= date.h：接口（what）=================
#ifndef DATE_H
#define DATE_H
#include <string>

class Date {
public:
    Date();                                          // 默认构造函数
    Date(int year, int month, int day,
         const std::string& label);                  // 重载构造函数（4 参数版）
    ~Date();                                         // 析构函数：死亡时自动调用

    int year() const;        // getter；const 承诺"不改状态"
    int month() const;
    int day() const;
    std::string label() const;

    void setYear(int year);  // setter：带范围校验
    void setMonth(int month);
    void setDay(int day);

    void printInfo() const;

private:
    int _year;               // 私有成员：客户端无法直接读写
    int _month;
    int _day;
    std::string _label;
};
#endif // DATE_H

// ================= date.cpp：实现（how）=================
#include <iostream>
#include "date.h"

Date::Date() {                       // 每个成员函数定义都要写 Date::
    _year = 2026; _month = 1; _day = 1; _label = "(未命名)";
}
Date::Date(int year, int month, int day, const std::string& label) {
    _year = year; _month = month; _day = day; _label = label;
}
Date::~Date() {
    std::cout << "【销毁】" << _label << " 离开这个世界" << std::endl;
}
int Date::year() const { return _year; }
int Date::month() const { return _month; }
int Date::day() const { return _day; }
std::string Date::label() const { return _label; }

void Date::setYear(int year) {
    if (year < 1900 || year > 2100) {
        std::cout << "年份 " << year << " 非法，已忽略" << std::endl;
        return;                     // 拒绝非法值，对象保持原状态
    }
    _year = year;
}
void Date::setMonth(int month) {
    if (month < 1 || month > 12) {
        std::cout << "月份 " << month << " 非法，已忽略" << std::endl;
        return;
    }
    _month = month;
}
void Date::setDay(int day) {
    if (day < 1 || day > 31) {
        std::cout << "日期 " << day << " 非法，已忽略" << std::endl;
        return;
    }
    _day = day;
}
void Date::printInfo() const {
    std::cout << _label << ": " << _year << "-" << _month << "-" << _day << std::endl;
}