《数据结构与算法》课程是计算机科学与技术的学科基础课程,不仅是《计算机图形学》、《计算机网络》、《编译原理》、《计算机操作系统》等后续课程的基础理论之一,其应用范围也早已扩展到图像处理与模式识别、海量数据挖掘、科学数据处理、复杂网络分析等许多计算机前沿领域。
本课程研究计算机处理数据的结构特性,学习线性表、树、图等常用数据结构的逻辑结构与存储结构;学习分治递归、动态规划、贪心算法等典型算法,掌握分析与推导算法效率的方法。
通过对本课程的学习,能够解决非数值计算与工程应用问题,达到选择或设计恰当的逻辑结构、存储结构及相应的算法的水平,为学生进一步理论学习和解决实际工程应用问题打下坚实的基础。通过理论知识的系统学习与工程实验的操作,初步培养学生的计算思维能力、算法设计与分析能力、程序设计与编程实现能力、计算机系统的认知、分析、设计和运用能力、工程实践能力。
本课程面向计算机专业或者非计算机专业,但有程序设计语言基础的同学。
第一章 绪论
1-教学安排
3-算法
2-数据结构基本概念,术语与主要学习内容
绪论测验
第二章2.1 线性表 (本章内容比较多,需要2周的学习时间)
5-栈
线性表测验
1-线性表的基本概念
2-基于线性表操作的简单应用
7-线性表的基本操作编程视频(请尽量自己实现)
3-线性表的存储结构及基本操作实现
4-线性表的应用
6-队列
第二章 2.2 查找
2-顺序查找
5-哈希查找
1-查找基本概念
3-折半查找
查找问题讨论
4-索引查找
查找测验
第二章 2.3 排序
3-选择排序
2-插入排序
4-交换排序
5-基数排序
6-外部排序
排序测验
1-排序的基本概念
第三章 递归与分治
1-递归
3-复杂度计算
2-分治
4-应用
递归与分治测验
第四章 树与二叉树 (本章内容需要2周学习时间)
3-二叉树的变形
4-树与二叉树的相互转换
1-引子
2-二叉树的定义与复原
AVL树的补充
树与二叉树测验
第五章 图论与贪心算法(本章内容需要2周学习时间)
2-贪心算法理论
贪心算法作业
3-图论与贪心算法的应用
1-图论的基本概念
第六章 动态规划
5-备忘录法
2-动态规划理论
6-项目实战
3-动态规划例子-矩阵连乘
动态规划作业
1-引言
4-动态规划要素
7-总结
程序设计语言(C,C++,java,python等任何一门语言)
本课程以C语言为基础进行讲解,但学习了其他语言的同学可以无障碍学习本课程内的容并同样受益。
平时作业:40%
讨论: 10%
期末考试:50%
优秀:>=80
合格:60--79
林劼,刘震,陈端兵,戴波. 数据结构与算法. 北京:北京大学出版社,2018.8
吴跃,等. 数据结构与算法. 北京: 机械工业出版社, 2010.
王晓东. 算法设计与分析. 2版. 北京:清华大学出版社.
Kleinberg,等. 算法导论. 北京:清华大学出版社.
Q : 那么多《数据结构》或者《数据结构与算法》课程,我们课程明显特色是什么?
A :
细心的同学可能发现不少名字叫做《数据结构》,或者名字叫《数据结构与算法》的课程,但其中算法部分只是包括了查找,排序等基本算法,而我们的算法课程除了其他课程的核心主要内容,还包括:递归与分治,贪心算法,动态规划。
这些算法经典而用途广泛,许多同学在学习其他数据结构课程的时候,常常有为什么这些人能够想到这种求解思路的困惑,或者有哪些规律,能够解决哪些类型的问题,我们课程中能够解答您的这些疑惑。举一个非常常见的 最小生成树 问题作为例子,其他课程您可能学习之后知道通过加点或者加边的方式能够得到最小生成树,但是您不会知道算法思想来自于贪心算法,也不知道为什么这种方法能够得到全局最优解,而比如找硬币问题,也可以采用贪心算法求解,可是却不一定能够得到全局最优解。通过这些典型算法的学习与应用,不但能够打下更加扎实的基础,还能够触类旁通,举一反三。
我们课程的另外1个特色,就是很多同学学习其他《数据结构》or《数据结构与算法》课程,会造成一种错觉:以为本课程就是一门理论课程,并不能解决寻找算法用程序编写软件解决大部分现实世界问题的能力。实际上,我们通过案例引导及分析,就是要让同学们不但能够找到解决问题的算法,还具有根据算法编写软件的能力。特别是第一章线性表,我们可以说是一步步的讲解怎么写程序实现基本操作,怎么写程序实现更加复杂的问题。
所以,学习本课程,不要满足于听懂,还要积极参与讨论,开拓您的思路;还要把所思所想转换成为代码程序,只有从基础开始多做思路转换为代码的编程练习,最终才具有解决复杂问题和未知问题的能力和编程水平!
Q : 课程采用C语言作为教学语言,我学的是python/c++/java/其他语言,能够学好本课程吗?怎么学?
A : 当然可以,我们虽然以C语言作为教学语言,但是原理都是通的,您只需要把我们的C语言代码用您熟悉代码展示,完成的作业或者测验也采用您的语言也是可以的。大部分作业或者测验,我们会考虑同学们编程语言不同的问题,尽量用算法或者伪代码描述,需要实际编程的不会限制语言。