《数据结构》

（专）

黄冈广播电视大学
丁仕贤





课程性质、任务与目的
　《数据结构》是计算机应用专业的一门专业基础课，主要任务是讨论各种数据组织中的数据逻辑结构，存储结构以及有关操作的算法。目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。







第一章 绪论
（一）重点掌握的内容：
　 1.
数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。
　　2.
集合结构、线性结构、树结构和图结构的特点。
　　3.
抽象数据类型的定义和表示方法。
　　4.
一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。 　　　　　　　　　　　


数据结构第一章





5.
普通函数重载和操作符函数重载的含义，定义格式和调用格式。
　　6. 函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。
　　7. 算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。

对于本章的其余内容均作一般掌握。


数据结构第一章





　　(二) 教学内容



　　1. 数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。
　　数据：所有能被输入到计算机中，且能被计算机处理的符号的集合。这样，一个文档、记录、数组、句子、单词、算式、符号等都统称为数据。

数据结构：数据及其相互之间的联系。要搞清什么是数据结构，就必须搞清两个问题：数据自身和数据与数据之间的关系。


数据结构第一章





数据结构第一章

数据的逻辑结构：数据的逻辑结构主要体现的是数据与数据之间的关系。在研究数据的逻辑结构时，可忽略数据自身情况，所以书中所举的例子中数据都使用的是简单的数值或字符。通常所说的数据结构是指数据的逻辑结构。


（1）集合


（2）线性结构


（3）树结构


（4）图结构


数据的逻辑结构可归结为以下四类:





数据的存储结构：一种数据结构在存储器中的存储方式称为数据的物理结构或存储结构。一种数据结构可以根据应用的需表示一种或几种存储结构。


（1）顺序映象：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，从而得到顺序存储结构。


（2）非顺序存储映象：数据元素在存储器中不是按照逻辑上的先后顺序存放，而是利用地址指针来表示元素之间的逻辑联系关系。


x


y


y


x


数据结构第一章

数据的存储结构大致可归结为两类。





学习建议：结合书本P3-P6的相关内容，掌握数据结构的二元组表示、序偶、前驱、后继等的具体含义，以及集合结构、线性结构、树结构、图结构的特点。


数据结构第一章





第二章 线性表
　(一)重点掌握的内容：
　　1.
线性表的定义和抽象数据类型的描述，线性表中插入、删除等操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
　　2. 线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。
　　3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。
　　4. 单链表中结点的结构，每个域的定义及作用，即LNode类型的定义及结构。

数据结构第二章





5. 带表头附加结点的链表、循环链表、双向链表的结构特点。
　　6. 线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。
　　7. 在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。
　　对于本章的其余内容均作一般掌握。

数据结构第二章





(二) 教学内容





第三章 稀疏矩阵和广义表
（一）重点掌握的内容：

1、稀疏矩阵的定义和三元组线性表表示。

2、稀疏矩阵的顺序存储、带行指针向量的链接存储，它们中非零元素结点的结构。

3、稀疏矩阵的转置运算和算法描述。

4、广义表的定义和表示，广义表长度和深度的计算。


数据结构第三章






5、广义表的链接存储结构中结点类型的定义、分别求广义表长度和深度的递归算法。

对于本章的其余内容均作一般掌握。


数据结构第三章





第四章 栈和队列
（一）重点掌握的内容：
　　1.
栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
　　2.
栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。
　　3．栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。
　　4.
栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。

数据结构第四章






5. 算术表达式的中缀表示和后缀表示，以及相互转换的规则。
　　6.
队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
　　7.
队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。
　　8.
队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。
　　9.
利用栈和队列解决简单问题的算法分析和设计。


数据结构第四章





　（二）一般掌握的内容：
　　1.
求解阶乘问题方法和算法。
　　2.
后缀表达式求值的方法和算法，
　　3.
把中缀表达式转换为后缀表达式的方法和算法。
　　4.
队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。


数据结构第四章





（三）一般了解的内容：
　　求解迷宫问题的方法和算法。


数据结构第四章





第五章 树和二叉树
　　（一）重点掌握的内容：
　　1.
树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示。
　　2.
树和二叉树的概念。
　　3.
树和二叉树的性质。
　　4.
二叉树中结点的编号规则和对应的顺序存储结构。


数据结构第五章





　 5.
二叉树的链接存储结构及存储结点的类型定义，即BTreeNode类型的定义和每个域的定义及作用。
　　6.
二叉树的先序、中序、后序遍历的递归过程和递归算法，中序遍历的非递归算法，按层遍历的过程和算法。
　　7.
在链接存储的二叉树上实现指定功能的算法分析和设计。


数据结构第五章





（二）一般掌握的内容
　　1.
普通树的链接存储结构，GTreeNode类型的定义和每个域的定义及作用。
　　2．普通树的先根、后根和按层遍历的过程及算法。

数据结构第五章





　第六章 二叉树的应用
　　（一）重点掌握的内容：
　　1.
二叉搜索树的定义和性质。
　　2.
二叉搜索树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素的查找长度，即从树根结点到该结点的路径上的结点数。
　　3.
二叉搜索树插入的递归算法和非递归算法，相应的时间复杂度。
　　4．根据一组数据采用顺序插入生成一棵二叉搜索树的过程。

数据结构第六章





　5.
堆的定义和顺序存储结构，小根堆和大根堆的异同。
　6.
向堆中插入元素的过程、算法描述及时间复杂度。
　7.
从堆中删除元素的过程、算法描述及时间复杂度。

数据结构第六章





（二）一般掌握的内容：
　　哈夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权构造哈夫曼树的过程。
　　对本章的其余内容均作一般了解。

数据结构第六章





第七章 图
　　（一）重点掌握的内容：
　　1.
图的定义，它的顶点集和边集表示。
　　2.
图的基本概念。
　　3.
图的邻接矩阵、邻接表和边集数组三种存储结构及相应的空间复杂度。
　　4.
存储图使用的vexlist, adjmatrix, adjlist, edgenode, edgeset, edge等类型的定义及用途。

5. 图的深度优先和广度优先搜索遍历的过程。


数据结构第七章





6.
对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以及相应的时间复杂度。
　　7.
对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描述以及相应的时间复杂度。

8. 图的生成树、生成树的权、最小生成树等的定义。
　　9. 根据普里姆算法求图的最小生成树的过程。
　　10．根据克鲁斯卡尔算法求图的最小生成树的过程。
　　11. 图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示的图进行拓扑排序的过程。
对本章的其余内容均作一般掌握。


数据结构第七章





第八章 查找
　 （一）重点掌握的内容：
　　1.
在顺序表上进行顺序查找的过程、算法、平均查找长度和时间复杂度。
　　2.
在顺序存储的有序表上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂度，二分查找一个给定值元素的查找长度（即查找路径上的元素数），二分查找对应的判定树的性质。
　　3.
索引存储的概念，索引表的存储结构和索引项的存储结构，索引查找一个元素的过程、平均查找长度和时间复杂度。
　　4.
散列存储的概念，散列函数、散列表、冲突、同义词、装填因子等术语的含义。


数据结构第八章





5.
利用除留余数法建立散列函数求元素散列地址的方法。
　　6.
利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程，利用链接法处理冲突进行散列存储和查找的过程。
　　7.
根据除留余数法构造散列函数，采用线性探查法或链接法处理冲突，把一组数据散列存储到散列表中，计算出一个给定值元素的查找长度和查找所有元素的平均查找长度。
　　8. B_树中每个结点的结构，树根结点或非树根结点中关键字的个数范围和子树的个数范围，B_的结构特性，从B_树上查找一个给定值元素的过程。


数据结构第八章





（二）一般掌握的内容：
　　1.
索引查找和分块查找算法。
　　2. B_树查找算法。
　　3.
向B_树中插入元素的过程。
　　对本章的其余内容均作一般了解。


数据结构第八章





　第九章
排序
　　（一）重点掌握的内容：
　　1.
在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算的过程、算法及时间复杂度，整个堆排序的算法描述及时间复杂度。
　　2.
快速排序的方法，对一组数据的排序过程，对应的二叉搜索树，快速排序过程中划分的层数和递归排序区间的个数。
　　3.
快速排序的递归算法，它在平均情况下的时间和空间复杂度，在最坏情况下的时间和空间复杂度。
　　4.
二路归并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路归并排序的趟数、时间复杂度和空间复杂度。


数据结构第九章





　（二）一般掌握的内容：
　　1.
直接插入、直接选择和冒泡排序的方法，排序过程及时间复杂度。
　　2.
每一种排序方法的稳定性。
　　3.
直接插入排序和直接选择排序的算法。

数据结构第九章





（三）一般了解的内容：
　　1.
二路归并排序过程中涉及的每个算法。
　　2.
冒泡排序算法。

数据结构第九章