基本信息
源码名称：python解决数据结构和算法.pdf
源码大小：10.87M
文件格式：.pdf
开发语言：Python
更新时间：2020-12-12
友情提示：（无需注册或充值，赞助后即可获取资源下载链接）
嘿，亲！知识可是无价之宝呢，但咱这精心整理的资料也耗费了不少心血呀。小小地破费一下，绝对物超所值哦！如有下载和支付问题，请联系我们QQ(微信同号)：813200300
本次赞助数额为： 4 元×
微信扫码支付：4 元
×
请留下您的邮箱，我们将在2小时内将文件发到您的邮箱
源码介绍
假设我们的有序列表中已有：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)