RootStack

DSA学习路线

12分钟阅读

DSA 数据结构与算法 学习路线

学习方式

每条学习步骤遵循四步法：

  1. 通读概念 — 理解数据结构的定义、性质、适用场景
  2. 手写实现 — 不看参考代码，手动实现核心操作（可用任何语言）
  3. 标准库练习 — 用语言的标准库容器/算法做题，熟悉接口
  4. 力扣刷题 — 按章节做推荐题目，每章 2-5 题

每章建议分 2-3 天完成：概念+手写、标准库用法+案例、习题+刷题。

Phase 1 — 入门基础：线性结构与排序 (建议 14 天)

Step 1: A_容器_Container — 容器概览

重点: 容器概念、连续存储 vs 节点存储、迭代器原理、vector 扩容机制。

配合算法: 数组 — 数组基础与遍历

必须手写的结构: SimpleVector

Step 2: D_链表_LinkedList — 链表

重点: 链表类型与内存布局、手动实现单向/双向链表全部操作、快慢指针。

配合算法: 双指针 — 快慢指针部分

必须手写的结构: 单向链表、双向链表

力扣刷题: 力扣约瑟夫环

Step 3: B_栈_Stack — 栈

重点: 栈的概念、函数调用栈原理、手动实现数组栈/链表栈、括号匹配、中缀转后缀、表达式求值。

必须手写的结构: ArrayStack、LinkedStack、MinStack

力扣刷题: 力扣逆波兰表达式、力扣有效括号

Step 4: F_队列_Queue — 队列

重点: 队列概念、手动实现循环队列/链表队列、BFS、滑动窗口。

配合算法: 搜索 — BFS 部分

必须手写的结构: CircularQueue、LinkedQueue

力扣刷题: 力扣约瑟夫环（队列版）、力扣队列

Step 5: Q_排序_八大排序_Sorting — 八大排序

学习顺序:

  1. 冒泡排序 -> 选择排序 -> 插入排序 (O(n^2) 三种)
  2. 希尔排序 (插入排序的改进)
  3. 归并排序 (分治思想入门)
  4. 快速排序 (分治 + 枢轴选择 + 优化策略)
  5. 堆排序 (学完堆之后回来看)
  6. 基数排序 (了解即可)

配合算法:

必须手写的排序: 冒泡、插入、归并、快排

力扣刷题: 力扣排序题、力扣去重排序、力扣排序

Step 6: 二分查找 — 二分查找 (算法补充)

内容: lower_bound/upper_bound 手写、二分查找变体、标准库二分查找。

前置知识: Q_排序_八大排序_Sorting

力扣刷题: 力扣二分查找、力扣两数之差、力扣二分查找

Phase 2 — 核心数据结构 (建议 14 天)

Step 7: G_哈希表_HashTable — 哈希表

重点: 哈希原理、冲突处理（链地址法与开放地址法）、装载因子。

必须手写的结构: 基于链地址法的 HashMap

力扣刷题: 力扣哈希表

Step 8: I_树_Tree_BST_AVL — 树、BST、AVL

重点: 二叉树概念与四种遍历、BST 增删查实现、AVL 四种旋转。

配合算法:

必须手写的结构: BST (insert/search/delete)、AVL 四种旋转

力扣刷题: 力扣平衡树、力扣树

Step 9: C_堆_Heap — 堆与优先队列

重点: 堆的完全二叉树数组表示、siftUp/siftDown、建堆 O(n) 证明。

前置: Step 8 树的前三节（二叉树概念 + 完全二叉树 + 数组表示）

配合算法:

必须手写的结构: MaxHeap (insert / extractMax / heapify)

力扣刷题: 力扣哈夫曼、力扣数据流中位数

Step 10: J_字典树_Trie — 字典树/前缀树

重点: Trie 节点结构、插入与查找、01 字典树求最大异或值。

力扣刷题: 力扣Trie

Phase 3 — 算法专题深化 (建议 14 天)

以下转向算法专题，掌握二分答案、前缀和差分、贪心、滑动窗口、递推递归、搜索、动态规划。

Step 11: 二分答案 — 二分答案

前置: 二分查找

力扣刷题: 力扣二分答案、力扣二分答案、力扣二分答案

Step 12: 前缀和 + 差分 — 前缀和与差分

力扣刷题:

  • 前缀和: 力扣前缀和
  • 差分: 力扣差分

Step 13: 贪心 — 贪心算法

前置知识: C_堆_Heap、Q_排序_八大排序_Sorting

力扣刷题: 力扣贪心、力扣哈夫曼、力扣贪心

Step 14: 滑动窗口 + 双指针 — 滑动窗口与双指针

前置知识: F_队列_Queue、前缀和

力扣刷题: 力扣滑动窗口、力扣双指针、力扣两数之差

Step 15: 递推递归 — 递推与递归

前置知识: B_栈_Stack、Q_排序_八大排序_Sorting

力扣刷题: 力扣递推、力扣斐波那契、力扣背包

Step 16: 搜索 — 搜索 (DFS / BFS)

前置知识: B_栈_Stack、F_队列_Queue、I_树_Tree_BST_AVL

力扣刷题: 力扣DFS、力扣BFS、力扣回溯

Step 17: 动态规划 — 动态规划

重点: 最优子结构、重叠子问题、状态定义与转移。经典模型：线性 DP、0/1 背包、完全背包。

前置知识: 递推递归、A_容器_Container

力扣刷题: 力扣背包问题、力扣背包问题、力扣最大子数组和、力扣完全背包

Phase 4 — 图论 (建议 10 天)

竞赛方向建议配合力扣/POJ/HDU/Codeforces练习；学习方向使用力扣即可。

Step 18: H_图_Graph — 图基础

重点: 图的定义、邻接矩阵/邻接表存储、BFS/DFS、Dijkstra、最小生成树。

配合算法: 图 — 图的最短路径、最小生成树

进阶图论:

力扣刷题: 743 网络延迟时间（Dijkstra）、1584 连接所有点的最小费用（MST）

Step 19: K_并查集_UnionFind — 并查集

重点: find（路径压缩）+ union（按秩合并）、Kruskal 应用。

配合算法: 连通性 — 并查集模板

力扣刷题: 547 省份数量（并查集）、684 冗余连接（并查集）

Step 20: P_图的高级算法_AdvancedGraph — 图高级算法

重点: 拓扑排序、Tarjan SCC、Floyd-Warshall、Bellman-Ford、网络流入门。

力扣刷题: 207 课程表（拓扑排序）、787 K 站中转内最便宜的航班（Bellman-Ford）、1192 查找集群内的关键连接（Tarjan）

Phase 5 — 进阶数据结构 (选学)

竞赛方向建议配合力扣/POJ/HDU/Codeforces练习；学习方向使用力扣即可。

顺序文件建议时机
21L_线段树_SegmentTree学完数组、递归后可选
22M_树状数组_BIT学完线段树后再看
23N_跳表_SkipList学完链表、哈希后可选
24E_红黑树_RedBlackTree学完 BST/AVL 后可选
25O_B树_BTree学完树、文件系统概念后可选

Phase 6 — 字符串与 DP 进阶 (选学)

竞赛方向建议配合力扣/POJ/HDU/Codeforces练习；学习方向使用力扣即可。

顺序文件建议时机
26Trie字典树学完哈希、图后可选
27字符串哈希学完哈希后可选
28后缀数组学完排序、二分后可选
29后缀自动机高级字符串
30区间DP学完基础 DP 后
31背包DP学完基础 DP 后
32树形DP学完树、DP 后
33状态压缩DP进阶优化
34数位DP进阶优化

算法技巧速查表

算法技巧文件前置知识对应数据结构章节
数组无A_容器_Container
循环无A_容器_Container
暴力枚举循环 + 数组Q_排序_八大排序_Sorting
二分查找排序Q_排序_八大排序_Sorting
双指针数组 + 循环D_链表_LinkedList
前缀和数组 + 循环A_容器_Container
差分前缀和A_容器_Container
二分答案二分查找Q_排序_八大排序_Sorting
贪心排序C_堆_Heap
滑动窗口双指针 + 前缀和F_队列_Queue
递推递归函数 + 数组B_栈_Stack
搜索递推递归B_栈_Stack, F_队列_Queue, I_树_Tree_BST_AVL
动态规划递推递归 + 堆A_容器_Container
图搜索 + 贪心H_图_Graph
连通性图 + 搜索K_并查集_UnionFind
优化全部L_线段树_SegmentTree, M_树状数组_BIT

学习节奏建议

Phase 1 (两周): 线性结构集训 -- 每天 1 个数据结构 + 少量算法题
Phase 2 (两周): 核心结构 -- 每 2-3 天一个主题，多手写
Phase 3 (两周): 算法专题 -- 每天一个算法技巧，大量刷题
Phase 4 (一到两周): 图论 -- 算法综合应用
Phase 5 (剩余时间): 选学进阶

每一章的标准动作:

  1. 阅读本章文件（先概念，再代码）
  2. 关掉文件，手写核心数据结构的实现
  3. 用语言标准库快速刷 2-3 道力扣题
  4. 阅读本章推荐的相关算法技巧文件

关系图谱

反向链接