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

一、课程基本信息

二、课程简介

《数据结构》是计算机科学与技术及其相关专业的专业基础课，也是计算机学科的核心课程。本课程系统地介绍各种典型的数据结构，包括它们的概念、存储结构、基本运算及其应用。本课程的学习过程也是算法设计的技巧和能力的训练过程，培养学生结合实际应用，设计有效的算法和数据结构的能力。

三、课程目标

《数据结构》是计算机学科相关专业的人才培养方案中的一门主要课程，该课程为后续多门计算机专业课指供了必要的基础，是一门核心基础课。通过本课程的学习，使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序；并对算法的效率进行简要分析和讨论。为将来学习操作系统、编译原理和数据库原理等后继课程奠定基础。

四、教学内容及要求

本课程由多位教师共同开设。

　(一) 第一章 绪论

教学内容:

数据结构的概念和术语；

算法描述与算法分析；

数据结构与算法。

教学基本要求:

掌握数据结构的基本概念和术语；

掌握逻辑结构、物理(存储)结构、顺序存储和链式存储的含义；

掌握算法的描述和算法分析，给定实例，进行算法效率分析和存储空间分析。

(二) 第二章 线性表

教学内容:

线性表及其逻辑结构；

线性表的顺序存储结构；

线性表的链式存储结构；

线性表的应用；

有序表。

教学基本要求:

掌握线性表的顺序存储以及顺序表的基本操作及其算法分析；

掌握线性表的链式存储以及单链表的基本操作及其算法分析；

理解循环单链表、双向链表和线性表的操作及其典型应用。

(三) 第三章 栈和队列

教学内容:

栈的定义及基本操作；

栈的顺序存储结构及其基本运算实现；

栈的链式存储结构及其基本运算实现；

栈的的应用举例

队列的定义及基本操作；

队列的顺序存储结构及其基本运算实现；

队列的链式存储结构及其基本运算实现；

队列的应用举例。

教学基本要求:

熟练掌握栈的定义及基本运算；

掌握顺序栈和链栈的实现，熟练掌握入栈和出栈运算的实现；

掌握括号匹配、表达式运算等几种堆栈的典型应用；

掌握队列的定义及基本运算；

掌握循环队列和链队列的实现；

理解队列的典型应用。

(四) 第四章 串

教学内容:

串的基本概念；

串的顺序存储和链式存储结构；

串的模式匹配:Brute—Force算法和KMP算法。

教学基本要求:

掌握串的定义、存储及串的基本运算；

掌握基本的串模式匹配算法（Brute—Force算法和KMP匹配算法）。

(五) 第五章 数组和广义表

教学内容:

数组的基本概念、存储结构和特殊矩阵的压缩存储；

稀疏矩阵的三元组表示和十字链表示；

广义表的定义、存储结构和运算。

教学基本要求:

掌握数组的定义及存储结构；

掌握特殊矩阵的压缩存储及运算；

掌握稀疏矩阵的三元组表、十字链表压缩存储及运算；

掌握广义表的定义、存储结构和运算。

(六) 第六章 递归

教学内容:

递归的概念、使用、模型和递归与数据归纳法；

递归算法的实现原理；

递归算法的设计。

教学基本要求:

掌握递归的概念；

掌握递归算法的设计方法；

理解递归算法的效率分析。

(七) 第七章 树和二叉树

教学内容:

树的定义、逻辑表示方法、基本术语、性质、基本运算和存储结构；

二叉树概念、性质和二叉树与树、森林之间的转换；

二叉树存储结构:顺序存储和链式存储；

二叉树的基本运算及其实现；

二叉树的遍历:前序遍历、中序遍历、后序遍历、层序遍历；

二叉树的构造；

线索二叉树；

哈夫曼树:定义、构造、Huffman算法；

用并查集求解等价问题。

教学基本要求:

掌握树的定义、存储结构及基本运算；

掌握二叉树的定义、几个重要性质以及二叉树的顺序存储和链式存储结构的设计；

掌握二叉树的先序、中序、后序、层序遍历过程及相应的遍历算法；

理解二叉树的线索化处理过程；

掌握哈夫曼树的构造和应用；

理解树的孩子表示法和双亲表示法，掌握树的孩子-兄弟表示法；

掌握树二叉树与树、森林的相互转化方法。

(八) 第八章 图

教学内容:

图的定义和术语；

图的存储结构:邻接矩阵存储结构、邻接表存储结构；

图的遍历:深度优先遍历算法、广度优先遍历算法；

图的生成树、最小生成树；

最短路径:基本概念、求最短路径的算法:迪杰斯特拉（Dijkstra）算法、弗洛伊德（Floyd）算法；

拓扑排序；

AOE网与与关键路径。

教学基本要求:

掌握图的定义以及顶点的度、连通和强连通、生成树等术语；

掌握图的邻接矩阵、邻接链表存储；

掌握图的深度优先遍历和广度优先遍历算法；

掌握求最小生成树的Prim算法和Kruskal算法；

掌握求最短路径的迪杰斯特拉算法和弗洛伊德算法；

掌握图的应用、拓扑排序。

(九) 第九章 查找

教学内容:

查找的基本概念:静态查找表、动态查找表及平均查找长度的定义；

线性表的查找:顺序查找、二分查找、分块查找算法及性能分析；

树表的查找:二叉排序树的定义、创建、插入、删除和查找算法及性能分析；

平衡二叉树、B树的定义和查找操作；

哈希表查找:基本概念、哈希函数构造、哈希冲突解决方法及哈希表上的运算。

教学基本要求:

掌握查找的基本概念、静态查找、动态查找的定义及平均查找长度的定义；

掌握顺序查找算法、二分查找及查找效率分析；

掌握二叉排序树的定义、创建、插入、删除和查找算法及查找效率分析；

了解平衡二叉树、B树的定义及查找过程。

(十) 第十章 内部排序

教学内容:

基本概念；

各种内部排序算法及比较。

教学基本要求:

掌握基本的插入排序、二分插入排序、希尔排序的算法及算法效率分析；

掌握冒泡排序、快速排序算法及算法效率分析；

掌握直接选择排序、堆排序算法及算法效率分析；

掌握归并排序算法及算法效率分析；

理解基数排序方法；

掌握各种内部排序算法比较和和选择。

（十一）第十一章 外排序

教学内容:

外排序概述、磁盘排序、磁带排序。

教学基本要求:

了解磁盘排序和磁带排序方法。

（十二）第十二章 文件

教学内容:

文件的基本概念、顺序文件、索引文件、哈希文件、多关键字文件。

教学基本要求:

了解各文件的存储结构及操作。

（十三）第十三章 采用面向对象的方法描述算法

教学内容:

面向对象的概念、用C++描述面向对象的程序、用C++描述数据结构算法。

教学基本要求:

了解用C++描述面向对象的程序和数据结构算法。

五、课时分配表

“课时分配”中，“其他”主要指课堂讨论、习题等教学环节。

六、教材及参考书

教材:

1．《数据结构教程（第4版）》（清华大学出版社，2013年1月出版，李春葆编著）；

2．《数据结构教程（第4版）上机实验指导》（清华大学出版社，2013年1月出版，李春葆编著）；

3．《数据结构教程（第4版）学习指导》（清华大学出版社，2013年1月出版，李春葆编著）。

参考书:

1．《数据结构》（清华大学出版社，严蔚敏、吴伟民 编著）；

2．《数据结构题集》（清华大学出版社，严蔚敏、吴伟民 编著）；

3．《算法与数据结构》（高等教育出版，张乃孝编著）。

七、教学策略与方法的建议

本课程教学主要采取讲授和实验方式。教学重点是从抽象数据类型的角度，分别讨论线性表、堆栈、队列、广义表、树和二叉树及图等基本类型的数据结构及其应用，并介绍了查找及排序的实现方法和分析比较。教学难点是要通过这些典型的数据类型，使学生学会分析研究计算机加工的数据结构的特性，为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析技术。同时，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚正确易读。

在教学内容上，本课程教学重点为:线性表、栈、树和二叉树、图、查找、排序；教学难点为:递归、串的改进模式匹配算法、线索二叉树、平衡二叉树、图的应用。

修订人 (签字) 钟秀玉

审核人 (签字)

批准人（签字）