Python数据结构与算法分析 (第2版)
本书是使用Python阐述数据结构与算法的经典教材。涵盖了Python基础复习、算法分析（大O记法）、基本数据结构（栈、队列、列表）、递归、搜索与排序、树及图算法。通过实战代码清单，帮助读者理解如何通过Python高效地实现各种抽象数据类型。
课程概述
📚 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
- 理解计算机科学、算法与编程的关系，并掌握抽象数据类型 (ADT) 和信息隐藏的概念。
- 熟练运用 Python 的内建集合数据类型（列表、元组、集、字典）及控制结构（循环、分支、异常处理）。
- 掌握 Python 面向对象编程的核心：包括类的定义、构造方法、运算符重载（如分数加法）、欧几里得算法应用，以及深浅相等的区别。
- 算法多方案对比：能够解释异序词检测的四种方案（清点、排序、暴力、计数）及其对应的时间复杂度。
- Python 容器性能量化：掌握 Python 列表 (List) 与字典 (Dict) 核心操作的大 O 效率，并能区分
pop()与pop(i)的性能差异。 - 性能验证能力：能够利用
timeit模块 design 实验，验证理论复杂度与实际运行时间的一致性。 - 理解并能区分线性数据结构（栈、队列、双端队列、列表）的逻辑特征。
- 能够使用 Python 的基础集合（如列表）实现自定义的栈、队列和双端队列。
- 掌握栈在表达式处理（中序转后序、后序求值）和队列在系统模拟（打印机模拟）中的应用。
- 掌握递归核心三原则：能够准确识别并编写包含基本情况、状态演变和自调用的递归函数。
课程 共 8 课时 · 预计 24.0h
课程
Lesson
This lesson introduces the core principles of computer science, focusing on problem-solving through algorithms, procedural abstraction, and Python’s object-oriented nature. Students will learn to manage complexity by leveraging Python’s dynamic variable references, efficient built-in data structures, and robust error-handling techniques to build reliable, scalable software.
本课程深入探讨了算法分析的核心工具——大O记法，通过异序词检测案例展示了从暴力法到计数法的性能优化过程。学习重点在于理解不同操作（如列表索引与pop操作）的复杂度差异，并掌握如何通过空间换时间及选择合适的数据结构来提升程序效率。
This lesson introduces linear data structures and the concept of Abstract Data Types (ADTs), focusing on the stack as a fundamental LIFO (Last-In, First-Out) structure. Students will learn to implement stacks in Python and apply them to complex tasks, including converting infix expressions to postfix notation and evaluating those expressions efficiently.
本课程深入探讨了递归算法的核心原理，重点讲解了递归三原则（基准情况、状态改变、自我调用）以及递归与系统调用栈之间的内在联系。通过进制转换、汉诺塔及动态规划等案例，学生将学习如何将复杂问题拆解为自相似的子问题，并掌握从递归思维向高效动态规划算法的进阶转换。
This lesson explores fundamental search and retrieval algorithms, progressing from $O(n)$ sequential search to the $O(\log n)$ efficiency of binary search and the $O(1)$ potential of hash tables. Students learn to optimize data access through divide-and-conquer strategies, sophisticated hash function design, and collision-handling techniques to build efficient, dictionary-like data structures.
This lesson explores the hierarchical and recursive nature of tree data structures, covering fundamental terminology, implementation methods like nested lists and object-oriented references, and the construction of expression trees. It also introduces essential tree traversal algorithms—preorder, inorder, and postorder—and explains how these recursive patterns are applied to tasks like file system analysis and AVL tree balancing.
This lesson introduces graph theory as a powerful tool for modeling real-world problems by abstracting entities as vertices and relationships as edges. Students will learn to implement graphs using adjacency lists, compare storage efficiency, and master the Breadth-First Search (BFS) algorithm to solve pathfinding and state-space challenges.
This lesson explores the memory efficiency of Python's ArrayList, explaining how amortized analysis ensures $O(1)$ performance for append operations through strategic over-allocation. It also covers the mathematical foundations of RSA encryption, demonstrating how modular exponentiation and divide-and-conquer algorithms optimize complex calculations for secure data processing.