通过python解决算法和数据结构问题

Problem Solving with Algorithms and Data Structures using Python

中文英文

由Brad Miller和David Ranum撰写，来自Luther College

作业

Gerry Jenkins录制了一系列精彩的YouTube视频，支持本书中所有章节的学习。

By Brad Miller and David Ranum, Luther College

• Assignments

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

1. 引言

1.Introduction

中文英文

• 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. 练习

• 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. 算法分析

2. Algorithm Analysis

中文英文

• 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. 练习

• 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. 基本数据结构

3. Basic Data Structures

中文英文

• 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. 练习

• 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. 递归

4. Recursion

中文英文

• 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. 练习

• 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. 搜索与排序

5. Searching and Sorting

中文英文

• 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. 练习

• 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. 树和树算法

中文英文

• 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. 练习

• 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. 图和图算法

7. Graphs and Graphing Algorithms

中文英文

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. 练习

• 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. 高级主题

8. Advanced Topics

中文英文

• 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. Map抽象数据类型
  • 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算法

• 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

致谢

Acknowledgements

中文英文

我们非常感谢Franklin Beedle Publishers允许我们免费提供这本互动教材的在线版本。这个版本献给我们的第一位编辑Jim Leisy，他希望我们“改变世界”。

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.”

---

最后更新: 2024年9月10日
创建日期: 2024年9月9日