| “数据结构与算法（Python 语言）”教学材料 |
| 本页提供课程的幻灯片、演示代码和其他材料。
相关教科书已出版：《数据结构与算法：Python语言描述》
裘宗燕著，机械工业出版社，2016年1月 | |||
|---|---|---|---|
| 幻灯片和材料目录 | 发布日期 | 附注 | |
| 1 | 引言：幻灯片， rational 类的实现（基本部分） | 两次课 2014-09-25 | 问题求解过程，交叉路口通行问题，算法，算法复杂性及其估计，Python程序的时间估计，问题复杂性，P-NP问题，数据与数据结构，抽象数据类型，Python的类（class）定义 |
| 2 | 线性表(1)，连续表：幻灯片 | 2014-10-09 | 计算机存储结构，对象和表示，线性表的概念和操作，顺序表实现，Python list, 复杂性分析 |
| 3 | 线性表(2)，链接表：幻灯片，结点类模块，简单单链表模块，带尾结点引用的单链表模块 | 2014-10-16 | 链接表结构，基本技术，基本操作，加入和删除元素，操作的复杂性，Python 实现，结点类，单链表类，继承/基类/派生类，带尾结点引用的单链表 |
| 4 | 线性表(3)，链接表的变形和应用：幻灯片，循环单链表类模块，双链表类模块，带反转和排序函数的单链表类模块，Josephus 问题的几个实现 | 2014-10-21 | 循环单链表的概念和实现，双链表的概念和一个实现，单链表元素反转算法，元素排序，单链接表元素排序的两个算法（分别采用移动元素和修改链接的方法），Josephus 问题的三种解法。 |
| 5 | 字符串(1)，概念和串匹配算法：幻灯片，匹配函数的代码文件 | 2014-10-23 | 字符串，概念，操作，实现，Python 的 str，字符串匹配，朴素匹配算法，KMP 算法 |
| 6 | 字符串(2)，串匹配与正则表达式：幻灯片 | 2014-10-26 | 串匹配问题，字符串集合的描述，正则表达式，Python 的正则表达式 |
| 7 | 栈和队列(1)，概念，栈和应用：幻灯片，连续栈实现代码文件，链接栈实现代码文件，栈的应用代码文件（括号匹配，后缀表达式求值，中缀表达式到后缀表达式的转换） | 2014-10-30 | 容器，缓存，数据生成和使用的顺序，栈（后进先出），队列（先进先出），栈的实现（连续表实现，链接表实现），两种 Python 实现，栈的应用：括号匹配，后缀表达式求值，中缀表达式到后缀表达式的转换 |
| 8 | 栈和队列(2)，栈和递归，队列实现和应用：幻灯片，队列的连续表实现代码文件 | 2014-11-4 | 栈与递归，运行栈，递归的与普通的函数调用，递归与非递归算法，队列的链接表实现，队列的连续表实现，用 list 实现队列，队列的实际应用 |
| 9 | 栈和队列(3)，迷宫和搜索：幻灯片，迷宫搜索问题代码文件 | 2014-11-6 | 迷宫问题，递归求解，回溯法求解和栈，搜索问题，迷宫问题的队列缓存求解，深度和宽度优先搜索，不同搜索方法的性质，栈和队列的变形结构，Python 的 deque 类 |
| 10 | 树和二叉树(1)，概念，性质，实现和应用：幻灯片，二叉树的 list 实现和表达式树的代码文件 | 2014-11-13 | 树形结构及其图示，树和树林的相关概念，二叉树的概念和性质，二叉树的 list 实现，表达式树和表达式计算 |
| 11 | 树和二叉树(2)，优先队列，离散事件模拟，二叉树的链接实现，遍历：幻灯片，优先队列的两种实现代码文件，海关检查站模拟代码文件 | 2014-11-18 | 优先队列的概念，连续表实现和堆实现，离散事件模拟的概念和基本技术，通用模拟框架类，事件类，海关检查站模拟系统，二叉树的链接表示，二叉树结点类，深度优先遍历（先根，中根和后根序），宽度优先遍历 |
| 12 | 树和二叉树(3)，二叉树的遍历，递归和非递归实现，二叉树类，哈夫曼树和哈夫曼算法，树与树林，树的实现，树与二叉树的关系：幻灯片，二叉树遍历和二叉树类等的代码文件，哈夫曼算法代码文件 | 2014-11-20 | 二叉树的遍历算法，非递归先根序和后根序遍历，链接表和二叉树迭代器，二叉树类，哈夫曼树和哈夫曼算法，哈夫曼编码，树的遍历，树林的遍历，树的表示，树（树林）和二叉树之间的转换，树的 Python 实现，本章总结 |
| 13 | 图(1)，图的概念和性质，实现，Python 实现，遍历，生成树：幻灯片，两个图类的定义代码文件，图遍历和生成树代码文件 （项目1问题总结，供参考） |
2014-11-27 | 图的概念，顶点和边，有向图和无向图，子图，路径，连通性，带权图，图的操作，图的表示，邻接矩阵，邻接表，在 Python 里的实现图，图的遍历，生成树，基于遍历构造生成树 |
| 14 | 图(2)，最小生成树，单源点最短路径：幻灯片，最小生成树算法的代码文件，最短路径算法的代码文件 | 2014-12-2 | 最小生成树，Kruskal 算法，Prim 算法，最短路径，单源点最短路径，Dijkstra 算法 |
| 15 | 图(3)，所有顶点间的最短路径，拓扑排序，关键路径：幻灯片，拓扑排序和关键路径的代码文件，顶点间最短路径算法也在代码文件 | 2014-12-4 | 所有顶点间的最短路径，Floyd-Warshal 算法，AOV 网，拓扑序列，拓扑排序和算法，AOE 网，关键路径和算法 |
| 16 | 字典和集合(1)，字典，线性表实现，散列表实现：幻灯片，关联类代码文件，二分检索等的代码文件 | 2014-12-11 | 字典的概念，关键码，检索，关联，基于线性表实现字典，基于排序表实现字典，散列，散列函数，散列表字典，冲突和冲突消解技术 |
| 17 | 字典和集合(2)，集合，Python字典和集合，二叉排序树：幻灯片，二叉排序树字典类代码文件 | 2014-12-16 | 集合，集合的线性表和排序表实现，集合的位向量实现，二叉排序树，最佳二叉排序树的概念 |
| 18 | 字典和集合(3)，最佳二叉排序树，平衡二叉排序树：幻灯片，最佳二叉排序树代码文件，平衡二叉排序树代码文件 | 2014-12-18 | 最佳二叉排序树的构造，等概率和不等概率情况下的构造算法；平衡二叉排序树（AVL树），概念，性质，插入和平衡调整，插入算法 |
| 19 | 字典和集合(4)，多分支排序树，B 树和 B+ 树：幻灯片。排序(1)，排序的概念，排序算法幻灯片 | 2014-12-25 | 插入、选择、起泡、快速等排序算法 |
| 20 | 排序(2)，归并排序算法等幻灯片, 课程总结 |
2014-12-30 | 归并，归并排序，Timsort（Python 使用的排序算法，参考材料），各种排序算法的比较 |
| 本页及相关页面（除另声明者外）由裘宗燕创建维护，可自由用于各种学习活动。其他使用需得到作者许可。 |