绪论：数据结构与算法详解 (进阶版)

“程序设计 = 数据结构 + 算法” —— 尼克劳斯·沃思 (Niklaus Wirth, 图灵奖得主)

如果把编程比作烹饪：

• 数据结构 (Data Structure) 是食材与厨具的收纳方式。你是把所有东西堆在桌子上（杂乱无章），还是把蔬菜放保鲜层、肉类放冷冻层、刀具挂在磁吸架上（井井有条）？这决定了你取用材料的效率。
• 算法 (Algorithm) 是菜谱与烹饪流程。是先切菜还是先烧油？是慢火炖还是大火爆炒？这决定了做菜的速度和口味。

本教程旨在通过可视化的方式，深入剖析计算机科学的这两大基石。

数据结构不仅仅是存储数据，更是为了高效地检索和操作数据。

在深入具体结构前，我们需要厘清以下术语的层级关系：

逻辑结构是指数据元素之间的相互关系，它与数据在计算机中的存储位置无关。我们通常将其分为四类。

• 特性：元素之间除了“同属于一个集合”外，无其他关系。
• 操作：主要涉及并集、交集、差集、判断元素是否存在。

• 特性：存在唯一的“第一个”和“最后一个”元素；除首尾外，每个元素都有且仅有一个前驱和一个后继。
• 典型代表：
  • 数组 (Array)：连续存储。
  • 链表 (Linked List)：离散存储。
  • 栈 (Stack)：后进先出 (LIFO)，如弹夹。
  • 队列 (Queue)：先进先出 (FIFO)，如排队。

• 特性：存在一个根节点；每个节点可以有多个子节点，但只能有一个父节点（根除外）。
• 典型代表：二叉树、红黑树、B树（数据库索引常用）。

• 特性：最复杂的结构，节点（顶点）之间可以任意连接（边）。
• 分类：有向图 vs 无向图；带权图 vs 无权图。

逻辑结构是“想出来的”，存储结构是“写在内存条上的”。

• 原理：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中。
• 代表：数组 (Array)。
• 优点：
  • 随机访问：可以通过下标 $index$ 瞬间找到地址：$Addr = Start + index \times size$。时间复杂度 $O(1)$。
  • 存储密度高：不需要额外空间存指针。
• 缺点：
  • 插入删除困难：插入一个元素，后面的所有元素都要往后挪，效率低。
  • 大小固定：需要预先分配空间，容易浪费或溢出。

• 原理：逻辑上相邻的元素在物理上可以不相邻。通过“指针” (Pointer) 链接。
• 代表：链表 (Linked List)。
• 优点：
  • 插入删除快：只需要修改指针指向，不需要移动数据。
  • 动态扩展：有多少数据申请多少内存，不浪费。
• 缺点：
  • 无法随机访问：想找第10个元素，必须从第1个顺藤摸瓜找下去。时间复杂度 $O(n)$。
  • 空间开销：每个数据都要额外存一个指针地址。

• 索引存储 (Index)：建立附加的索引表（类似字典目录）。虽然检索快，但增加了索引表的空间开销和维护成本。
• 散列存储 (Hash)：速度之王。
  • 不通过比较，而是通过公式（哈希函数）直接计算出存储地址。
  • 冲突 (Collision)：当不同的数据算出了相同的地址时，需要特殊处理（如拉链法）。

算法是解决特定问题求解步骤的描述。一个好的算法应该具备：正确性、可读性、健壮性、高效率。

我们不计算具体的秒数（因为这取决于机器性能），而是计算操作步骤数量随数据量 $n$ 的增长趋势。

• $O(1)$ 常数阶：代码执行次数固定，不随数据增加而增加。

    int n = 10000;
    x = n + 1; // 无论n多大，这行只执行一次

• $O(n)$ 线性阶：一层循环。

    for(int i=0; i<n; i++) { ... }

• $O(n^2)$ 平方阶：双层嵌套循环。

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) { ... }
    }

• $O(\log n)$ 对数阶：每次循环，数据量都砍半（如二分查找）。

    while(n > 1) {
        n = n / 2; // 1024 -> 512 -> 256 ... 10次就到了
    }

这是算法的灵魂，掌握这些思想比背诵代码更重要。

• 别名：暴力破解法。
• 核心：列出所有可能的情况，逐一验证。
• 优点：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。
• 缺点：效率极低。
• 案例：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。

• 核心口诀：分而治之，各个击破。
• 适用场景：问题可以拆解为多个独立的子问题，且子问题与原问题结构相同。
• 典型应用：归并排序 (Merge Sort)、快速排序 (Quick Sort)、MapReduce (大数据处理)。

• 核心：历史记录。通过空间换时间。
• 原理：将复杂问题分解为子问题，但与分治法不同的是，DP 的子问题是重叠的。为了避免重复计算，DP 会把每个子问题的结果存进一张表里。
• 案例：斐波那契数列 (1, 1, 2, 3, 5, 8…)
  • 求第 5 个数：$F(5) = F(4) + F(3)$
  • 求 $F(4)$ 时需要算 $F(3) + F(2)$。
  • 注意：$F(3)$ 被计算了两次！如果是递归，$n$ 很大时重复计算量是指数级的。
  • DP做法：算完 $F(3)$ 就把它记在本子上，下次直接看本子。

• 核心：活在当下。
• 策略：每一步都做出在当前看来最好的选择。它不从整体最优考虑，但在很多情况下（如最小生成树），局部最优能导致全局最优。
• 案例：找零钱
  • 问题：找 66 元，纸币规格有 100, 50, 20, 10, 5, 1。
  • 贪心策略：优先用面值最大的。
  • 步骤：
    • 66 < 100，跳过。
    • 66 >= 50，给一张 50。剩 16。
    • 16 < 20，跳过。
    • 16 >= 10，给一张 10。剩 6。
    • 6 >= 5，给一张 5。剩 1。
    • 给一张 1。结束。
• 局限：如果纸币规格是 1, 3, 4，找 6 元。贪心会给 4+1+1 (3张)，但最优解是 3+3 (2张)。此时贪心失效，需用 DP。

• 核心：试错与回退。
• 策略：这是一种深度优先搜索 (DFS)。一条路走到黑，如果发现走不通（不满足条件），就回溯到上一个路口，换一条路继续走。
• 剪枝 (Pruning)：在搜索过程中，如果发现当前分支已经不可能找到解，就直接切断该分支，不再往下搜，大大提高效率。
• 典型应用：走迷宫、八皇后问题、数独。