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

假设我们的有序列表中已有：17，26，54，77 和 93，我们想添加值 31，则 add 方法必须在 26和 54 之间添加这个新的节点。图 17 显示了具体做法。正如前面解释的，我们需要遍历链表来寻找添加新节点的位置。遍历时，当我们遍历完了整个列或者当前节点的值大于我们要添加的值时，我们就找到了添加新节点的位置。在我们的例子中，找到了值 54 就停止遍历。 
【目录】
问题求解：算法与数据结构（Python 版）目录一. 引言 ...........................................................................................................................................101.1. 目标..................................................................................................................................................101.2. 开始学习..........................................................................................................................................101.3. 计算机科学是什么 ..........................................................................................................................101.4. 什么是程序设计 ..............................................................................................................................111.5. 为何要学习数据结构和抽象数据类型 ..........................................................................................121.6. 为何要学习算法 ..............................................................................................................................131.7. Python 入门 .....................................................................................................................................131.7.1. 从数据开始 ...................................................................................................................131.7.2 输入与输出 ....................................................................................................................271.7.3 控制结构 ....................................................................................................................311.7.4 异常处理 ........................................................................................................................351.7.5 定义函数 ........................................................................................................................371.7.6．Python 面向对象编程：定义类.................................................................................38小结..........................................................................................................................................................54关键词......................................................................................................................................................54问题讨论..................................................................................................................................................54编程练习..................................................................................................................................................55二．算法分析 ..................................................................................................................................562.2.什么是算法分析................................................................................................................................562.2.1. 大“O”表示法.............................................................................................................602.2.2 变位词检测 .....................................................................................................................632.3 Python 数据结构的性能 ..................................................................................................................692.3.1 列表 List.........................................................................................................................692.3.2 字典 .................................................................................................................................732.4 小结....................................................................................................................................................762.5 关键字................................................................................................................................................762.6 问题讨论............................................................................................................................................76三．基本数据结构类型 ..................................................................................................................783.1 学习目标...........................................................................................................................................783.2 什么是线性结构？...........................................................................................................................783.3 栈........................................................................................................................................................783.3.1 什么是栈？ ....................................................................................................................783.4 栈的抽象数据类型............................................................................................................................803.4．队列.................................................................................................................................................803.4.1．什么是队列 ..................................................................................................................803.4.2.抽象数据类型 Queue（队列）......................................................................................813.4.3.在 Python 中实现 Queue...............................................................................................823.4.4. 模拟算法：热土豆 .......................................................................................................843.4.5. 模拟算法：打印任务 ...................................................................................................863.4.6. 主要模拟步骤 ...............................................................................................................883.4.7 Python 实现.....................................................................................................................883.4.8. 讨论 ...............................................................................................................................963.5.双端队列............................................................................................................................................973.5.1. 什么是双端队列 ...........................................................................................................973.5.2. 抽象数据类型 ...............................................................................................................973.5.3 在 Python 中实现双端队列 Deque ..............................................................................983.5.4 “回文词”判定 ............................................................................................................993.6 列表 List ..........................................................................................................................................1013.6.1. 抽象数据类型无序列表 UnorderedList .....................................................................1013.6.2.采用链表实现无序列表 ...............................................................................................1023.6.3 抽象数据类型：有序列表 ..........................................................................................1113.6.4. 实现有序列表 .............................................................................................................1123.6.5. 链表实现算法分析......................................................................................................1143.7.小结..................................................................................................................................................1153.8.关键词（按：依英文原词的词典顺序排列） ..............................................................................1153.9.问题讨论..........................................................................................................................................1164.递归 Recursion ............................................................................................................................1194.1 目标..................................................................................................................................................1194.2 什么是递归.....................................................................................................................................1194.2.1 计算数字列表的和 ......................................................................................................1194.2.2 递归三大定律 ..............................................................................................................1224.2.3.将整数转化成任意进制表示的字符串形式 ...............................................................1234.3 栈帧：实现递归 .............................................................................................................1254.4. 图示递归........................................................................................................................................1274.4.1. 谢尔宾斯基三角形 .....................................................................................................1324.5.复杂递归问题..................................................................................................................................1354.5.1.河内塔问题 ...................................................................................................................1354.6.探索迷宫..........................................................................................................................................1374.7 动态规划..........................................................................................................................................1484.8 小结..................................................................................................................................................1544.9 关键词..............................................................................................................................................1544.10 问题讨论........................................................................................................................................1544.11 词汇表............................................................................................................................................155编程练习................................................................................................................................................1565. 排序与搜索 ...............................................................................................................................1585.1.目标..................................................................................................................................................1585.2.搜索..................................................................................................................................................1585.2.1.顺序搜索 .......................................................................................................................1585.2.2.二分法搜索 ...................................................................................................................1615.2.3. 散列 .............................................................................................................................1645.3.排序..................................................................................................................................................1755.3.1.冒泡排序 .......................................................................................................................1755.3.2.选择排序 .......................................................................................................................1785.3.3.插入排序 .......................................................................................................................1795.3.4. 希尔排序..................................................................................................................................1825.3.5.归并排序....................................................................................................................................1855.3.6.快速排序....................................................................................................................................1865.4.小结..................................................................................................................................................1875.5 关键词............................................................................................................................................1885.6.问题讨论..........................................................................................................................................1885.7.编程练习........................................................................................................................................1896.树和树算法 .................................................................................................................................1916.1.目标..................................................................................................................................................1916.2.树的例子..........................................................................................................................................1916.3.术语表和定义..................................................................................................................................1936.4.通过嵌套列表实现树......................................................................................................................1956.5.节点和引用......................................................................................................................................1996.6 解析树 .........................................................................................................................................2036.7 树的遍历 .....................................................................................................................................2106.8 二叉堆 BINARY HEAP 实现的优先队列 .........................................................................2136.8.1 二叉堆操作 ...................................................................................................................2136.8.2 二叉堆实现 ...................................................................................................................2146.9 二叉搜索树......................................................................................................................................2226.9.1 搜索树操作 ..................................................................................................................2226.9.2 搜索树实现 ...................................................................................................................2236.9.3 搜索树分析 ..................................................................................................................2436.10 平衡二叉搜索树...........................................................................................................................2446.10.1 AVL 树性能...............................................................................................................2456.10.2 AVL 树实现 ..............................................................................................................2476.11 ADT Map 实现小结...................................................................................................................2546.12 小结...............................................................................................................................................2556.13 关键词...........................................................................................................................................2556.14 问题讨论.......................................................................................................................................2556.15 小试牛刀.......................................................................................................................................2577. 图和图算法 ...............................................................................................................................2597.1. 目标................................................................................................................................................2597.2. 词汇表及定义................................................................................................................................2597.3. 图抽象数据类型............................................................................................................................2607.4. 邻接矩阵........................................................................................................................................2617.5. 邻接表............................................................................................................................................2617.6.实现..................................................................................................................................................2627.7. Word Ladder 词梯问题...............................................................................................................2647.7.1. 建立 Word Ladder 图.............................................................................................2657.7.2. 实现广度优先搜索(BFS) ........................................................................................2677.7.3. 广度优先搜索（BFS）的分析.................................................................................2707.8. 骑士周游问题..............................................................................................................................2717.8.1. 建立骑士周游图 ......................................................................................................2717.8.2. 实现骑士周游 ..........................................................................................................2747.8.3．骑士周游分析 ..........................................................................................................2787.8.4. 通用深度优先搜索 ..................................................................................................2807.9 拓扑排序..........................................................................................................................................2857.10 强连通分支....................................................................................................................................2867.11 最短路径问题................................................................................................................................2897.11.1.Dijkstra 算法 ..........................................................................................................2917.11.2.Dijkstra算法分析 ...................................................................................................2967.12.Prim 最小生成树算法...................................................................................................................2967.13. 小结............................................................................................................................................3027.14 ．关键词.......................................................................................................................................3027.15 问题讨论.......................................................................................................................................3037.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)