《数据结构》课程教学大纲

2．基本要求（1）掌握线性表的定义和特点;（2）熟练掌握线性表的顺序存储表示和插入、删除、查找等实现算法；（3）熟练掌握单链表、循环链表、双向链表三种链表的表示,以及单链表的查找、插入、删除、创建等实现算法。3．自学内容：静态链表。（三）栈和队列（5学时）1．主要内容：（1）栈和队列的结构特性和抽象数据类型定义；（2）栈和队列的顺序存储表示和实现；（3）栈和队列的链式存储表示和实现;（4）栈和队列在程序设计中的应用。2．基本要求（1）掌握栈和队列两种抽象数据类型的特点;（2）掌握栈的两种存储表示和实现，特别注意栈满栈空的条件；（3）掌握队列的两种存储表示和实现，特别注意队满队空的条件；（4）了解递归算法与栈的关系.3．自学内容：链栈，离散事件模拟（四）串（3学时）1．主要内容：（1）串的抽象数据类型定义;（2）串的表示和实现:定长顺序存储结构和堆分配存储结构;（3）串的各种基本操作的实现及其应用；（4）串的模式匹配操作。2．基本要求（1）熟悉串的一些基本操作的定义，并能利用基本操作实现串的其它操作；（2）掌握串的定长顺序存储结构以及基本操作的实现；（3）掌握串的堆分配存储结构以及基本操作的实现;（4）掌握串的简单模式匹配算法，理解KMP算法。3．自学内容：串操作的应用实例。（五）数组和广义表（4学时）1．主要内容:（1）数组的抽象数据类型定义及其顺序表示和实现;（2）特殊矩阵和稀疏矩阵的压缩存储;（3）广义表的抽象数据类型定义和存储结构。2．基本要求（1）了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；(2)掌握对特殊矩阵进行压缩存储时的下标变换公式;(3)熟悉稀疏矩阵的三元组顺序表存储结构下的一般转置和快速转置算法;了解十字链表等存储结构;(4)掌握广义表的结构特点、取表头表尾操作,及其存储表示方法。3．自学内容：采用十字链表存储结构创建稀疏矩阵。(六)树和二叉树(10学时)1．主要内容：(1)树的抽象数据类型定义和基本术语；(2)二叉树的抽象数据类型定义、性质和存储结构；(3)二叉树的遍历；(4)线索二叉树的定义、遍历及线索化二叉树;(5)树的存储结构、树和森林的遍历以及与二叉树的转换；(6)Huffman树及其应用。2．基本要求(1)掌握树型结构的特点和基本术语；(2)熟练掌握二叉树的性质，了解相应的证明方法；(3)了解二叉树的顺序存储结构和链式存储结构，熟练掌握二叉链表存储结构；(4)熟练掌握二叉树三种遍历的递归算法和中序遍历非递归算法，能灵活运用遍历算法实现二叉树的其他操作；(5)熟练掌握二叉树的线索化过程,以及在中序线索二叉树上找结点的前驱与后继的方法；(6)熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法；(7)了解Huffman树的特性，掌握建立Huffman树和Huffman编码的方法。3．自学内容：先序、后序遍历二叉树非递归算法,层次遍历二叉树算法.(七)图(9学时)1．主要内容:(1)图的定义和术语；(2)图的四种存储结构:数组表示法(邻接矩阵)、邻接表、十字链表和邻接多重表；(3)图的两种遍历策略：深度优先遍历和广度优先遍历；(4)图的连通性和最小生成树；(5)有向无环图及其应用：拓扑排序和关键路径;(6)最短路径问题。2．基本要求(1)熟悉图的定义和术语；(2)了解图的存储结构，熟练掌握数组表示法(邻接矩阵)和邻接表存储表示；(3)熟练掌握图的深度优先遍历和广度优先遍历算法；(4)掌握无向连通带权图的最小生成树求解算法；(5)了解有向无环图、AOV网、AOE网及其在实际中的应用，熟悉拓扑排序算法和关键路径算法；(6)熟悉两种最短路径问题求解算法。3．自学内容：树的先根遍历算法与图的深度优先遍历算法比较；树的层次遍历算法与图的广度优先遍历算法比较。（八）查找（4学时）1．主要内容：（1）查找的基本概念和相关术语；（2）静态查找表：顺序查找、折半查找和索引顺序表查找;（3）动态查找表：二叉排序树的查找、插入和删除；（4）哈希表.2．基本要求（1）了解查找的作用，熟悉相关术语；（2）熟练掌握顺序查找、折半查找和索引顺序表查找;（3）熟练掌握二叉排序树的特性、构造和查找方法；（4）熟练掌握哈希表的构造方法，特别是哈希函数和处理冲突方法的选取;（5）通过分析等概率下的平均查找长度来衡量各种查找方法的效率.3．自学内容：平衡二叉树。（九）内部排序（4学时）1．主要内容：（1）排序的基本概念和相关术语;（2）插入排序:直接插入排序、折半插入排序和希尔排序;（3）交换排序:起泡排序和快速排序;（4）选择排序:简单选择排序和堆排序；（5）归并排序:二路归并排序；（6）基数排序：链式基数排序；（7）各种内部排序方法的比较讨论。2．基本要求（1）了解排序作用，熟悉相关术语；（2）掌握多种排序的基本思想、算法特点和排序过程，分析它们的时间复杂度、空间复杂度和稳定性。3．自学内容：二路插入排序、表插入排序和树形选择排序。四、教学安排建议作业练习完成每章的教学后进行布置习题，使用教材配套的《数据结构题集（C语言版）》。尽量选择基础的并且加注了标记的题，应注重于精，而不要求多。要求积极独立完成所布置的习题，建议安排至少六次.案例分析可参考选择以下一些案例：（1）学生通讯录管理系统,（2）表达式求值问题（3）交通咨询系统，等。专题研讨可参考选择以下一些：（1）最小生成树问题（2）航班信息查询与检索系统，（3）内部排序算法比较，等。实验安排为了达到理论与实际应用的结合，让学生能将所学知识应用于实际问题的求解中，培养学生的实际动手能力，从而加深对概念及所学知识的理解,灵活、牢固掌握教材内容，提高程序设计及解决实际问题的能力,实验环节的安排非常重要。建议实验安排为八次，共16学时，分别如下：实验1线性表的顺序存储结构的实现（2学时）实验2线性表的链式存储结构的实现（2学时）实验3栈的算法实现（2学时）实验4队列的算法实现（2学时）实验5串类型及操作（2学时）实验6二叉树的建立与遍历（2学时）实验7图的建立与遍历（2学时）实验8查找与排序（2学时）注：教师可根据教学实际情况（如：学生情况及学时情况等）,适当调整实践教学内容及学时分配。五、课程考核考核形式及成绩评定办法本课程考核形式为：平时成绩占40％，期末考试成绩占60％。其中平时成绩的结构分包括：课堂表现10%、平时作业10％和实验20%，期末考试为闭卷笔试考试：120分钟，卷面分满分100分。期末考试成绩低于50分者，本课程成绩按不及格论处。本课程考核的基本要求课堂表现10％：包括课堂考勤和课堂提问，如果缺课课时达到本课程教学时数的1/3,则取消考试资格。平时作业10%：根据上交次数及完成情况进行评定.实验20％：根据各次实验完成情况及实验报告成绩进行评定。期末考试60%：本课程的期末考试考核内容主要包括线性表、栈与队列、串、数组与广义表、树与二叉树、图、查找和内部排序.其中,线性表、二叉树、图、查找和内部排序内容为考核的重点。六、本课程与其它课程的先行后续关系先行课程：《高级程序设计语言》、《离散数学》后续课程:《操作系统》、《编译原理》、《数据库理论》、《算法分析与设计》等七、建议教材及教学参考书。教材：严蔚敏，吴伟民编著，《数据结构（C语言版）》，清华大学出版，2012。5严蔚敏，吴伟民编著，《数据结构题集（C语言版）》，清华大学出版，2012。5.参考书：许卓群，张乃孝，杨冬青，唐世渭，《数据结构》，高等教育出版社，2004.徐孝凯，《数据结构简明教程》,清华大学出版社，1995[3]陈文博,朱青，《数据结构与算法》，机械工业出版社，1996[4]李云清，杨庆红，揭安全编著，《数据结构》（C语言版），人民邮电出版社，2007.杨秀金主编，《数据结构》，西安电子科技大学出版社,2002.李廉治,姜文清，郭福顺，《数据结构》，大连理工大学出版社，19897]AhoAV，HopcroftJE，UllmanJD.DataStructuresandAlgorithms.Addison-WesleyPublishingCompany,Inc.,1983BaronRJ，ShapiroLG。DataStructuresandtheir