发布时间 : 星期一 文章10-11(2)新版数据结构授课计划64 - 图文更新完毕开始阅读dfa9e59bc4da50e2524de518964bcf84b8d52dd4
中山职业技术学院 授课计划
所属系部:计算机工程系 课程名称:数据结构 任课教师:张玉霞 授课班级:10软件2班
授课学期:10-11第2学期
教学大纲 （课程标准） 教材名称 (主编/书号) 《数据结构》课程标准，自编 《数据结构》（C++版），王红梅、胡明，王涛，清华大学出版社，2009 主要教参 (主编/书号) 《数据结构》（C++版）学习辅导与实验指导，王红梅、胡明，王涛，清华大学出版社，2009 《数据结构》（C++版）教师用书，王红梅、胡明，王涛，清华大学出版社，2009 《数据结构》，严蔚敏，清华大学出版社 总学时数 64 理论学时数 32 实践学时数 32 课程整体教学设计 1） 课程在本专业中的地位和作用。 数据结构是软件技术专业重要的专业基础课，在整个课程体系中处于承上启下的核心地位，它一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法，一方面为进一步学习操作系统、编译原理、数据库等专业课奠定坚实的理论与实践基础。本课程在教给学生数据结构设计和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和形式化思维方法，增强分析问题、解决问题和总结问题的能力，更重要的是培养专业兴趣树立创新意识。 2）课程教学目标 用数字计算机解决实际问题都离不开数据表示和数据处理，而数据表示和处理的核心问题致意是数据结构及实现——这正是数据结构课程的基本内容。从这个意义上说，数据结构课程在知识学习和技能培养两个方面都处于关键性地位。通过本课程的学习，应达到知识和技能两方面的目标： 1.知识方面：从数据结构及其实现的角度系统地学习和掌握常用基本数据结构及其不同的实现方法，了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同算法实现的原则和方法，为后继课程的学习打下良好的基础。 2.技能方面：通过对本课程的知识传递、算法设计和上机实践的训练，培养学生的数据抽象能力、逻辑思维能力和程序设计的能力，提高分析问题和解决问题的能力。 3）课程主要教学内容及组织 1.绪论（4学时） 教学内容：介绍数据结构中常用的基本概念和术语及学习数据结构的意义。 教学要求：熟练掌握数据结构的一些基本术语和概念，了解抽象数据类型定义和使用，了解算法的基本概念和术语，了解算法的描述方法，掌握算法的时间复杂性分析。 重点：了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，算法的概念和特性。 难点：算法时间复杂性分析方法。 2.线性表（8学时） 教学内容：介绍线性表的逻辑结构和存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。 教学要求：熟练掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；了解循环链表和双向链表的定义和它的插入、删除等操作方法。 重点：熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析。 难点：使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。 3.特殊线性表——栈、队列和串（8学时） 教学内容：介绍栈和队列的逻辑结构定义以及在存储结构上如何实现栈和队列的基本运算，介绍串的逻辑结构、存储结构及其串上的基本运算。 教学要求：熟练掌握栈和队列的定义，掌握顺序和链式存储的栈和队列的各种运算的方法及程序实现，掌握表达式求值等经典问题求解方法并了解其算法，掌握串的有关概念及基本运算，掌握串的存储结构，理解串的BF算法，了解KMP算法。 重点：熟练掌握栈和队列的特点；掌握栈和队列在两种存储结构上实现的基本运算。 难点：两栈共享空间；循环队列边界条件的处理；队满队空的判定条件，串的模式匹配算法。 4．广义线性表——数组和广义表（4学时） 教学内容：介绍数据的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念。 教学要求：掌握数组的逻辑结构特征及其存储方式，了解特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，了解广义表的逻辑结构和存储结构。 重点：掌握数组的存储方式。 难点：稀疏矩阵压缩存储表示下实现的算法。 5．树和二叉树（10学时） 教学内容：介绍树、二叉树等的有关概念、存储结构等方面。 教学要求：掌握树的定义、性质、存储结构，熟练掌握二叉树的定义、性质、存储结构及各种遍历算法与实现，掌握树与二叉树的转换，了解线索二叉树，了解树的遍历，了解哈夫曼树的定义，一般了解其应用，了解森林与二叉树转换等。 重点：掌握二叉树的性质及遍历算法及其有关应用。 难点：二叉树的非递归算法，使用本章所学到的有关知识设计出应用问题的有效算法。 6．图（10学时） 教学内容：介绍图的概念、两种常用的存储结构、两种遍历算法以及图的应用算法。 教学要求：掌握图的定义和术语；掌握邻接矩阵和邻接表表示法；熟练掌握图两种遍历的基本思想和算法；了解求图的最小生成树的prim和kruskal算法；了解最短路径问题和拓扑排序。 重点：掌握在图的两种存储结构上实现的遍历算法。 难点：求最小生成树，求最短路径以及拓扑排序。 7．检索技术（6学时） 教学内容：介绍关于线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。 教学要求：理解查找的基本概念，掌握线性表的顺序查找的思想和算法；理解二叉查找树的概念以及二叉查找树上查找的基本思想和算法；理解平衡二叉树的调整方法；理解哈希表、哈希表构造的基本方法以及处理冲突的方法；以及各种查找方法的时间性能分析。 重点：掌握顺序查找、折半查找，二叉查找树上查找的基本思想和算法实现。 难点：二叉查找树的删除算法。 8．排序技术（8学时） 教学内容：介绍内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。 教学要求：排序是计算机程序设计的重要运算，是数据处理的一项基本活动。掌握内部排序方法的指导思想和特点，熟悉各种内部排序算法并理解其基本思想；了解各种内排序算法的优缺点、时间和空间的性能比较以及使用场合。 重点：各种内排序的基本思想及内排序方法的执行过程。 难点：各种内排序方法的实现。 9．索引技术（2学时） 教学内容：各种索引结构的构造方法，各种索引结构基本操作（查找、插入、删除）的执行过程，各种索引结构的适用情况。 教学要求：掌握索引的基本概念，掌握稠密索引和分块索引及其查找过程，理解多重表和倒排表的