数据结构教学大纲.docx

数据结构课程教学大纲一、课程基本情况开课单位：计算机与信息工程系 课程编码：Z060106适用专业：高职高专计算机类各专业 修课方式：必修总 学 时： 6476学时 考核方式：考试教 材：陈雁.数据结构. 高等教育出版社. 2002年教学参考书：严尉敏 .数据结构. 清华大学出版社. 2003年苏德富 .数据结构. 重庆大学出版社. 2002年二、课程的性质、任务和目的数据结构是介于数学、硬件及软件三者之间的一门核心课程，它不仅是一般程序设计，尤其是非数值性程序设计的基础，而且是设计实现编译程序、操作系统、数据库系统、大型应用程序及其它系统程序的重要基础。所以数据结构从课程性质上讲是一门专业基础课。本课程的目的和任务就是训练学生对计算机加工的数据对象进行分析的能力，选择适当的数据结构、存贮结构及相应算法的能力，并且能够创造性地进行算法设计和程序设计，使所设计的程序结构清楚，正确易读，并上机调试通过。三、课程的主要内容与学时分配(一) 主要内容1数据结构概述 2学时1.1 数据结构研究的对象-数据、数据之间的关系1.2 实际问题抽象成数学模型-线性结构、层次结构、网状结构1.3 数据结构中使用的基本术语-数据、数据元素、数据项、数据对象、数据结构、存储结构1.4 数据结构的发展及它的地位-为什么要学习数据结构1.5 算法描述的语言及对算法分析的方法-算法、算法特征、时间复杂度，空间复杂度的分析2线性表 12 学时（6+2+4 ）2.1 顺序表的定义-存储原理、运算（查找、插入、删除）2.2 链式存储结构、运算-存储原理、运算（查找、插入、删除）2.3 循环链、双向链3栈和队列 8学时（6+2）3.1 栈的逻辑结构、栈的基本运算3.2 队列的基本运算、循环队列3.3 栈与队的应用4数组 6学时(4+*2)4.1 数组的概念4.2 特殊矩阵、稀疏矩阵的存储方法5串 2学时5.l 串的定义及基本运算5.2 串的存贮结构5.3 串的基本运算的实现模式匹配（KMP）6树 12学时（6+2+4）6.1 树的概念6.2 二叉树的概念6.3 二叉树的存储结构6.4 树的遍历6.5 线索树6.6 树的存储结构6.7 树、二叉树和森林之间的转换6.8 哈夫曼树（Huffman）算法及其应用（哈夫曼编码）7图 12学时（8+2+2）7.1 图的定义，术语7.2 图的存贮结构顺序链式存储7.3 图的遍历7.4 最小生成树7.5 拓扑排序7.6 最短路径7.7 关键路径8检索 10学时（6+2+2）8.1 顺序检索、有序检索、分块检索、散列表的检索8.2 二叉排序树8.3 平衡二叉排序树* 8.4 B_树9排序 8学时（6+2+2）9.1 插入排序9.2 快速排序9.3 选择排序9.4 堆排序9.5 归并排序9.6 基数排序9.7 内部排序方法的比较9.8 外部排序简介*10文件 2学时10.l 顺序文件10.2 索引文件10.3 直接存取文件10.4 多关键字文件(二) 学时分配序号章 节课 时 分 配理论课习题课实验课其它共计1数据结构概述2dd22线性结构表624123栈、队列6d284数组4d*265串2dd26树6*22+*2127图8*22128查找6*22109排序6*221010文件2dd2合 计481018d76四、课程教学基本要求及重点1数据结构概述：了解数据结构研究的对象、数据结构的发展及地位，掌握实际问题抽象成数学模型的概念、数据结构中使用的基本术语和算法描述的语言及算法分析的方法。具体为：学会分析数据结构研究的对象 -数据、数据之间的关系；会将实际问题抽象成数学模型 -线性结构、层次结构、网状结构；掌握数据结构中使用的基本术语 -数据、数据元素、数据项、数据对象、数据结构、存储结构；了解数据结构的发展及它的地位 -为什么要学习数据结构；掌握算法描述的语言及对算法分析的方法 -算法、算法特征、时间复杂度，空间复杂度的分析。重点：概念、算法分析的方法。难点：算法分析的方法。2线性结构熟练掌握顺序表的定义、向量 (或一维数组)的存储、插入、删除元素等运算。掌握链式表的建立、插入、删除元素等运算。熟悉链表的连接，多项式的加、减运算等操作。熟悉循环链、双向链的操作。重点：概念、基本运算实现方法。难点：应用。3栈、队列掌握栈的定义，顺序栈存储结构和链式栈存储结构的建立、基本操作（运算）。熟悉栈在计算表达式中的应用、栈与递归过程。掌握循环队列的操作和实现，应用。熟悉队列的定义，顺序队列（循环队列）存储结构和链式队列存储结构的建立、基本操作（运算）。熟悉队列的应用。重点：概念、栈和队列基本运算实现方法。难点：栈和队列的应用。4数组掌握数组的定义、数组的顺序表示和实现；掌握特殊矩阵： 三角矩阵、对称矩阵及稀疏矩阵的定义、存储方法，地址计算式；熟悉稀疏矩阵的十字链表存储方法；熟悉特殊矩阵的一些算法。重点：概念、存储方法，地址计算式；难点：应用。5串掌握串的定义及基本运算；掌握串的存贮结构；掌握串基本运算的实现；熟悉串的基本运算的实现 -模式匹配（KMP）。重点：串的定义及基本运算。6树熟练掌握树的概念、二叉树的概念、二叉树的性质、完全二叉树、满二叉树的概念和特点；掌握二叉树的存储结构（顺序存储和链式存储）；掌握二叉树的遍历算法（使用栈的遍历）前序、中序和后序；掌握线索树的概念，线索方法；掌握树的存储结构、树、二叉树和森林之间的转换、哈夫曼树（ Huffman）算法及其应用（哈夫曼编码）。重点：二叉树的概念、二叉树的性质、完全二叉树、满二叉树的概念和特点；二叉树的遍历。难点：遍历过程、线索树的线索方法。7图熟练掌握图的定义，术语、图的存贮结构、图的两种遍历方法；掌握最小生成树的 Kruskal和Prim两种生成过程，掌握Prim算法。掌握拓扑排序、最短路径、关键路径的算法思想。重点：图的定义，术语、图的存贮结构、图的两种遍历方法；难点：拓扑排序、最短路径、关键路径的算法思想。8排序熟练掌握插入排序、快速排序、选择排序、堆排序、归并排序和基数排序的思想、算法、时间和空间复杂度；会对各种内部排序方法进行时间和空间复杂度的比较；熟悉外部排序方法。重点：插入排序、快速排序、选择排序、堆排序、归并排序和基数排序的思想、算法、时间和空间复杂度分析。难点：各排序方法的使用情况和比较。9检索熟练掌握顺序检索、二分检索、分块检索、散列表的检索的方法；掌握顺序检索中监视哨的作用。掌握散列的基本思想、处理冲突常用的方法；掌握用除余法构造散列函数的方法、掌握用开放地址法（重点：线性探测再散列）和拉链处理冲突的方法；掌握二叉排序树、平衡二叉排序树的概念；掌握二叉排序树、熟悉平衡二叉排序树构造方法。熟悉 B_树的概念。重点：各种检索的思想、算法、时间和空间复杂度分析。难点：二叉排序树构造机删除方法、平衡二叉排序树构造方法。10文件熟悉顺序文件、索引文件、直接存取文件和多关键