这是本文档旧的修订版！
绪论：数据结构与算法详解
程序设计的核心公式（N.沃思）：
程序 = 数据结构 + 算法
- 数据结构：就像是做饭的“食材”和“摆盘方式”（问题的数学模型）。
- 算法：就像是“菜谱”和“烹饪步骤”（处理问题的策略）。
第一部分：数据结构 (Data Structure)
1. 核心概念辨析
我们通过一个“学生信息管理系统”的例子来理解以下概念：
- 数据 (Data)：计算机处理的符号总称。
- 数据元素 (Data Element)：数据的基本单位。
- *例子*：学生表中的一行记录（包含姓名、学号、班级）。
- 数据项 (Data Item)：构成元素的不可分割的最小单位。
- *例子*：某条记录中的“学号”这一项。
- 数据对象 (Data Object)：性质相同的数据元素的集合。
- *例子*：整数集、所有学生的集合。
2. 逻辑结构：数据之间的“关系”
逻辑结构描述的是数据在思想上的关联，与它们在电脑里存哪里无关。
| 类型 | 关系特点 | 生活中的例子 | 图示说明 |
|---|---|---|---|
| 集合结构 | 松散。除了“同在一个圈子”外，没别的关系。 | 操场上散开做操的同学。 | ( A B C ) |
| 线性结构 | 一对一。像一条线，有头有尾，前后相连。 | 排队打饭的队伍；挂在墙上的一串钥匙。 | A → B → C |
| 树状结构 | 一对多。层次分明，像倒过来的树。 | 电脑里的文件夹（C盘 → 用户 → 文档）；家族族谱。 | A → (B, C) |
| 图形结构 | 多对多。错综复杂，四通八达。 | 城市交通网；微信的好友关系网。 | A ↔ B ↔ C |
3. 存储结构：数据在“内存”中的样子
这是逻辑结构在计算机中的物理实现。这是本章的重点，我们可以通过 HTML 可视化来理解。
HTML 可视化演示：顺序 vs 链式
1. 顺序存储 (Sequential Storage) - 类似数组
特点：物理位置紧邻，像电影院连座。
1101
1105
1202
1203
addr:0
addr:1
addr:2
addr:3
2. 链式存储 (Linked Storage) - 类似寻宝游戏
特点：物理位置随意，靠“小纸条(指针)”指引下一站。
1101
•
→
1105
•
→
1202
^
3.1 详细对比
| 特性 | 顺序存储 (数组) | 链式存储 (链表) |
| 物理位置 | 必须相邻。 | 可以不相邻，散落在内存各处。 |
| 关系表示 | 靠位置体现（$A$ 的后面就是 $B$）。 | 靠指针体现（$A$ 手里拿着 $B$ 的地址）。 |
| 优点 | 查找快（直接算地址），存储密度大。 | 插入、删除快（不用移动元素，改指针即可）。 |
| 缺点 | 插入删除需要移动大量元素；需要预分配空间。 | 查找慢（必须从头找）；指针占用额外空间。 |
第二部分：算法 (Algorithm)
算法不仅要算出结果，还要算得“快”且“省”。
1. 算法的五大特性
记忆口诀：有输（出）入，可行确（定）穷。
- 有穷性：算法不能陷入死循环，必须能跑完。
- 确定性：代码不能模棱两可，同样的输入必须得到同样的输出。
- 可行性：每一步都能通过有限次基本运算完成。
- 输入：0个或多个（例如 `void print_hello()` 就没有输入）。
- 输出：1个或多个（没有输出的算法是无意义的）。
2. 算法效率度量
我们用 大O记号 ($O$) 来表示“大概的趋势”，而不是精确的秒数。
2.1 时间复杂度 (Time Complexity)
随着数据量 $n$ 的增大，耗时增长的趋势。
* $O(1)$ 常数阶：无论数据多少，耗时不变。
- *例子*：访问数组的第 5 个元素 `a[5]`。
* $O(n)$ 线性阶：数据翻倍，耗时翻倍。
- *例子*：遍历一个列表，找某个数。
* $O(n^2)$ 平方阶：数据翻倍，耗时变成 4 倍。
- *例子*：双层循环，如冒泡排序。
* $O(\log_2 n)$ 对数阶：非常快。
- *例子*：二分查找（在有序书中找页码）。
效率排序： $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$
第三部分：五大常用算法思想详解
这是绪论中最具实战意义的部分，以下结合图片内容进行深度解析。
1. 穷举法 (Brute Force)
- 别名：暴力破解法。
- 核心：“笨”办法，试遍所有可能。
- 案例：破解密码。
- 假设密码是4位数字（0000-9999）。
- 算法：从 0000 开始，一直试到 9999。
- *分析*：理论上一定能找到，但如果密码很长，时间会无法接受。
2. 递推法与迭代法
* 核心：利用旧值推出新值。 * 案例：阶乘计算 ($n!$)。
- 公式：$n! = n \times (n-1)!$
- 边界：$0! = 1$
- 实现：使用 `for` 循环（迭代）或者函数调用自身（递归）。
- *代码逻辑*：`result = 1; for(i=1; i⇐n; i++) { result = result * i; }`
3. 分治法 (Divide and Conquer)
- 核心：大事化小，各个击破。
- 三步走：
- 分 (Divide)：把大问题切成几个独立的小问题。
- 治 (Conquer)：递归解决小问题。
- 合 (Combine)：把小问题的结果拼起来。
- 案例：排序问题。
- 要给 1000 个数排序，先分成两组各 500 个，再分…直到只剩 1 个数（不用排了），然后再两两合并有序序列。
- 关键条件：子问题必须是相互独立的（子问题A的结果不依赖子问题B）。
4. 贪婪算法 (Greedy Algorithm)
- 核心：目光短浅，只顾眼前。不追求整体最优，只做当前看起来最好的选择。
- 特点：一旦选定，不回溯（不后悔）。
- 案例：找零钱问题。
- *场景*：要找回 15 元，现有面值 11元、5元、1元。
- *贪心策略*：优先选最大的。
- 选 11元（剩4元）。
- 5元不够，选 1元（剩3元）。
- 选 1元…
- 结果：1张11元 + 4张1元 = 5张。
- *问题*：这真的最优吗？
- 最优解其实是：3张5元 = 3张。
- *结论*：贪心算法快，但不一定能得到全局最优解（除非硬币面值设计得好，如 1, 5, 10）。
5. 动态规划 (Dynamic Programming)
- 核心：精打细算，拒绝重复。
- 与分治法的区别：
- 分治法处理独立子问题。
- 动态规划处理重叠子问题（即：很多小问题是一样的）。
- 手段：引入一个表格（数组），算过的结果记下来，下次直接查表，不用重算。
- 案例：斐波那契数列 (Fibonacci)。
- 求 `Fib(5)` 需要 `Fib(4)` 和 `Fib(3)`。
- 求 `Fib(4)` 需要 `Fib(3)` 和 `Fib(2)`。
- *发现*：`Fib(3)` 被重复计算了！
- *DP做法*：算完 `Fib(3)` 后存入数组 `arr[3]`。下次需要时，直接读取 `arr[3]`。
- 适用场景：最优化问题，具有最优子结构和重叠子问题性质。
张叶安