问题求解：算法与数据结构（Python 版）

一. 引言
	1.1. 目标
	1.2. 开始学习
	1.3. 计算机科学是什么
	1.4. 什么是程序设计
	1.5. 为何要学习数据结构和抽象数据类型
	1.6. 为何要学习算法
	1.7. Python 入门
		1.7.1. 从数据开始
			1.7.1.1.预置核心数据类型
			1.7.1.2 预置集合数据类型
		1.7.2 输入与输出
			1.7.2.1 字符串格式化输出
		1.7.3   控制结构
			牛刀小试
			牛刀小试
		1.7.4 异常处理
		1.7.5 定义函数
			牛刀小试
			挑战
		1.7.6．Python 面向对象编程：定义类
			1.7.6.1.示例：Fraction 类
				牛刀小试
			1.7.6.2 继承：逻辑门与门电路
				牛刀小试
	小结
	关键词
	问题讨论
	编程练习
二．算法分析
	2.2.什么是算法分析
		2.2.1. 大“O”表示法
			小试牛刀
		2.2.2变位词检测
			牛刀小试
	2.3 Python 数据结构的性能
		2.3.1 列表 List
		2.3.2字典
			牛刀小试
	2.4小结
	2.5关键字
	2.6问题讨论
		2.7编程练习
三．基本数据结构类型
	3.1 学习目标
	3.2 什么是线性结构？
	3.3栈
		3.3.1 什么是栈？
	3.4栈的抽象数据类型
	3.4．队列
		3.4.1．什么是队列
		3.4.2.抽象数据类型Queue（队列）
		3.4.3.在Python 中实现Queue
			牛刀小试
		3.4.4. 模拟算法：热土豆
		3.4.5. 模拟算法：打印任务
		3.4.6. 主要模拟步骤
		3.4.7 Python实现
		3.4.8. 讨论
			牛刀小试
	3.5.双端队列
		3.5.1. 什么是双端队列
		3.5.2. 抽象数据类型
		3.5.3 在Python 中实现双端队列Deque
		3.5.4 “回文词”判定
	3.6 列表List
		3.6.1. 抽象数据类型无序列表UnorderedList
		3.6.2.采用链表实现无序列表
			3.6.2.1. 类：节点Node
			3.6.2.2. 类：无序列表Unordered List
				牛刀小试
		3.6.3 抽象数据类型：有序列表
		3.6.4. 实现有序列表
		3.6.5. 链表实现算法分析
	3.7.小结
	3.8.关键词（按：依英文原词的词典顺序排列）
	3.9.问题讨论
4.递归Recursion
	4.1目标
	4.2 什么是递归
		4.2.1 计算数字列表的和
		4.2.2 递归三大定律
			小试牛刀：
		4.2.3.将整数转化成任意进制表示的字符串形式
			小试牛刀：
		4.3 栈帧：实现递归
	4.4. 图示递归
		牛刀小试
		4.4.1. 谢尔宾斯基三角形
	4.5.复杂递归问题
		4.5.1.河内塔问题
	4.6.探索迷宫
		自我测试
	4.7动态规划
	4.8小结
	4.9关键词
	4.10问题讨论
	4.11词汇表
	编程练习
5. 排序与搜索
	5.1.目标
	5.2.搜索
		5.2.1.顺序搜索
			5.2.1.1.排序算法的分析
				自我测试
		5.2.2.二分法搜索
			5.2.2.1.  二分搜索分析
				自我检测
		5.2.3. 散列
			5.2.3.1. 散列函数
			5.2.3.2.冲突解决方法
				自我检测
			5.2.3.3.实现映射的抽象数据类型
			5.2.3.4.对散列的分析
	5.3.排序
		5.3.1.冒泡排序
			自我检测
		5.3.2.选择排序
			自我测试
		5.3.3.插入排序
			自我检测
	5.3.4. 希尔排序
		自我检测
	5.3.5.归并排序
		自我检测
	5.3.6.快速排序
		自我检测
	5.4.小结
	5.5 关键词
	5.6.问题讨论
	5.7.编程练习
6.树和树算法
	6.1.目标
	6.2.树的例子
	6.3.术语表和定义
	6.4.通过嵌套列表实现树
		自我测试
	6.5.节点和引用
		自我测试
	6.6 解析树
	6.7 树的遍历
	6.8 二叉堆 Binary Heap 实现的优先队列
		6.8.1二叉堆操作
		6.8.2二叉堆实现
			6.8.2.1二叉堆的结构性质
			6.8.2.2 堆的次序性
			6.8.2.3 二叉堆操作的实现
	6.9二叉搜索树
		6.9.1 搜索树操作
		6.9.2搜索树实现
			自我检测
		6.9.3 搜索树分析
	6.10 平衡二叉搜索树
		6.10.1  AVL树性能
		6.10.2  AVL树实现
	6.11  ADT Map 实现小结
	6.12 小结
	6.13 关键词
	6.14 问题讨论
	6.15 小试牛刀
		1. 扩展 buildParseTree 函数，使它能够解决没有空格分隔的数学表达式。
		2. 修改 buildParseTree 函数和 evaluate 函数，用它们解决布尔表达式（与 and，                   或 or 和非not） 。记住非是一个一元操作符，这会让你的编程稍稍复杂一点。
		3. 使用 findSuccessor 方法，写一个二叉搜索树的非递归的前序遍历。
		4. 修改二叉搜索树的代码使其成为链式的。写一个链式的二叉搜索树的非递归的前序遍历方法。一个链式的二叉搜索树中，每个节点只有对其后继的引用（即没有parent 这个参量—译者注） 。
		5. 修改二叉搜索树代码，使其能够正确解决重复键值问题。也就是说，如果一个键值
		（key）已经存在于该树当中，新的负载（value）需要取代旧的而不是添加另外一个相同的键值。
		6. 实现一个大小有限的二叉堆。也就是说，这个堆仅仅保存 n 个优先级最高的数据项。如果堆的大小即将超过 n，最不重要的节点将被丢弃。
		7. 整理 printexp 函数，使其不包括多余的括号。
		8. 使用 buildHeap方法，写一个排序函数，它能在 O(nlogn)时间内将一个列表排序。
		9. 写一个函数，它可以为数学表达式构建解析树，并能够计算某些特殊形式的数学表达式的导函数。
		10. 实现二叉堆，作为一个最大堆。
		11. 使用 BinaryHeap 类，实现一个新的类 PriorityQueue。你的 PriorityQueue 类应该包括构造函数，加上入队 enqueue、出队 dequeue 方法。
7. 图和图算法
	7.1. 目标
	7.2. 词汇表及定义
	7.3. 图抽象数据类型
	7.4. 邻接矩阵
	7.5. 邻接表
	7.6.实现
	7.7.  Word Ladder 词梯问题
		7.7.1. 建立 Word Ladder 图
		7.7.2. 实现广度优先搜索(BFS)
		7.7.3. 广度优先搜索（BFS）的分析
	7.8. 骑士周游问题
		7.8.1. 建立骑士周游图
		7.8.2. 实现骑士周游
		7.8.3．骑士周游分析
		7.8.4. 通用深度优先搜索
	7.9拓扑排序
	7.10强连通分支
	7.11最短路径问题
		7.11.1.Dijkstra 算法
		7.11.2.Dijkstra 算法分析
	7.12. Prim 最小生成树算法
	7.13. 小结
	7.14 ．关键词
	7.15 问题讨论
	7.16 编程练习