数据结构-k8凯发旗舰

一、课程性质和目的

课程性质:数据结构b是计算机科学与技术（物联网方向）、网络工程专业的一门重要学科基础课，是必修课。

教学目的:通过本课程的学习，一方面，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

二、课程教学内容、学时分配和课程教学基本要求

1. 绪论（理论2学时）

教学内容:

(1) 数据结构的一些基本概念:数据、数据元素、数据的逻辑结构、物理结构、算法等。

(2) 抽象数据类型的表示和实现。

(3) 算法时间复杂度和空间复杂度的分析。

基本要求:

掌握数据结构的基本概念，了解抽象数据类型，掌握算法时间复杂度和空间复杂度的分析方法。

2. 线性表 （理论6学时，实验2学时）

教学内容:

(1) 线性表的类型定义。

(2) 线性表的顺序表示和实现。

(3) 线性表的链式表示和实现。

基本要求:

理解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。掌握顺序表的查找、插入和删除算法，掌握链表的查找、插入和删除算法。能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。

实验:

实验内容:单链表的基本操作。实验要求:以单链表形式创建一个学生表或图书表，并能实现相关的查找、插入和删除等算法。

3. 栈和队列 （理论4学时，实验2学时）

教学内容:

(1) 栈的类型定义，栈的顺序存储和链接存储的表示和实现。

(2) 栈的应用举例，如迷宫求解和表达式求值。

(3) 栈与递归的实现，hanoi塔问题。

(4) 队列的类型，队列的顺序存储(循环队)和链接存储的表示和实现。

基本要求:

掌握栈和队列的特点，并能在相应的应用问题中正确选用。熟练掌握栈的顺序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件。熟练掌握循环队列和链队列的进队出队算法，特别是循环队列中队头与队尾指针的变化情况。理解递归算法执行过程中栈的状态变化过程。了解在表达式计算时栈是如何使用的，重点了解计算表达式的方法和算法思路。

实验:

实验内容:栈的应用。实验要求:借助栈来解决某些实际应用问题，如表达式求值等。

4. 串 、数组和广义表（理论2学时）

教学内容:

(1) 串的表示和实现，包括顺序存储和链式存储表示。古典的模式匹配算法。

(2) 数组的存储方法。

(3) 广义表的逻辑结构和存储结构。

基本要求:

了解串的顺序存储结构和堆存储结构。掌握串的古典的模式匹配算法。掌握数组的地址计算方法。了解广义表的结构特点及其存储方法。

5. 树和二叉树 （理论6学时，实验2学时）

教学内容:

(1) 二叉树的定义和术语，二叉树的性质，特殊的二叉树。

(2) 二叉树的存储结构，顺序存储和二叉链表。

(3) 二叉树的的前序、中序、后序、层次遍历方法。

(4) 树的应用，哈夫曼树及哈夫曼编码。

基本要求:

了解树和森林的概念，包括树的定义、树的术语。掌握二叉树的概念、性质及二叉树的表示。熟练掌握二叉树的遍历算法，并且能灵活运用遍历算法实现二叉树的其他操作。掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算。

实验:

实验内容:二叉树的基本算法。实验要求:利用二叉链表方法建立二叉树，实现二叉树的前、中、后序三种遍历算法，并运用遍历算法实现二叉树的其他操作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等。

6. 图（理论6学时）

教学内容:

(1) 图的定义和术语。

(2) 图的存储结构两种存储结构:邻接矩阵和邻接表表示法。

(3) 图的两种遍历策略:深度优先搜索和广度优先搜索。

(4) 构造最小生成树的两种算法:普里姆算法和克鲁斯卡尔算法。

(5) 拓扑排序。

(6) 求最短路径问题的算法，迪杰斯特拉算法。

基本要求:

掌握图的基本概念及相关术语和性质，掌握图的邻接矩阵和邻接表表示法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。熟练掌握图的两种搜索路径的遍历:深度优先搜索和广度优先搜索算法的思想。掌握构造最小生成树的两种算法及拓扑排序算法的思想，掌握迪杰斯特拉算法的思想。

7. 查找 （理论6学时，实验2学时）

教学内容:

(1) 查找的基本概念，平均查找长度。

(2) 基于线性表的查找:顺序查找、折半查找。

(3) 基于树表的查找:二叉排序树。

(4) 散列表:散列表的基本概念，散列函数的构造方法、处理冲突的方法、散列表的查找与分析。

基本要求:

熟练掌握顺序表和有序表的查找方法及其实现，掌握二叉排序树的插入和查找算法的思想。熟练掌握散列表的构造方法、处理冲突的方法，深刻理散列表与其他结构的表的实质性的差别，了解各种散列函数的特点。掌握描述折半查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。

8. 排序 （理论6学时，实验2学时）

教学内容:

(1) 排序的基本概念，包括正序，逆序，稳定性，排序方法的分类。

(2) 插入排序:直接插入排序、折半插入排序。

(3) 交换排序:冒泡排序和快速排序。

(4) 选择排序:简单选择排序和堆排序。

(5) 归并排序:2-路归并排序。

(6) 排序算法分析:各种排序算法的比较和移动次数，时间复杂度和空间复杂度的分析。

基本要求:

明确排序的基本概念，排序方法的分类。深刻理解排序算法的过程、特点及其依据的原则，并能加以灵活应用。掌握各种排序方法的时间和空间复杂度的分析方法。能从关键字间的比较次数和移动次数分析算法的平均情况和最坏情况的时间性能。理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。快速排序、堆排序和归并排序等高效排序方法是本章的学习重点和难点。

实验:

实验内容:综合性实验。实验要求:选取一个合适的数据结构存储数据，能对数据进行插入、删除，用不同查找算法进行查找、用不同的排序算法进行排序等。

三、本课程与其它课程的联系和分工

本课程的先修课为程序设计基础，本课程可以c/c 或java语言作为算法描述和上机实践的工具。同时，本课程又是软件开发与设计等方面课程的基础，如数据库、操作系统、软件工程等课程。

四、本课程的考核方式

期末考试采用笔试形式，考试题型为:选择、填空、判断、应用题和算法设计题。总评成绩由平时成绩和期末成绩组成，其中平时成绩占30%--40%，期末考试占70%--60%。

课程实习的成绩由平时成绩和实习作业两部分组成，其中平时成绩占30%，实习作业占70%。

五、建议教材与教学参考书

建议教材:

1. 严蔚敏，李冬梅，吴伟民．数据结构（c语言版）．北京:人民邮电出版社．

2. 严蔚敏主编．数据结构（c语言版）．北京:清华大学出版社．

3. 殷人昆主编．数据结构（用面向对象方法与c 描述）．北京:清华大学出版社．

建议教学参考书:

1. [美]bruno r.preiss著，胡广斌，王崧等译．数据结构与算法-面向对象的c 设计模式．北京:电子工业出版社．

2. 殷人昆主编．数据结构与习题解析（用面向对象方法与c 描述）．北京:清华大学出版社．