NORTH STAR / 长期目标
学到什么程度才算真正掌握？
看到操作约束就能选择表示，并用不变量证明实现正确、用摊还分析解释成本。
结构与不变量CS-10 / REPRESENTATION
数据结构Data Structures
围绕“操作集合—表示方式—不变量—复杂度”学习数据结构；不仅会调用容器，还能解释它为什么正确、何时退化以及如何测试边界。
PREREQUISITES / 先修检查
进入路线前
- 掌握函数、循环、递归与指针/引用
- 理解 O、Ω、Θ 的渐近含义
- 会写单元测试和随机测试
- 了解栈与堆的基本内存模型
FOUNDATIONS / 地基
第一轮优先补齐
- 集合、序列、树与图
- 循环不变量与递归不变量
- 最坏/平均/摊还复杂度
- 接口、表示与封装边界
STAGED ROUTE / 阶段路线
用可验证产出推进，而不是只计算观看时长
阶段可并行回看；勾选只表示完成过该阶段的产出与自检，不代表永久掌握。
D13 周 线性结构
从头实现动态数组、链表、栈和队列。
- 写明每个结构的表示不变量
- 测量扩容与局部性
- 用性质测试验证操作序列
D23–4 周 查找与优先级
掌握哈希表、堆、BST 与平衡树的权衡。
- 实现开放寻址哈希表
- 证明堆操作保持堆序
- 追踪 AVL 或红黑树旋转
D33 周 图与集合
根据稀疏度选择图表示并熟练使用并查集。
- 对比邻接矩阵与邻接表
- 实现带路径压缩的并查集
- 为多重边/自环设计测试
D4长期 工程化容器
把复杂度、内存、泛型与迭代器约束写进实现。
- 建立 benchmark 与内存基线
- 实现 fail-fast 或稳定迭代语义
- 撰写结构选择决策记录
KNOWLEDGE MAP / 知识地图
概念、方法、练习和回忆锚点在同一张卡里
输入关键词或选择分类；按 / 可快速聚焦搜索，Esc 清空。
5 个知识节点
01线性
数组、链表、栈与队列
线性结构的关键差异是连续性、端点操作和定位成本。
数组链表栈队列双端队列
CORE / 核心概念
- 动态数组容量与长度不变量
- 链表指针连接与哨兵节点
- LIFO/FIFO/Deque 的接口语义
METHOD / 常用方法
- 用势能法分析倍增扩容
- 用哨兵消除首尾特判
- 用状态机覆盖空/单元素/多元素
PRACTICE / 练习
- 实现环形队列并处理回绕
- 反转链表并证明无节点丢失
- 比较数组和链表遍历缓存性能
02查找
哈希表与集合
哈希把键映射到桶；正确性依赖相等关系，性能依赖分布和装载因子。
哈希冲突装载因子开放寻址拉链法
CORE / 核心概念
- hash/equality 契约
- 冲突解决与墓碑标记
- 装载因子、再散列与期望复杂度
METHOD / 常用方法
- 构造碰撞与恶意分布测试
- 区分空槽、占用与删除状态
- 记录探测长度而非只看总耗时
PRACTICE / 练习
- 实现线性探测哈希表
- 比较拉链法和开放寻址
- 证明查找不会越过可终止空槽
03层次
树、堆与平衡搜索树
树用层次组织顺序；高度直接控制搜索、插入和删除的路径长度。
二叉树堆BSTAVL红黑树
CORE / 核心概念
- 遍历顺序与递归结构
- BST 次序不变量与堆序不变量
- 旋转保持中序序列并恢复平衡
METHOD / 常用方法
- 画局部旋转前后子树
- 用结构归纳证明遍历
- 把空树与单节点作为一级边界
PRACTICE / 练习
- 实现迭代中序遍历
- 实现堆化并证明 O(n)
- 为 AVL 插入记录平衡因子
04关系
图的表示与遍历
图结构先决定顶点、边及权重语义，再根据稀疏度选择表示。
图邻接表邻接矩阵BFSDFS
CORE / 核心概念
- 有向/无向、加权/无权与多重边
- 邻接矩阵 O(V²) 与邻接表 O(V+E)
- 访问状态、树边与遍历森林
METHOD / 常用方法
- 先定义图模型再写算法
- 按白/灰/黑维护访问不变量
- 用小图手工追踪队列或栈
PRACTICE / 练习
- 实现可切换表示的图接口
- 找连通分量并输出遍历树
- 为自环、孤点、平行边写测试
05关系
并查集与摊还分析
并查集维护动态等价类，按秩合并和路径压缩使操作几乎常数。
并查集DSU路径压缩按秩合并摊还
CORE / 核心概念
- 森林表示与代表元
- 父指针终止于根的不变量
- 逆 Ackermann 级摊还界
METHOD / 常用方法
- 先证明合并不改变类内等价
- 把优化前后分别实现比较
- 用操作序列而非单次操作衡量
PRACTICE / 练习
- 实现 Quick Find / Quick Union / 优化版
- 用于离线连通性问题
- 用随机图与 BFS 结果交叉验证
没有匹配的知识节点
换一个更短的关键词，或清空分类后再试。
OUTPUT LAB / 练习与项目
用可交付作品检验理解
项目不是装饰：交付物、检查点与复盘记录缺一不可。
泛型容器库
动态数组、链表、栈、队列、堆与哈希表，附复杂度契约。
完成检查
- 每个结构写出表示不变量
- 随机操作与参考实现对拍
- 空值、重复键和扩容有测试
结构可视化器
逐步展示树旋转、堆化、哈希探测和并查集压缩。
完成检查
- 每步状态可前进和回退
- 显示被维护的不变量
- 移动端无横向溢出
性能实验报告
用真实分布比较容器的延迟、内存与缓存行为。
完成检查
- 含 warm-up 与多次采样
- 报告输入分布和硬件环境
- 区分理论界与实测常数
REFERENCE SOURCES / 可核验资料
先读官方、大学与专业组织资料，再用高质量参考补齐
外部页面可能更新；课程顺序以本页路线为导航，资料以来源明确、可核验为优先。