《数据结构》是一门研究非数值计算程序设计中的操作对象以及这些对象之间的关系和操作的学科，其主要研究数据组织和数据处理的方法。在国外，该课程作为一门独立的课程始于1968年，它出现在美国一些大学的计算机系的教学计划中，目前，该课程已成为计算机类专业一门非常重要的专业基础课程，它所研究的数据组织和数据处理的方法在后续的操作系统、编译原理、人工智能、计算机网络、数据库等课程中都是重要而必备的基础。

课程内容主要包括：数据结构的基本概念、线性表、栈和队列、串、数组和广义表、树、图、查找和排序。

从本质上讲，数据结构属于程序设计类课程，是程序设计语言课程的进阶篇。首先，程序是对数据的操作，由输入产生输出的IPO模式。对于比较复杂的处理对象，就需要从数据结构的角度来组织和存储数据，如采用顺序存储还是链式存储结构更加高效；另外，对于比较复杂的数据操作，就需要采用一些相应的数据结构来求解，如迷宫问题就借助于栈来完成。所以数据结构课程要讲解人们在软件开发中常见的数据结构，并从逻辑结构到存储结构，再到算法设计这三个层面加以学习。程序设计解决问题往往有多种方法，且不同方法之间的效率可能相差甚远。程序的时间和空间效率，不仅跟数据的组织方式有关，也跟处理流程的巧妙程度有关。本课程将介绍有关数据组织、算法设计、时间和空间效率的概念和通用分析方法，帮助学生学会数据的组织方法和一些典型算法的实现，是学生能够针对问题的应用背景分析问题及选择解决该问题应采用的数据结构，从而培养高级程序设计技能。

在线答题考试，期中成绩占40%，期末成绩占60%

C语言程序设计

离散数学

一、课程性质和目的                                   

课程性质：数据结构是计算机类专业的一门重要学科基础课，属于必修课。

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

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

1. 绪论

教学内容：

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

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

(3) 算法的概念和特性。

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

基本要求：

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

2. 线性表

教学内容：

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

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

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

(4) 线性表的应用，包括无序表和有序表的合并、多项式的加法运算等。

基本要求：

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

3. 栈和队列

教学内容：

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

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

(3) 栈与递归的实现，递归程序转换为非递归程序的方法。

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

(5) 队列的应用举例，如打印杨晖三角形，模拟汽车加油站等问题。

基本要求：

掌握栈和队列的特点，并能在相应的应用问题中正确选用。熟练掌握栈的顺序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件。掌握利用栈实现表达式求值的算法，了解迷宫求解算法。理解递归算法执行过程中栈的状态变化过程，了解将递归程序转换为非递归程序的方法。熟练掌握循环队列和链队列的进队出队算法，特别是循环队列中队头与队尾指针的变化情况。了解队列的应用。

4. 串 、数组和广义表

教学内容：

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

(2) 数组的存储方法。

(3) 特殊矩阵和稀疏矩阵的压缩存储，稀疏矩阵的转置运算。

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

基本要求：

了解串的顺序存储结构和堆存储结构。掌握串的古典的模式匹配算法。掌握数组的地址计算方法。了解稀疏矩阵的两种压缩存储方法的特点和适用范围。了解广义表的结构特点及其存储方法。

5. 树和二叉树

教学内容：

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

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

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

(4) 树和森林的定义，树的存储，树、森林与二叉树的转换。

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

基本要求：

了解树和森林的概念，包括树的定义、树的术语。掌握二叉树的概念、性质及二叉树的表示。熟练掌握二叉树的遍历算法，并且能灵活运用遍历算法实现二叉树的其他操作。掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法。了解树的存储、树和森林与二叉树的转换方法。掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算。

6. 图

教学内容：

(1) 图的定义和术语。

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

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

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

(5) 拓扑排序和关键路径。

(6) 两类求最短路径问题的算法，迪杰斯特拉算法和弗洛伊德算法。

基本要求：

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

7. 查找

教学内容：

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

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

(3) 基于树表的查找：二叉排序树、平衡二叉树、B-树和B+树。

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

基本要求：

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

8. 排序

教学内容：

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

(2) 插入排序：直接插入排序、折半插入排序和希尔排序。

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

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

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

(6) 基数排序：多关键字的排序和链数基数排序。

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

基本要求：

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

‍

数据结构在线课程教学日历

1. 教材

严蔚敏、李冬梅、吴伟民等。《数据结构》（C语言版），人民邮电出版社。

2.参考教材：

(1)《数据结构》（C语言版），严蔚敏，吴伟民，清华大学出版社.

(2)《数据结构教程》（第5版），李春葆主编 清华大学出版社.

(3)《数据结构》，陈越、何钦铭等,高等教育出版社.

(4)《数据结构学习与实验指导》，陈越、何钦铭等,高等教育出版社.

(５)《数据结构》 耿国华等编,西安电子科技大学.