《自学考试数据结构笔记(超级详细_可做考试条)》由会员分享，可在线阅读，更多相关《自学考试数据结构笔记(超级详细_可做考试条)（86页珍藏版）》请在金锄头文库上搜索。
1、. . . . .自考数据结构笔记(详尽版) 感谢热心自考人：liuii322 笔记特点：图例丰富，超级详细，几乎涵盖本课程所有要求掌握的知识点，。用于复习和做小条概论- 学习数据结构的意义5概论- 算法的描述和分析(一)5线性表 - 链式存储结构- 单链表的运算（一）14三 栈和队列 - 栈 - 栈的定义及基本运算22三栈和队列 - 队列 - 队列的定义及基本运算25三栈和队列 - 队列 - 顺序队列25栈和队列 - 队列 - 链队列26三栈和队列 - 栈和队列的应用实例 - 栈的应用实例（一）27四串的基本概念（一）30图 - 图的概念（一）63图 - 图的存储结构 - 邻接矩阵表示法67
2、图 - 图的遍历 - 深度优先遍历（一）72图 - 图的遍历 - 广度优先遍历 （一）75图 - 生成树和最小生成树 - 生成树77图 - 生成树和最小生成树 - 最小生成树（一）79图 - 最短路径 （一）82图 - 拓扑排序 （一）84排序 - 排序基本概念 （一）86排序 - 插入排序 - 直接插入排序（一）87排序 - 插入排序 - 直接插入排序（二）88排序 - 插入排序 - 希尔排序89排序 - 交换排序 - 冒泡排序（一）90排序 - 交换排序 - 快速排序 （一）92排序 - 选择排序 - 堆排序（一）96排序 - 归并排序（一）98排序 - 分配排序 - 基数排序101排序
3、- 各种内部排序方法的比较和选择（一）102查找 - 查找的基本概念103查找-线性表的查找-顺序查找104查找 - 线性表的查找 - 二分查找（一）105查找 - 线性表的查找 - 分块查找107查找 - 树上的查找 - 二叉排序树（一）109查找 - 树上的查找 - 树114查找 - 散列技术 - 散列表的概念121查找 - 散列技术 - 散列函数的构造方法122文件 - 文件的基本概念（一）123文件 - 顺序文件125文件 - 索引文件（一）126文件 - 索引顺序文件 - ISAM文件（一）127文件 - 索引顺序文件 - VSAM文件 （一）130文件 - 散列文件131文件 -
4、多关键字文件 - 多重表文件132文件 - 多关键字文件 - 倒排文件133概论-基本概念和术语数据：数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据结构：指的是数据之间的相互关系，即数据的组织形式。1数据结构一般包括以下三方面内容： 数据元素之间的逻辑关系，也称数据的逻辑结构；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 数据元素及其关系在计算机存储器内的表示称数据的存储结构； 数据的运
5、算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。（1）逻辑结构：表中每一行是一个数据元素(或记录、结点)，由学号、姓名等数据项组成。数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点称直接前趋最多只有一个； （2）存储结构：该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？2数据的逻辑结构分类：逻辑结构简称为数据结构。 （1）线性结构：逻辑特征是：若结构是
6、非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前 趋和一个直接后继。 线性表,栈,队列,串等都是线性结构。（2）非线性结构：逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 3数据的四种基本存储方法（1）顺序存储方法：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。（如数组）（2）链接存储方法：该方法不要求逻辑上相邻
7、的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称链式存储结构,通常借助于程序语言的指针类型描述。（3）索引存储方法：该方法通常在储存结点信息的同时，还建立附加的索引表。 索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法：根据结点关键字直接计算出该结点存储地址。 四种存储方法
8、可单独使用也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。4数据结构三方面的关系：数据的逻辑结构、存储结构及数据的运算这三方面是一个整体。存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠不同数据结构名称来标识。 【例】线性表是一种逻辑结构，用顺序方法的存储表示，称其为顺序表；用链式存储方法，称为链表；用散列存储方法，称为散列表。数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。数据类型：是一个值的集合以及在这些值上定义的一组操作的总称
9、。通常数据类型可以看作是程序设计语言中已实现的数据结构。按值是否可分解，可将数据类型划分为两类：原子类型：其值不可分解。通常是由语言直接提供。结构类型：其值可分解为若干个成分（或称为分量）。抽象数据类型（简称ADT）：是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现信息隐藏。ADT和类的概念实际上反映了程序或软件设计的两层抽象：ADT相当于是在概念层（或称为抽象层）上描述问题，而类相当于是在实现层
10、上描述问题。不采用ADT的形式来描述数据结构 概论- 学习数据结构的意义1 计算机处理问题的分类 （1）数值计算问题 （2）非数值性问题 2非数值问题求解 瑞士计算机科学家沃思教授曾提出： 算法+数据结构=程序 数据结构是数据的逻辑结构和存储结构，算法是对数据运算的描述 概论- 算法的描述和分析(一) 数据的运算通过算法(Algorithm)描述 1算法 ：非形式地说，算法是任意一个良定义的计算过程。它以一个或多个值作为输入，并产生一个或多个值作为输出。（1）一个算法可以被认为是用来解决一个计算问题的工具。 （2）一个算法是一系列将输入转换为输出的计算步骤。 2算法的描述 ；一个算法可以用自然
11、语言、计算机程序语言或其它语言来说明，惟一的要求是该说明必须精确地描述计算过程。 描述算法最合适的语言是介于自然语言和程序语言之间的伪语言。算法分析 算法分析的目的是（评价算法的效率）1评价算法好坏的标准：首先应是正确的。此外主要考虑三点： 执行算法所耗费的时间；执行算法所耗费的存储空间，主要考虑辅助存储空间；算法应易于理解，易于编码，易于调试等。 算法的效率分为时间效率和空间效率真3算法的时间性能分析 （1）算法所耗费的时间=算法中每条语句的执行时间之和 每条语句的执行时间=语句的执行次数(即频度)语句执行一次所需时间的乘积。【例】求两个n阶方阵的乘积 C=AB,其算法如下: # defin
12、e n 100 / n 可根据需要定义,这里假定为100 void MatrixMultiply(int Aa，int B nn，int Cnn) int i ,j ,k; (1) for(i=0; in;j+) n+1 (2) for (j=0;jn;j+) n(n+1) (3) Cij=0; n 2 (4) for (k=0; kn; k+) n 2 (n+1) (5) Cij=Cij+Aik*Bkj; n 3 该算法中所有语句的频度之和为： T(n)=2n 3 +3n 2 +2n+1 分析：算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。 （2）问题规模和算法的时间
13、复杂度 算法求解问题的输入量称为问题的规模(Size),用一个整数表示。 【例】一个图论问题的规模则是图中的顶点数或边数。 一个算法的时间复杂度(也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。 【例3】算法MatrixMultidy的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有 当n充分大时，T(n)和n 3 之比是一个不等于零的常数。即T(n)和n 3 是同阶的，或者说T(n)和n 3 的数量级相同。记作T(n)=O(n 3)是算法MatrixMultiply
14、的渐近时间复杂度。 数学符号O的严格的数学定义： 若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n)表示存在正的常数C和n0，使得当nn0时都满足0T(n)Cf(n)。 （3）渐进时间复杂度评价算法时间性能 ：主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。 将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 当有若干个循环语句时，算法的时间复杂度由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。 （4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。 【例312】在数值A0.n-1中查找给定值K的算法大致如下： (1)i=n-1; (2)while(i=0&(Ai!=k) (3) i-; (4)return i; 此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关: 若A中没有与K相等的元素，则语句(3
