数据结构与算法
分享
课程详情
课程评价
spContent=本课程针对学习程序设计语言之后,需要开发软件而遇到问题不知怎么处理,怎么寻找解决问题的方法,怎么存储数据及关系,以及学习了《数据结构与算法》课程,但是写程序就感觉无从下手的同学。 关于本课程详细特色请见本页最后的常见问题。
—— 课程团队
课程概述

    《数据结构与算法》课程是计算机科学与技术的学科基础课程,不仅是《计算机图形学》、《计算机网络》、《编译原理》、《计算机操作系统》等后续课程的基础理论之一,其应用范围也早已扩展到图像处理与模式识别、海量数据挖掘、科学数据处理、复杂网络分析等许多计算机前沿领域。

      本课程研究计算机处理数据的结构特性,学习线性表、树、图等常用数据结构的逻辑结构与存储结构;学习分治递归、动态规划、贪心算法等典型算法,掌握分析与推导算法效率的方法。  


     通过对本课程的学习,能够解决非数值计算与工程应用问题,达到选择或设计恰当的逻辑结构、存储结构及相应的算法的水平,为学生进一步理论学习和解决实际工程应用问题打下坚实的基础。通过理论知识的系统学习与工程实验的操作,初步培养学生的计算思维能力、算法设计与分析能力、程序设计与编程实现能力、计算机系统的认知、分析、设计和运用能力工程实践能力。

 


授课目标

本课程面向计算机专业或者非计算机专业,但有程序设计语言基础的同学。



课程大纲

本课程共46学时

第一章   绪论(1周)

1.       教学内容

(1)    数据结构相关概念和术语。

(2)    程序、数据结构、算法的关系。

(3)    算法的定义及特性;算法的最坏复杂度性能分析,常见计算机算法的运行时间。

2.       教学要求

(1)    掌握:数据结构及算法的概念内涵、特点及作用;分析和计算算法的时间和空间复杂度。

(2)    理解:算法分析的数学基础,渐近表示的特点及其与精确数学表示的差异。

(3)    了解:项目开发基本流程;分析程序效率的基本方法;常见算法的运行时间。

3.       教学方法

多媒体课件结合板书面授

第二章   线性表、栈与队列(2周)

1.       教学内容

(1) 线性表的定义、逻辑结构特点。

(2) 线性表的存储结构——顺序存储和链式存储及其存储特点。

(3) 线性表的基本操作——查找、插入、删除在顺序存储及链式存储结构上的具体编程实现。

(4) 各种变形链表(循环链表、双向链表、带头结点的链表等)的含义及基本操作的编程实现。

(5) 数组的地址计算方法

(6)    栈、队列的定义,栈与队列在两种存储结构上的实现。循环队列的判满、判空方法。栈与队列的简单应用。

2.       教学要求

(1)    掌握

a)         线性表的两种存储表示及其实现。

b)        顺序表和链表的一些常见操作及编程实现,及这两种线性结构各自适用的应用场合。运用线性表解决一些简单的实际问题。

c)         栈和队列定义、特征及基本操作。循环队列的入队、出队、判满、判空等基本操作。

(2)    理解

a)       线形表的4类基本操作类型。

b)      顺序表和链表在存储及实现上的异同。

c)       队列的假溢出。

d)      变形链表的存储特征及用途

e)       数组的地址计算方法。

f)         

(3)    了解

3.       教学方法

(1) 多媒体课件结合板书面授;

(2) 多媒体课件结合示例代码讲解、分析和演示;

(3) 程序编写与调试演示;

(4) 上机编程练习与辅导

第三章   查找、排序与分治递归(3周,每个内容各1周)

1.       教学内容

(1)    查找的基本概念。顺序查找、折半查找、索引查找的方法。

(2)    哈希表的基本概念,哈希函数构造方法及冲突处理策略,哈希表的查找、插入、删除等操作方法。

(3)    排序的基本概念。各种内部排序算法,包括插入排序、快速排序、选择排序、归并排序。各种排序算法的性能及复杂度分析。

(4)    分治递归算法的思想,分治递归算法设计基本步骤,利用分治递归的思想设计:大整数乘法。

(5)    利用代换法、递归树与主方法求解递归式。

2.       教学要求

(1)    掌握

a)       顺序查找、折半查找、索引查找以及哈希表的查找方法。

b)      哈希函数的基本构造方法,解决地址冲突的一些基本策略

c)       直接插入排序、折半插入排序等插入排序算法;冒泡排序和快速排序等交换排序算法;简单选择排序算法;归并排序算法

d)      分治递归方法及其应用:大整数乘法。

e)       利用主方法求解递归式表达式。

(2)    理解

a)       各查找算法的时间复杂度和空间复杂度。

b)      分治递归算法的解题思路。

c)       代换法和递归树求解递归式的过程和方法。

(3)    了解

a)       各种排序算法的稳定性和时空性能分析过程。

b)      分治递归算法的思想。

3.       教学方法

(1) 多媒体课件结合板书面授;

(2) 多媒体课件结合示例代码讲解、分析和演示;

(3) 程序编写与调试演示;

(4) 上机编程练习与辅导。

(5) 程序编写与课堂讨论;

第四章   树与二叉树(2周)

1.       教学内容

(1)    二叉树和树的递归定义和基本性质。

(2)    满二叉树和完全二叉树的概念及特征。

(3)    二叉树、树及森林的顺序存储及链式存储,各种遍历方法及相互间的转换。

(4)    二叉排序树、平衡二叉树的构建、结点查找、插入与删除。

(5)    哈夫曼树的构建和哈夫曼编码。

(6)    二叉树及树的典型应用——堆排序。

2.       教学要求

(1)    掌握

a)       二叉树、树、森林的基本概念、遍历以及他们之间的相互转换。

b)      二叉树的基本性质。

c)       二叉排序树的基本操作与编程实现。

d)      构建哈夫曼树的方法。

e)       堆的定义、堆的建立与调整,堆排序的方法,堆与优先队列的关系。

f)        满二叉树和完全二叉树的概念和特征。

(2)    理解

a)       平衡二叉树的构建及基本操作。

b)      哈夫曼编码

(3)    了解

B树、2-3树的定义及基本操作。

3.       教学方法

(1) 多媒体课件结合板书面授;

(2) 多媒体课件结合示例代码讲解、分析和演示;

(3) 提问式引导教学;

(4) 程序编写与调试演示,课题讨论;

(5) 上机编程练习与辅导

第五章   图论与贪心算法(2周)

1.       教学内容

(1)    图的基本概念,基本操作和存储——邻接矩阵、邻接表(逆邻接表)。

(2)    图的遍历方法——深度优先和广度优先。

(3)    贪心算法思想,贪心算法基本要求,调度问题(Interval Scheduling)。

(4)    图的生成树和最小生成树,最小生成树的两种构建方法——普里姆和克鲁斯卡尔。

(5)    图中两结点以及所有结点间最短路径的求取方法——迪杰斯特拉和弗洛伊德方法。

(6)    有向无环图的拓扑排序和关键路径求取。

2.       教学要求

(1)    掌握

a)       图的基本概念。

b)      图的存储结构——邻接矩阵和邻接表。

c)       图基本操作——深度优先和广度优先遍历。

d)      最小生成树,结点间的最短路径,图的拓扑排序以及关键路径。

e)       贪心算法的设计思路,调度问题的贪心算法。

(2)    理解

贪心算法的性质。

(3)    了解

a)       图的存储结构——十字链表与邻接多重表表示法的定义与存储结构

b)      图的连通分支、最大流、欧拉图、哈密尔顿图的应用。

c)       贪心算法的思想。

3.       教学方法

(1) 多媒体课件结合板书面授;

(2) 多媒体课件结合案例讲解工程开发流程;

(3) 上机编程练习与辅导。

(4) 项目驱动型教学;

(5) 程序编写与课堂讨论;

第六章   动态规划(1周)

1.       教学内容

(1)    动态规划算法的思想;动态规划技术及其特点。

(2)    动态规划与分治递归算法的区别。

(3)    动态规划应用:包括0-1背包问题、矩阵链乘法问题、文本相似度对比问题、装配线调度问题、权重化的活动安排问题等。

2.       教学要求

(1)                掌握

a)       递归程序的动态规划描述。

b)      动态规划问题解题方法和典型应用:0-1背包问题、矩阵链乘法问题、文本相似度对比问题、权重化的活动安排问题。

(2)                理解

动态规划的基本原理、指导原则、基本步骤和最优化思想。

(3)                了解

其他各种动态规划算法及其变形。

3.       教学方法

(1) 多媒体课件结合板书面授;

(2) 多媒体课件结合案例讲解工程开发流程;

(3) 上机编程练习与辅导

(4) 项目驱动型教学;

(5) 程序编写与课堂讨论;


预备知识

程序设计语言(C,C++,java,python等任何一门语言)


本课程以C语言为基础进行讲解,但学习了其他语言的同学可以无障碍学习本课程内的容并同样受益。

 


 

证书要求

平时作业:40%

讨论: 20%

期末考试: 40%


优秀:>=80

合格:60--79

 

参考资料

林劼,刘震,陈端兵,戴波. 数据结构与算法. 北京:北京大学出版社,2018.

吴跃,等. 数据结构与算法. 北京: 机械工业出版社, 2010.

王晓东. 算法设计与分析. 2版. 北京:清华大学出版社.

Kleinberg,等. 算法导论.  北京:清华大学出版社.

 

常见问题


Q :  那么多《数据结构》或者《数据结构与算法》课程,我们课程明显特色是什么?

A :  

细心的同学可能发现不少名字叫做《数据结构》,或者名字叫《数据结构与算法》的课程,但其中算法部分只是包括了查找,排序等基本算法,而我们的算法课程除了其他课程的核心主要内容,还包括:递归与分治,贪心算法,动态规划。


这些算法经典而用途广泛,许多同学在学习其他数据结构课程的时候,常常有为什么这些人能够想到这种求解思路的困惑,或者有哪些规律,能够解决哪些类型的问题,我们课程中能够解答您的这些疑惑。举一个非常常见的 最小生成树 问题作为例子,其他课程您可能学习之后知道通过加点或者加边的方式能够得到最小生成树,但是您不会知道算法思想来自于贪心算法,也不知道为什么这种方法能够得到全局最优解,而比如找硬币问题,也可以采用贪心算法求解,可是却不一定能够得到全局最优解。通过这些典型算法的学习与应用,不但能够打下更加扎实的基础,还能够触类旁通,举一反三。


我们课程的另外1个特色,就是很多同学学习其他《数据结构》or《数据结构与算法》课程,会造成一种错觉:以为本课程就是一门理论课程,并不能解决寻找算法用程序编写软件解决大部分现实世界问题的能力。实际上,我们通过案例引导及分析,就是要让同学们不但能够找到解决问题的算法,还具有根据算法编写软件的能力。特别是第一章线性表,我们可以说是一步步的讲解怎么写程序实现基本操作,怎么写程序实现更加复杂的问题。


所以,学习本课程,不要满足于听懂,还要积极参与讨论,开拓您的思路;还要把所思所想转换成为代码程序,只有从基础开始多做思路转换为代码的编程练习,最终才具有解决复杂问题和未知问题的能力和编程水平!



Q :  课程采用C语言作为教学语言,我学的是python/c++/java/其他语言,能够学好本课程吗?怎么学?

A :  当然可以,我们虽然以C语言作为教学语言,但是原理都是通的,您只需要把我们的C语言代码用您熟悉代码展示,完成的作业或者测验也采用您的语言也是可以的。大部分作业或者测验,我们会考虑同学们编程语言不同的问题,尽量用算法或者伪代码描述,需要实际编程的不会限制语言。