《数据结构》教学大纲
Data Structure
课程编号：J6110G0003 课程性质：学科基础课程
适用专业：计算机科学与技术、网络工程、数字媒体技术 先行课：计算机科学导论、离散数学、高级语言程序设计； 后续课：无 。 学分数：5
主讲教师：任燕、王命延、冯豫华、周石林、王玮立等
一、课程的目的与任务
数据结构是信息与计算科学专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。
本课程的目的是使学生掌握数据组织、存储和处理的常用方法，为以后进行软件开发和学习后续专业课程打下基础。主要任务是讨论现实世界中数据的各种逻辑结构，在计算机中的存储结构以及进行各种非数值运算的算法。
本课程达到《认证通用标准》规定中关于“毕业要求”的第三款项（具有运用工程基础知识和本专业基本理论知识解决问题的能力，具有系统的工程实践学习经历；了解本专业的前沿发展现状和趋势）、第四款项（具备设计和实施工程实验的能力，并能够对实验结果进行分析）。
二、课程的基本要求
通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关系； 熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；掌握设计算法的步骤和算法分析方法； 掌握数据结构在排序、查找和路由选择等常用算法中的应用。
最后学生应达到知识技能两方面的目标：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。
三、课程教学内容
第一章 绪论
基本要求:
掌握数据结构的基本概念，抽象数据类型在软件设计中的意义，算法的概念和算法的时间复杂度分析，了解算法的描述和评价。 基本知识点:
数据结构的基本概念；
● 算法特性、描述；
● 算法分析：时间复杂度和空间复杂度； 教学重点:
● 数据结构的基本概念；
● 算法分析：时间复杂度和空间复杂度； 实验:
实验1: 对某一组数据排序, 采用不同的算法定义与实现，并进行算法分析。 习题课安排:
安排一次课下习题, 并进行一次课堂讲解.
第二章 线性表
教学要求:
理解线性表的定义和线性表基本操作的功能；掌握线性表的顺序和链式存储结构；掌握顺序表的设计及应用；掌握单链表的设计及应用。掌握两种存储结构的实现及优缺点。 基本知识点:
● 线性表的类型定义：概念、长度、抽象数据类型定义，基本操作的应用； ● 线性表的顺序存储结构、构造一个空的线性表、线性表的插入操作、线性表的删除
操作、线性表的查找、线性表的合并，插入、删除算法的算法分析；
● 线性表的链式实现、返回线性表第i 个数据元素的值、在线性表第i 个位置之前插
入元素e 、在带头结点的线性表L 中删除第i 个元素、链表的合并； ● 静态链表、循环链表、双向链表；
教学重点:
● 线性表的定义和抽象数据类型；顺序和链式存储结构；顺序表的设计；单链表的设计，
算法分析。
实验:
实验2：顺序表的基本操作 实验3：单链表的基本操作
实验4：双向链表或循环链表的基本操作 习题课安排:
安排两次次课下习题, 并进行一到两次课堂讲解.
第三章 栈和队列
教学要求:
理解堆栈的概念，掌握顺序堆栈和链式堆栈的设计方法；理解队列的概念，掌握顺序循环队列和链式队列的设计方法；了解堆栈和队列的应用方法，掌握堆栈和队列的基本应用。 基本知识点:
● 堆栈的基本概念、堆栈的抽象数据类型定义、 ● 堆栈的顺序表示和实现、堆栈的链式表示和实现；
● 堆栈应用（数制转换问题、括号匹配问题等、表达式求值、栈与递归的实现等）； ● 队列的基本概念、队列的抽象数据类型定义、 ● 顺序队列、顺序循环队列、链式队列、队列应用。 教学重点:
● 顺序堆栈和链式堆栈的设计方法；顺序循环队列和链式队列的设计方法。
实验:
实验5：栈的基本操作
实验6：队列的基本操作 习题课安排:
安排一次课下习题, 并进行一次课堂讲解.
第四章 串
教学要求:
掌握串及其基本概念；理解串的存储结构及串基本操作的实现；了解串的模式匹配算法; 基本知识点:
● 串的定义和基本运算；
● 串的存储表示及基本运算的实现； 教学重点:
● 串的存储结构； 实验:
实验7：串的基本操作
第五章 数组
教学要求:
掌握数组的定义及其实现机制；了解数组的抽象数据类型；掌握特殊矩阵的压缩存储和稀疏矩阵的压缩存储；了解广义表的概念和表示。 基本知识点:
● 数组的定义及其实现机制；
● 特殊矩阵（包括n 阶对称矩阵、n 阶三角矩阵）的压缩存储方法； ● 稀疏矩阵的压缩存储方法：三元组顺序表、三元组链表。 ● 广义表的概念和表示。 教学重点:
● 特殊矩阵的压缩存储； ● 稀疏矩阵的压缩存储。 实验:
实验8：数组的三元组实现和逆置. 习题课安排:
安排一次课下习题, 并进行一次课堂讲解.
第六章 树
教学要求:
理解树与二叉树的基本概念，掌握二叉树的性质与存储结构；掌握二叉树的遍历算法和二叉树问题的遍历算法设计分析和实现. 基本知识点:
● 树的定义；
● 二叉树的定义及性质； ● 二叉树的存储结构； ● 二叉树的遍历； ● 树的存储；
● 数、森林与二叉数的转换； ● 最优二叉树的构造；
教学重点:
● 二叉树的先序遍历、中序遍历、后序遍历和层次遍历。 实验:
实验9：二叉树的遍历 实验10：哈夫曼树
实验11：二叉树的应用 习题课安排:
安排二次课下习题, 并进行一到两次课堂讲解.
第七章 图
教学要求:
了解图的基本概念和术语；掌握图的邻接矩阵和邻接表存储结构以及图操作的实现方法；理解图的深度和广度遍历方法和算法设计方法；理解最小生成树的概念、普里姆算法和克鲁斯卡尔算法；了解最短路径问题的基本概念和从一个结点到其余各结点最短路径的算法。
基本知识点:
● 图的基本运算的定义 ● 图的存储结构 ● 图的遍历算法
● 如何得到图的最小生成树以及构造最小生成树的算法 ● 拓扑排序和AOV 网（顶点表示活动的有向网） ● 关键路径问题和AOE 网（边表示活动的有向网）
● 单源最短路径——迪杰斯特拉(Dijkstra)算法和每对顶点间的最短路径——弗洛伊德
（Floyd ）算法
教学重点：图的邻接矩阵和图的邻接表存储结构；图的深度和广度遍历方法；普里姆算法和克鲁斯卡尔算法。 教学难点：
● 操作的实现方法 实验:
实验12：图的创建和遍历 习题课安排:
安排一次课下习题, 并进行一次课堂讲解.
第九章 查找
教学要求:
掌握各种查找算法的特点、代码实现及应用范围；能应用各种查找算法解决实际问题。 基本知识点:
● 顺序查找算法； ● 折半查找算法； ● 索引查找的算法； ● 哈希表。 教学重点:
● 顺序查找算法和折半查找算法； ● 索引查找的算法。
● 哈希表 实验:
实验13：查找算法的实现 习题课安排:
安排一次课下习题.
第十章 排序
教学要求:
掌握排序的基本概念和排序算法的评判标准；掌握直接插入排序、希尔排序、直接选择排序、堆排序、快速排序、二路归并排序、基数排序的算法思想。
基本知识点:
● 直接插入排序及其性能分析； ● 冒泡排序及其性能分析； ● 简单选择排序及其性能分析； ● 快速排序及其性能分析。
● 希尔排序、堆排序、二路归并排序和基数排序的算法思想. 教学重点:
希尔排序、堆排序、快速排序、二路归并排序和基数排序的算法思想。. 实验:
实验14：排序算法的实现 习题课安排:
安排一次课下习题, 并进行一次课堂讲解.
四、课程学时分配
平时考评(学生出勤考评, 学生交作业情况考评) 占20%
期中考试(随堂考试) 占20% 期末考试(闭卷考试) 占60%
六、选用教材及参考资料（与考试大纲一致）
教材：1．任燕主编《数据结构 C++语言描述》，清华大学出版社，2011年 2. 严蔚敏 《数据结构（C 语言版）》清华大学出版社出版 实验教材：
1、任燕主编《数据结构上机实验指导 C++语言描述》，清华大学出版社，2011年 2、系自制的实验指导
七、教学大纲编制说明
大纲起草人： 冯豫华 教研室审核人：
《数据结构》教学大纲
Data Structure
课程编号：J6110G0003 课程性质：学科基础课程
适用专业：计算机科学与技术、网络工程、数字媒体技术 先行课：计算机科学导论、离散数学、高级语言程序设计； 后续课：无 。 学分数：5
主讲教师：任燕、王命延、冯豫华、周石林、王玮立等
一、课程的目的与任务
数据结构是信息与计算科学专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。
本课程的目的是使学生掌握数据组织、存储和处理的常用方法，为以后进行软件开发和学习后续专业课程打下基础。主要任务是讨论现实世界中数据的各种逻辑结构，在计算机中的存储结构以及进行各种非数值运算的算法。
本课程达到《认证通用标准》规定中关于“毕业要求”的第三款项（具有运用工程基础知识和本专业基本理论知识解决问题的能力，具有系统的工程实践学习经历；了解本专业的前沿发展现状和趋势）、第四款项（具备设计和实施工程实验的能力，并能够对实验结果进行分析）。
二、课程的基本要求
通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关系； 熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；掌握设计算法的步骤和算法分析方法； 掌握数据结构在排序、查找和路由选择等常用算法中的应用。
最后学生应达到知识技能两方面的目标：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。
三、课程教学内容
第一章 绪论
基本要求:
掌握数据结构的基本概念，抽象数据类型在软件设计中的意义，算法的概念和算法的时间复杂度分析，了解算法的描述和评价。 基本知识点:
数据结构的基本概念；
● 算法特性、描述；
● 算法分析：时间复杂度和空间复杂度； 教学重点:
● 数据结构的基本概念；
● 算法分析：时间复杂度和空间复杂度； 实验:
实验1: 对某一组数据排序, 采用不同的算法定义与实现，并进行算法分析。 习题课安排:
安排一次课下习题, 并进行一次课堂讲解.
第二章 线性表
教学要求:
理解线性表的定义和线性表基本操作的功能；掌握线性表的顺序和链式存储结构；掌握顺序表的设计及应用；掌握单链表的设计及应用。掌握两种存储结构的实现及优缺点。 基本知识点:
● 线性表的类型定义：概念、长度、抽象数据类型定义，基本操作的应用； ● 线性表的顺序存储结构、构造一个空的线性表、线性表的插入操作、线性表的删除
操作、线性表的查找、线性表的合并，插入、删除算法的算法分析；
● 线性表的链式实现、返回线性表第i 个数据元素的值、在线性表第i 个位置之前插
入元素e 、在带头结点的线性表L 中删除第i 个元素、链表的合并； ● 静态链表、循环链表、双向链表；
教学重点:
● 线性表的定义和抽象数据类型；顺序和链式存储结构；顺序表的设计；单链表的设计，
算法分析。
实验:
实验2：顺序表的基本操作 实验3：单链表的基本操作
实验4：双向链表或循环链表的基本操作 习题课安排:
安排两次次课下习题, 并进行一到两次课堂讲解.
第三章 栈和队列
教学要求:
理解堆栈的概念，掌握顺序堆栈和链式堆栈的设计方法；理解队列的概念，掌握顺序循环队列和链式队列的设计方法；了解堆栈和队列的应用方法，掌握堆栈和队列的基本应用。 基本知识点:
● 堆栈的基本概念、堆栈的抽象数据类型定义、 ● 堆栈的顺序表示和实现、堆栈的链式表示和实现；
● 堆栈应用（数制转换问题、括号匹配问题等、表达式求值、栈与递归的实现等）； ● 队列的基本概念、队列的抽象数据类型定义、 ● 顺序队列、顺序循环队列、链式队列、队列应用。 教学重点:
● 顺序堆栈和链式堆栈的设计方法；顺序循环队列和链式队列的设计方法。
实验:
实验5：栈的基本操作
实验6：队列的基本操作 习题课安排:
安排一次课下习题, 并进行一次课堂讲解.
第四章 串
教学要求:
掌握串及其基本概念；理解串的存储结构及串基本操作的实现；了解串的模式匹配算法; 基本知识点:
● 串的定义和基本运算；
● 串的存储表示及基本运算的实现； 教学重点:
● 串的存储结构； 实验:
实验7：串的基本操作
第五章 数组
教学要求:
掌握数组的定义及其实现机制；了解数组的抽象数据类型；掌握特殊矩阵的压缩存储和稀疏矩阵的压缩存储；了解广义表的概念和表示。 基本知识点:
● 数组的定义及其实现机制；
● 特殊矩阵（包括n 阶对称矩阵、n 阶三角矩阵）的压缩存储方法； ● 稀疏矩阵的压缩存储方法：三元组顺序表、三元组链表。 ● 广义表的概念和表示。 教学重点:
● 特殊矩阵的压缩存储； ● 稀疏矩阵的压缩存储。 实验:
实验8：数组的三元组实现和逆置. 习题课安排:
安排一次课下习题, 并进行一次课堂讲解.
第六章 树
教学要求:
理解树与二叉树的基本概念，掌握二叉树的性质与存储结构；掌握二叉树的遍历算法和二叉树问题的遍历算法设计分析和实现. 基本知识点:
● 树的定义；
● 二叉树的定义及性质； ● 二叉树的存储结构； ● 二叉树的遍历； ● 树的存储；
● 数、森林与二叉数的转换； ● 最优二叉树的构造；
教学重点:
● 二叉树的先序遍历、中序遍历、后序遍历和层次遍历。 实验:
实验9：二叉树的遍历 实验10：哈夫曼树
实验11：二叉树的应用 习题课安排:
安排二次课下习题, 并进行一到两次课堂讲解.
第七章 图
教学要求:
了解图的基本概念和术语；掌握图的邻接矩阵和邻接表存储结构以及图操作的实现方法；理解图的深度和广度遍历方法和算法设计方法；理解最小生成树的概念、普里姆算法和克鲁斯卡尔算法；了解最短路径问题的基本概念和从一个结点到其余各结点最短路径的算法。
基本知识点:
● 图的基本运算的定义 ● 图的存储结构 ● 图的遍历算法
● 如何得到图的最小生成树以及构造最小生成树的算法 ● 拓扑排序和AOV 网（顶点表示活动的有向网） ● 关键路径问题和AOE 网（边表示活动的有向网）
● 单源最短路径——迪杰斯特拉(Dijkstra)算法和每对顶点间的最短路径——弗洛伊德
（Floyd ）算法
教学重点：图的邻接矩阵和图的邻接表存储结构；图的深度和广度遍历方法；普里姆算法和克鲁斯卡尔算法。 教学难点：
● 操作的实现方法 实验:
实验12：图的创建和遍历 习题课安排:
安排一次课下习题, 并进行一次课堂讲解.
第九章 查找
教学要求:
掌握各种查找算法的特点、代码实现及应用范围；能应用各种查找算法解决实际问题。 基本知识点:
● 顺序查找算法； ● 折半查找算法； ● 索引查找的算法； ● 哈希表。 教学重点:
● 顺序查找算法和折半查找算法； ● 索引查找的算法。
● 哈希表 实验:
实验13：查找算法的实现 习题课安排:
安排一次课下习题.
第十章 排序
教学要求:
掌握排序的基本概念和排序算法的评判标准；掌握直接插入排序、希尔排序、直接选择排序、堆排序、快速排序、二路归并排序、基数排序的算法思想。
基本知识点:
● 直接插入排序及其性能分析； ● 冒泡排序及其性能分析； ● 简单选择排序及其性能分析； ● 快速排序及其性能分析。
● 希尔排序、堆排序、二路归并排序和基数排序的算法思想. 教学重点:
希尔排序、堆排序、快速排序、二路归并排序和基数排序的算法思想。. 实验:
实验14：排序算法的实现 习题课安排:
安排一次课下习题, 并进行一次课堂讲解.
四、课程学时分配
平时考评(学生出勤考评, 学生交作业情况考评) 占20%
期中考试(随堂考试) 占20% 期末考试(闭卷考试) 占60%
六、选用教材及参考资料（与考试大纲一致）
教材：1．任燕主编《数据结构 C++语言描述》，清华大学出版社，2011年 2. 严蔚敏 《数据结构（C 语言版）》清华大学出版社出版 实验教材：
1、任燕主编《数据结构上机实验指导 C++语言描述》，清华大学出版社，2011年 2、系自制的实验指导
七、教学大纲编制说明
大纲起草人： 冯豫华 教研室审核人：