DSA 数据结构与算法 学习路线
学习方式
每条学习步骤遵循四步法：
- 通读概念 — 理解数据结构的定义、性质、适用场景
- 手写实现 — 不看参考代码，手动实现核心操作（可用任何语言）
- 标准库练习 — 用语言的标准库容器/算法做题，熟悉接口
- 力扣刷题 — 按章节做推荐题目，每章 2-5 题
每章建议 2-3 天完成：概念+手写、标准库用法+案例、习题+刷题。
Phase 0 — 前置技能（建议在 Phase 1 之前完成）
Step -2: 0 基本知识 — 计算机基础
内存、CPU、缓存、指针、数学基础、时间/空间复杂度。所有数据结构的硬件和数学根基，必须最先阅读。
Step -1: 0x_数据结构表达方式_Representation — 表达方式
掌握自然语言、数学公式、流程图（Mermaid）三种数据结构表达语言。学会用文字精确定义结构，用 LaTeX 公式分析复杂度，用 Mermaid 画内存布局和算法流程。
Step 0: 0y_表达方式之间的转化_RepresentationConversion — 表达方式之间的转化
在四种表达（文字 ↔ 流程图 ↔ 公式 ↔ 代码）之间自由转化。这是数据结构学习的核心技能：读论文（公式）能画流程图，画完流程图能写出代码，写完代码能推导出复杂度公式。
Phase 1 — 入门基础：从数组到排序
Step 0A: A_数组_Array — 数组
数据结构中最基本的连续存储模型。理解数组的寻址公式、静态分配与动态分配的区别、多维数组的行优先/列优先布局，以及大数组对 cache 和虚拟内存的影响。
配合算法: 数组 — 数组基础与遍历
必须手写的结构: StaticArray（带边界检查）
力扣刷题: 1 两数之和、268 丢失的数字、448 找到所有数组中消失的数字
Step 0B: B_字符串_String — 字符串
字符串的底层表示：C 风格以 \0 结尾，长度前缀表示避免了 O(n) 的 strlen。字符串匹配从暴力的 BF 到 KMP，核心是前缀函数的数学推导与自动机思想。SSO 小字符串优化在 C++ 标准库中广泛使用。
配合算法: 字符串
必须手写的结构: KMP 的前缀函数构建与匹配
力扣刷题: 28 实现 strStr()、459 重复的子字符串、214 最短回文串
Step 0C: C_线性表_LinearList — 线性表与顺序表
线性表是最基础的抽象数据类型：n 个元素的有限序列，两种存储实现（顺序表/链表）的总览与取舍。重点掌握顺序表的插入/删除算法与平均移动次数推导（插入 n/2、删除 (n-1)/2），以及 408 高频的顺序表算法设计题（合并、就地逆置、删除、中位数、循环移位）。
前置: A_数组_Array — 顺序表的底层是数组
必须手写的结构: SeqList（含插入/删除/扩容）
力扣刷题: 344 反转字符串、189 轮转数组、4 寻找两个正序数组的中位数
Step 0D: D_稀疏矩阵_SparseMatrix — 稀疏矩阵
实际工程中大量矩阵元素为零时，如何用更紧凑的格式存储？COO、CSR、十字链表三种表示法的空间/时间权衡，以及 COO 转 CSR 的 O(k) 计数排序思想。
必须手写的结构: COO 转置、COO 转 CSR
力扣刷题: 311 稀疏矩阵的乘法、1570 两个稀疏向量的点积
Step 1: E_容器_Container — 容器概览
在深入学习各个数据结构之前，先建立容器的大图景：连续存储 vs 节点存储、迭代器抽象、vector 的扩容均摊分析、deque 的分块设计、以及各类容器的内存开销对比。本章还深入虚拟内存和 malloc 分配器底层。
配合算法: 数组
必须手写的结构: SimpleVector（含扩容逻辑）
力扣刷题: 448 找到所有数组中消失的数字、1920 基于排列构建数组、344 反转字符串
Step 2: F_链表_LinkedList — 链表
链表是节点存储的典型代表，单链、双链、循环链表各有适用场景。核心操作包括增删查和反转，快慢指针是解决环检测、中点查找等问题的高频技巧。理解链表 vs 数组在 cache 行为和内存碎片上的本质差异。
配合算法: 双指针 — 快慢指针部分
必须手写的结构: 单向链表、双向链表
力扣刷题: 206 反转链表、141 环形链表、21 合并两个有序链表、160 相交链表
Step 3: G_栈_Stack — 栈
LIFO 原则的抽象数据结构。最经典的应用是函数调用栈，它直接对应 CPU 的 push/pop 指令。栈也用于括号匹配、中缀表达式转后缀、DFS 的非递归实现等场景。单调栈是一个高频的进阶变体。
必须手写的结构: ArrayStack、LinkedStack、MinStack
力扣刷题: 20 有效的括号、150 逆波兰表达式求值、155 最小栈、739 每日温度
Step 4: H_队列_Queue — 队列
FIFO 原则，从消息队列到 BFS 遍历，再到线程池的任务调度，无处不见队列的身影。循环队列用取模运算绕过了数组搬移的开销。双端队列（deque）和单调队列是进阶面试常客。
必须手写的结构: CircularQueue、LinkedQueue
力扣刷题: 622 设计循环队列、225 用队列实现栈、239 滑动窗口最大值
Step 5: I_排序_八大排序_Sorting — 八大排序
排序是算法分析的入门课。O(n^2) 三种（冒泡、选择、插入）建立基本直觉，归并排序引领分治思想，快速排序在平均 O(nlogn) 的极致优雅，堆排序则关联堆数据结构。每种排序的稳定性、空间复杂度、是否原地的权衡是工程选型的基础。
学习顺序:
- 冒泡排序 -> 选择排序 -> 插入排序 (O(n^2) 三种)
- 希尔排序 (插入排序的改进)
- 归并排序 (分治思想入门)
- 快速排序 (分治 + 枢轴选择 + 优化策略)
- 堆排序 (学完堆之后回来看)
- 基数排序与桶排序
必须手写的排序: 冒泡、插入、归并、快排
力扣刷题: 912 排序数组、215 数组中的第K个最大元素、148 排序链表
Step 6: 二分查找 — 二分查找
前置知识: I_排序_八大排序_Sorting
力扣刷题: 704 二分查找、35 搜索插入位置、34 在排序数组中查找元素的第一个和最后一个位置
Phase 2 — 核心数据结构
Step 7: O_哈希表_HashTable — 哈希表
哈希函数将任意规模的键空间映射到有限的地址空间。冲突不可避免，链地址法与开放地址法各有优劣。装载因子的控制、再哈希策略、一致性哈希与布隆过滤器等工程话题同样重要。
必须手写的结构: 基于链地址法的 HashMap
力扣刷题: 1 两数之和、242 有效的字母异位词、128 最长连续序列、49 字母异位词分组
Step 8: K_树_Tree_BST_AVL — 树、BST、AVL
树是递归定义的典范。二叉树的基本结构、四种遍历（前中后序、层序）为后续所有树形结构打基础。二叉搜索树（BST）利用有序性质实现 O(logn) 的查找，AVL 通过四种旋转维持平衡，引出自平衡二叉树的思路。
配合算法:
必须手写的结构: BST (insert/search/delete)、AVL 四种旋转
力扣刷题: 94 二叉树的中序遍历、102 二叉树的层序遍历、98 验证二叉搜索树、108 将有序数组转换为二叉搜索树
Step 9: J_堆_Heap — 堆与优先队列
堆是完全二叉树的数组实现，siftUp/siftDown 两个核心操作支撑起插入、删除和建堆。建堆 O(n) 的证明是均摊分析的经典案例。堆排序、Top-K、数据流中位数是堆的高频应用场景。
前置: Step 8 树的前三节（二叉树概念 + 完全二叉树 + 数组表示）
配合算法:
- 贪心 — 优先队列在贪心中的应用
- 回到 I_排序_八大排序_Sorting 复习堆排序
必须手写的结构: MaxHeap (insert / extractMax / heapify)
力扣刷题: 215 数组中的第K个最大元素、295 数据流的中位数、347 前K个高频元素
Step 10: M_字典树_Trie — 字典树/前缀树
Trie 用公共前缀压缩存储大量字符串，在自动补全、拼写检查、IP 路由等场景中广泛应用。01 字典树将 Trie 的思想迁移到整数域，用于解决最大异或对等问题。
必须手写的结构: Trie (insert / search / startsWith)
力扣刷题: 208 实现 Trie、211 添加与搜索单词、421 数组中两个数的最大异或值
Phase 3 — 算法技巧专题
以下转向算法技巧，掌握二分答案、前缀和差分、贪心、滑动窗口、递推递归、搜索、动态规划。
Step 11: 二分答案 — 二分答案
前置: 二分查找
力扣刷题: 875 爱吃香蕉的珂珂、1011 在 D 天内送达包裹的能力
Step 12: 前缀和 + 差分 — 前缀和与差分
力扣刷题:
- 前缀和: 303 区域和检索、560 和为K的子数组
- 差分: 1094 拼车、1109 航班预订统计
Step 13: 贪心 — 贪心算法
前置知识: J_堆_Heap、I_排序_八大排序_Sorting
力扣刷题: 455 分发饼干、435 无重叠区间、55 跳跃游戏
Step 14: 滑动窗口 + 双指针 — 滑动窗口与双指针
前置知识: H_队列_Queue、前缀和
力扣刷题: 3 无重复字符的最长子串、76 最小覆盖子串、11 盛最多水的容器
Step 15: 递推递归 — 递推与递归
前置知识: G_栈_Stack、I_排序_八大排序_Sorting
力扣刷题: 509 斐波那契数、70 爬楼梯、22 括号生成
Step 16: 搜索 — 搜索 (DFS / BFS)
前置知识: G_栈_Stack、H_队列_Queue、K_树_Tree_BST_AVL
力扣刷题: 200 岛屿数量、46 全排列、51 N 皇后、752 打开转盘锁
Step 17: 动态规划 — 动态规划
重点: 最优子结构、重叠子问题、状态定义与转移。经典模型：线性 DP、0/1 背包、完全背包。
前置知识: 递推递归、E_容器_Container
力扣刷题: 53 最大子数组和、322 零钱兑换、416 分割等和子集、300 最长递增子序列
Phase 4 — 图论
Step 18: T_图_Graph — 图基础
图的邻接矩阵/邻接表存储、BFS/DFS 遍历、Dijkstra 单源最短路径、Kruskal/Prim 最小生成树。
配合算法: 图 — 图的最短路径、最小生成树
进阶图论:
必须手写的结构: Graph(邻接表) + BFS + DFS、Dijkstra
力扣刷题: 200 岛屿数量、743 网络延迟时间、1584 连接所有点的最小费用
Step 19: P_并查集_UnionFind — 并查集
并查集是维护集合合并与查询的数据结构，find 的路径压缩和 union 的按秩合并将均摊复杂度推至接近常数。在图连通性判断、Kruskal 最小生成树中频繁使用。
必须手写的结构: UnionFind（含路径压缩和按秩合并）
力扣刷题: 547 省份数量、684 冗余连接、200 岛屿数量（并查集解法）、1319 连通网络的操作次数
Step 20: U_图的高级算法_AdvancedGraph — 图高级算法
拓扑排序（Kahn 与 DFS 两种写法）、Tarjan SCC 强连通分量、Floyd-Warshall 全源最短路径、Bellman-Ford 负权边最短路径、网络流 Dinic 算法。
力扣刷题: 207 课程表、210 课程表 II、787 K 站中转内最便宜的航班、1192 查找集群内的关键连接
Phase 5 — 进阶数据结构 (选学)
| 顺序 | 文件 | 建议时机 |
|---|---|---|
| 21 | R_线段树_SegmentTree | 学完数组、递归后可选 |
| 22 | S_树状数组_BIT | 学完线段树后再看 |
| 23 | Q_跳表_SkipList | 学完链表、哈希后可选 |
| 24 | L_红黑树_RedBlackTree | 学完 BST/AVL 后可选 |
| 25 | N_B树_BTree | 学完树、文件系统概念后可选 |
Phase 6 — 字符串与 DP 进阶 (选学)
| 顺序 | 文件 | 建议时机 |
|---|---|---|
| 26 | Trie字典树 | 学完哈希、图后可选 |
| 27 | 字符串哈希 | 学完哈希后可选 |
| 28 | 后缀数组 | 学完排序、二分后可选 |
| 29 | 后缀自动机 | 高级字符串 |
| 30 | 区间DP | 学完基础 DP 后 |
| 31 | 背包DP | 学完基础 DP 后 |
| 32 | 树形DP | 学完树、DP 后 |
| 33 | 状态压缩DP | 进阶优化 |
| 34 | 数位DP | 进阶优化 |
算法技巧速查表
| 算法技巧文件 | 前置知识 | 对应数据结构章节 |
|---|---|---|
| 数组 | 无 | E_容器_Container |
| 循环 | 无 | E_容器_Container |
| 暴力枚举 | 循环 + 数组 | I_排序_八大排序_Sorting |
| 二分查找 | 排序 | I_排序_八大排序_Sorting |
| 双指针 | 数组 + 循环 | F_链表_LinkedList |
| 前缀和 | 数组 + 循环 | E_容器_Container |
| 差分 | 前缀和 | E_容器_Container |
| 二分答案 | 二分查找 | I_排序_八大排序_Sorting |
| 贪心 | 排序 | J_堆_Heap |
| 滑动窗口 | 双指针 + 前缀和 | H_队列_Queue |
| 递推递归 | 函数 + 数组 | G_栈_Stack |
| 搜索 | 递推递归 | G_栈_Stack, H_队列_Queue, K_树_Tree_BST_AVL |
| 动态规划 | 递推递归 + 堆 | E_容器_Container |
| 图 | 搜索 + 贪心 | T_图_Graph |
| 连通性 | 图 + 搜索 | P_并查集_UnionFind |
| 优化 | 全部 | R_线段树_SegmentTree, S_树状数组_BIT |
学习节奏建议
Phase 1 (三周): 线性结构集训 -- 每天 1 个数据结构 + 少量算法题
Phase 2 (两周): 核心结构 -- 每 2-3 天一个主题，多手写
Phase 3 (两周): 算法技巧 -- 每天一个算法技巧，大量刷题
Phase 4 (一到两周): 图论 -- 算法综合应用
Phase 5-6 (选学): 按需深入
每一章的标准动作:
- 阅读本章文件（先概念，再代码）
- 关掉文件，手写核心数据结构的实现
- 用语言标准库快速刷 2-3 道力扣题
- 阅读本章推荐的相关算法技巧文件
扩展阅读：数据结构背后的底层原理
数据结构回答”怎么做”，深入底层回答”为什么这样做”。以下两个模块提供支撑数据结构性能分析所需的硬件和操作系统知识：
建议在学完 Phase 1（容器 + 链表 + 栈 + 队列）之后，通读操作系统教程的前四章和计算机原理的前三章，再回头继续 Phase 2-3 的数据结构。