spContent=本课程着力于应用型本科院校学生及自学数据结构课程的学生,着重于实践能力培养,让学生掌握各类数据结构和算法的基本理论及实践操作。使学生学会分析研究计算机加工的数据的结构特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的基本操作算法,初步掌握算法时间和空间分析的技术。
本课程着力于应用型本科院校学生及自学数据结构课程的学生,着重于实践能力培养,让学生掌握各类数据结构和算法的基本理论及实践操作。使学生学会分析研究计算机加工的数据的结构特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的基本操作算法,初步掌握算法时间和空间分析的技术。
—— 课程团队
课程概述
数据结构与算法是计算机类专业的专业技术基础课程、核心课程。它所讨论的知识内容和提倡的技术方法,无论对进一步学习计算机领域的其它课程,还是对从事软件工程的开发,都有着不可替代的作用。
通过本课程的学习,使学生学会分析研究计算机加工的数据的结构特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的基本操作算法,能利用相应知识对计算机中处理的数据选择或建立适当的描述模型;初步掌握算法的时间和空间分析的技术,并学习各种常用算法的基本思想和实现技术,并能对不同的算法和数据描述模型能进行比较和评价。
本课程首先综述数据、数据结构和抽象数据类型等基本概念;其次,从抽象数据类型的角度,分别讨论线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用;最后,从时间上进行定性和定量的分析和比较了各种查找和排序方法。
授课目标
1、通过本课程的学习,使学生学会分析研究计算机加工的数据的结构特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的基本操作算法,能用相应知识对计算机中处理的数据选择或建立适当的描述模型;初步掌握算法的时间和空间分析的技术,并学习各种常用算法的基本思想和实现技术,并能对不同的算法和数据描述模型能进行比较和评价。
2、本课程的学习过程也是复杂程序设计的训练过程,要求学生编写的程序代码结构清晰、正确易读,符合软件工程的规范。在高级程序设计语言课程所进行的结构化程序设计的初步训练的基础上,进一步培养学生的数据抽象能力和算法分析设计的实践能力,并能认识到解决计算机软件开发的方案有多种可选性。
3、了解计算机学科的知识组织结构,了解本专业的前沿发展现状和趋势,并能用所学知识解决计算机相应的复杂工程问题,对复杂的工程问题能通过分析研究相关文献,获得关键环节的初步解决方案。
成绩 要求
课程成绩达到60分及以上者,成绩合格。总评达到85分及以上,成绩优秀。
课程大纲
绪论
课时目标:了解数据结构相关的术语与概念、算法的空间复杂度分析;理解抽象数据类型ADT描述、算法及其设计原则;掌握数据结构的顺序与链式存储的特点、算法的渐近时间复杂度方法。
1.1 什么是数据结构?如何学习数据结构?
1.2 算法定义、描述和分析
基本线性结构-线性表
课时目标:掌握线性表的特点及其两种存储方式实现;深入理解顺序表和链表的特点;在实际应用中,能正确选择存储方式,熟练运用线性表的基本操作求解问题。
2.1 线性表概念
2.2 顺序表及其实现
2.3 链表及其实现
2.4 线性表的应用(有序表的合并、一元多项式相加等)
限定性线性结构-栈和队列
课时目标:理解栈和队列的特点;掌握顺序栈的出栈、入栈操作,循环队列的入队、出队操作;掌握栈的典型应用问题:数制转换、表达式计算等的实现方法;能针对实际应用问题,利用栈和队列实现求解。
3.1 栈的定义与实现
3.2 栈的典型应用(数制转换、括号匹配、表达式计算)
3.3 队列的定义与实现
特殊的线性结构-串
课时目标:理解串的应用范围;掌握串的存储结构及基本操作;重点掌握串的模式匹配算法(KMP和BF);了解串的模式匹配算法效率的重要性。
4.1 串的定义及存储表示
4.2 串的基本操作
4.3 串的模式匹配
4.4 应用实例
扩展线性结构-数组和广义表
课时目标:了解特殊矩阵的特点;理解广义表的存储特点;掌握特殊矩阵的转换存储,广义表的存储结构,广义表的深度求解。
5.1 数组
5.2 矩阵的压缩存储
5.3 广义表
树形结构-树和二叉树
课时目标:理解树与二叉树的定义;理解二叉树的顺序存储,二叉树的线索过程;掌握二叉树的重要性质,二叉树的链式存储,二叉树的遍历,树与森林的转换,霍夫曼树的构造及对应霍夫曼编码。
6.1 树的定义
6.2 二叉树的定义及存储表示
6.3 二叉树的遍历
6.4 二叉树的算法应用
6.5 树和森林的定义
6.6 哈夫曼树及其应用
图形结构-图
课时目标:理解图的定义及其相关术语;掌握图的邻接矩阵、邻接表的存储表示;掌握图的深度、广度优先搜索遍历;掌握图的最小生成树、最短路径、拓扑排序、关键路径的算法应用。
7.1 图的定义
7.2 图的存储表示
7.3 图的遍历
7.4 图的典型应用-最小生成树
7.5 图的典型应用-拓扑排序
7.6 图的典型应用-关键路径
7.7 图的典型应用-最短路径
常用算法-查找
课时目标:了解B树*、键树*;理解基于静态表和动态表查找的特点、分析各种查找算法的时间复杂度;掌握顺序查找、二叉排序树查找、折半查找的算法实现,平衡二叉树的构造,除留余数法哈希表构造,开放地址法和链地址法处理哈希地址冲突。
8.1 查找定义
8.2 树表查找
8.3 哈希查找
常用算法-排序
课时目标:理解各种排序算法的时间复杂度分析及其稳定性;掌握希尔排序、快速排序、2-路归并排序、堆排序算法基本思想与程序实现和相应算法的时间复杂度分析;了解折半插入排序、基数排序;了解外部排序的多路平衡归并、置换-选择排序、最佳归并树的概念和思想。
展开全部
预备知识
参考资料
(1)邹永林、周蓓、唐晓阳 主编. 数据结构与算法 . 清华大学出版社,2015
(2)邹永林、周蓓、唐晓阳 主编. 数据结构与算法习题解析与实验指导,清华大学出版社,2015
(3)严蔚敏等 主编. 数据结构(C语言版). 清华大学出版社,2007
(4)马睿等 主编.《数据结构》(C语言版),北京邮电大学出版社,2009
(5)李春葆 主编.《数据结构习题与解析》(C语言篇),清华大学出版社,2000