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

1、PAGE PAGE 10数据结构教学大纲课程基本情况课程名称：数据结构 （Data Structure）课程编号：71001410课程总学时：108学时（授课72学时，实验36学时）课程学分：5学分课程分类：专业必修课开设学期：第三学期适用专业：计算机科学与技术（师范/非师范、软件工程、网络与信息安全、物联网工程）先修课程：离散数学、线性代数、高级语言后续课程：数据库，编译原理，操作系统等（一）课程性质 数据结构是计算机专业的一门核心专业课程，是软件课程中非常重要的一门课程，在整个专业教学中占有十分重要的地位，是一门理论性非常强的课程。通过课堂教学、课外练习和上机实习，使学生了解数据对象的特性

2、，数据组织的基本方法，并初步具备分析和解决现实世界问题在计算机中如何表示和处理的能力以及培养良好的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。（二）教学目的数据结构课程作为计算机专业重要的主干课程，它要求学生学会分析和研究需解决的问题中的数据的特性，为其选择合适的数据结构来描述，在此数据结构的基础上写出相应的算法，并初步掌握算法的时间复杂度和空间复杂度的分析技术。另一方面，通过本课程的学习，培养和训练学生编写复杂程序的能力，要求编写的程序结构清楚、正确易读，符合软件工程的规范，使学生的编程能力有一个质的提高。（三）教学内容 数据结构系统地介绍线性表、栈、队列、字符串、数组、广

3、义表、树、二叉树、图、查找表、内部排序、外部排序等常用数据结构的基本概念、操作及其典型应用例子。在知识方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法，使学生了解数据对象的特性，数据组织的基本方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。（四）教学时数 共108学时，其中授课72学时、上机实验36学时。（五）教学方式 采用课堂教学和上机实验相结合的方式。二、教学主要内容理论部分第1章 绪论教学要点： 了解数据结构的意义与发展过程、数据结构在计算机科学中的作用、学习本课程的目的、任务及要求。理解数据结构的基本概念、算法设计方法、掌握

4、算法的时间和空间复杂度。教学时数：2学时教学内容：1.1 什么是数据结构（0.5学时） 了解数据结构的发展历史、应用及其重要性1.2 基本概念和术语（0.5学时）熟练掌握数据结构的基本概念，包括数据、数据对象、数据元素、数据结构以及数据的逻辑结构、存储结构和算法。1.3 抽象数据类型的表示与实现（0.5学时） 熟练掌握用类高级语言描述抽象数据类型的目的和意义。1.4 算法和算法分析（0.5学时）掌握算法的基本概念，算法的设计要求，算法效率的度量（时间复杂度、空间复杂度），算法的存储空间需求第2章 线性表教学要点： 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两

5、类不同的存储结构是顺序存储结构和链式存储结构；熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现；能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合；掌握用线性表来表示一元多项式的方法及相应操作的实现。教学时数：6学时教学内容：2.1 线性表的类型定义（1学时） 掌握线性表的基本概念，包括什么是线性表、数据元素、数据项、记录、文件，以及线性表的抽象数据类型描述。2.2 线性表的顺序表示和实现 （2学时） 熟练掌握线性表如何顺序存储、存储地址的计算方法，线性表顺序存储后的基本操作（包括建立、查找、插入、删除等），以及插入、删除等操作的时间、空间复杂度的分析

6、和计算。 2.3 线性表的链式表示和实现 （2学时）熟练掌握线性表如何链式存储（包括单链表、循环链表、双链表等），线性表的各种链式存储的基本操作（包括建立、查找、插入、删除等），以及操作的时间、空间复杂度的分析和计算。2.4 一元多项式的表示及相加 （1学时） 掌握一元多项式的分析、存储，以及2个一元多项式的相加、相减等操作。第3章 栈和队列教学要点： 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们；熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法；熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法；理解递归算法执行过程中栈的状态变化

7、过程。教学时数：6学时教学内容：3.1 栈 （0.5学时） 掌握抽象数据类型栈的定义，栈的表示与实现。3.2 栈的应用举例 （0.5学时） 了解数制转换、括号匹配的检验、行编辑程序、迷宫求解、表达式求值。3.3 栈与递归的实现 （2学时） 熟练掌握栈在递归中的应用。3.4 队列 （2学时） 熟练掌握抽象数据类型队列的定义、队列的链式表示和实现、循环队列的表示和实现。3.5 离散事件模拟 （1学时） 掌握队列的此应用。第4章 串教学要点： 熟悉串的定义及串的基本操作；熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法；了解串的堆存储结构及块链存储结构；掌握串的模式匹配算法的基本算法和改进算法

8、。教学时数： 4学时教学内容：4.1 串类型的定义 （0.5学时） 掌握串的基本概念，串的抽象数据类型定义4.2 串的表示和实现 （1.5学时） 掌握串的顺序存储、堆分配存储以及串的块链存储表示。4.3 串的模式匹配算法 （2学时） 掌握串的基本模式匹配算法和模式匹配的改进算法。4.4 串操作应用举例 （选讲） 了解文本编辑和建立词索引表。第5章 数组和广义表教学要点： 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；掌握对特殊矩阵进行压缩存储时的下标变换公式；了解稀疏矩阵的三类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；了解

9、广义表的结构特点及其存储表示方法。教学时数：6学时教学内容：5.1 数组的定义 （0.5学时） 了解数组的顺序存储和链接存储方法，并掌握数组在以行为主的存储结构中的地址计算方法。5.2 数组的顺序表示和实现（0.5学时） 熟练掌握数组的顺序表示方法及实现。5.3 矩阵的压缩存储 （2学时） 熟练掌握特殊矩阵和稀疏矩阵的存储以及相应的操作。5.4 广义表的定义 （1学时） 了解广义表的基本结构及定义，广义表的抽象数据类型定义。5.5 广义表的存储结构 （2学时）掌握广义表的链式存储及基本操作。5.6 m元多项式的表示 （选讲）5.7 广义表的递归算法 （选讲）第6章 树和二叉树教学要点： 熟练掌

10、握二叉树的结构特性(五个性质)，了解相应的证明方法；熟悉二叉树的各种存储结构的特点及适用范围；遍历二叉树是二叉树各种操作的基础，熟练掌握各种遍历策略的递归算法，了解其非递归算法；理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法；熟悉树的各种存储结构及其特点，掌握树和森林与二叉树之间的相互转换方法；了解Huffman树的特性，掌握建立Huffman树和Huffman编码的算法教学时数： 8学时教学内容：6.1 树的定义和基本术语 （1学时） 熟练掌握树的定义，以及与树相关的一系列概念。6.2 二

11、叉树 （1学时） 熟练掌握二叉树的定义、性质和存储结构。6.3 遍历二叉树和线索二叉树 （2学时） 熟练掌握二叉树的前序、中序、后序遍历的递归以及非递归算法；熟练掌握按中序线索化二叉树的过程，了解按前序和后序线索化二叉树的方法。6.4 树和森林 （2学时） 熟练掌握树的存储、森林与二叉树的转换方法、树和森林的遍历。6.5 树与等价问题（选讲）6.6 赫夫曼（Huffman）树及其应用 （2学时）了解Huffman树的特性，掌握建立Huffman树和Huffman编码的算法。6.7 回溯法与树的遍历 （选讲）6.8 树的计数 （选讲） 第7章 图教学要点： 熟悉图的各种存储结构及其构造算法，了解

12、实际问题的求解效率与采用何种存储结构和算法有密切联系；熟练掌握图的两种搜索路径（深度优先和广度优先）的遍历算法，注意图的遍历算法与树的遍历算法之间的类似和差异；熟练掌握求最小生成树的Prim算法和Kruskal算法；熟练掌握求最短路径的Dijkstra算法，了解求任意两点之间的最短路径的Floyd算法；掌握求拓扑排序的算法及其应用，了解求关键路径的方法及其应用。教学时数：10学时教学内容：7.1 图的定义和术语 （0.5学时） 熟练掌握图的基本概念和术语。7.2 图的存储结构 （1.5学时） 熟练掌握图的数组表示法、邻接表、十字链表、邻接多重表的存储结构。7.3 图的遍历 （2学时） 熟练掌握

13、图的深度优先遍历和广度优先遍历的算法。7.4 图的连通性问题（2学时） 熟练掌握无向图的连通分量和求最小生成树的Prim算法和Kruskal算法。7.5 有向无环图及其应用 （2学时）熟练掌握求最短路径的Dijkstra算法，了解求任意两点之间的最短路径的Floyd算法；掌握求拓扑排序的算法及其应用。7.6 最短路径（2学时）了解求关键路径的方法及其应用。第8章 动态存储管理教学要点： 掌握边界标识法和伙伴系统；无用单元收集和紧缩。教学时数： 6学时教学内容：8.1 概述 （0.5学时） 了解动态存储管理的目的、意义。8.2 可利用空间表及分配方法（1.5学时） 掌握可利用空间表的3种分配方法

14、。8.3 边界标识法 （2学时） 掌握边界标识法的分配和回收算法。8.4 伙伴系统 （2学时） 了解伙伴系统的可利用空间结构、分配算法和回收算法。8.5 无用单元收集 （选讲）8.6 存储紧缩（选讲）第9章 查找教学要点： 熟练掌握顺序表和有序表的查找方法及其平均查找长度的计算方法；熟练掌握二叉排序树的构造和查找方法，掌握在二叉排序树上插入结点和删除结点的算法；熟练掌握平衡二叉树(AVL树)的定义及平衡旋转技术，了解其相应的算法；简单了解B-树、B+树的特点以及它们的建树和查找的过程；熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握按定义计算各种查找方法在等概率情况下

15、查找成功时的平均查找长度。教学时数：8学时教学内容：9.1 静态查找表 （2学时） 熟练掌握顺序表和有序表的查找方法及其平均查找长度的计算方法9.2 动态查找表 （4学时） 熟练掌握二叉排序树的构造和查找方法，掌握在二叉排序树上插入结点和删除结点的算法；熟练掌握平衡二叉树(AVL树)的定义及平衡旋转技术，了解其相应的算法；简单了解B-树、B+树的特点以及它们的建树和查找的过程；9.3 哈希表 （2学时） 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。第10章 内部排序教学要点： 了解排序的定义和各种排序方

16、法的特点，熟悉各种方法的排序过程及其依据的原则；熟练掌握直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序的实现算法；掌握各种排序方法的时间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能；了解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的教学时数： 8学时教学内容：10.1 概述 （0.5学时） 了解排序的概念及意义。10.2 插入排序 （1.5学时） 熟练掌握直接插入排序、其他插入排序、希尔排序的实现算法。10.3 快速排序 （1学时） 熟练掌握快速排序的实现算法。10.4 选择排序 （2学时） 熟练

17、掌握简单选择排序、树形选择排序、堆排序的实现算法。10.5 归并排序 （1学时）熟练掌握归并排序的实现算法。10.6 基数排序 （1学时） 了解基数排序的实现算法。10.7 各种内部排序方法的比较讨论（1学时）掌握各种排序方法的时间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能；了解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的第11章 外部排序教学要点： 理解外部排序的基本方法；掌握多路平衡归并的实现；了解置换-选择排序、最佳归并树。教学时数：4学时教学内容：11.1 外存信息的存取 （0.5学时） 了解外存信息的

18、存取方法。11.2 外部排序的方法 （1.5学时） 理解外部排序的基本方法11.3 多路平衡归并的实现 （2学时） 掌握多路平衡归并的实现。11.4 置换选择排序 （选讲）11.5 最佳归并树 （选讲） 第12章 文件教学要点： 掌握文件的基本概念，对顺序文件、索引文件、直接存取文件、多关键字文件等有一定程度的了解。教学时数：6学时教学内容：12.1 有关文件的基本概念 （1学时） 掌握文件的基本概念。12.2 顺序文件 （1学时） 了解顺序文件的概念及存取方法。12.3 索引文件 （1学时） 了解索引文件的概念及存取方法。12.4 ISAM文件和VSAM文件 （1学时） 了解ISAM文件和V

19、SAM文件文件的概念及存取方法。12.5 直接存取文件 （1学时）了解直接存取文件的概念及存取方法。12.5 多关键字文件（1学时）了解索引文件的概念及存取方法。实验部分（一）基本要求 本课程是一门实践性很强的专业课，只有了解这门课程的特点和基本要求，学习时才能做到有的放矢，举一反三，本课程特点主要有以下几个方面：(1) 内容丰富，理论性强。本课程为以后学习专业基础课和专业课（如：计算机操作系统、数据库原理等）打下良好的基础。(2) 注重理论联系实际，加强实验环节的训练。只有通过实验，才能透彻理解基本原理。（二）实验项目总表 序号项目名称项目类别项目类型项目学时1线性表的顺序存储实验基础性必做

20、22线性表的链式存储实验基础性必做43顺序栈的实现及表达式的括号匹配综合性必做44队列的顺序与链式实现综合性选做45实现二叉树的建立与遍历综合性必做66实现有向图的拓扑排序综合性必做47实现多种（至少4种）排序算法及它们的时间测试综合性必做48三元组法实现稀疏矩阵的转置设计性选做49静态查找树的构造和查找设计性选做4（三）实验项目内容及要求 实验要求的设备为计算机，统一在计算机实验室完成。实验项目共9个，项目类别分为基础性、综合性和设计性三种，实验项目类型分为必做和选做。要求学生在36学时必须完成必做项目，在完成的基础上实现选做项目。实验一 线性表的顺序存储实验1、实验目的及要求：了解线性表的

21、顺序存储方法，掌握在VC环境下上机调试顺序表的基本方法。掌握顺序表的插入、删除、查找、求表长以及有序顺序表的合并算法的实现2、实验内容及学时分配： （2学时）顺序表基本操作的实现有序顺序表的合并，已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的非递减有序顺序表lc，并且不破坏la和lb表实验二 线性表的链式存储实验1、实验目的及要求：掌握用在VC环境下上机调试单链表的基本方法掌握单链表、循环链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现2、实验内容及学时分配： （4学时）单链表基本操作的实现有序单链表的合并，已知单链表la和lb中的数

22、据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列，要求不破坏la表和lb表的结构。实验三 顺序栈的实现及表达式的括号匹配1、实验目的及要求：掌握栈的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。掌握栈的特点，即先进后出的原则。掌握栈的基本操作实现方法。2、实验内容及学时分配： （4学时）实现栈的顺序存储及其插入、删除操作利用栈求表达式的值实验四队列的顺序与链式实现1、实验目的及要求：掌握队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。掌握队列的特点，即先进先出的原则。掌握队列的基本操作实现方法。2、实验内容及学时分配： （4学时，选做）实现队列的顺序存储及其插入、删除操作实现队列的链式存储及其插入、删除操作实验五 实现二叉树的建立与遍历1、实验目的及要求：掌握二叉树的二叉链表存储掌握二叉树的遍历算法2、实验内容及学时分配： （6学时）以二叉链表作存储结构，编写前序、中序、后序顺序遍历二叉树的算法。以二叉链表作存储结构，编写计算二叉树深度、叶子结点数的算法实验六 实现有向图的拓扑排序1、实验目