学习数据结构时，最容易出现一种错觉：能背出“链表插入是 O(1)、二分查找是 O(log n)”，却说不清程序到底改了哪些数据，也不知道这些结论需要什么前提。这套笔记从一次操作开始：画出操作前后的状态，观察每一步改变什么，再用不变量和复杂度解释它。
文章集中在独立的数据结构与算法分类。前半部分解释存储与容器，后半部分按序列处理、搜索与贪心、动态规划、图算法展开；数值优化保留为扩展。旧文章链接继续有效，示例统一使用 C++17。
一、先看一个问题，而不是先记一个定义
已有序列 [10,20,30]，现在要求在下标 1 插入 15。
如果数据连续存储，为了保留原顺序，要把 30 向右移、20 向右移，最后填入 15。移动方向必须从后往前，否则先把 20 写入 30 的位置就会丢掉 30。
如果数据通过链接相连，可以新建一个值为 15 的节点，让它指向 20，再让 10 指向它。两种结构最终都表示 [10,15,20,30]，内部过程却不同。数据结构决定数据怎样放，算法决定怎样一步步改它们。
但链表并不因此在所有插入场景都更快：先找到“下标 1 的前驱”也需要工作。如果下标是很远的 k，单链表通常要走 k 次链接；只有前驱已经在手中，修改链接才是 O(1)。数组可以直接用下标找到位置，却要移动后面的元素。
学习一个结构，至少回答四件事：元素在哪里、如何定位、如何修改、哪些约束必须始终成立。
二、按这条路线学习
| 顺序 | 文章与操作 | 读完应能独立解释 |
|---|---|---|
| 01 | 存储布局与结构选择：数组移动、队列、堆、哈希、树与图 | 为什么一个结构在某项操作上方便，却在另一项上付出代价 |
| 02 | 链表的指针过程：插入、删除、反转 | 每个指针修改前后还拥有谁，空链表和头尾边界怎样处理 |
| 03 | STL 数据处理：过滤、去重、查找 | 为什么 remove 不会缩短容器，迭代器何时失效 |
| 04 | 查找、排序与动态规划：二分、插入排序、最少硬币 | 循环不变量、状态与递推怎样证明结果 |
| 05 | 序列处理：前缀和、差分、双指针、滑动窗口与答案二分 | 什么条件允许指针单向移动，何时必须换用前缀和与哈希 |
| 06 | 分治、回溯与贪心：逆序对、排列与区间调度 | 拆分、枚举与局部选择各依靠什么正确性依据 |
| 07 | 动态规划的状态与恢复：背包、LIS、LCS 与计数 | 初始化与遍历方向为什么会改变问题，怎样恢复一个具体方案 |
| 08 | 图算法：最短路、拓扑排序与最小生成树 | 无权距离、带权路径、依赖顺序与连通成本为什么需要不同算法 |
| 扩展 | 数值优化：梯度、步长、Newton | 如何从离散操作转向连续变量上的目标函数最小化 |
逐步演示把每次更新前后的状态放在同一处；正文解释为什么必须这样更新，配套源码展示真实输出与边界处理。静态说明与示例已经包含完整过程。
三、复杂度是随规模增长的工作量
不要从一张 O 记号表开始。假设每次比较算一次工作，在长度为 n 的序列中寻找一个不在里面的值：
- 顺序查找最多检查
n个元素，工作量随n线性增长。 - 已排序、支持随机访问的序列做二分，每次把剩余范围缩小约一半，比较次数随
log₂ n增长。 - 插入排序遇到完全逆序的数据，第 2 个元素移动 1 次，第 3 个移动 2 次，累计
n(n−1)/2次移动。
| n | 顺序检查上界 n | 二分查找比较次数的量级 | 逆序插入排序移动次数 n(n−1)/2 |
|---|---|---|---|
| 8 | 8 | 约 4 | 28 |
| 32 | 32 | 约 6 | 496 |
| 128 | 128 | 约 8 | 8128 |
表中二分的数字是理解规模的近似，不是所有实现都执行完全相同次数。O 记号忽略常数因子和低阶项；它也不直接等于耗时。连续内存的访问局部性、分配器、缓存和数据规模，都会影响实际运行。
最坏、平均、摊还不是同一个结论
- 最坏情况：固定输入规模中最不利的输入。例如哈希表碰撞严重时，查找可能需要线性工作。
- 平均情况：在明确的输入分布或散列假设下取期望。不能把“平均 O(1)”写成无条件保证。
- 摊还分析：分析一串操作的总成本，再平均到每次操作，不需要假设随机输入。例如 vector 连续尾部追加，偶尔扩容要搬走所有旧元素，但标准库保证追加的摊还常数复杂度。
“vector 追加摊还 O(1)”不代表每一次都快，也不代表每次调用 reserve(size()+1) 之后仍有同样的增长表现。人为频繁请求精确的小容量可能破坏原本的扩容策略。
空间复杂度同样要先约定口径：统计全部存储，还是只统计算法额外申请的辅助空间？递归调用栈也属于辅助空间。比较算法时，先统一口径再比较数字。
四、用三个不变量把程序看透
不变量是“每次进入某个循环位置时一定成立的事实”。它把视觉过程和正确性联系起来。
| 操作 | 可以检查的不变量 | 结束时为什么得到答案 |
|---|---|---|
| 插入排序 | [0,i) 已经有序 |
每轮把第 i 个值放入有序前缀，直到前缀覆盖全序列 |
| BFS | 发现的顶点入队时就已标记，队列按层扩展 | 同一顶点只入队一次；第一次到达的层数是无权最短距离 |
| 链表反转 | prev 指向已反转前缀，current 指向未处理后缀 |
后缀为空时，整个序列都已连接到新的头部 |
实际写代码可以按“初始化是否成立 → 一次更新是否保持 → 结束条件推出什么”检查。发现无法写出不变量，往往说明还没想清楚变量的职责。
五、配套 C++17 示例
可直接查看源码与运行说明。源码按主题分开，但共用一个运行入口：
| 文件 | 可以核对的结果 |
|---|---|
| structures.cpp | 容器布局与操作、BFS、Trie、并查集及边界输入 |
| linked_list.hpp / 测试 | 所有权、插入删除反转，与 vector 参考结果对照 |
| stl_operations.cpp | 过滤、排序去重、查找及安全 erase |
| algorithms.cpp | 二分与标准库对照、稳定排序、动态规划与独立搜索对照 |
| sequence_algorithms.cpp | 区间求和、差分、双指针、窗口、精确和计数与分段容量 |
| search_greedy.cpp | 归并逆序对、去重排列、区间调度与枚举参考结果 |
| dynamic_programming.cpp | 背包、LIS、LCS、方案恢复与组合/有序计数 |
| graph_algorithms.cpp | Dijkstra、Bellman–Ford、拓扑排序和 Kruskal |
| optimization.cpp | 合适步长收敛、过大步长振荡或发散 |
在网站仓库根目录执行：
./bin/site.sh algorithms-build |
第一条复用仓库已有的 GDB 教学镜像配方，构建一次即可。第二条在无网络容器内以 C++17 编译各个示例，并启用 AddressSanitizer、UndefinedBehaviorSanitizer 和断言。源文件只读挂载，编译产物留在临时容器中，日志保存在 build/data-structure-lab/。第三条验证网页逐步演示的状态过程。
断言覆盖的是这套教学实现和选定边界，不是对任意程序正确性的证明。完整源码同时包含输入约束、独立参考结果和边界检查，便于核对正文结论。
六、根据问题选择算法
| 问题特征 | 优先考虑 | 必须确认的前提 |
|---|---|---|
| 同一静态序列反复求区间和 | 前缀和 | 查询区间和下标定义一致 |
| 批量修改区间，最后统一读取 | 差分 | 不要求每次更新后立即回答查询 |
| 连续段的条件随端点移动具有单调性 | 滑动窗口 | 负数、回退或多种约束可能破坏单调性 |
| 求最小可行阈值 | 答案二分 | 可行性判断本身正确，且随阈值单调 |
| 所有方案都需要生成 | 回溯 | 输出规模可能本来就呈指数或阶乘增长 |
| 局部选择能交换成全局最优 | 贪心 | 存在证明，不能只依据几个成功样例 |
| 子问题重复且历史可被有限状态概括 | 动态规划 | 状态足够、转移无循环依赖或有正确处理方式 |
| 有向依赖的执行顺序 | 拓扑排序 | 有环时不能给出覆盖全部顶点的合法顺序 |
| 非负带权图中的单源最短路 | Dijkstra | 负边权会破坏定点正确性依据 |
| 尽量低成本连通全部顶点 | 最小生成树 | 连通成本与单条最短路径是不同目标 |
数据结构提供操作能力，算法则利用问题条件减少工作。比如优先队列既能管理任务，也能服务于 Dijkstra；哈希表既能建立设备索引，也能计数前缀和。结构与算法之间的联系，比孤立记住名称更有用。
