python解决数据结构和算法.pdf

【实例简介】

假设我们的有序列表中已有：17，26，54，77 和 93，我们想添加值 31，则 add 方法必须在 26 和 54 之间添加这个新的节点。图 17 显示了具体做法。正如前面解释的，我们需要遍历链表来寻找 添加新节点的位置。遍历时，当我们遍历完了整个列或者当前节点的值大于我们要添加的值时，我 们就找到了添加新节点的位置。在我们的例子中，找到了值 54 就停止遍历。 

【实例截图】

【目录】

问题求解：算法与数据结构
（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
7.8.1. 建立骑士周游图 ......................................................................................................271
7.8.2. 实现骑士周游 ..........................................................................................................274
7.8.3．骑士周游分析 ..........................................................................................................278
7.8.4. 通用深度优先搜索 ..................................................................................................280
7.9 拓扑排序..........................................................................................................................................285
7.10 强连通分支....................................................................................................................................286
7.11 最短路径问题................................................................................................................................289
7.11.1.Dijkstra 算法 ..........................................................................................................291
7.11.2.Dijkstra算法分析 ...................................................................................................296
7.12.Prim 最小生成树算法...................................................................................................................296
7.13. 小结............................................................................................................................................302
7.14 ．关键词.......................................................................................................................................302
7.15 问题讨论.......................................................................................................................................303
7.16 编程练习.......................................................................................................................................303

【核心代码】

def add(self, item):
 current = self.head
 previous = None
 stop = False
 while current != None and not stop:
 if current.get_data() > item:
 stop = True
 else:
 previous = current
 current = current.get_next()
 temp = Node(item)
 if previous == None:
 temp.set_next(self.head)
 self.head = temp
 else:
 temp.set_next(current)
 previous.set_next(temp)