用Python解决数据结构和算法资源-CSDN文库

需积分: 12 162 浏览量 2018-05-12 16:23:06 上传评论 2 收藏 10.9MB PDF 举报

资源推荐

资源详情

资源评论

问题求解：算法与数据结构 
（Python  版） 
目录 
一.  引言 ........................................................................................................................................... 10 
1.  目标 .................................................................................................................................................. 10 
2.  开始学习 .......................................................................................................................................... 10 
3.  计算机科学是什么 .......................................................................................................................... 10 
4.  什么是程序设计 .............................................................................................................................. 11 
5.  为何要学习数据结构和抽象数据类型 .......................................................................................... 12 
6.  为何要学习算法 .............................................................................................................................. 13 
7. Python  入门 ..................................................................................................................................... 13 
7.1.  从数据开始 ................................................................................................................... 13 
7.2  输入与输出 .................................................................................................................... 27 
7.3      控制结构 .................................................................................................................... 31 
7.4  异常处理 ........................................................................................................................ 35 
7.5  定义函数 ........................................................................................................................ 37 
7.6．Python  面向对象编程：定义类 ................................................................................. 38 
小结 .......................................................................................................................................................... 54 
关键词 ...................................................................................................................................................... 54 
问题讨论 .................................................................................................................................................. 54 
编程练习 .................................................................................................................................................. 55 
二．算法分析 .................................................................................................................................. 56 
2.什么是算法分析 ................................................................................................................................ 56 
2.1.  大“O”表示法 ............................................................................................................. 60 
2.2 变位词检测 ..................................................................................................................... 63 
3 Python  数据结构的性能 .................................................................................................................. 69 
3.1  列表  List ......................................................................................................................... 69 
3.2 字典 ................................................................................................................................. 73 
4 小结 .................................................................................................................................................... 76 
5 关键字 ................................................................................................................................................ 76 
6 问题讨论 ............................................................................................................................................ 76 

三．基本数据结构类型 .................................................................................................................. 78 
1  学习目标 ........................................................................................................................................... 78 
2  什么是线性结构？ ........................................................................................................................... 78 
3 栈 ........................................................................................................................................................ 78 
3.1  什么是栈？ .................................................................................................................... 78 
4 栈的抽象数据类型 ............................................................................................................................ 80 
4．队列 ................................................................................................................................................. 80 
4.1．什么是队列 .................................................................................................................. 80 
4.2.抽象数据类型 Queue（队列） ...................................................................................... 81 
4.3.在 Python  中实现 Queue ............................................................................................... 82 
4.4.  模拟算法：热土豆 ....................................................................................................... 84 
4.5.  模拟算法：打印任务 ................................................................................................... 86 
4.6.  主要模拟步骤 ............................................................................................................... 88 
4.7 Python 实现 ..................................................................................................................... 88 
4.8.  讨论 ............................................................................................................................... 96 
5.双端队列 ............................................................................................................................................ 97 
5.1.  什么是双端队列 ........................................................................................................... 97 
5.2.  抽象数据类型 ............................................................................................................... 97 
5.3  在 Python  中实现双端队列 Deque .............................................................................. 98 
5.4  “回文词”判定 ............................................................................................................ 99 
6  列表 List .......................................................................................................................................... 101 
6.1.  抽象数据类型无序列表 UnorderedList ..................................................................... 101 
6.2.采用链表实现无序列表 ............................................................................................... 102 
6.3  抽象数据类型：有序列表 .......................................................................................... 111 
6.4.  实现有序列表 ............................................................................................................. 112 
6.5.  链表实现算法分析 ...................................................................................................... 114 
7.小结 .................................................................................................................................................. 115 
8.关键词（按：依英文原词的词典顺序排列） .............................................................................. 115 
9.问题讨论 .......................................................................................................................................... 116 
递归 Recursion ............................................................................................................................ 119 
1 目标 .................................................................................................................................................. 119 
2  什么是递归 ..................................................................................................................................... 119 
2.1  计算数字列表的和 ...................................................................................................... 119 
2.2  递归三大定律 .............................................................................................................. 122 

2.3.将整数转化成任意进制表示的字符串形式 ............................................................... 123 
3  栈帧：实现递归 ............................................................................................................. 125 
4.  图示递归 ........................................................................................................................................ 127 
4.1.  谢尔宾斯基三角形 ..................................................................................................... 132 
5.复杂递归问题 .................................................................................................................................. 135 
5.1.河内塔问题 ................................................................................................................... 135 
6.探索迷宫 .......................................................................................................................................... 137 
7 动态规划 .......................................................................................................................................... 148 
8 小结 .................................................................................................................................................. 154 
9 关键词 .............................................................................................................................................. 154 
10 问题讨论 ........................................................................................................................................ 154 
11 词汇表 ............................................................................................................................................ 155 
编程练习 ................................................................................................................................................ 156 
 排序与搜索 ............................................................................................................................... 158 
1.目标 .................................................................................................................................................. 158 
2.搜索 .................................................................................................................................................. 158 
2.1.顺序搜索 ....................................................................................................................... 158 
2.2.二分法搜索 ................................................................................................................... 161 
2.3.  散列 ............................................................................................................................. 164 
3.排序 .................................................................................................................................................. 175 
3.1.冒泡排序 ....................................................................................................................... 175 
3.2.选择排序 ....................................................................................................................... 178 
3.3.插入排序 ....................................................................................................................... 179 
3.4. 希尔排序 .................................................................................................................................. 182 
3.5.归并排序 .................................................................................................................................... 185 
3.6.快速排序 .................................................................................................................................... 186 
4.小结 .................................................................................................................................................. 187 
5 关键词 ............................................................................................................................................ 188 
6.问题讨论 .......................................................................................................................................... 188 
7.编程练习 ........................................................................................................................................ 189 
树和树算法 ................................................................................................................................. 191 
1.目标 .................................................................................................................................................. 191 
2.树的例子 .......................................................................................................................................... 191 

3.术语表和定义 .................................................................................................................................. 193 
4.通过嵌套列表实现树 ...................................................................................................................... 195 
5.节点和引用 ...................................................................................................................................... 199 
6  解析树 ......................................................................................................................................... 203 
7  树 的 遍 历  ..................................................................................................................................... 210 
8  二叉堆  BINARY HEAP  实 现 的 优 先 队 列  ......................................................................... 213 
8.1 二叉堆操作 ................................................................................................................... 213 
8.2 二叉堆实现 ................................................................................................................... 214 
9 二叉搜索树 ...................................................................................................................................... 222 
9.1  搜索树操作 .................................................................................................................. 222 
9.2 搜索树实现 ................................................................................................................... 223 
9.3  搜索树分析 .................................................................................................................. 243 
10  平衡二叉搜索树 ........................................................................................................................... 244 
10.1    AVL 树性能 ............................................................................................................... 245 
10.2    AVL 树实现 .............................................................................................................. 247 
11    ADT Map  实现小结 ................................................................................................................... 254 
12  小结 ............................................................................................................................................... 255 
13  关键词 ........................................................................................................................................... 255 
14  问题讨论 ....................................................................................................................................... 255 
15  小试牛刀 ....................................................................................................................................... 257 
 图和图算法 ............................................................................................................................... 259 
1.  目标 ................................................................................................................................................ 259 
2.  词汇表及定义 ................................................................................................................................ 259 
3.  图抽象数据类型 ............................................................................................................................ 260 
4.  邻接矩阵 ........................................................................................................................................ 261 
5.  邻接表 ............................................................................................................................................ 261 
6.实现 .................................................................................................................................................. 262 
7.    Word Ladder  词梯问题 ............................................................................................................... 264 
7.1. 建立 Word Ladder 图............................................................................................. 265 
7.2. 实现广度优先搜索(BFS) ........................................................................................ 267 
7.3. 广度优先搜索（BFS）的分析 ................................................................................. 270 
8. 骑士周游问题 .............................................................................................................................. 271 