《数据结构》课程教学大纲
【课程代码】：14314021
【英文译名】：Data Structure
【适用专业】：计算机科学与技术、软件工程、信息安全
【学 分 数】：3.5
【总学时数】：56
一、本课程教学目的和课程性质课程教学目的：通过本课程的学习，使学生学会分析研究计算机加工的数据的结构特性，掌握基本的数据组织、数据存储及数据处理的方法，掌握算法的效率分析方法，培养学生根据实际问题的需要选择和设计合适的逻辑结构、存储结构及算法的能力。
课程性质：计算机科学与技术、软件工程、信息安全专业的必修专业基础课程，可以作为其它专业的选修课程。
二、本课程的基本要求通过本课程的教学，应使学生能从逻辑结构、存储结构和算法三个层面理解和掌握常用数据结构，并达到以下要求：
1、掌握线性表、栈、队列、数组、树、图的逻辑结构及常用的存储结构和算法，了解串、广义表、文件、优先队列、线索二叉树、回溯法，掌握顺序存储、链式存储、索引存储和散列存储；
2、掌握递归方法；
3、掌握插入排序、选择排序和交换排序，理解归并排序、基数排序；
4、掌握顺序表查找、索引表查找、散列表查找和树表查找；
5、能运用时间和空间复杂度分析算法的效率；
6、能针对实际问题，选择和设计合适的逻辑结构、存储结构及算法。
三、本课程与其他课程的关系本课程要求学生对计算机硬件、离散数学有初步的了解，并有一定的程序设计经验（C/C++）。
前修课程：离散数学、C/C++程序设计；
后续课程：操作系统、数据库原理；
四、课程内容
（一）数据结构及算法性能分析
1、数据、数据元素、数据项的概念及相互关系；
2、逻辑结构、存储结构的特点及分类；
3、逻辑结构、存储结构、算法的联系与区别；
4、抽象数据类型的概念；
5、算法的时间和空间复杂度。
重点：逻辑结构、存储结构及算法的联系；评价算法效率的标准及方法。
难点：算法的时间、空间复杂度分析。
（二）线性表
1、线性表逻辑结构；
2、顺序存储结构；
3、顺序表的定义及基本算法的实现；
4、链式存储结构；
5、链表（单链表、单循环链表、双向循环链表）的定义及算法实现；
6、基本算法的效率分析。
重点：线性表的定义及逻辑特点；顺序表上插入、删除和定位算法的实现；单链表、单循环链表、双向循环链表的结构特点；单链表和双向循环链表的插入、删除算法的实现。
难点：头结点在链表中的作用；双向循环链表的插入、删除算法的指针操作顺序。
（三）栈和队列
1、栈的特点；
2、顺序栈和链栈的基本算法的实现；
3、队列的特点；
4、循环队列和链队列的基本算法的实现；
5、优先队列的实现。
重点：栈的定义及逻辑特点；栈的顺序（链式）存储结构及入栈、出栈算法的实现；队列的定义及逻辑特点；队列的顺序（链式）存储结构及入队、出队算法的实现。
难点：循环队列的队空、队满条件；循环队列上的插入、删除算法；优先队列。
（四）数组、串、广义表
1、多维数组；
2、特殊矩阵的压缩存储；
3、稀疏矩阵；
4、串的定义、存储结构及基本操作；
5、串的模式匹配算法；
6、广义表的特点及应用。
重点：计算多维数组元素的存储地址；对称矩阵、三角矩阵的压缩存储；稀疏矩阵的三元组表示法；串的模式匹配算法；广义表的特点。
难点：稀疏矩阵的压缩存储算法；串的模式匹配算法。
（五）递归
1、递归的概念；
2、递归的设计及应用；
3、递归的效率分析；
4、回溯法。
重点：适用递归的条件。
难点：递归过程分析；递归的效率分析。
（六）树和二叉树
1、树定义、逻辑结构及特点；
2、树的存储结构；
3、树和森林；
4、二叉树的定义、性质及存储方法；
5、树和二叉树的转换；
6、二叉链表存储；
7、二叉树的前序、中序及后序遍历；
8、二叉树的线索化方法；
9、哈夫曼树和哈夫曼算法。
重点：树的递归定义；树的存储结构；二叉树的定义、逻辑特点及五个性质；二叉树的链式存储结构；二叉树的三种遍历方法及算法实现；哈夫曼树和哈夫曼算法。
难点：树与二叉树的转换；递归在遍历算法中的应用；哈夫曼算法及其应用。
（七）图
1、图的概念及术语；
2、图的操作；
3、图的邻接矩阵和邻接表存储方法；
4、图的深度优先搜索遍历和广度优先搜索遍历；
5、最小生成树的概念；
6、Prim算法和Kruskal算法；
7、拓扑排序；
8、最短路径；
重点：图的邻接矩阵和邻接表存储；图的深度优先搜索遍历方法和广度优先搜索遍历方法；生成树和最小生成树的概念；Prim算法的实现；最短路径的算法实现。
难点：图的存储结构特点；深度优先搜索遍历和广度优先搜索遍历的算法；最短路径算法。
（八）排序
1、排序的概念；
2、排序算法的稳定性；
3、插入排序；
4、选择排序；
5、交换排序；
6、归并排序；
7、基数排序；
重点：内排序和外排序、稳定排序和非稳定排序的区别；直接插入排序、直接选择排序、冒泡排序、快速排序、堆排序的思路及算法实现；
难点：希尔排序；快速排序；归并排序。
（九） 查找
1、查找概念；
2、静态查找和动态查找；
3、顺序表查找；
4、索引表查找；
5、树表查找；
6、散列表（哈希表）查找；
重点：折半查找；索引表查找；二叉排序树；散列表及冲突解决的方法；散列表的查找、插入和删除算法的实现。
难点：平衡二叉树；B-树和B+树；散列表算法。
（十）文件
1、文件的概念；
2、顺序文件；
3、索引文件；
4、直接存储文件；
5、多重表文件和倒排文件。
重点：文件的逻辑结构；文件存储结构。
难点：文件的动态索引结构。
五、教学方法建议课程的难点在于应用，教师可以用案例来示范数据结构知识的综合运用，学生在课后应分析并完善所讲案例。
六、考核方式采用结构化评分，总成绩中建议平时成绩（作业、课堂提问、案例分析、课堂测试等）占50%、期末笔试成绩占50%。
七、其它说明本课程配套有独立开课的实验课程：《数据结构应用设计》（24学时）。
八、选用教材及主要参考书
1、教材
[1]数据结构--使用C++语言(第二版).朱战立.西安电子科技大学出版社,2005
2、参考书
[1]数据结构(用面向对象方法与C++描述).殷人昆.清华大学出版社,2004
[2]数据结构与算法.齐德昱.清华大学出版社,2003
[3]数据结构与问题求解(C++版)(第2版).Mark Allen Weiss(美),张丽萍.
清华大学出版社,2005
九、学时分配课程内容
讲课
实验
上机
作业
小计
数据结构及算法性能分析
2
线性表
8
栈和队列
6
数组、串、广义表
4
递归
2
树和二叉树
10
图
8
排序
4
查找
6
文件
2
案例分析
4
合 计
56
编写负责人,曾立胜 审核人,部门主管领导,
【课程代码】：14314021
【英文译名】：Data Structure
【适用专业】：计算机科学与技术、软件工程、信息安全
【学 分 数】：3.5
【总学时数】：56
一、本课程教学目的和课程性质课程教学目的：通过本课程的学习，使学生学会分析研究计算机加工的数据的结构特性，掌握基本的数据组织、数据存储及数据处理的方法，掌握算法的效率分析方法，培养学生根据实际问题的需要选择和设计合适的逻辑结构、存储结构及算法的能力。
课程性质：计算机科学与技术、软件工程、信息安全专业的必修专业基础课程，可以作为其它专业的选修课程。
二、本课程的基本要求通过本课程的教学，应使学生能从逻辑结构、存储结构和算法三个层面理解和掌握常用数据结构，并达到以下要求：
1、掌握线性表、栈、队列、数组、树、图的逻辑结构及常用的存储结构和算法，了解串、广义表、文件、优先队列、线索二叉树、回溯法，掌握顺序存储、链式存储、索引存储和散列存储；
2、掌握递归方法；
3、掌握插入排序、选择排序和交换排序，理解归并排序、基数排序；
4、掌握顺序表查找、索引表查找、散列表查找和树表查找；
5、能运用时间和空间复杂度分析算法的效率；
6、能针对实际问题，选择和设计合适的逻辑结构、存储结构及算法。
三、本课程与其他课程的关系本课程要求学生对计算机硬件、离散数学有初步的了解，并有一定的程序设计经验（C/C++）。
前修课程：离散数学、C/C++程序设计；
后续课程：操作系统、数据库原理；
四、课程内容
（一）数据结构及算法性能分析
1、数据、数据元素、数据项的概念及相互关系；
2、逻辑结构、存储结构的特点及分类；
3、逻辑结构、存储结构、算法的联系与区别；
4、抽象数据类型的概念；
5、算法的时间和空间复杂度。
重点：逻辑结构、存储结构及算法的联系；评价算法效率的标准及方法。
难点：算法的时间、空间复杂度分析。
（二）线性表
1、线性表逻辑结构；
2、顺序存储结构；
3、顺序表的定义及基本算法的实现；
4、链式存储结构；
5、链表（单链表、单循环链表、双向循环链表）的定义及算法实现；
6、基本算法的效率分析。
重点：线性表的定义及逻辑特点；顺序表上插入、删除和定位算法的实现；单链表、单循环链表、双向循环链表的结构特点；单链表和双向循环链表的插入、删除算法的实现。
难点：头结点在链表中的作用；双向循环链表的插入、删除算法的指针操作顺序。
（三）栈和队列
1、栈的特点；
2、顺序栈和链栈的基本算法的实现；
3、队列的特点；
4、循环队列和链队列的基本算法的实现；
5、优先队列的实现。
重点：栈的定义及逻辑特点；栈的顺序（链式）存储结构及入栈、出栈算法的实现；队列的定义及逻辑特点；队列的顺序（链式）存储结构及入队、出队算法的实现。
难点：循环队列的队空、队满条件；循环队列上的插入、删除算法；优先队列。
（四）数组、串、广义表
1、多维数组；
2、特殊矩阵的压缩存储；
3、稀疏矩阵；
4、串的定义、存储结构及基本操作；
5、串的模式匹配算法；
6、广义表的特点及应用。
重点：计算多维数组元素的存储地址；对称矩阵、三角矩阵的压缩存储；稀疏矩阵的三元组表示法；串的模式匹配算法；广义表的特点。
难点：稀疏矩阵的压缩存储算法；串的模式匹配算法。
（五）递归
1、递归的概念；
2、递归的设计及应用；
3、递归的效率分析；
4、回溯法。
重点：适用递归的条件。
难点：递归过程分析；递归的效率分析。
（六）树和二叉树
1、树定义、逻辑结构及特点；
2、树的存储结构；
3、树和森林；
4、二叉树的定义、性质及存储方法；
5、树和二叉树的转换；
6、二叉链表存储；
7、二叉树的前序、中序及后序遍历；
8、二叉树的线索化方法；
9、哈夫曼树和哈夫曼算法。
重点：树的递归定义；树的存储结构；二叉树的定义、逻辑特点及五个性质；二叉树的链式存储结构；二叉树的三种遍历方法及算法实现；哈夫曼树和哈夫曼算法。
难点：树与二叉树的转换；递归在遍历算法中的应用；哈夫曼算法及其应用。
（七）图
1、图的概念及术语；
2、图的操作；
3、图的邻接矩阵和邻接表存储方法；
4、图的深度优先搜索遍历和广度优先搜索遍历；
5、最小生成树的概念；
6、Prim算法和Kruskal算法；
7、拓扑排序；
8、最短路径；
重点：图的邻接矩阵和邻接表存储；图的深度优先搜索遍历方法和广度优先搜索遍历方法；生成树和最小生成树的概念；Prim算法的实现；最短路径的算法实现。
难点：图的存储结构特点；深度优先搜索遍历和广度优先搜索遍历的算法；最短路径算法。
（八）排序
1、排序的概念；
2、排序算法的稳定性；
3、插入排序；
4、选择排序；
5、交换排序；
6、归并排序；
7、基数排序；
重点：内排序和外排序、稳定排序和非稳定排序的区别；直接插入排序、直接选择排序、冒泡排序、快速排序、堆排序的思路及算法实现；
难点：希尔排序；快速排序；归并排序。
（九） 查找
1、查找概念；
2、静态查找和动态查找；
3、顺序表查找；
4、索引表查找；
5、树表查找；
6、散列表（哈希表）查找；
重点：折半查找；索引表查找；二叉排序树；散列表及冲突解决的方法；散列表的查找、插入和删除算法的实现。
难点：平衡二叉树；B-树和B+树；散列表算法。
（十）文件
1、文件的概念；
2、顺序文件；
3、索引文件；
4、直接存储文件；
5、多重表文件和倒排文件。
重点：文件的逻辑结构；文件存储结构。
难点：文件的动态索引结构。
五、教学方法建议课程的难点在于应用，教师可以用案例来示范数据结构知识的综合运用，学生在课后应分析并完善所讲案例。
六、考核方式采用结构化评分，总成绩中建议平时成绩（作业、课堂提问、案例分析、课堂测试等）占50%、期末笔试成绩占50%。
七、其它说明本课程配套有独立开课的实验课程：《数据结构应用设计》（24学时）。
八、选用教材及主要参考书
1、教材
[1]数据结构--使用C++语言(第二版).朱战立.西安电子科技大学出版社,2005
2、参考书
[1]数据结构(用面向对象方法与C++描述).殷人昆.清华大学出版社,2004
[2]数据结构与算法.齐德昱.清华大学出版社,2003
[3]数据结构与问题求解(C++版)(第2版).Mark Allen Weiss(美),张丽萍.
清华大学出版社,2005
九、学时分配课程内容
讲课
实验
上机
作业
小计
数据结构及算法性能分析
2
线性表
8
栈和队列
6
数组、串、广义表
4
递归
2
树和二叉树
10
图
8
排序
4
查找
6
文件
2
案例分析
4
合 计
56
编写负责人,曾立胜 审核人,部门主管领导,
