问题求解：算法与数据结构
（Python 版）
目录
一. 引言 ........................................................................................................................................... 10
1.1. 目标 .................................................................................................................................................. 10
1.2. 开始学习 .......................................................................................................................................... 10
1.3. 计算机科学是什么 .......................................................................................................................... 10
1.4. 什么是程序设计 .............................................................................................................................. 11
1.5. 为何要学习数据结构和抽象数据类型 .......................................................................................... 12
1.6. 为何要学习算法 .............................................................................................................................. 13
1.7. Python 入门 ..................................................................................................................................... 13
1.7.1. 从数据开始 ................................................................................................................... 13
1.7.2 输入与输出 .................................................................................................................... 27
1.7.3 控制结构 .................................................................................................................... 31
1.7.4 异常处理 ........................................................................................................................ 35
1.7.5 定义函数 ........................................................................................................................ 37
1.7.6．Python 面向对象编程：定义类 ................................................................................. 38
小结 .......................................................................................................................................................... 54
关键词 ...................................................................................................................................................... 54
问题讨论 .................................................................................................................................................. 54
编程练习 .................................................................................................................................................. 55
二．算法分析 .................................................................................................................................. 56
2.2.什么是算法分析 ................................................................................................................................ 56
2.2.1. 大“O”表示法 ............................................................................................................. 60
2.2.2 变位词检测 ..................................................................................................................... 63
2.3 Python 数据结构的性能 .................................................................................................................. 69
2.3.1 列表 List ......................................................................................................................... 69
2.3.2 字典 ................................................................................................................................. 73
2.4 小结 .................................................................................................................................................... 76
2.5 关键字 ................................................................................................................................................ 76
2.6 问题讨论 ............................................................................................................................................ 76
三．基本数据结构类型 .................................................................................................................. 78
3.1 学习目标 ........................................................................................................................................... 78
3.2 什么是线性结构？ ........................................................................................................................... 78
3.3 栈 ........................................................................................................................................................ 78
3.3.1 什么是栈？ .................................................................................................................... 78
3.4 栈的抽象数据类型 ............................................................................................................................ 80
3.4．队列 ................................................................................................................................................. 80
3.4.1．什么是队列 .................................................................................................................. 80
3.4.2.抽象数据类型 Queue（队列） ...................................................................................... 81
3.4.3.在 Python 中实现 Queue ............................................................................................... 82
3.4.4. 模拟算法：热土豆 ....................................................................................................... 84
3.4.5. 模拟算法：打印任务 ................................................................................................... 86
3.4.6. 主要模拟步骤 ............................................................................................................... 88
3.4.7 Python 实现 ..................................................................................................................... 88
3.4.8. 讨论 ............................................................................................................................... 96
3.5.双端队列 ............................................................................................................................................ 97
3.5.1. 什么是双端队列 ........................................................................................................... 97
3.5.2. 抽象数据类型 ............................................................................................................... 97
3.5.3 在 Python 中实现双端队列 Deque .............................................................................. 98
3.5.4 “回文词”判定 ............................................................................................................ 99
3.6 列表 List .......................................................................................................................................... 101
3.6.1. 抽象数据类型无序列表 UnorderedList ..................................................................... 101
3.6.2.采用链表实现无序列表 ............................................................................................... 102
3.6.3 抽象数据类型：有序列表 .......................................................................................... 111
3.6.4. 实现有序列表 ............................................................................................................. 112
3.6.5. 链表实现算法分析 ...................................................................................................... 114
3.7.小结 .................................................................................................................................................. 115
3.8.关键词（按：依英文原词的词典顺序排列） .............................................................................. 115
3.9.问题讨论 .......................................................................................................................................... 116
4.递归 Recursion ............................................................................................................................ 119
4.1 目标 .................................................................................................................................................. 119
4.2 什么是递归 ..................................................................................................................................... 119
4.2.1 计算数字列表的和 ...................................................................................................... 119
4.2.2 递归三大定律 .............................................................................................................. 122
4.2.3.将整数转化成任意进制表示的字符串形式 ............................................................... 123
4.3 栈帧：实现递归 ............................................................................................................. 125
4.4. 图示递归 ........................................................................................................................................ 127
4.4.1. 谢尔宾斯基三角形 ..................................................................................................... 132
4.5.复杂递归问题 .................................................................................................................................. 135
4.5.1.河内塔问题 ................................................................................................................... 135
4.6.探索迷宫 .......................................................................................................................................... 137
4.7 动态规划 .......................................................................................................................................... 148
4.8 小结 .................................................................................................................................................. 154
4.9 关键词 .............................................................................................................................................. 154
4.10 问题讨论 ........................................................................................................................................ 154
4.11 词汇表 ............................................................................................................................................ 155
编程练习 ................................................................................................................................................ 156
5. 排序与搜索 ............................................................................................................................... 158
5.1.目标 .................................................................................................................................................. 158
5.2.搜索 .................................................................................................................................................. 158
5.2.1.顺序搜索 ....................................................................................................................... 158
5.2.2.二分法搜索 ................................................................................................................... 161
5.2.3. 散列 ............................................................................................................................. 164
5.3.排序 .................................................................................................................................................. 175
5.3.1.冒泡排序 ....................................................................................................................... 175
5.3.2.选择排序 ....................................................................................................................... 178
5.3.3.插入排序 ....................................................................................................................... 179
5.3.4. 希尔排序 .................................................................................................................................. 182
5.3.5.归并排序 .................................................................................................................................... 185
5.3.6.快速排序 .................................................................................................................................... 186
5.4.小结 .................................................................................................................................................. 187
5.5 关键词 ............................................................................................................................................ 188
5.6.问题讨论 .......................................................................................................................................... 188
5.7.编程练习 ........................................................................................................................................ 189
6.树和树算法 ................................................................................................................................. 191
6.1.目标 .................................................................................................................................................. 191
6.2.树的例子 .......................................................................................................................................... 191
6.3.术语表和定义 .................................................................................................................................. 193
6.4.通过嵌套列表实现树 ...................................................................................................................... 195
6.5.节点和引用 ...................................................................................................................................... 199
6.6 解析树 ......................................................................................................................................... 203
6.7 树 的 遍 历 ..................................................................................................................................... 210
6.8 二叉堆 BINARY HEAP 实 现 的 优 先 队 列 ......................................................................... 213
6.8.1 二叉堆操作 ................................................................................................................... 213
6.8.2 二叉堆实现 ................................................................................................................... 214
6.9 二叉搜索树 ...................................................................................................................................... 222
6.9.1 搜索树操作 .................................................................................................................. 222
6.9.2 搜索树实现 ................................................................................................................... 223
6.9.3 搜索树分析 .................................................................................................................. 243
6.10 平衡二叉搜索树 ........................................................................................................................... 244
6.10.1 AVL 树性能 ............................................................................................................... 245
6.10.2 AVL 树实现 .............................................................................................................. 247
6.11 ADT Map 实现小结 ................................................................................................................... 254
6.12 小结 ............................................................................................................................................... 255
6.13 关键词 ........................................................................................................................................... 255
6.14 问题讨论 ....................................................................................................................................... 255
6.15 小试牛刀 ....................................................................................................................................... 257
7. 图和图算法 ............................................................................................................................... 259
7.1. 目标 ................................................................................................................................................ 259
7.2. 词汇表及定义 ................................................................................................................................ 259
7.3. 图抽象数据类型 ............................................................................................................................ 260
7.4. 邻接矩阵 ........................................................................................................................................ 261
7.5. 邻接表 ............................................................................................................................................ 261
7.6.实现 .................................................................................................................................................. 262
7.7. Word Ladder 词梯问题 ............................................................................................................... 264
7.7.1. 建立 Word Ladder 图............................................................................................. 265
7.7.2. 实现广度优先搜索(BFS) ........................................................................................ 267
7.7.3. 广度优先搜索（BFS）的分析 ................................................................................. 270
7.8. 骑士周游问题 .............................................................................................................................. 271
