使用 Python 解决算法和数据结构问题

参考原文: https://runestone.academy/ns/books/published/pythonds3/index.html?mode=browsing#

中文英文

Gerry Jenkins 录制了精彩的 YouTube 视频集，以支持本文中的所有章节。

1. 简介
   • 1.1. 目标
   • 1.2. 入门
   • 1.3. 什么是计算机科学?
   • 1.4. 什么是编程?
   • 1.5. 为什么要研究数据结构和抽象数据类型?
   • 1.6. 为什么要研究算法?
   • 1.7. 回顾Python基础
   • 1.8. 数据入门
     • 1.8.1. 内置原子数据类型
     • 1.8.2. 内置集合数据类型
   • 1.9. 输入和输出
     • 1.9.1. 字符串格式化
   • 1.10. 结构控制
   • 1.11. 异常处理
   • 1.12. 定义函数
   • 1.13. Python 中的面向对象编程：定义类
     • 1.13.1. 一个分数类
     • 1.13.2. 继承：逻辑门和电路
   • 1.14. 总结
   • 1.15. 关键术语
   • 1.16. 练习
2. 算法分析
   • 2.1. 目标
   • 2.2. 什么是算法分析?
   • 2.3. 大 O 表示法
   • 2.4. 字谜检测示例
     • 2.4.1. 解决方案 1：核对字谜检测
     • 2.4.2. 字谜检测解决方案2：排序和比较
     • 2.4.3. 字谜检测解决方案3：暴力破解
     • 2.4.4. 字谜检测解决方案 4：计数和比较
   • 2.5. Python数据结构的性能
   • 2.6. 列表
   • 2.7. 字典
   • 2.8. 总结
   • 2.9. 关键术语
   • 2.10. 练习
3. 数据结构基础
   • 3.1. 目标
   • 3.2. 什么是线性结构?
   • 3.3. 堆栈
   • 3.4. 堆栈抽象数据类型
   • 3.5. 在 Python 中实现堆栈
   • 3.6. 简单平衡括号
   • 3.7. 平衡符号（一般情况）
   • 3.8. 将十进制数转换为二进制数
   • 3.9. 中缀、前缀和后缀表达式
     • 3.9.1. 中缀表达式到前缀和后缀的转换
     • 3.9.2. 通用中缀到后缀转换
     • 3.9.3. 后缀评估
   • 3.10. 队列
   • 3.11. 队列抽象数据类型
   • 3.12. 在 Python 中实现队列
   • 3.13. 队列模拟：烫手山芋
   • 3.14. 队列模拟：打印任务
     • 3.14.1. 主要模拟步骤
     • 3.14.2. Python实现
     • 3.14.3. 讨论
   • 3.15. 双端队列
   • 3.16. 双端队列抽象数据类型
   • 3.17. 在 Python 中实现双端队列
   • 3.18. 回文检查器
   • 3.19. 列表
   • 3.20. 无序列表抽象数据类型
   • 3.21. 实现无序列表：链接列表
     • 3.21.1. 节点类
     • 3.21.2. 无序列表类
   • 3.22. 有序列表抽象数据类型
   • 3.23. 实现有序列表
     • 3.23.1. 链表分析
   • 3.24. 总结
   • 3.25. 关键术语
   • 3.26. 练习
4. 递归
   • 4.1. 目标
   • 4.2. 什么是递归?
   • 4.3. 计算数字列表的总和
   • 4.4. 递归三定律
   • 4.5. 将整数转换为任何基数的字符串
   • 4.6. 堆栈帧：实现递归
   • 4.7. 可视化递归
   • 4.8. 谢尔宾斯基三角
   • 4.9. 复杂的递归问题
   • 4.10. 河内塔
   • 4.11. 探索迷宫
   • 4.12. 动态规划
   • 4.13. 总结
   • 4.14. 关键术语
   • 4.15. 练习
5. 搜索和排序
   • 5.1. 目标
   • 5.2. 搜寻中
   • 5.3. 顺序搜索
     • 5.3.1. 顺序搜索分析
   • 5.4. 二分查找
     • 5.4.1. 二分查找分析
   • 5.5. 哈希
     • 5.5.1. 哈希函数
     • 5.5.2. 碰撞解决
     • 5.5.3. 实现Map抽象数据类型
     • 5.5.4. 哈希分析
   • 5.6. 排序
   • 5.7. 冒泡排序
   • 5.8. 选择排序
   • 5.9. 插入排序
   • 5.10. 希尔排序
   • 5.11. 归并排序
   • 5.12. 快速排序
   • 5.13. 总结
   • 5.14. 关键术语
   • 5.15. 练习
6. 树和树算法
   • 6.1. 目标
   • 6.2. 树的例子
   • 6.3. 词汇和定义
   • 6.4. 实现
   • 6.5. 基于列表的列表表示法
   • 6.6. 节点和参考
   • 6.7. 解析树
   • 6.8. 树遍历
   • 6.9. 基于二进制堆的优先级队列
   • 6.10. 二进制堆的操作
   • 6.11. 二进制堆的实现
     • 6.11.1. 结构性质
     • 6.11.2. 堆顺序属性
     • 6.11.3. 堆操作
   • 6.12. 二叉搜索树
   • 6.13. 搜索树的操作
   • 6.14. 搜索树的实现
   • 6.15. 搜索树的分析
   • 6.16. 平衡二叉搜索树
   • 6.17. AVL 树性能
   • 6.18. AVL树的实现
   • 6.19. Map ADT 的实现总结
   • 6.20. 总结
   • 6.21. 关键术语
   • 6.22. 练习
7. 图形和图形算法
   • 7.1. 目标
   • 7.2. 词汇和定义
   • 7.3. 图抽象数据类型
   • 7.4. 邻接矩阵
   • 7.5. 邻接表
   • 7.6. 实现
   • 7.7. 字梯问题
   • 7.8. 构建字梯图
   • 7.9. 实施广度优先搜索
   • 7.10. 广度优先搜索分析
   • 7.11. 骑士之旅问题
   • 7.12. 构建骑士之旅图
   • 7.13. 实现骑士之旅
   • 7.14. 骑士之旅分析
   • 7.15. 一般深度优先搜索
   • 7.16. 深度优先搜索分析
   • 7.17. 拓扑排序
   • 7.18. 强连通分量
   • 7.19. 最短路径问题
   • 7.20. Dijkstra 算法
   • 7.21. Dijkstra算法分析
   • 7.22. Prim 的生成树算法
   • 7.23. 总结
   • 7.24. 关键术语
   • 7.25. 练习
8. 高级主题
   • 8.1. 目标
   • 8.2. 重温 Python 列表
   • 8.3. 重温递归
     • 8.3.1. 模算术定理
     • 8.3.2. 模幂
     • 8.3.3. 最大公约数和乘法逆元
     • 8.3.4. RSA算法
   • 8.4. 重温词典：跳过列表
     • 8.4.1. 地图抽象数据类型
     • 8.4.2. 用 Python 实现字典
   • 8.5. 重温树：量化图像
     • 8.5.1. 数字图像快速回顾
     • 8.5.2. 量化图像
     • 8.5.3. 一种改进的八叉树量化算法
   • 8.6. 重温图表：模式匹配
     • 8.6.1. 生物弦
     • 8.6.2. 简单比较
     • 8.6.3. 使用图：有限状态自动机
     • 8.6.4. 使用图表：Knuth-Morris-Pratt

Problem Solving with Algorithms and Data Structures using Python

There is a wonderful collection of YouTube videos recorded by Gerry Jenkins to support all of the chapters in this text.

1. Introduction
   • 1.1. Objectives
   • 1.2. Getting Started
   • 1.3. What Is Computer Science?
   • 1.4. What Is Programming?
   • 1.5. Why Study Data Structures and Abstract Data Types?
   • 1.6. Why Study Algorithms?
   • 1.7. Review of Basic Python
   • 1.8. Getting Started with Data
     • 1.8.1. Built-in Atomic Data Types
     • 1.8.2. Built-in Collection Data Types
   • 1.9. Input and Output
     • 1.9.1. String Formatting
   • 1.10. Control Structures
   • 1.11. Exception Handling
   • 1.12. Defining Functions
   • 1.13. Object-Oriented Programming in Python: Defining Classes
     • 1.13.1. A Fraction Class
     • 1.13.2. Inheritance: Logic Gates and Circuits
   • 1.14. Summary
   • 1.15. Key Terms
   • 1.16. Exercises
2. Algorithm Analysis
   • 2.1. Objectives
   • 2.2. What Is Algorithm Analysis?
   • 2.3. Big O Notation
   • 2.4. An Anagram Detection Example
     • 2.4.1. Solution 1: Anagram Detection Checking Off
     • 2.4.2. Anagram Detection Solution 2: Sort and Compare
     • 2.4.3. Anagram Detection Solution 3: Brute Force
     • 2.4.4. Anagram Detection Solution 4: Count and Compare
   • 2.5. Performance of Python Data Structures
   • 2.6. Lists
   • 2.7. Dictionaries
   • 2.8. Summary
   • 2.9. Key Terms
   • 2.10. Exercises
3. Basic Data Structures
   • 3.1. Objectives
   • 3.2. What Are Linear Structures?
   • 3.3. Stacks
   • 3.4. The Stack Abstract Data Type
   • 3.5. Implementing a Stack in Python
   • 3.6. Simple Balanced Parentheses
   • 3.7. Balanced Symbols (A General Case)
   • 3.8. Converting Decimal Numbers to Binary Numbers
   • 3.9. Infix, Prefix, and Postfix Expressions
     • 3.9.1. Conversion of Infix Expressions to Prefix and Postfix
     • 3.9.2. General Infix-to-Postfix Conversion
     • 3.9.3. Postfix Evaluation
   • 3.10. Queues
   • 3.11. The Queue Abstract Data Type
   • 3.12. Implementing a Queue in Python
   • 3.13. Queue Simulation: Hot Potato
   • 3.14. Queue Simulation: Printing Tasks
     • 3.14.1. Main Simulation Steps
     • 3.14.2. Python Implementation
     • 3.14.3. Discussion
   • 3.15. Deques
   • 3.16. The Deque Abstract Data Type
   • 3.17. Implementing a Deque in Python
   • 3.18. Palindrome Checker
   • 3.19. Lists
   • 3.20. The Unordered List Abstract Data Type
   • 3.21. Implementing an Unordered List: Linked Lists
     • 3.21.1. The Node Class
     • 3.21.2. The UnorderedList Class
   • 3.22. The Ordered List Abstract Data Type
   • 3.23. Implementing an Ordered List
     • 3.23.1. Analysis of Linked Lists
   • 3.24. Summary
   • 3.25. Key Terms
   • 3.26. Exercises
4. Recursion
   • 4.1. Objectives
   • 4.2. What Is Recursion?
   • 4.3. Calculating the Sum of a List of Numbers
   • 4.4. The Three Laws of Recursion
   • 4.5. Converting an Integer to a String in Any Base
   • 4.6. Stack Frames: Implementing Recursion
   • 4.7. Visualizing Recursion
   • 4.8. Sierpinski Triangle
   • 4.9. Complex Recursive Problems
   • 4.10. Tower of Hanoi
   • 4.11. Exploring a Maze
   • 4.12. Dynamic Programming
   • 4.13. Summary
   • 4.14. Key Terms
   • 4.15. Exercises
5. Searching and Sorting
   • 5.1. Objectives
   • 5.2. Searching
   • 5.3. The Sequential Search
     • 5.3.1. Analysis of Sequential Search
   • 5.4. The Binary Search
     • 5.4.1. Analysis of Binary Search
   • 5.5. Hashing
     • 5.5.1. Hash Functions
     • 5.5.2. Collision Resolution
     • 5.5.3. Implementing the Map Abstract Data Type
     • 5.5.4. Analysis of Hashing
   • 5.6. Sorting
   • 5.7. The Bubble Sort
   • 5.8. The Selection Sort
   • 5.9. The Insertion Sort
   • 5.10. The Shell Sort
   • 5.11. The Merge Sort
   • 5.12. The Quicksort
   • 5.13. Summary
   • 5.14. Key Terms
   • 5.15. Exercises
6. Trees and Tree Algorithms
   • 6.1. Objectives
   • 6.2. Examples of Trees
   • 6.3. Vocabulary and Definitions
   • 6.4. Implementation
   • 6.5. List of Lists Representation
   • 6.6. Nodes and References
   • 6.7. Parse Tree
   • 6.8. Tree Traversals
   • 6.9. Priority Queues with Binary Heaps
   • 6.10. Binary Heap Operations
   • 6.11. Binary Heap Implementation
     • 6.11.1. The Structure Property
     • 6.11.2. The Heap Order Property
     • 6.11.3. Heap Operations
   • 6.12. Binary Search Trees
   • 6.13. Search Tree Operations
   • 6.14. Search Tree Implementation
   • 6.15. Search Tree Analysis
   • 6.16. Balanced Binary Search Trees
   • 6.17. AVL Tree Performance
   • 6.18. AVL Tree Implementation
   • 6.19. Summary of Map ADT Implementations
   • 6.20. Summary
   • 6.21. Key Terms
   • 6.22. Exercises
7. Graphs and Graphing Algorithms
   • 7.1. Objectives
   • 7.2. Vocabulary and Definitions
   • 7.3. The Graph Abstract Data Type
   • 7.4. An Adjacency Matrix
   • 7.5. An Adjacency List
   • 7.6. Implementation
   • 7.7. The Word Ladder Problem
   • 7.8. Building the Word Ladder Graph
   • 7.9. Implementing Breadth-First Search
   • 7.10. Breadth-First Search Analysis
   • 7.11. The Knight’s Tour Problem
   • 7.12. Building the Knight’s Tour Graph
   • 7.13. Implementing Knight’s Tour
   • 7.14. Knight’s Tour Analysis
   • 7.15. General Depth-First Search
   • 7.16. Depth-First Search Analysis
   • 7.17. Topological Sorting
   • 7.18. Strongly Connected Components
   • 7.19. Shortest Path Problems
   • 7.20. Dijkstra’s Algorithm
   • 7.21. Analysis of Dijkstra’s Algorithm
   • 7.22. Prim’s Spanning Tree Algorithm
   • 7.23. Summary
   • 7.24. Key Terms
   • 7.25. Exercises
8. Advanced Topics
   • 8.1. Objectives
   • 8.2. Python Lists Revisited
   • 8.3. Recursion Revisited
     • 8.3.1. Modular Arithmetic Theorems
     • 8.3.2. Modular Exponentiation
     • 8.3.3. The Greatest Common Divisor and Multiplicative Inverses
     • 8.3.4. RSA Algorithm
   • 8.4. Dictionaries Revisited: Skip Lists
     • 8.4.1. The Map Abstract Data Type
     • 8.4.2. Implementing a Dictionary in Python
   • 8.5. Trees Revisited: Quantizing Images
     • 8.5.1. A Quick Review of Digital Images
     • 8.5.2. Quantizing an Image
     • 8.5.3. An Improved Quantization Algorithm Using Octrees
   • 8.6. Graphs Revisited: Pattern Matching
     • 8.6.1. Biological Strings
     • 8.6.2. Simple Comparison
     • 8.6.3. Using Graphs: Finite State Automata
     • 8.6.4. Using Graphs: Knuth-Morris-Pratt

致谢

中文英文

我们非常感谢 Franklin Beedle 出版社允许我们免费提供这本互动教科书。 这个在线版本是为了纪念我们的第一位编辑 Jim Leisy，他希望我们“改变世界”。

Acknowledgements

We are very grateful to Franklin Beedle Publishers for allowing us to make this interactive textbook freely available. This online version is dedicated to the memory of our first editor, Jim Leisy, who wanted us to “change the world.”

---

最后更新: 2023年10月15日
创建日期: 2023年10月10日