数据结构与算法基础：提升你的编程内功

数据结构与算法基础：提升你的编程内功

一句话定位：把每种数据结构当作一门内功心法来修炼——招式（API 怎么用）、心法（不变量与复杂度为什么成立）、走火入魔（什么场景会翻车），读完能对任意一段代码估出效率量级，并按问题特征选对结构。

为什么这门课要按内功来讲

同样是一段查重代码，有人写出来瞬间出结果，有人写出来程序卡到怀疑人生。差距往往不在语言、不在框架，而在一样看不见的东西——组织数据的方式与处理数据的套路。武林高手过招，胜负常在动手之前就由内力深浅决定；程序员解题，快慢也常在落笔之前就由结构选型决定。

这本教程因此不按"名词解释加代码罗列"的套路走。每门数据结构，都拆成三层来练：

• 招式：对外暴露的操作与接口，好比一套动作，照着做就能用；
• 心法：结构内部必须始终成立的不变量，以及由它推出的复杂度量级——这是招式威力的来源；
• 走火入魔：违反心法前提的典型误用，附可复现的症状与解法。

只背招式不懂心法，换个题面就束手无策；懂心法却没见过走火入魔现场，上了生产环境照样出事故。三层齐修，才算内功入门。

全册知识地图

七章内容不是并列关系，而是一条修炼主线：先立总纲（会量内力），再练线性与树形两路根基结构，随后进入图论与排序查找两大应用场，最后把分治、动态规划等"套路"融会贯通，收束于并查集、线段树等高阶兵器。

数据结构与算法修炼路线图

第一章是总纲，后面每一章的复杂度论证都靠它；第二章的数组与链表是所有结构的原材料；第三章的树建立在"节点与链接"之上；第四章把树推广成任意的图；第五章把前几章的结构当兵器用进排序与查找；第六章抽出可迁移的解题套路；第七章是融会贯通后的高阶组合技。

适合谁读

• 学过一门编程语言（本册示例以 Python 为主，个别坑用 Java 对照）、能写循环和函数，但说不清自己代码快慢量级的读者；
• 刷题时"能过但不知道为什么"，或者遇到变形题就卡壳的读者；
• 准备技术面试，需要把复杂度、不变量、边界条件讲成体系而不是背结论的读者；
• 想读开源容器代码（比如语言内置的哈希表、平衡树）但总被内部实现劝退的读者。

学完你能做什么

1. 拿到一段代码，能数出基本操作次数并推导出大 O、大 Ω、大 Θ 三种渐进刻画；
2. 对数组、链表、栈、队列、哈希表、树、堆、图，说出各自的不变量与每种操作的复杂度；
3. 手写并验证冒泡、插入、快排、归并、堆排、计数排序与二分查找等核心算法；
4. 按问题特征（有序性、稀疏性、动态性、区间性）做结构选型，并说明代价；
5. 用分治、动态规划、贪心、回溯四类范式建模新问题，并能证明或反驳贪心的正确性；
6. 识别十类以上高频"走火入魔"场景：哈希最坏退化、快排碰到有序输入、递归爆栈等，并给出对策。

学习路线

怎么用这个教程

每章开头是一张问答式支柱页：先抛出本章要回答的问题，再给出各节分工与知识点清单，读完每节可以回头对照自查。正文示例以 Python 为主，所有代码都带注释与运行输出，复杂度测算给的数字都可以亲手复算——这是本册的规矩：凡是量级，必可复现。建议顺序通读，遇到"走火入魔"小节务必动手复现症状；已有基础的读者可以直奔第六章与第七章，再按需回查。