数据结构教学大纲.doc

数据结构课程教学大纲 课程名称：数据结构 课程编号: 04516017英文名称：Data Structure课程类型: 专业基础平台课（必修） 是否独立开设实验: 否总 学 时：96 讲课学时：64 实验学时：32学分：5适用对象:软件工程、网络工程专业本科先修课程：计算机科学导论、C/C+程序语言设计一、课程简介数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与操作的学科，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，属于计算机学科中的一门必修专业基础课程，它不仅是一般程序设计的基础，也是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。二、课程性质、目的和任务性质：数据结构是计算机类学科的重要学科基础平台课，是必修课。学习本课程所讨论的知识内容和提倡的技术方法和思路，无论对进一步学习计算机领域的其他课程，还是对从事软件工程的开发，都有着不可替代的作用。目的：通过本课程的学习，使学生能够使用合理的数据组织和清晰的算法来编写效率更高的程序，积累复杂程序编写的经验。要求学生（1）学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术；（2）通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。 三、教学基本要求 1理解和掌握数据结构的基本概念，各种逻辑结构和存储结构；2熟练掌握常见的数据结构（如线性表，栈和队列、数组和广义表，二叉树，图等）的逻辑结构和存储结构，以及在其上的基本运算；3. 熟练掌握一些常用操作（如排列、查找）的算法实现；4. 了解一些基本的实际应用，培养、训练学生分析数据对象特性选择合适的数据结构，能编写具有良好风格的应用程序，5. 并具有初步评价算法的能力。四、教学内容及要求 1.绪论 （理论2学时，实验2学时）教学内容：(1) 数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结构等。(2) 抽象数据类型的表示和实现。(3) 算法的定义和特性。(4) 算法时间复杂度和空间复杂度的基本概念。基本要求：理解数据结构、抽象数据类型以及算法含义。掌握算法特点及描述、算法分析。领会数据、数据元素和数据项的概念及其相互间的关系。理解4种不同逻辑结构的特点，清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现。算法时间复杂度和空间复杂度仅作概念上的要求，让学生知道可以从这两个方面衡量一个算法。实验：（1）多个数的求和、平均、最大值、最小值；（2）集合的交、并、差2.线性表 （理论10学时，实验10学时）教学内容：(1) 线性表的类型定义。(2) 线性表的顺序表示和实现。(3) 线性表的链式表示和实现。(4) 线性表的应用，包括无序表和有序表的合并、多项式的加法运算等。基本要求：理解线性表的定义及其运算。理解顺序表和链表的定义、组织形式、结构特征和类型说明，掌握在这两种表上实现的插入、删除和按值查找的算法。了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。线性表应用中重点讲解线性表归并算法，一元多项式的表示和相加可以把算法思想介绍给学生。实验：（1）顺序表的基本操作（2）链表的基本操作3.栈和队列 （理论8学时，实验4学时）教学内容：(1) 栈的类型定义，栈的顺序存储和链接存储的表示和实现。(2) 栈的应用举例，如数制转换、括号匹配的检验和表达式求值。(3) 栈与递归的实现，递归程序转换为非递归程序的方法。(4) 队列的类型，队列的顺序存储(循环队)和链接存储的表示和实现。基本要求：理解栈和队列的定义、特征及在其上所定义的基本运算，掌握在两种存储结构上对栈和队列所施加的基本运算的实现。重点在顺序栈的表示和实现，栈的应用部分只要求数制转换和和表达式求值两部分。栈与递归部分不做要求。队列部门重点在循环队列部分以及链队的表示和实现。队列的应用一节不做要求。实验：（1）顺序栈的基本操作（2）链队列的基本操作4.串 （理论4学时）教学内容：(1) 串的表示和实现，包括顺序存储和链式存储表示。(2) 串的模式匹配算法。基本要求：了解串的定义、存储方式和常用的串运算串的模式匹配算法只要求BF算法，KMP算法可以简单提及算法思想，不做过多要求。5.数组和广义表（理论6学时，实验4学时）教学内容：(1) 数组的存储方法。(2) 特殊矩阵和稀疏矩阵的压缩存储，稀疏矩阵的转置运算。(3) 广义表的逻辑结构和存储结构。基本要求：理解数组的定义、基本运算和存储结构，掌握特殊矩阵的压缩存储；扩充稀疏矩阵的压缩存储和2种转置运算；了解广义表的定义、术语、存储结构、常用运算。实验：矩阵的2种转置运算6.树和二叉树（理论10学时，实验8学时）教学内容：(1) 二叉树的定义和术语，二叉树的性质，特殊的二叉树。(2) 二叉树的存储结构，顺序存储和二叉链表。(3) 二叉树的的前序、中序、后序、层次遍历方法。线索化二叉树。(4) 树和森林的定义，树的存储，树、森林与二叉树的转换。(5) 树的应用，哈夫曼树及哈夫曼编码。基本要求：深刻理解树和二叉树的定义、性质及其存储方法，熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义，并能画出给定二叉树的二叉链表的结构示意图；理解并掌握二叉树的四种遍历方法，并能写出该四种遍历的算法；掌握线索二叉树的概念，理解线索的含义，能够按照某一遍历算法，为二叉树添加线索；掌握树的存储结构，完成树、森林与二叉树间的相互转换，学会树和森林的遍历算法；理解哈夫曼树的构造方法，并能对给定的数据集合构造出哈夫曼树。实验：（1）二叉树的应用（2）赫夫曼树的构建7.图（理论10学时，实验4学时）教学内容：(1) 图的定义和术语。(2) 图的存储结构两种存储结构：邻接矩阵和邻接表表示法。(3) 图的两种遍历策略：深度优先搜索和广度优先搜索。 (4) 构造最小生成树的两种算法：普里姆算法和克鲁斯卡尔算法。(5) 拓扑排序和关键路径。(6) 两类求最短路径问题的算法，迪杰斯特拉算法。基本要求：理解图的基本概念及术语，掌握图的常用存储结构(邻接矩阵、邻接表、十字链表、多重邻接表)的表示方法；熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Kruscal算法和Prim算法构造最小生成树，具体算法不做要求；了解并掌握拓扑排序、关键路径、最短路径的算法思想和求解方法。实验：构造无向图（算法7.1），深度和广度遍历8.查找（理论8学时）教学内容：(1) 查找的基本概念，平均查找长度。(2) 基于线性表的查找：顺序查找、折半查找、索引表查找。(3) 基于树表的查找：二叉排序树、平衡二叉树。(4) 散列表：散列表的基本概念，散列函数的构造方法、处理冲突的方法、散列表的查找与分析。基本要求：了解查找的基本思想及查找成功和不成功的概念，掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相应的平均查找长度。要求学生掌握顺序查找、折半查找、树表的查找和散列表的查找。其中树表的查找重点在二叉排序树，平衡二叉树让学生知道基本概念即可，具体操作不做要求，B-树不要求。9.排序（理论6学时）教学内容：(1) 排序的基本概念，包括正序，逆序，稳定性，排序方法的分类。(2) 插入排序：直接插入排序、折半插入排序、2路插入排序和希尔排序。(3) 交换排序：冒泡排序和快速排序。(4) 选择排序：简单选择排序、锦标赛排序和堆排序。(5) 归并排序：2-路归并排序。(6) 排序算法分析：各种排序算法的比较和移动次数，时间复杂度和空间复杂度的分析。基本要求：了解排序的基本思想和基本概念，理解和掌握插入排序（直接插入排序、折半插入排序和希尔排序）、交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、归并排序和基数排序的基本思想。五、实践环节 该环节是强化动手能力培养及对技术细节知识掌握的重要组成部分，也是融会贯通各章知识内容的极好手段。通过上机调试运行自编程序，熟练掌握程序设计、调试程序的方法，进一步领会程序设计的特点。具体内容参加数据结构实验大纲。本课程的教学环节包括：课堂讲授、实验、实习、作业、答疑、小测验等。其中，课堂讲授以教师讲授为主，授课时将电子教案和板书相结合，充分发挥各自的优点。采用启发式教学，鼓励学生自学，培养学生的自学能力，以“少而精”为原则，精选教学内容，调动学生学习的主观能动性。实验针对相应单元所学的内容，能够采取合适的数据结构和算法解决有关问题。实验重点培养学生的动手能力。实习针对较为复杂的应用问题，能够综合运用所学的各种数据结构进行算法设计和实现，注重学生数据抽象能力和算法设计能力的培养。六、课外习题及课程讨论 本课程的基本概念比较多，运算的实现又与存储方式有关，因此习题的灵活性比较大，故需要专门的习题课将理论知识和习题结合起来讲授以启发学生对所学知识的灵活掌握；本课程所述数据结构与实际工作和生活紧密相连，故在讲授时可以采取课堂讨论的方式，让学生感受到数据结构的实际应用。七、教学方法与手段 多媒体教学为主，板书教学为辅；课堂讲授为主，鼓励提问和讨论。每章讲授完毕后，要求学生做完相应章节的书面作业并上交。八、各教学环节学时分配章 节理论学时实验学时总学时第1章绪论224第2章线性表101020第3章栈和队列8412第4章串404第5章 数组和广义表6410第6章树和二叉树10818第7章图10414第9章查找808第10章内部排序606合计643296九、考核方式 考核：闭卷，书面考试期末考试采用笔试形式，考试题型为：选择、填空、判断、简单题、算法分析题和应用题。总评成绩由平时成绩和期末成绩组成，其中平时成绩占30%（实验 20分、作业+日常考勤 10分），期末考试占70%。十、推荐教材