数据结构与算法
Data Structures and Algorithms
📖这门课到底讲什么
数据结构与算法研究数据如何组织、算法如何设计才能高效运行：线性表、栈与队列、串与模式匹配、树与二叉树、堆与优先队列、图、查找结构（哈希表、平衡树、跳表）以及排序与分治、贪心、动态规划等算法思想。课程的核心不是背实现，而是三件事：选择合适结构、分析时间与空间复杂度、把现实问题抽象成可计算的模型。它是所有后续专业课与所有技术面试的共同基础，学完你应能手写顺序表、链表、二叉树、堆的实现，熟练实现各类遍历与排序，用哈希表与并查集解决问题，并对一道未见过的问题给出复杂度可接受的设计方案。
🎯为什么必须学好
它是技术面试的第一道门槛，几乎所有大厂笔试与手撕环节都在考；也是考研 408 的核心课程之一，分值占比最高，且是操作系统、数据库、网络课程中各种数据结构的前置。保研机试、ACM 校赛、课程设计全部依赖它。没有这门课，后面所有课程会变成背诵；有了它，你会开始用复杂度的眼光审视一切代码，这是软件工程师与写代码的人的真正分野。
📌核心知识清单
- 复杂度分析：大 O 与均摊分析、递归时间复杂度（主定理）、空间复杂度的估算
- 线性表：顺序表与单/双向链表、循环链表的插入删除实现与边界处理、链表常见技巧（双指针、快慢指针、哑结点）
- 栈与队列：顺序栈与链栈、循环队列、单调栈与单调队列的经典应用（下一个更大元素、滑动窗口最大值）
- 树与二叉树：三种遍历的递归与非递归实现、层序遍历、线索二叉树、树与森林的转换
- 二叉搜索树、平衡树与堆：BST 的增删查、AVL 旋转、堆的建堆与堆排、优先队列的应用（TopK、合并K个有序链表）
- 哈希表：散列函数设计、开放定址与链地址法、负载因子与扩容、用哈希解决两数之和与去重
- 图：邻接矩阵与邻接表、DFS/BFS、拓扑排序、最小生成树（Prim/Kruskal）、最短路（Dijkstra/Floyd）与并查集
- 排序与查找：快排、归并排、堆排的实现与复杂度对比、二分查找及其变形（左右边界、旋转数组搜索）
- 字符串与算法思想：KMP 与 Trie、分治、贪心、回溯与剪枝、动态规划入门（背包、最长子序列）
✍️怎么学（可执行步骤）
- 主干教材用严蔚敏《数据结构（C语言版）》或《算法（第4版）》，每学一个结构立刻用 C++/Java/Python 各实现一遍，禁止只读代码
- 刷题平台选 LeetCode 中文站与洛谷：按专题刷（数组/链表/二叉树/图/DP 各五十题），用 leetcode-master 或 labuladong 的分类顺序推进，坚持写题解
- 用 OI Wiki 与 VisuAlgo 对照可视化理解算法执行过程，尤其是 KMP、Dijkstra、AVL 旋转这些光看代码想不明白的部分
- 每道题写完必须写复杂度分析，三个月后开始做限时训练（每题二十分钟）与手写代码训练（在纸上写链表反转与快排），模拟面试场景
📚推荐教材与书籍
国内考研指定参考书，抽象数据类型与算法伪码风格需适应，重点第二至七章
配套 Java 实现与可视化，代码质量极高，适合作为动手实践的主参考
语言通俗、图解多，适合初学时建立直觉，之后一定要回到严谨教材
理论最完整的权威教材，重点读分治、堆、红黑树、动态规划、图算法章节，适合大三后精读
🎬视频课程 / 公开课
浙江大学陈越、何钦铭讲授，口碑极佳，配套编程作业体系完整，建议全程跟做
英文经典入门算法课，讲复杂度与算法设计的思路非常清楚
🌐网站与文档
把排序、树、图算法逐步动画展示，理解指针变化与递归过程的最佳工具
中文算法百科，从入门到进阶覆盖完整，附代码模板与复杂度说明
面试题库与周赛，建议从热题一百开始按专题刷
🐙GitHub 开源资料
代码随想录，按数据结构与算法专题编排题解，最适合系统刷题的中文资料
用套路与框架讲动态规划、二叉树、回溯，能显著降低刷题痛苦度
多语言题解合集，看同一题不同语种与不同思路的实现
各类数据结构的 Python 纯实现，适合对照自己的手写版本查漏补缺
🧪动手实践任务
实践 1
从零实现一个支持泛型的动态数组与双向链表，包含插入、删除、查找、扩容，并写单元测试验证边界情况（空表、首尾插入）
实践 2
实现并压测三种排序（快排、归并、堆排）在一百万随机整数上的运行时间，绘制复杂度曲线并解释差异
实践 3
完成一个小型图算法项目：读入城市铁路网络数据，实现最短路查询与连通性检测（Dijkstra 加并查集），输出路径与耗时
实践 4
用哈希表与堆各实现一次 TopK 热搜统计，比较在不同数据规模下的性能差别并写出结论
🧾考试与面试
💼 面试会怎么考
必考：手撕反转链表与判断链表是否有环（快慢指针）、二叉树三种遍历的非递归写法；数组类题目考滑动窗口与双指针（最长无重复子串）；动态规划考背包与最长递增子序列，重点在状态定义与转移方程；图题考拓扑排序与最短路。此外会追问复杂度：哈希表为什么平均 O(1) 而最坏退化、快排为什么最坏 O(n^2) 以及如何避免、堆排序与快排的适用场景。
📝 期末与考研怎么过
期末通常为卷面考试：选择题考性质与复杂度、填空题考树的遍历序列与哈希计算、大题考手动模拟（哈希插入、AVL 旋转、图的最短路、快排一趟划分）与算法设计题。考研 408 中此部分约四十五分，是所有科目中最高。备考方法：手动模拟题必须拿笔在纸上推到底，算法设计题背熟常用模板并写清复杂度。目标：校内九十分以上，考研此模块接近满分。
⚠️ 常见坑
- 只看不写，把看懂题解当成会做题，面试手撕环节直接暴露；必须闭卷手写完整代码
- 链表题不处理边界（头结点、单结点、尾结点）与指针丢失问题，写完不画图验证
- 递归写得对但不会转非递归，也不分析递归深度导致的栈溢出，面试被追问就卡住
- 刷题只求数量不写题解不复盘，同一类型题反复错，应该按专题攻克并记录错题原因
- 忽略复杂度分析，交出 O(n^2) 的方案还不知道为什么超时