《数据结构》-付立冬.doc

数据结构教学大纲课程代码：040631003课程英文名称：Data Structure课程总学时：48 讲课：40 实验：0 上机：8适用专业：信息管理与信息系统大纲编写（修订）时间：2010.7一、大纲使用说明（一）课程的地位及教学目标本课程是信息管理与信息系统专业的一门重要的专业基础课,它较详细地阐述了使用计算机解决具体问题时，所建立的数学模型的逻辑结构与存储结构的多种类型，以及对数据进行具体操作的算法实现。通过本课程的学习，使学生了解和掌握使用高级语言编程时组织数据的基本理论和方法，是学生进一步学习其他专业课程的必备基础。 通过本课程的学习，学生将达到以下要求： 1了解数据结构及其分类、数据结构与算法的密切关系； 2熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构； 3掌握设计算法的步骤和算法分析的方法； 4掌握数据结构在排序和查找等常用算法中的应用。（二）知识、能力及技能方面的基本要求要求学生了解各种形式多样的客观问题中所涉及的数据对象可通过适当的分解，从而可以对应几种数据结构。学生应该能够使用高级语言正确定义数据的逻辑结构和选择有效的存储结构，以解决具体问题。其操作的实现算法应注重时间效率和空间效率。对数据对象的查找与排序操作时较常用的基本操作，学生应掌握基本的算法，并学会合理使用。（三）实施说明 1教学方法：本课程对学生的动手能力要求较强，应配置相应的上机实验。使学生在编程的训练中，真正掌握算法的实现方法。在教师的讲解过程中应深入浅出、循序渐进、联系实际、结合实例，才能收到较好的效果。应培养学生良好的算法设计思想、方法与技巧，强化程序抽象能力与数据抽象能力。 2教学手段：本课程属于专业基础课，在教学中采用多媒体教学为主，辅以板书讲解。确保在有限的学时内，全面、高质量地完成课程教学任务。（四）对先修课的要求要求学生有高级语言的基础知识与编程经验。（五）对习题课、实践环节的要求 1对重点、难点章节（如：线性表的链表实现、二叉树的遍历、图的存储结构和遍历、排序算法的实现等）应安排习题课。 2课后作业要少而精，内容要多样化，作业题内容必须包括基本概念、基本算法理论及设计方面的内容，作业要能起到巩固理论，掌握数据结构算法的分析和设计技巧。对作业中的重点、难点，课上应做必要的提示，并适当安排课内讲评作业。学生必须独立、按时完成课外习题和作业，作业的完成情况应作为评定课程成绩的一部分。 3每个学生要完成大纲中规定的必修上机实验，通过实验环节，学生应掌握典型数据结构的设计及实现方法。实验成绩作为评定课程成绩的一部分。（六）课程考核方式1.考核方式：考试。2.考核目标：在考核学生对数据结构基本知识、算法的理论和设计方法的基础上，重点考核学生的问题分析能力和算法设计能力。3.成绩构成：本课程的总成绩主要由三部分组成：平时成绩（包括中期考试、作业、小测验、提问、出勤情况等）占10%，实验成绩占20%，期末考试成绩占70%。平时成绩由任课教师视具体情况按百分制给出；实验成绩由实验老师参照相关规定按百分制给出，实验无成绩或实验不及格，取消期末考试资格，总成绩直接以不及格计。（七）主要参考书目:数据结构(C语言版) 严蔚敏 清华大学出版社 2006.9数据结构 李筠，姜学军 清华大学出版社 2008.8二、中文摘要本课程是信息管理与信息系统专业学生必修的一门专业技术基础课程。通过对本课程的讲授，使得学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法。课程主要内容包括数据结构基本概念、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序等。本课程将为后续课程的学习以及毕业设计奠定重要的基础。三、课程学时总体分配表序号教学内容学时讲课实验上机1绪论222线性表8622.1线性表的类型定义，顺序表示和实现22.2线性表的链式表示和实现4线性表的应用实验23栈和队列8623.1栈23.2栈的应用23.3队列2栈应用实验24串444.1串的定义、表示和实现24.2串的模式匹配算法25数组和广义表445.1数组25.2广义表26树和二叉树8626.1树的定义，二叉树126.2二叉树2，树和森林26.3赫夫曼树及其应用2实现二叉树的遍历实验27图447.1图的定义、存储结构、遍历27.2图的连通性问题28查找448.1静态查找表，动态查找表128.2动态查找表2，哈希表29内部排序6429.1插入排序，快速排序29.2选择排序，归并排序2排序实验2合计48408四、教学内容及基本要求第1部分 绪论总学时(单位：学时):2 讲课:2 实验:0 上机:0 具体内容：1) 基本概念与术语2) 抽象数据类型的表示与实现3) 算法与算法分析重 点: 有关数据结构中的基本概念难 点: 算法的描述方法习 题: 算法时间复杂度的计算第2部分 线性表总学时(单位：学时):8 讲课:6 实验:0 上机:2 具体内容：1) 线性表的类型定义2) 线性表的顺序表示和实现3) 线性表的链式表示和实现4) 循环链表和双向链表重 点: 顺序存储结构、链式存储结构、双向链表的特点，双向链表的类型定义及相关操作的实现难 点: 顺序表的插入删除算法中数据元素的移动 链表的插入与删除算法习 题: 顺序表和各种链表的插入和删除操作实 验: 线性表的应用实验（2学时）第3部分 栈和队列总学时(单位：学时):8 讲课:6 实验:0 上机:2 具体内容：1) 栈概念2) 栈的基本运算3) 栈的表示和实现4) 栈的应用举例5) 队列的基本运算6) 队列的顺序存储结构7) 队列的链式存储结构重 点: 堆栈和队列的各种运算方法难 点: 链式存储结构及其实现方法习 题: 栈和队列的基本操作实 验: 栈应用实验（2学时）第4部分 串总学时(单位：学时):4 讲课:4 实验:0 上机:0 具体内容：1) 串类型的定义2) 串的表示和实现3) 串的模式匹配算法4) 串操作应用举例重 点: 基本概念和存储结构难 点: 串的模式匹配第5部分 数组和广义表总学时(单位：学时):4 讲课:4 实验:0 上机:0 具体内容：1) 数组的定义2) 数组的顺序表示和实现3) 矩阵的压缩存储4) 广义表的定义5) 广义表的存储结构重 点: 数组的几种常用表示方法、矩阵的存储、广义表的存储结构方法难 点: 广义表的存储结构方法第6部分 树和二叉树总学时(单位：学时):8 讲课:6 实验:0 上机:2 具体内容：1) 二叉树的定义和性质2) 二叉树的存储结构3) 遍历二叉树4) 线索二叉树5) 树和森林重 点: 二叉树的定义和性质，遍历二叉树难 点: 线索二叉树习 题: 二叉树的遍历，树与二叉树的转换实 验: 实现二叉树的遍历实验（2学时）第7部分 图总学时(单位：学时):4 讲课:4 实验:0 上机:0 具体内容：1) 图的定义和术语2) 图的存储结构3) 图的遍历4) 图的连通性重 点: 图的存储结构，图的遍历难 点: 图的遍历，最小生成树习 题: 图的存储表示及遍历算法第8部分 查找总学时(单位：学时):4 讲课:4 实验:0 上机:0 具体内容：1) 顺序表的查找2) 有序表的查找3) 动态查找表4) 哈希表重 点: 有序表的查找，动态查找表难 点: 哈希表习 题: 有序表