《数据结构与算法》课程教学大纲

1、数据结构与算法课程教学大纲一、课程概况所属专业:数学与应用数学开课单位：数学计算机科学学院课程类型:院系选修课课程代码:07491340开课学期:6学分：3+1学时：51+34核心课程:否拟使用教材：1 严蔚敏, 吴伟民.数据结构（C语言版）.清华大学出版社. 2011.7国内(外)现有教材：HYPERLINK /author/%D1%CF%CE%B5%C3%F4_1 t _blank严蔚敏, HYPERLINK /author/%C0%EE%B6%AC%C3%B7_1 t _blank李冬梅, HYPERLINK /author/%CE%E2%CE%B0%C3%F1_1 t _blank吴伟

2、民. 数据结构（C语言版）（第2版）. 人民邮电出版社. 2016.8HYPERLINK /author/%B3%C2%D1%E0_1 t _blank陈燕,HYPERLINK /author/%B2%DC%E5%FB_1 t _blank曹妍,HYPERLINK /author/%BC%D6%BA%EC%D3%EA_1 t _blank贾红雨,HYPERLINK /author/%C0%EE%EA%CA_1 t _blank李晔. 数据结构(C语言版) . 科学出版社. 2016.5HYPERLINK /author/%D0%EC%B7%EF%C9%FA_1 t _blank徐凤生. 数据结

3、构与算法：C语言版. 机械工业出版社. 2014.10学习参考资料：HYPERLINK /author/%C8%FB%C6%E6%CD%FE%BF%CB_1 t _blank塞奇威克.算法：C语言实现（第1-4部分）基础知识、数据结构、排序及搜索（原书第3版）. 机械工业出版社. 2009.10HYPERLINK /author/%CD%F5%C3%CE%BE%D5_1 t _blank王梦菊，HYPERLINK /author/%C6%EB%BE%B0%BC%CE_1 t _blank齐景嘉. 数据结构习题与实训教程（C语言描述）（第2版）. 清华大学出版社. 2015.7HYPERLINK

4、 /author/%D4%AC%BA%CD%BD%F0_1 t _blank袁和金. 数据结构习题分析与解答（语言版）. 中国电力出版社. 2012.8二、课程描述本课程是计算机科学技术、信息管理等专业的核心课程，是一门理论与工程实践密切相关的综合性课程，在计算机学科教学中具有十分重要的作用。主要解决数据的表示和数据的处理，系统介绍计算机领域的常用数据结构以及各种查找和排序的算法。通过强化数据结构基本知识和程序设计基本能力的双基训练，为学生后续计算机专业课程的学习打下坚实的基础。三、课程目标 系统学习常用基本数据结构及其在不同存储方式下的实现，掌握分析、选择不同的数据结构和存储结构的原则和方法

5、。学习和掌握在各种存储结构上实现的各种算法及其设计思想，从而学习各种分析问题和解决问题的能力。掌握各种算法的时空效率的分析方法，学会在实际应用中选择合适的算法。掌握各种查找和排序的算法以及效率，并将其应用在程序设计中。四、教学要求课程概念多、抽象、涉及面广，因此课程教学采用课堂讲授配合多媒体辅助教学讲授方式、课堂讨论、习题课、课程网站教学资源等多种形式进行课程教学，积极引导学生，激发学生的思维，让学生参与到教学中。每章布置3-6道习题以巩固教学；另外安排9个上机实验使理论与实际相结合（参考实验大纲），训练学生的实际动手能力。本课程的基本要求有：(1)熟练掌握线性表、树、图等各种数据结构的特点、

6、存储表示，操作算法及在计算机科学中基本应用。 (2)初步掌握算法的时间分析和空间分析的技巧。 (3)培养、训练学生选用合格的数据结构和使用类C语言编写质量高、风格好的应用程序及初步评价算法程序的能力。五、考核方式及要求为实现课程教学目标，本门课程采用过程性考核和期末考核结合的方式进行考核。过程性考核占总成绩40%，其中：考勤占10%，随机点到，每人不少于3次，其中无故缺席1次，按无考勤成绩计算；课程测验2次，占40%，测验时间和内容根据教学进度由教师安排；课程作业6次，按批改成绩折算，占40%；教师随堂检查学生课堂笔记记录情况并打分，占10%。期末考核占总成绩60%，为闭卷考试。六、课程内容第

7、一章：绪论（授课时间：第六学期第一、二周）教学目标：了解数据结构的课程性质、内容、应用领域及与其他学科的关系；掌握数据结构的相关概念和术语；掌握四类基本的数据关系；理解抽象数据类型的表示及实现；对算法、算法要求、算法效率的度量进行有效的分析教学重点：数据结构的相关概念和术语；抽象数据类型的表示及实现；算法、算法要求教学难点：基本数据关系；算法效率的度量及有效的分析学时：课堂教学6学时教学方法：讲授法、演示法主要内容：(1) 数据结构的基本概念和术语(2) 抽象数据类型的表示和实现(3) 算法定义及特性(4) 时间复杂度及空间复杂度学习方法：小组讨论、实验操作课后作业：要求理解和掌握四类基本的数

8、据关系；并在日常生活中举例进行说明；算法的5个特征；程序的语句的频度的分析第二章：线性表（授课时间：第六学期第三、四、五周）教学目标：理解线性表的定义和特点；掌握顺序表以达到利用基本算法进行较复杂算法设计的目的；理解线性表的链表的特点，掌握在这种存储结构上各种基本运算的实现算法以及效率的分析，并学习在这种存储结构上进行算法设计的方法；掌握一元多项式的表示及相加的方法与算法教学重点：线性表的定义和特点；线性表的顺序表示及实现；线性表的链式表示及实现教学难点：线性表的顺序存储实现；单链表的插入、删除、查找和归并操作；一元多项式相加的方法学时：课堂教学9学时教学方法：讲授法、演示法主要内容：(1)

9、线性表的类型定义(2) 线性表的顺序表示和实现(3) 线性表的链式表示和实现(4) 一元多项式的表示及相加学习方法：小组讨论、实验操作课后作业：顺序存储结构上结点的插入、删除算法；链式结构上结点的插入、删除算法第三章：栈与队列（授课时间：第六学期第六周）教学目标：理解栈的定义、特点，掌握判断其空和满的判断条件；学习栈的存储方式及相关算法，以及栈的简单应用；掌握队列的数据结构和链队列的相关操作；掌握循环队列的相关内容教学重点：栈的定义、特点，栈的存储方式及相关算法；队列的数据结构和链队列的相关操作教学难点：栈的简单应用；循环队列的相关操作学时：课堂教学3学时教学方法：讲授法、演示法主要内容：(1

10、) 栈及其实现(2) 栈的应用(3) 循环队列及相关运算学习方法：小组讨论、实验操作课后作业：栈基本操作的算法；循环队列的基本操作算法第四章：串（授课时间：第六学期第七周）教学目标：掌握串的定义、定长顺序存储表示；了解串的块链存储表示；掌握求子串位置的定位函数（模式匹配算法）教学重点：串的定义、定长顺序存储表示；串的块链存储表示教学难点：模式匹配算法学时：课堂教学3学时教学方法：讲授法、演示法主要内容：(1) 串的定义(2) 串的表示和实现(3) 串的模式匹配算法学习方法：小组讨论、实验操作课后作业：串的链接操作；串的模式匹配算法第五章：数组与广义表（授课时间：第六学期第八周）教学目标：掌握数

11、组的定义、数组的顺序表示和实现；掌握特殊矩阵和稀疏矩阵的存储方法；掌握稀疏矩阵的转置算法；掌握广义表的相关定义及基本操作教学重点：数组的定义、数组的顺序表示和实现；特殊矩阵和稀疏矩阵的存储方法；稀疏矩阵的转置算法；广义表的相关定义及基本操作教学难点：数组的顺序表示和实现；稀疏矩阵的转置算法学时：课堂教学3学时教学方法：讲授法、演示法主要内容：(1) 数组的定义(2) 数组的顺序表示和实现(3) 矩阵的压缩存储(4) 广义表学习方法：小组讨论、实验操作课后作业：计算1-3维数组的任意元素的存储地址；稀疏矩阵的转置算法第六章：树与二叉树（授课时间：第六学期第九、十周）教学目标：掌握树的定义和基本术

12、语、掌握二叉树的定义及二叉树的性质；掌握二叉树的两种存储；掌握二叉树的遍历方法；掌握树的存储结构；掌握森林与二叉树的转换；掌握哈夫曼树的构造及哈夫曼编码的编码方法教学重点：树的定义和基本术语、二叉树的定义；二叉树的两种存储结构、二叉树的遍历方法；树的三种存储结构、森林与二叉树的转换；哈夫曼树的构造方法教学难点：二叉树的性质；二叉树的存储结构及遍历方法；森林与二叉树的转换；哈夫曼编码学时：课堂教学6学时教学方法：讲授法、演示法主要内容：(1) 树的定义和基本术语(2) 二叉树的定义(3) 二叉树的性质(4) 二叉树的存储结构(5) 二叉树的遍历(6) 树的存储结构(7) 森林与二叉树的转换(8)

13、 树的遍历(9) 哈夫曼树及其应用学习方法：小组讨论、实验操作课后作业：二叉树的基本形态及性质；对二叉树进行三种遍历操作；将树和森林与二叉树进行相互转换；构造哈夫曼书并进行编码第七章：图（授课时间：第六学期第十一、十二、十三周）教学目标：熟练掌握和理解有关图的各种定义和术语；理解和熟练掌握图的四种存储结构；熟练掌握图的遍历操作；数量掌握求图的连通分量的问题和最小生成树的问题；理解和熟练掌握图的拓扑排序的方法；理解和掌握求解图的关键路径的问题；教学重点：图的各种定义和术语；数组表示法、邻接表；图的遍历操作、求图的连通分量的问题；图的拓扑排序的方法；图的关键路径的问题；最短路径问题；教学难点：图的

14、生成树、图的连通性；邻接多重表；最小生成树的问题；学时：课堂教学9学时教学方法：讲授法、演示法主要内容：(1) 图的定义(2) 图的存储结构(3)图的遍历(4) 拓扑排序(5) 最短路径学习方法：小组讨论、实验操作课后作业：求解图的深度、广度优先搜索过程；构造最小生成树；求某一顶点到其它各顶点的最短路径第九章：查找（授课时间：第六学期第十四、十五周）教学目标：掌握顺序表的查找、有序表的查找、索引顺序表的查找、哈希表的构造方法以及处理冲突的方法。教学重点：顺序表的查找、哈希表的构造方法以及处理冲突的方法。教学难点：哈希表处理冲突的方法。学时：课堂教学6学时教学方法：讲授法、演示法主要内容：(1)

15、 静态查找表(2) 动态查找表(3) 哈希表学习方法：小组讨论、实验操作课后作业：顺序查找算法；哈希表构造并采用开放定址法及链地址法处理冲突。第十章：内部排序（授课时间：第六学期第十六、十七周）教学目标：掌握直接插入排序、其他插入排序、希尔排序、冒泡排序、快速排序及堆排序算法思想及性能分析。教学重点：直接插入排序、希尔排序、冒泡排序、快速排序及堆排序算法思想。教学难点：希尔排序、快速排序及堆排序算法思想及性能分析。学时：课堂教学6学时教学方法：讲授法、演示法主要内容：(1) 内部排序概念(2) 插入排序(3) 快速排序(4) 归并排序基数排序各种排序方法比较学习方法：小组讨论、实验操作课后作业

16、：熟练掌握各种内部排序方法以及性能分析。实验一：简单算法实验（授课时间：第六学期第一、二周）教学目标：C语言相关知识回顾主要内容：复习C语言指针的用法，复习C语言结构体的用法，理解时间复杂度分析的基本方法学时：4学时教学方法：演示法/讲授/现场指导实验类型：验证性实验实验二：线性表的顺序存储实验（授课时间：第六学期第三、四周）教学目标：顺序表基本操作的实现主要内容：了解线性表的顺序存储方法，掌握用在VC环境下上机调试单链表的基本方法；掌握顺序表的插入、删除、查找、求表长以及有序顺序表的合并算法的实现学时：4学时教学方法：演示法/讲授/现场指导实验类型：验证性实验实验三：线性表的链式存储实验（授

17、课时间：第六学期第五、六周）教学目标：链表基本操作的实现主要内容：了解线性表的链式存储方法，掌握用在VC环境下上机调试单链表的基本方法；掌握链表的插入、删除、查找、求表长以及有序链式的合并算法的实现学时：4学时教学方法：演示法/讲授/现场指导实验类型：验证性实验实验四：栈的存储结构及运算实验（授课时间：第六学期第七、八周）教学目标：掌握栈的顺序存储结构和链式存储结构，以便在实际背景下灵活运用主要内容：利用栈的顺序存储，实现栈实现数制转换，实现多项式的四则运算学时：4学时教学方法：演示法/讲授/现场指导实验类型：验证性实验实验五：队列的存储结构及运算实验（授课时间：第六学期第九周）教学目标：掌握

18、队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用主要内容：实现循环队列的顺序存储学时：2学时教学方法：演示法/讲授/现场指导实验类型：验证性实验实验六：二叉树的基本操作及应用（授课时间：第六学期第十、十一周）教学目标：掌握二叉树的结构特性，以及各种存储结构的特点和适用范围主要内容：以二叉链表作存储结构，试编写程序实现计算二叉树深度、所有结点总数、叶子结点数、孩子结点个数等算法学时：4学时教学方法：演示法/讲授/现场指导实验类型：验证性实验实验七：哈夫曼算法实验（授课时间：第六学期第十二、十三周）教学目标：哈夫曼树的建立；哈夫曼编码的生成主要内容：利用建立哈夫曼树的算法思想，将要发送的字符信息进行哈夫曼编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。学时：4学时教学方法：演示法/讲授/现场指导实验类型：验证性实验实验八：图的遍历算法实验（授