数据结构 C语言版 教学大纲 作者 严蔚敏 李冬梅 吴伟民 数据结构教学大纲(参考).docx
- 文档编号:1982686
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:6
- 大小:14.58KB
数据结构 C语言版 教学大纲 作者 严蔚敏 李冬梅 吴伟民 数据结构教学大纲(参考).docx
《数据结构 C语言版 教学大纲 作者 严蔚敏 李冬梅 吴伟民 数据结构教学大纲(参考).docx》由会员分享,可在线阅读,更多相关《数据结构 C语言版 教学大纲 作者 严蔚敏 李冬梅 吴伟民 数据结构教学大纲(参考).docx(6页珍藏版)》请在冰点文库上搜索。
数据结构
课程代码:
DataStructure
学时数:
64(讲课50 实验14 研讨0 实习实践1周) 学分数:
3、4
课程类别:
学科基础课 开课学期:
4
主讲教师:
编写日期:
2011年7月1日
一、课程性质和目的
课程性质:
数据结构A是计算机科学与技术、数字媒体艺术、信息管理与信息系统专业的一门重要学科基础课,是必修课。
教学目的:
通过本课程的学习,一方面,使学生学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法,并初步了解对算法的时间分析和空间分析技术。
另一方面,通过对本课程算法设计和上机实践的训练,还应培养学生的数据抽象能力和程序设计的能力。
二、课程教学内容、学时分配和课程教学基本要求
1.绪论(理论2学时)教学内容:
(1)数据结构的一些基本概念:
数据、数据元素、数据的逻辑结构、物理结构等。
(2)抽象数据类型的表示和实现。
(3)算法的概念和特性。
(4)算法时间复杂度和空间复杂度的分析。
基本要求:
掌握数据结构的基本概念,了解抽象数据类型,掌握算法时间复杂度和空间复杂度的分析方法。
2.线性表(理论8学时,实验4学时)
教学内容:
(1)线性表的类型定义。
(2)线性表的顺序表示和实现。
(3)线性表的链式表示和实现。
(4)线性表的应用,包括无序表和有序表的合并、多项式的加法运算等。
基本要求:
理解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构(顺序表)和链式存储结构(链表)。
熟练掌握这两类存储结构的描述方法,掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。
掌握顺序表的查找、插入和删除算法,掌握链表的查找、插入和删除算法。
能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。
掌握无序表和有序表的合并算法,了解多项式的加法运算。
实验:
实验内容:
单链表的基本操作。
实验要求:
以单链表形式创建一个学生表或图书表,并能实现相关的查找、插入和删除等算法。
3.栈和队列(理论6学时,实验4学时)
教学内容:
(1)栈的类型定义,栈的顺序存储和链接存储的表示和实现。
(2)栈的应用举例,如迷宫求解和表达式求值。
(3)栈与递归的实现,递归程序转换为非递归程序的方法。
(4)队列的类型,队列的顺序存储(循环队)和链接存储的表示和实现。
(5)队列的应用举例,如打印杨晖三角形,模拟汽车加油站等问题。
基本要求:
掌握栈和队列的特点,并能在相应的应用问题中正确选用。
熟练掌握栈的顺序栈和链栈的进栈出栈算法,特别应注意栈满和栈空的条件。
掌握利用栈实现表达式求值的算法,了解迷宫求解算法。
理解递归算法执行过程中栈的状态变化过程,了解将递归程序转换为非递归程序的方法。
熟练掌握循环队列和链队列的进队出队算法,特别是循环队列中队头与队尾指针的变化情况。
了解队列的应用。
实验:
实验内容:
栈的应用。
实验要求:
借助栈来解决某些实际应用问题,如表达式求值、迷宫问题等。
4.串、数组和广义表(理论2学时)
教学内容:
(1)串的表示和实现,包括顺序存储和链式存储表示。
古典的模式匹配算法。
(2)数组的存储方法。
(3)特殊矩阵和稀疏矩阵的压缩存储,稀疏矩阵的转置运算。
(4)广义表的逻辑结构和存储结构。
基本要求:
了解串的顺序存储结构和堆存储结构。
掌握串的古典的模式匹配算法。
掌握数组的地址计算方法。
了解稀疏矩阵的两种压缩存储方法的特点和适用范围。
了解广义表的结构特
点及其存储方法。
5.树和二叉树(理论8学时,实验2学时)教学内容:
(1)二叉树的定义和术语,二叉树的性质,特殊的二叉树。
(2)二叉树的存储结构,顺序存储和二叉链表。
(3)二叉树的的前序、中序、后序、层次遍历方法。
线索化二叉树。
(4)树和森林的定义,树的存储,树、森林与二叉树的转换。
(5)树的应用,哈夫曼树及哈夫曼编码。
基本要求:
了解树和森林的概念,包括树的定义、树的术语。
掌握二叉树的概念、性质及二叉树的表示。
熟练掌握二叉树的遍历算法,并且能灵活运用遍历算法实现二叉树的其他操作。
掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法。
了解树的存储、树和森林与二叉树的转换方法。
掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算。
实验:
实验内容:
二叉树的基本算法。
实验要求:
利用二叉链表方法建立二叉树,实现二叉树的前、中、后序三种遍历算法,并运用遍历算法实现二叉树的其他操作,如计算二叉树结点个数、叶子结点个数、二叉树的高度等。
6.图(理论8学时,实验2学时)
教学内容:
(1)图的定义和术语。
(2)图的存储结构两种存储结构:
邻接矩阵和邻接表表示法。
(3)图的两种遍历策略:
深度优先搜索和广度优先搜索。
(4)构造最小生成树的两种算法:
普里姆算法和克鲁斯卡尔算法。
(5)拓扑排序和关键路径。
(6)两类求最短路径问题的算法,迪杰斯特拉算法和弗洛伊德算法。
基本要求:
掌握图的基本概念及相关术语和性质,掌握图的邻接矩阵和邻接表表示法,了解实际问题的求解效率与采用何种存储结构和算法有密切联系。
熟练掌握图的两种搜索路径的遍历:
深度优先搜索和广度优先搜索的算法。
掌握构造最小生成树的两种算法及拓扑排序算法的思想,掌握迪杰斯特拉算法。
了解关键路径的概念和求解方法,了解弗洛伊德算法。
实验:
实验内容:
图的建立和搜索。
实验要求:
使用邻接矩阵或邻接表表示法存储一个图,实现图的深度优先搜索和广度优先搜索的算法。
7.查找(理论6学时)
教学内容:
(1)查找的基本概念,平均查找长度。
(2)基于线性表的查找:
顺序查找、折半查找。
(3)基于树表的查找:
二叉排序树、平衡二叉树、B-树和B+树。
(4)散列表:
散列表的基本概念,散列函数的构造方法、处理冲突的方法、散列表的查找与分析。
基本要求:
熟练掌握顺序表和有序表的查找方法及其实现,掌握二叉排序树的插入和查找算法及其实现,了解平衡二叉树、B-树和B+树的各种操作。
熟练掌握散列表的构造方法、处理冲突的方法,深刻理散列表与其他结构的表的实质性的差别,了解各种散列函数的特点。
掌握描述折半查找过程的判定树的构造方法,以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
8.排序(理论8学时,实验2学时)
教学内容:
(1)排序的基本概念,包括正序,逆序,稳定性,排序方法的分类。
(2)插入排序:
直接插入排序、折半插入排序和希尔排序。
(3)交换排序:
冒泡排序和快速排序。
(4)选择排序:
简单选择排序和堆排序。
(5)归并排序:
2-路归并排序。
(6)基数排序:
多关键字的排序和链数基数排序。
(7)排序算法分析:
各种排序算法的比较和移动次数,时间复杂度和空间复杂度的分析。
基本要求:
明确排序的基本概念,排序方法的分类。
深刻理解排序算法的过程、特点及其依据的原则,并能加以灵活应用。
掌握各种排序方法的时间和空间复杂度的分析方法。
能从关键字间的比较次数和移动次数分析算法的平均情况和最坏情况的时间性能。
理解排序方法“稳定”或“不稳定”的含义,弄清楚在什么情况下要求应用的排序方法必须是稳定的。
快速排序、堆排序和归并排序等高效排序方法是本章的学习重点和难点。
实验:
实验内容:
综合性实验。
实验要求:
选取一个合适的数据结构存储数据,能对数据进行插入、删除,用不同查找算法进行查找、用不同的排序算法进行排序等。
9.实习(1周)
教学内容:
(1)设计准备:
理解实习任务,明确相关算法,搜集可用资源,熟悉实习环境。
(2)方案设计:
完成设计目标、设计路线的确定,并进行模块设计和任务分工。
(3)代码编写:
各模块代码编写,模块测试。
(4)代码测试:
模块组装,整体测试。
(5)设计报告:
完成设计文档,制作设计报告。
基本要求:
能将数据结构课程中所学的基本知识融会贯通,综合运用所学的知识解决相关的实际问题,能够把所学知识(包括算法和结构)在计算机上用编程语言加以实现,并且能够根据实际需求创建自己的数据结构和实现自己的算法。
本课程的教学环节包括:
课堂讲授、实验、实习、作业、答疑、小测验等。
其中,课堂讲授以教师讲授为主,授课时将电子教案和板书相结合,充分发挥各自的优点。
采用启发式教学,鼓励学生自学,培养学生的自学能力,以“少而精”为原则,精选教学内容,调动学生学习的主观能动性。
实验针对相应单元所学的内容,能够采取合适的数据结构和算法解决有关问题。
实验重点培养学生的动手能力。
实习针对较为复杂的应用问题,能够综合运用所学的各种数据结构进行算法设计和实现,注重学生数据抽象能力和算法设计能力的培养。
三、本课程与其它课程的联系和分工
本课程的先修课为程序设计基础和离散数学,本课程可以C/C++或Java语言作为算法描述和上机实践的工具。
同时,本课程又是软件开发与设计等方面课程的基础,如数据库、操作系统、编译原理、软件工程等课程。
四、本课程的考核方式
期末考试采用笔试形式,考试题型为:
选择、填空、判断、应用题和算法设计题。
总评成绩由平时成绩和期末成绩组成,其中平时成绩占30%--40%,期末考试占70%--60%。
课程实习的成绩由平时成绩和实习作业两部分组成,其中平时成绩占30%,实习作业占70%。
五、建议教材与教学参考书
建议教材:
1.严蔚敏,李冬梅,吴伟民.数据结构(C语言版).北京:
人民邮电出版社.
2.严蔚敏主编.数据结构(C语言版).北京:
清华大学出版社.
3.殷人昆主编.数据结构(用面向对象方法与C++描述).北京:
清华大学出版社.
建议教学参考书:
1.[美]BrunoR.Preiss著,胡广斌,王崧等译.数据结构与算法-面向对象的C++设计模式.北京:
电子工业出版社.
2. 殷人昆主编.数据结构与习题解析(用面向对象方法与C++描述).北京:
清华大学出版社.
六、课程简介
数据结构是一门专业基础课,是学习其他软件开发与设计等方面课程的基础。
主要内容包括:
线性表、栈和队列、串、数组和广义表、树、图、查找算法和排序算法。
数据结构研究数据的组织方式,内容丰富、学习量大,隐含在各部分内容中的方法和技术多,旨在让学生掌握计算机软件系统所必需的数据结构的算法。
要求学生掌握贯穿全课程的动态链表存储结构,掌握算法设计的动态性和抽象性。
要求学生学会分析研究计算机加工的数据对象的特征,以便在实际应用中选择适当的数据结构、存储结构和相应算法,初步掌握算法的时间与空间性能分析技巧,并培养复杂程序设计的技能。
执笔人:
审核人:
教学院长:
院学术委员会:
院长:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 C语言版 教学大纲 作者 严蔚敏 李冬梅 吴伟民 数据结构教学大纲参考 语言版 参考