内容发布更新时间 : 2024/5/17 15:58:51星期一 下面是文章的全部内容请认真阅读。

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

Data Structure

执笔人： 编写日期：

一、课程基本信息

1. 课程编号：

2. 课程性质/类别： 必修课 / 专业主干课

3. 学时/学分： 48 学时（另实验16学时） / 4 学分

4. 适用专业：计算机科学与技术、软件工程、网络工程、信息管理与信息系统等专业

二、课程教学目标及学生应达到的能力

数据结构课程是计算机相关专业的专业基础课、必修课程，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。通过本课程的学习，要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，培养学生分析问题、解决问题的能力，并为后续课程的学习打下良好的理论基础和实践基础。

三、课程教学内容与基本要求

（一）绪论（ 3 学时） 1．主要内容：

（1）介绍什么是数据结构；

（2）基本概念和术语: 数据、数据元素、数据对象，以及数据结构的定义、逻辑结构、物理结构（理解）数据类型、抽象数据类型；

（3）抽象数据类型的表示与实现；

（4）算法和算法分析: 算法的概念、算法设计的要求以及算法效率的度量。 2．基本要求

（1）了解学习数据结构的重要性；

（2）掌握数据结构的定义及相关概念和术语； （3）了解抽象数据类型的定义、表示与实现方法； （4）理解算法的概念、特点并掌握度量其效率的基本方法。 3．自学内容：

类C语言的书写规范。 （二）线性表（ 6 学时） 1．主要内容：

（1）线性表的抽象数据类型定义和相关概念：数据项、记录、文件等； （2）线性表顺序存储表示和基本操作的实现； （3）线性表的链式存储表示和基本操作的实现；

（4）稀疏多项式的抽象数据类型定义、表示和加法的实现。

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）熟悉两种最短路径问题求解算法。