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

数据结构课程教学大纲DataStructure总学时数：64其中：实训学时：18课外学时：0学分数：4适用专业：信息与计算科学一、课程的性质、目的和任务《数据结构》是信息与计算科学专业本科生的必修专业课程之一，主要介绍非数值计算领域计算机所处理的数据对象如数组，顺序表，字符串，链表，栈，队列，树，二叉树，集合，图等的逻辑关系、存储结构以及对这些数据的基本操作；介绍递归、搜索及排序的算法设计及应用。通过本课程的学习，使学生掌握各种数据结构的特点、存储方法、基本算法及一些基本应用，培养学生良好的编程风格和能力，编制高效可靠的程序，为后续课程的学习打下良好基础。课程采用面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C++语言作为算法的描述工具，强化数据结构基本知识和面向对象程序设计基本能力的双基训练。二、课程教学的基本要求1.了解数据结构及其分类、数据结构与算法的密切关系。2.熟练掌握常用的基本数据结构（包括数组、顺序表、字符串、链表、栈与队列、优先级队列、广义表、树与森林、二叉树、堆、集合、图、搜索结构、索引结构、散列结构等）的类定义和对象的使用、存储表示和操作的实现。3.了解并掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法。4.掌握对象类的设计方法及面向对象的程序设计风格，实现不同存储结构的算法。5.学会数据结构在排序和搜索等常用算法中的应用。三、课程的教学内容、重点和难点第一章绪论1.数据、数据元素、数据对象、数据结构、数据的逻辑结构与物理结构、数据结构的抽象层次。抽象数据类型及面向对象。3.算法及算法的描述、算法的时间复杂度和空间复杂度。重点:重点:数据结构、数据的逻辑结构与物理结构。难点:算法的时间复杂度。第二章数组1.数组的基本概念、逻辑结构、顺序存储结构，一维数组、二维数组的地址计算方法。2.顺序表的定义和特点，顺序表的类定义及其主要操作，如插入、删除和查找的实现。3.字符串的定义字符串抽象数据类型的类定义，字符串中各种重载操作的实现和使用，简单的模式匹配算法和匹配事例。重点：重点：数组的按行顺序存储及存放地址计算；数组的逻辑结构、存储结构以及插入、删除和查找算法。难点:数组的逻辑结构、存储结构以及插入、删除和查找算法；字符串重载操作的定义与实现。第三章链表1.单链表类定义的复合方式，单链表的搜索、插入、删除算法。2.循环链表与单链表的异同；3.双向循环链表的定义，搜索、插入与删除算法。重点：带表头结点单链表、带表头结点单循环链表的类定义及搜索、插入与删除算法；带表头结点双循环链表的类定义及搜索、插入与删除算法。重点：带表头结点单链表、带表头结点单循环链表的类定义及搜索、插入与删除算法；带表头结点双循环链表的类定义及搜索、插入与删除算法。难点:带表头结点单循环链表的搜索、插入与删除算法；带表头结点双循环链表的搜索、插入与删除算法。第四章栈和队列1.栈的特性，栈的顺序存储结构（数组）实现，栈的链式存储结构实现，栈满及栈空条件,栈的应用。2.队列的特性，队列的顺序存储结构（数组）的实现，队列的链式存储结构的实现，循环队列中队头与队尾指针的表示，队满及队空条件，链式队列中队头与队尾指针的表示，队列的应用，优先队列的插入与删除算法。重点：重点：栈的数组实现、栈的链表实现：队列的数组实现、队列的链表实现，队列的应用。难点:队列的应用。第五章递归1.递归的定义、递归的数据结构、递归问题的递归求解方法，单向递归问题的递归解法和迭代解法。2.广义表的概念、性质，用图表示广义表的存储结构，广义表的递归算法包括复制、求深度等，广义表的表头、表尾操作。重点：重点：递归问题用递归过程求解；用图形表示广义表的存储结构，广义表的表头、表尾操作。难点:递归问题用递归过程求解。第六章树与森林1.树和森林的定义，树的抽象数据类型。二叉树的定义，二叉树的性质，二叉树的抽象数据类型，二叉树的数组表示和链表存储表示，二叉树的遍历，包括前序、中序、后序遍历方法。3.堆的定义极其实现方法，堆的建立、插入与删除过程。4.树/森林与二叉树的转换，树及森林的遍历方法。霍夫曼树的实现方法及霍夫曼编码的概念。重点：重点：二叉树的前序、中序、后序遍历的方法；堆的建立、插入与删除方法；树、森林与二叉树的转换；霍夫曼树的构造方法、霍夫曼编码方法、带权路径长度的计算。难点:二叉树的前序、中序、后序遍历的递归算法，堆的建立、插入与删除算法，霍夫曼树的构造算法，霍夫曼编码算法。第七章集合与搜索1.集合及其表示方法,包括位数组表示、有序链表表示及其相关操作的实现方法。2.等价类及并查集。3.搜索的概念，静态搜索表的顺序搜索和折半搜索算法及其性能分析方法。4.二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法。重点:重点:静态搜索表的顺序搜索和折半搜索算法；二叉搜索树的表示、搜索、插入、删除方法。难点:二叉搜索树的表示、搜索、插入、删除方法；。第八章图1.图的基本概念、图的存储表示。图的两种遍历算法：深度优先遍历算法和广度优先遍历算法。3.构造最小生成树的Kruskal和Prim算法。4.图的最短路径算法。AOV拓扑排序算法，AOE关键路径的计算。重点:重点:深度优先遍历算法和广度优先遍历算法；最小生成树的Kruskal和Prim算法；图的最短路径算法；AOE关键路径的计算。难点:最小生成树的Kruskal和Prim算法,图的最短路径算法,AOV拓扑排序算法，AOE关键路径的计算。第九章排序1.排序的基本概念。插入排序：直接插入排序算法、折半插入排序算法，链表插入排序算法的设计。3.交换排序：起泡排序算法、快速排序的递归算法的设计。4.选择排序：直接选择排序算法、链表选择排序算法的设计，堆排序算法。迭代的归并排序等内排序的方法及其性能分析方法。多路平衡归并等外排序方法。重点:重点:直接插入排序算法、折半插入排序算法、起泡排序算法、堆排序算法。难点:起泡排序算法、堆排序算法。第十章索引与散列1.静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法。2.掌握散列法，包括散列函数的构造，散列表分析。重点:重点:散列表与散列方法。难点:散列函数的构造。四、课程各教学环节要求本课程以课堂教学和实验并行的方式教学，其中，内容讲授46课时，实验（上机）18课时。课堂教学采用以多媒体投影教学为主的方式进行，实验在《微机实验室》进行。五、学时分配章节主要内容各教学环节学时分配作业题量备注讲授实验讨论习题课外其它小计一绪论441二数组5272三链表64101四栈和队列3251五递归22六树与森林6288七集合与搜索4262八图6286九排序6282十索引结构与散列4261合计46186424附：其中上机实验安排如下实验1：数组实验目的：学习程序设计中数组线性结构数据的处理实验要求：掌握数组数据结构数据的处理实验设备：VisualC++6实验内容：将有关数组的算法转换为C++语言实现之实验学时：2学时实验2：顺序表实验目的：学习程序设计中顺序表线性结构数据的处理实验要求：掌握顺序表数据结构数据的处理实验设备：VisualC++6实验内容：将有关顺序表的算法转换为C++语言实现之实验学时：2学时实验3：单链表实验目的：学习程序设计中单链表线性结构数据的处理实验要求：掌握单链表数据结构数据的处理实验设备：VisualC++6实验内容：将有关单链表的算法转换为C++语言实现之实验学时：2学时实验4：栈和队列实验目的：学习栈和队列结构的处理实验要求：掌握队列的常用操作实验设备：VisualC++6实验内容：将有关栈和队列的算法转换为C++语言实现之实验学时：2学时实验5：二叉树实验目的：学习程序设计中二叉树型数据结构的处理实验要求：掌握二叉树前序遍历算法设计实验设备：VisualC++6实验内容：将二叉树中的前序遍历算法转换为C++语言实现之实验学时：2学时实验6：散列实验目的：学习程序设计中散列表数据结构的处理实验要求：掌握建立散列表并进行线性探测冲突算法设计实验设备：VisualC++6实验内容：将散列表的建立算法转换为C++语言实现之实验学时：2学时实验7：搜索实验目的：学习程序设计中各种搜索方法实验要求：掌握各种常用的搜索方法实验设备：VisualC++6实验内容：将有关搜索的算法转换为C++语言实现之实验学时：2学时实验8：图实验目的：学习程序设计中图数据结构的处理实验要求：初步掌握图数据结构的处理实验设备：VisualC++6实验内容：将图数据结构中的有关算法转换为C++语言实现之实验学时：2学时实验9：排序实验目的：学习程序设计中各种排序方法实验要求：掌握各种常用的排序方法实验设备：VisualC++6实验内容：将有关排序的算法转换为C++语言实现之实验学时：2学时六、课程与其它课程的联系《数据结构》是信息专业的一门专业课程，它的先修课为《离散数学》和《C++语言程序设计》。学生通过这门课程的学习，进一步提高软件设计和编程水平。七、教材与教学参考书(一)教