数据结构与算法Python版（陈斌）北京大学

课程地址

课程内容

01概述（1周）

介绍计算理论和计算复杂性

• 1.引子
• 2.关于计算的概念和定义：问题求解的计算之道
• 3.图灵机计算模型
• 4.可计算性和计算复杂度；
• 5.什么是抽象
• 6.什么是编程实现
• 7.为什么研究数据结构与抽象数据类型
• 8.为什么研究算法

02算法分析（1周）

介绍算法分析，大O表示法，以及用实例来演示同一个问题的不同解决方案的算法分析。

• 1.什么是算法分析？
• 2.大O表示法
• 3.案例分析：“变位词”判断问题
• 4.Python数据结构的性能：列表List和字典Dictionary

03基本结构（2周）

介绍栈、队列、双端队列和列表等线性结构。

• 1.什么是线性结构？
• 2.栈Stack抽象数据类型及Python实现
• 3.栈的应用：简单括号匹配
• 4.栈的应用：十进制转换为二进制
• 5.栈的应用：中缀、前缀和后缀表达式
• 6.队列Queue抽象数据类型及Python实现
• 7.队列的应用：热土豆
• 8.队列的应用：打印任务
• 9.双端队列Deque抽象数据类型及Python实现
• 10.双端队列应用：回文词判定
• 11.列表List抽象数据类型及Python实现
• 12.无序表实现及链表
• 13.有序表抽象数据类型及Python实现

04 递归（3周）

介绍递归和动态规划算法，以及分治策略解决问题。

• 1.什么是递归
• 2.实例分析：列表求和的递归算法
• 3.递归“三定律”
• 4.递归的应用：任意进制转换
• 5.实现递归：调用栈
• 6.递归的可视化
• 7.递归的应用：塞宾斯基三角形绘制
• 8.复杂递归问题
• 9.递归的应用：汉诺塔
• 10.递归的应用：探索迷宫
• 11.动态规划Dynamic Programming

05排序与查找（2周）

介绍经典的排序和查找算法

• 1.什么是查找？
• 2.顺序查找算法及分析
• 3.二分查找算法及分析
• 4.散列：散列函数、碰撞解决和映射数据类型
• 5.什么是排序？
• 6.冒泡排序算法及分析；
• 7.选择排序算法及分析；
• 8.插入排序算法及分析；
• 9.谢尔排序算法及分析；
• 10.归并排序算法及分析；
• 11.快速排序算法及分析。

06树及算法（3周）

介绍树结构和树结构的处理算法，以及应用

• 1.树的基本概念及相关术语
• 2.树的列表实现；
• 3.树的链表实现；
• 4.树的应用：表达式解析
• 5.树的遍历
• 6.二叉堆实现的优先队列
• 7.二叉堆的实现
• 8.二叉查找树及操作
• 9.二叉查找树实现及算法分析
• 10.平衡的二叉查找树
• 11.AVL树的性能
• 12.AVL树的实现

07图及算法（3周）

介绍图结构和图的应用。

• 1.图的基本概念及相关术语
• 2.图抽象数据类型
• 3.邻接矩阵和邻接表
• 4.图的实现
• 5.Word Ladder词梯问题
• 6.构建词梯问题的图数据结构
• 7.实现广度优先搜索BFS
• 8.BFS算法分析
• 9.骑士周游问题
• 10.构建骑士周游问题的图数据结构
• 11.骑士周游问题算法实现
• 12.骑士周游问题算法分析
• 13.通用的深度优先搜索DFS
• 14.DFS算法分析
• 15.拓扑排序
• 16.强连通分支
• 17.最短路径问题Dijkstra算法及算法分析
• 18.Prim最小生成树算法

参考资料

北京大学地空学院数据结构与算法B课程网站
数据结构与算法Python-中文版-内部教材
在线英文版教材
Python3官方中文版文档
Python3烹饪书
在线Python代码规范