数据结构与算法（Rust 实现）
作者：Shieber | 2021年出版 | 基于 Rust 1.58 全书共 9 章 298 页，从计算机科学基础讲起，逐步深入到数据结构、算法分析、树、图，最后以实战项目收尾。所有代码示例均使用 Rust 实现。
全书概览
本书的核心思路是用 Rust 语言作为工具，系统讲解数据结构与算法。不同于传统教材用 C/Java/Python 讲解，本书充分利用 Rust 的所有权系统、泛型、生命周期、trait 等特性来实现各种数据结构，让读者在学习算法的同时也能提升 Rust 编程能力。
全书结构：
| 章节 | 主题 | 核心内容 |
|---|---|---|
| 第1章 | 计算机科学 | 抽象数据类型(ADT)、算法定义、Rust 基础回顾 |
| 第2章 | 算法分析 | 大 O 表示法、时间/空间复杂度、Rust 基准测试 |
| 第3章 | 基本数据结构 | 栈、队列、双端队列、链表、Vec |
| 第4章 | 递归 | 递归三定律、尾递归、动态规划、汉诺塔 |
| 第5章 | 查找 | 顺序查找、二分查找、哈希查找、HashMap 实现 |
| 第6章 | 排序 | 10 种排序算法 + TimSort |
| 第7章 | 树 | 二叉树、堆、二叉查找树、AVL树、红黑树 |
| 第8章 | 图 | 邻接表/矩阵、BFS、DFS、最短路径、最小生成树 |
| 第9章 | 实战 | 编辑距离、字典树、布隆/布谷鸟过滤器、LRU、一致性哈希、区块链 |
第一章：计算机科学基础
核心观点
- 计算机科学 ≠ 研究计算机：计算机科学是对问题、解决方案及产生方案的过程的研究。计算机只是工具。
- 算法是核心：计算机科学家的目标是开发一个算法——一系列指令列表，用于解决某类问题的任何实例。
- 某些问题没有算法：如 NPC 问题，目前不能解决，但对其的研究本身很重要（类似哥德巴赫猜想推动了数学发展）。
抽象数据类型 (ADT)
ADT 是对数据和操作的逻辑描述——只关心数据表示什么，不关心它的最终形式。
- 逻辑视图（用户视图）：知道接口怎么用就行，不需要知道内部实现（“黑箱”思想）
- 物理视图（实现者视图）：用原始数据类型构建 ADT，即数据结构
- 封装的价值：允许程序员在不改变交互方式的情况下替换实现细节
编程的本质
编程是将算法编码为计算机指令的过程。没有算法就没有程序。
编程语言至少需要提供：
- 顺序处理
- 决策选择
- 重复迭代
Rust 学习资源推荐
入门书籍：《Rust 程序设计语言》、《深入浅出 Rust》、《Rust 编程之道》、《通过例子学 Rust》、《Rust Primer》、《Rust Cookbook》、《Rust in Action》、《Rust 语言圣经》
进阶：《Cargo 教程》、Rustlings、《通过链表学 Rust》、《Rust 设计模式》
高阶：rustc 手册、《Rust 宏小册》、《Rust 死灵书》、《Rust 异步编程》
第二章：算法分析
大 O 分析法
为什么需要大 O？ 基准测试依赖具体硬件和语言，我们需要一种独立于机器的度量来比较算法效率。
核心思想：当问题规模 n 变大时，T(n) 中增长最快的部分起决定作用，其他项和常数系数可以忽略。
常见复杂度等级（从低到高）
| 大 O | 名称 | 典型例子 |
|---|---|---|
| O(1) | 常数 | 数组索引访问、数学公式计算 |
| O(log n) | 对数 | 二分查找 |
| O(n) | 线性 | 顺序查找、单循环遍历 |
| O(n log n) | 线性对数 | 归并排序、快速排序（平均） |
| O(n²) | 平方 | 冒泡排序、插入排序、双重循环 |
| O(n³) | 立方 | 三重循环 |
| O(2ⁿ) | 指数 | 暴力递归、某些 NPC 问题 |
三种情况分析
- 最坏情况：导致性能最差的特定数据集（算法分析通常关注这个）
- 最好情况：最优数据集下的性能
- 平均情况：大多数情况下的性能
💡 程序员需要了解这三种情况的区别，避免被某一个特定情况误导。
第三章：基本数据结构
线性数据结构总览
| 结构 | 特性 | 基本操作 | 典型应用 |
|---|---|---|---|
| 栈 (Stack) | 后进先出 LIFO | push, pop, is_empty | 表达式解析、函数调用栈、撤销操作 |
| 队列 (Queue) | 先进先出 FIFO | enqueue, dequeue, is_empty | 任务调度、广度优先搜索 |
| 双端队列 (Deque) | 两端都可进出 | add_front/remove_front, add_rear/remove_rear | 回文检测、滑动窗口 |
| 链表 (LinkedList) | 非连续内存存储 | insert, remove, search | 灵活插入删除、避免数组扩容 |
| Vec | 动态数组（Rust 内置） | push, pop, 索引访问 | 通用容器、栈的底层实现 |
栈的重要应用：表达式求值
- 前缀表达式（波兰式）：运算符在操作数之前，如
+ A B - 中缀表达式：运算符在中间，如
A + B（人类常用，但计算机处理麻烦） - 后缀表达式（逆波兰式）：运算符在操作数之后，如
A B +
计算机不用中缀表达式。栈可以轻松实现中缀转后缀、后缀表达式求值。
第四章：递归
递归三定律
- 基本情况（Base Case）：递归必须有一个不再递归的终止条件
- 递归调用：必须调用自身
- 向基本情况演进：每次递归调用都要使问题规模变小，向基本情况靠近
递归的本质
递归是迭代的另一种形式。任何递归都可以改写为迭代，反之亦然。
尾递归优化
尾递归是指递归调用是函数的最后一个操作。某些语言/编译器可以将尾递归优化为循环，避免栈溢出。
⚠️ Rust 目前不自动优化尾递归（与 Scala、Haskell 等函数式语言不同），深递归仍可能栈溢出。
动态规划
动态规划是一类高效算法的代表，核心思想是将大问题分解为重叠子问题，保存子问题的解避免重复计算。通常用递归或迭代实现。
经典递归问题
- 进制转换（十进制转任意进制）
- 汉诺塔问题
- 斐波那契数列（朴素递归低效，动态规划高效）
第五章：查找
查找算法对比
| 算法 | 前提条件 | 时间复杂度（平均/最坏） | 空间复杂度 |
|---|---|---|---|
| 顺序查找 | 无 | O(n) / O(n) | O(1) |
| 二分查找 | 数据已排序 | O(log n) / O(log n) | O(1) |
| 指数查找 | 数据已排序，适合数据量极大且目标靠前的情况 | O(log i)（i为目标位置） | O(1) |
| 哈希查找 | 哈希表 | O(1) / O(n)（冲突极端） | O(n) |
哈希表
核心思想：通过哈希函数将键映射为数组索引，实现 O(1) 查找。
冲突解决方法：
- 开放寻址法：冲突时找下一个空位（线性探测、二次探测）
- 链地址法：每个槽位挂一个链表（Rust HashMap 采用的是改良版）
Rust 的
HashMap默认使用 SipHash 1-3 算法，防哈希碰撞攻击，但性能不是最高。可通过FnvHashMap等第三方库换取更高性能。
第六章：排序
本书详细讲解了 10 + 1 种排序算法：
基础排序（O(n²)）
| 算法 | 思想 | 稳定性 | 适用场景 |
|---|---|---|---|
| 冒泡排序 | 相邻元素两两比较交换 | 稳定 | 教学演示，实际几乎不用 |
| 选择排序 | 每次选最小的放到前面 | 不稳定 | 交换次数少，但比较多 |
| 插入排序 | 逐个插入到已排序序列的正确位置 | 稳定 | 小规模/近乎有序数据极快 |
| 希尔排序 | 插入排序的改进，分组插入 | 不稳定 | 中等规模数据 |
高效排序（O(n log n)）
| 算法 | 思想 | 稳定性 | 适用场景 |
|---|---|---|---|
| 快速排序 | 分治，选基准分区 | 不稳定 | 大多数情况的首选 |
| 归并排序 | 分治，两两合并 | 稳定 | 需要稳定排序、链表排序 |
| 堆排序 | 利用堆的性质 | 不稳定 | 内存有限时（原地排序） |
非比较排序（O(n)，但有限制条件）
| 算法 | 思想 | 适用场景 |
|---|---|---|
| 桶排序 | 按范围分桶再分别排序 | 数据分布均匀 |
| 计数排序 | 统计每个值出现的次数 | 值范围小的整数 |
| 基数排序 | 按位逐次排序 | 整数或固定长度字符串 |
TimSort —— 工业界的王者
TimSort 是归并排序 + 插入排序的混合算法，已经成为 Java、Python、Rust 等语言的默认排序算法。
核心思想：
- 利用现实中数据往往存在部分有序（“run”）的特性
- 短 run 用插入排序扩展长度
- 长 run 用归并排序合并
- 最坏情况 O(n log n)，最好情况接近 O(n)
Rust 中的排序：
slice::sort()—— TimSort，稳定排序slice::sort_unstable()—— 模式-defeat quicksort，不稳定但更快
第七章：树
树的家族谱
树
├── 二叉树
│ ├── 二叉堆 (Binary Heap) → 优先队列
│ ├── 二叉查找树 (BST)
│ │ └── 平衡二叉树
│ │ ├── AVL 树
│ │ └── 红黑树
│ └── 表达式解析树
├── B 树 / B+ 树（数据库索引）
├── 八叉树（空间索引）
└── 字典树 Trie（第9章实战）
核心数据结构性能对比
| 操作 | 有序列表 | 哈希表 | 二叉查找树（最坏） | 平衡二叉树 | 红黑树 |
|---|---|---|---|---|---|
| insert | O(n) | O(1) | O(n) | O(log n) | O(log n) |
| search | O(log n) | O(1) | O(n) | O(log n) | O(log n) |
| delete | O(n) | O(1) | O(n) | O(log n) | O(log n) |
重要概念
- 二叉堆：用数组实现的完全二叉树，可做优先队列，插入和弹出都是 O(log n)
- AVL 树：通过旋转保持左右子树高度差 ≤1，严格平衡
- 红黑树：通过颜色约束保持大致平衡，插入删除旋转次数少于 AVL，实际应用更广（Rust 的 BTreeMap 是 B 树而非红黑树）
第八章：图
图的基本概念
- 顶点 (Vertex)：图的基本元素，有键和负载
- 边 (Edge)：连接顶点的关系，可单向/双向、可带权重
- 图的表示：G = (V, E)
- 路径：顶点的连接序列
- 环：起点和终点相同的路径
- DAG（有向无环图）：没有环的有向图，许多重要问题可用 DAG 表示
存储形式
| 方式 | 空间 | 边查找 | 适用场景 |
|---|---|---|---|
| 邻接矩阵 | O(V²) | O(1) | 稠密图 |
| 邻接表 | O(V+E) | O(degree) | 稀疏图（大多数现实情况） |
图算法
| 算法 | 用途 | 时间复杂度 |
|---|---|---|
| 广度优先搜索 (BFS) | 最短路径（无权图）、层序遍历 | O(V+E) |
| 深度优先搜索 (DFS) | 拓扑排序、连通性、环检测 | O(V+E) |
| Dijkstra 算法 | 单源最短路径（非负权重） | O((V+E) log V) 用优先队列 |
| 最小生成树 | 连接所有顶点的最小代价树 | Prim / Kruskal 算法 |
第九章：实战项目
本章是全书精华，用前面所学解决实际问题：
9.2 编辑距离
- 汉明距离：等长字符串对应位置不同字符的数量（简单但适用有限）
- 莱文斯坦距离：通过插入、删除、替换将一个字符串变成另一个所需的最少操作数
- 实现：动态规划，二维 DP 表
9.3 字典树 (Trie)
- 用于前缀匹配、自动补全、拼写检查
- 每个节点代表一个字符，路径代表一个词
- Rust 中可用
HashMap<char, TrieNode>实现子节点
9.4 过滤器
布隆过滤器 (Bloom Filter)：
- 用位数组 + 多个哈希函数判断”元素可能存在或一定不存在”
- 优点：空间效率极高，O(1) 查询
- 缺点：有假阳性（误判存在），不能删除元素
布谷鸟过滤器 (Cuckoo Filter)：
- 改进版布隆过滤器，支持删除元素
- 基于布谷鸟哈希，两个候选位置
- 假阳性率更低，空间效率更高
9.5 LRU 缓存淘汰算法
- Least Recently Used：最近最少使用的先淘汰
- 经典实现：哈希表 + 双向链表
- 哈希表：O(1) 查找节点
- 双向链表：维护使用顺序，O(1) 移动/删除
- Rust 中可用
HashMap+LinkedList或VecDeque实现 - 标准库
std::collections暂无内置 LRU，社区有lrucrate
9.6 一致性哈希
- 解决分布式系统中节点增减导致的数据大规模迁移问题
- 将节点和数据都映射到哈希环上
- 数据顺时针找到的第一个节点就是其存储节点
- 节点增减只影响相邻节点的少量数据
- 虚拟节点：解决节点少导致的数据分布不均问题
9.8 区块链（全书综合项目）
逐步实现一个简化版区块链，涵盖：
- 区块结构（索引、时间戳、交易、哈希、前一区块哈希）
- 工作量证明 (Proof of Work)
- 区块链存储（可持久化到磁盘）
- 交易与 UTXO 模型
- 账户与签名
- 挖矿奖励机制
这个项目综合运用了哈希、链表（链）、Merkle 树、加密签名等多种数据结构和算法，是全书的集大成实践。
本书特色与评价
优点
- Rust 原生实现：所有数据结构都用 Rust 特性（所有权、泛型、生命周期、trait）实现，不是 C 语言思路的翻译
- 循序渐进：从计算机科学基础讲起，到具体数据结构，再到算法分析，最后综合实战
- 代码可独立编译：每段代码都能单独编译运行，方便动手实践
- 中文原创：不是翻译书，语言流畅自然
- 覆盖面广：从基础栈队列到区块链，内容跨度大，适合系统复习
注意事项
- 使用的 Rust 版本为 1.58（2022年初），部分语法可能已演化，但核心概念不过时
- 算法实现偏教学导向，不是最优工程实现（作者明确指出，目的是抓重点）
- 适合有一定 Rust 基础的读者，纯新手建议先学 Rust 语法再看本书
配套资源
- 代码仓库：GitHub 和 Gitee 均有，按章节分类
- 参考底本：部分内容参考了 Brad Miller 的《Problem Solving with Algorithms and Data Structures Using Python》