Python数据结构与算法分析 (第2版)

📚 Content Summary

本书是使用 Python 阐述数据结构与算法的经典教材。涵盖了 Python 基础复习、算法分析（大 O 记法）、基本数据结构（栈、队列、列表）、递归、搜索与排序、树及图算法。通过实战代码清单，帮助读者理解如何通过 Python 高效地实现各种抽象数据类型。

只有洞彻数据结构与算法，才能真正精通 Python。

Author: 布拉德利·米勒 (美国路德学院计算机科学名誉教授) 、戴维·拉努姆 (IBM Watson认知软件工程师)

Acknowledgments: 感谢同事 Steve Hubbard 为第1版提供的大量反馈以及为新版提供的新素材，同时感谢各地同行发邮件指出错误并提供意见 。感谢迪科拉市 Java John's 咖啡馆的 Mary、Bob 等服务员，允许我们在休假期间成为店里的“常驻作者” 。此外，感谢 Franklin, Beedle & Associates 出版公司的各位员工（特别是 Jim Leisy 和 Tom Sumner）的愉快合作 。最后，特别感谢我们两人的妻子 Jane Miller 和 Brenda Ranum，她们的爱与支持使得本书终成现实 。

🎯 Learning Objectives

1. 理解计算机科学、算法与编程的关系，并掌握抽象数据类型 (ADT) 和信息隐藏的概念。
2. 熟练运用 Python 的内建集合数据类型（列表、元组、集、字典）及控制结构（循环、分支、异常处理）。
3. 掌握 Python 面向对象编程的核心：包括类的定义、构造方法、运算符重载（如分数加法）、欧几里得算法应用，以及深浅相等的区别。
4. 算法多方案对比：能够解释异序词检测的四种方案（清点、排序、暴力、计数）及其对应的时间复杂度。
5. Python 容器性能量化：掌握 Python 列表 (List) 与字典 (Dict) 核心操作的大 O 效率，并能区分 pop() 与 pop(i) 的性能差异。
6. 性能验证能力：能够利用 timeit 模块 design 实验，验证理论复杂度与实际运行时间的一致性。
7. 理解并能区分线性数据结构（栈、队列、双端队列、列表）的逻辑特征。
8. 能够使用 Python 的基础集合（如列表）实现自定义的栈、队列和双端队列。
9. 掌握栈在表达式处理（中序转后序、后序求值）和队列在系统模拟（打印机模拟）中的应用。
10. 掌握递归核心三原则：能够准确识别并编写包含基本情况、状态演变和自调用的递归函数。

🔹 Lesson 1: Python 编程基础与面向对象抽象

Overview: 本课程模块旨在引导学习者从计算机科学的基础理论过渡到 Python 编程实践。课程首先界定计算机科学、算法与抽象数据类型 (ADT) 的核心定义，随后深入讲解 Python 的内建集合、控制结构与异常处理。最终通过构建 Fraction 类与“逻辑门”继承层次结构，展示面向对象编程 (OOP) 在过程抽象与数据抽象中的强大应用。

Learning Outcomes:

• 理解计算机科学、算法与编程的关系，并掌握抽象数据类型 (ADT) 和信息隐藏的概念。
• 熟练运用 Python 的内建集合数据类型（列表、元组、集、字典）及控制结构（循环、分支、异常处理）。
• 掌握 Python 面向对象编程的核心：包括类的定义、构造方法、运算符重载（如分数加法）、欧几里得算法应用，以及深浅相等的区别。

🔹 Lesson 2: 算法分析与 Python 容器性能

Overview: 本课程深入探讨如何通过大 O 记法评估算法效率，并以“异序词检测”为例展示了从 O(n!) 到 O(n) 不同复杂度的演进。同时，课程定量分析了 Python 核心数据结构（列表与字典）的常用操作性能，旨在帮助开发者在实际编程中做出最优的容器选择与算法设计。

Learning Outcomes:

• 算法多方案对比：能够解释异序词检测的四种方案（清点、排序、暴力、计数）及其对应的时间复杂度。
• Python 容器性能量化：掌握 Python 列表 (List) 与字典 (Dict) 核心操作的大 O 效率，并能区分 pop() 与 pop(i) 的性能差异。
• 性能验证能力：能够利用 timeit 模块设计实验，验证理论复杂度与实际运行时间的一致性。

🔹 Lesson 3: 基本线性结构：栈、队列与链表

Overview: 本课程深入探讨四种基础线性数据结构：栈 (Stack)、队列 (Queue)、双端队列 (Deque) 和列表 (List)。线性结构的核心在于项之间保持相对顺序，其主要区别在于添加和移除项的方式。通过 Python 实现这些抽象数据类型 (ADT)，学习者将掌握如何利用 LIFO（后进先出）、FIFO（先进先出）等原则解决实际算法问题，如表达式转换、模拟系统及链表内存管理。

Learning Outcomes:

• 理解并能区分线性数据结构（栈、队列、双端队列、列表）的逻辑特征。
• 能够使用 Python 的基础集合（如列表）实现自定义的栈、队列 and 双端队列。
• 掌握栈在表达式处理（中序转后序、后序求值）和队列在系统模拟（打印机模拟）中的应用。

🔹 Lesson 4: 递归算法原理与动态规划入门

Overview: 本课程深入探讨递归算法的核心原理，从基础的递归三原则出发，通过数值转换、分形几何、经典解谜（汉诺塔与迷宫）等实例，揭示递归调用的底层机制——栈帧。最后，课程引入动态规划 (Dynamic Programming) 的概念，展示如何通过记忆化技术解决递归中的重复计算问题，从而实现算法效率的质变。

Learning Outcomes:

• 掌握递归核心三原则：能够准确识别并编写包含基本情况、状态演变和自调用的递归函数。
• 透析底层执行机制：理解 Python 调用栈 (Stack Frame) 如何在递归过程中管理局部变量和返回路径。
• 具备复杂问题建模能力：能够利用递归和回溯思想解决汉诺塔、迷宫寻路等非线性问题。

🔹 Lesson 5: 搜索技术、散列与排序算法

Overview: 本课程模块聚焦于计算机科学中核心的数据处理技术：搜索、散列 (Hashing) 与排序。内容涵盖从基础的顺序搜索到高效的二分搜索，深入探讨散列表 (Hash Tables) 的构造原理、冲突解决方法及映射 (Map) 抽象数据类型的实现。同时详细剖析冒泡排序、希尔排序与归并排序的算法逻辑与性能表现。

Learning Outcomes:

• 理解并能对比顺序搜索与二分搜索的适用场景及时间复杂度（O(n) vs O(\log n)）。
• 掌握散列函数的设计（折叠法、平方取中法）及冲突处理机制（线性探测、平方探测、链接法）。
• 能够手动模拟并编程实现冒泡排序、希尔排序和归并排序，理解分治策略在排序中的应用。

🔹 Lesson 6: 树结构：二叉堆、搜索树与平衡树 (AVL)

Overview: 本课程深入探讨计算机科学中最核心的数据结构——树。我们将从基础术语和二叉树的实现入手，逐步进阶到二叉树的高级应用，包括表达式解析树及其遍历方法。随后，我们将学习两种高效的变体：用于优先级队列的二叉堆以及用于高效搜索的二叉搜索树 (BST)。最后，我们将研究 AVL 树，通过旋转操作维护平衡因子，解决 BST 在最坏情况下的性能退化问题。

Learning Outcomes:

• 能够准确定义树的核心术语（根、边、路径、高度等）并描述二叉树的递归性质。
• 掌握使用 Python 实现二叉堆、二叉搜索树及 AVL 树的核心算法（如插入、删除、旋转、再平衡）。
• 能够执行并解释三种树遍历算法，并利用解析树处理数学表达式。

🔹 Lesson 7: 图论算法：搜索、最短路径与最小生成树

Overview: 本课程深入探讨图论的基础理论及其在 Python 中的高效实现。内容涵盖图的抽象数据类型（邻接矩阵与邻接表）、基础搜索算法（BFS 与 DFS）及其经典应用场景。最终进阶到加权图中的最短路径 (Dijkstra) 与最小生成树 (Prim) 算法。

Learning Outcomes:

• 理解并能对比图的两种主要表示法（邻接矩阵与邻接表）的性能与适用场景。
• 掌握宽度优先搜索 (BFS) 与深度优先搜索 (DFS) 的算法原理，并能解决路径搜索与周游问题。
• 能够应用图算法解决复杂逻辑依赖（拓扑排序）及网络连通性（强连通单元、最小生成树）问题。

🔹 Lesson 8: 专题复习：RSA 加密、跳表与八叉树量化

Overview: 本课程深入探讨了计算机科学中从基础数据结构到复杂算法的应用迁移。内容涵盖了 Python 列表 (ArrayList) 的底层实现与均摊分析、支持 RSA 加密的数论递归算法、提升字典搜索效率的跳表构建，以及利用八叉树进行数字图像颜色量化的原理。

Learning Outcomes:

• 理解 ArrayList 的内存布局及均摊分析 (Amortized Analysis) 的数学推导。
• 掌握 RSA 加密的核心数学原理，包括同余定理、幂剩余及扩展欧几里得算法。
• 能够描述跳表的层级结构、概率性构建过程及其 O(\log n) 的搜索效率。