自考~数据结构笔记体会(超级详细可做专业考试条).doc

《自考~数据结构笔记体会(超级详细可做专业考试条).doc》由会员分享，可在线阅读，更多相关《自考~数据结构笔记体会(超级详细可做专业考试条).doc（87页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、.自考数据结构笔记(详尽版)感谢热心自考人：liuii322 笔记特点笔记特点：图例丰富，超级详细，几乎涵盖本课程所有要求掌握的知识点，。用于复习和做小条概论- 学习数据结构的意义.5 概论- 算法的描述和分析(一).5 线性表 - 链式存储结构- 单链表的运算（一）.14 三 栈和队列 - 栈 - 栈的定义及基本运算.22 三栈和队列 - 队列 - 队列的定义及基本运算.25 三栈和队列 - 队列 - 顺序队列.25 栈和队列 - 队列 - 链队列.26 三栈和队列 - 栈和队列的应用实例 - 栈的应用实例（一）.27 四串的基本概念（一）.30 图 - 图的概念（一）.63 图 - 图的存

2、储结构 - 邻接矩阵表示法.67 图 - 图的遍历 - 深度优先遍历（一）.72 图 - 图的遍历 - 广度优先遍历 （一）.75 图 - 生成树和最小生成树 - 生成树.77 图 - 生成树和最小生成树 - 最小生成树（一）.79 图 - 最短路径 （一）.82 图 - 拓扑排序 （一）.84 排序 - 排序基本概念 （一）.86 排序 - 插入排序 - 直接插入排序（一）.87 排序 - 插入排序 - 直接插入排序（二）.88 排序 - 插入排序 - 希尔排序.89 排序 - 交换排序 - 冒泡排序（一）.90 排序 - 交换排序 - 快速排序 （一）.92 排序 - 选择排序 - 堆排序

3、（一）.96 排序 - 归并排序（一）.98 排序 - 分配排序 - 基数排序.101 排序 - 各种内部排序方法的比较和选择（一）.102 查找 - 查找的基本概念.103 查找-线性表的查找-顺序查找.104 查找 - 线性表的查找 - 二分查找（一）.105 查找 - 线性表的查找 - 分块查找.107 查找 - 树上的查找 - 二叉排序树（一）.109 查找 - 树上的查找 - 树.114 查找 - 散列技术 - 散列表的概念.121 查找 - 散列技术 - 散列函数的构造方法.122 文件 - 文件的基本概念（一）.123 文件 - 顺序文件.125 文件 - 索引文件（一）.126

4、 文件 - 索引顺序文件 - ISAM 文件（一）.127 文件 - 索引顺序文件 - VSAM 文件 （一）.130 文件 - 散列文件.131 文件 - 多关键字文件 - 多重表文件.132.文件 - 多关键字文件 - 倒排文件.133概论概论-基本概念和术语基本概念和术语数据数据：数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据结构数据结构：指的是数据之间的相互关系，即数据的组织形式。1数据结构一般包括以下三方面内容：数据结构一般包括以下三方面内容： 数据元

5、素之间的逻辑关系，也称数据的逻辑结构数据的逻辑结构；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 数据元素及其关系在计算机存储器内的表示称数据的存储结构数据的存储结构； 数据的运算数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。（1）逻辑结构逻辑结构：表中每一行是一个数据元素(或记录、结点)，由学号、姓名等数据项组成。

6、数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点称直接前趋直接前趋最多只有一个； （2）存储结构存储结构：该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？2数据的逻辑结构分类：数据的逻辑结构分类：逻辑结构简称为数据结构。 （1）线性结构线性结构：逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前 趋和一个直接后继。 线性表,栈栈,队列队列,串等都是线性结构。串等都是线性结构。（2）非线性结构非线性结构：逻辑特征是：一个结点可能有多个直接

7、前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。数组、广义表、树和图等数据结构都是非线性结构。 3数据的四种基本存储方法数据的四种基本存储方法（1）顺序存储方法：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构 ，通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。（如数组）（2）链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称链式存储结构,通常借助于程序语言的

8、指针类型描述。（3）索引存储方法：该方法通常在储存结点信息的同时，还建立附加的索引表。 索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引稠密索引。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引稀疏索引。索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法：根据结点关键字直接计算出该结点存储地址。 四种存储方法可单独使用也可组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。

9、同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。4数据结构三方面的关系：数据结构三方面的关系：数据的逻辑结构、存储结构及数据的运算这三方面是一个整体。存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠不同数据结构名称来标识。 【例例】线性表是一种逻辑结构，用顺序方法的存储表示，称其为顺序表；用链式存储方法，称为链表；用散列存储方法，称为散列表。数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。数据类型数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可

10、以看作是程序设计语言中已实现的数据结构。按按“值值“是否可分解，可将数据类型划分为两类：是否可分解，可将数据类型划分为两类：原子类型：原子类型：其值不可分解。通常是由语言直接提供。结构类型：结构类型：其值可分解为若干个成分（或称为分量）。抽象数据类型（简称抽象数据类型（简称 ADT）：是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点优点是将数据和操作封装在一起，使得用户程序只能通过在 ADT里定义的某些操作来访问其中的数据，从而实现信息隐藏。ADT 和类的概念实际上反映了程序或软件设计的两层

11、抽象：ADT 相当于是在概念层（或称为抽象层）上描述问题，而类相当于是在实现层上描述问题。不采用 ADT 的形式来描述数据结构 概论概论- - 学习数据结构的意义学习数据结构的意义 1 计算机处理问题的分类计算机处理问题的分类 （1）数值计算问题 （2）非数值性问题 .2非数值问题求解非数值问题求解 瑞士计算机科学家沃思教授曾提出： 算法+数据结构=程序 数据结构是数据的逻辑结构和存储结构，算法是对数据运算的描述 概论概论- - 算法的描述和分析算法的描述和分析( (一一) ) 数据的运算通过算法(Algorithm)描述 1算法算法 ：非形式地说，算法是任意一个良定义的计算过程。它以一个或多

12、个值作为输入，并产生一个或多个值作为输出。（1）一个算法可以被认为是用来解决一个计算问题的工具。 （2）一个算法是一系列将输入转换为输出的计算步骤。 2算法的描述算法的描述 ；一个算法可以用自然语言、计算机程序语言或其它语言来说明，惟一的要求是该说明必须精确地描述计算过程。 描述算法最合适的语言是介于自然语言和程序语言之间的伪语言。算法分析算法分析 算法分析的目的是（评价算法的效率）算法分析的目的是（评价算法的效率）1评价算法好坏的标准：评价算法好坏的标准：首先应是“正确“的。此外主要考虑三点： 执行算法所耗费的时间；执行算法所耗费的存储空间，主要考虑辅助存储空间；算法应易于理解，易于编码，易

13、于调试等。 算法的效率算法的效率分为时间效率和空间效率真3算法的时间性能分析算法的时间性能分析 （1）算法所耗费的时间=算法中每条语句的执行时间之和 每条语句的执行时间=语句的执行次数(即频度)语句执行一次所需时间的乘积。【例】求两个 n 阶方阵的乘积 C=AB,其算法如下: # define 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

14、(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）问题规模和算法的时间复杂度 算法求解问题的输入量称为问题的规模规模(Size),用一个整数表示。 【例】一个图论问题的规模则是图中的顶点数或边数。 一个算法的时间复杂度(也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模 n 的函数。当问题的规模 n 趋向无穷大时，时间复杂度 T(n)的数量级

15、(阶)称为算法的渐进时间复杂度算法的渐进时间复杂度。 【例 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 的渐近时间复杂度。 数学符号数学符号“O“的严格的数学定义：的严格的数学定义： 若 T(n)和 f(n)是定义在正整数集合上的两个函数，则 T(n)=O(f(n)表示存在正的常数 C 和 n0，使得当 nn0 时都满足 0T

16、(n)Cf(n)。 （3）渐进时间复杂度评价算法时间性能）渐进时间复杂度评价算法时间性能 ：主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。 将渐近时间复杂度 T(n)=O(f(n)简称为时间复杂度，其中的 f(n)一般是算法中频度最大的语句频度。 当有若干个循环语句时，算法的时间复杂度由嵌套层数最多的循环语句中最内层语句的频度当有若干个循环语句时，算法的时间复杂度由嵌套层数最多的循环语句中最内层语句的频度 f(n)决定的。决定的。 （4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。 【例 312】在数值 A0.n-1中查找给定值 K 的算

17、法大致如下： (1)i=n-1; (2)while(i=0 (4)return i; 此算法中的语句(3)的频度不仅与问题规模 n 有关，还与输入实例中 A 的各元素取值及 K 的取值有关: 若 A 中没有与 K 相等的元素，则语句(3)的频度 f(n)=n； 若 A 的最后一个元素等于 K,则语句(3)的频度 f(n)是常数 0。 （5） 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 常见的时间复杂度按数量级递增递增排列依次为：常数 0(1)、对数阶0(log 2 n)、线形阶0(n)、线形对数阶0(nlog 2 n)、平方阶0(n 2 )立方阶0(n 3

18、 )、k次方阶0(n k )、指数阶0(2 n )。 .一个算法的空间复杂度 S(n)定义为该算法所耗费的存储空间，它也是问题规模 n 的函数。渐近空间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。 线性表的逻辑结构线性表的逻辑结构 线性表的逻辑定义线性表的逻辑定义线性表是由 n 个数据元素（结点）a1，a2，an 组成的有限序列。线性表的逻辑结构特征（线性表的逻辑结构特征（对于非非空的线性表:）仅有一个开始结点 a1，没有直接前趋，仅有一个直接后继 a2；仅有一个终结结点 an，没有直接后继，仅有一个直接前趋 a

19、n-1；其余的内部结点 ai 都有且仅有一个直接前趋和一个直接后继。常见的线性表的基本运算常见的线性表的基本运算1 InitList（L） ：构造一个空的线性表 L，即表的初始化。2 ListLength（L） ：求线性表 L 中的结点个数，即求表长。3 GetNode（L，i） ：取线性表 L 中的第 i 个结点，1iListLength(L)4LocateNode（L，x）：在 L 中查找值为 x 的结点,并返回 x 在 L 中的位置。若 L 中没结点的值为 x，返回个特殊值表示查找失败。5InsertList（L，x，i）：在表 L 的第 i 个位置上插入一个值 x 6 DeleteLi

20、st（L，i） ：删除线性表 L 的第 i 个结点 顺序表顺序表1顺序表的定义顺序表的定义：用顺序存储方法存储的线性表。(随机存取结构)(1) 顺序顺序存储存储方法方法：即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。2 结点结点 ai 的存储地址：的存储地址： 设线性表中所有结点类型相同，每个结点占用存储空间大小亦相同。假设每个结点占用 c 个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设开始结点 a1 的存储地址（简称基地址）是 LOC（a1），那么结点 ai 的存储地址LOC（ai）可通过下式计算：LOC（ai）= LOC（a1）+（i-1）*c 1in

21、3顺序表类型定义顺序表类型定义#define ListSize 100 /表空间的大小假设为 100typedef int DataType; /DataType 的类型假设为 inttypedef struct DataType dataListSize；/向量 data 用于存放表结点int length；/当前的表长度 SeqList；注意：注意：用结构类型来定义顺序表类型。存放线性表结点的向量空间的大小 ListSize 应仔细选值，既满足表结点的数目动态增加需求，又不致于过大浪费存储空间。若 L 是 SeqList 类型的顺序表，则线性表的开始结点 a1 和终端结点 an 分别存储在

22、 Ldata0和 LDataLlength-1中。 若 L 是 SeqList 类型的指针变量，则 a1 和 an 分别存储在L-data0和 L-dataL-length-1中。4顺序表的特点顺序表的特点顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址。顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。顺序表上实现的基本运算顺序表上实现的基本运算1.表的初始化表的初始化: void InitList（SeqList *L）顺序表的初始化即将表的长度置为 0 L-length=0；2.求表长求表长 : int ListLength（

23、SeqList *L）求表长只需返回 L-length return L-length.3.取表中第取表中第 i 个结点个结点 只需返回 L-datai-1即可DataType GetNode（L，i） if (i L-length-1) Error(“position error“)； return L-datai-1； 5. 插入插入（1） 插入运算的逻辑描述插入运算的逻辑描述线性表的插入运算是指在表的第 i（1in+1）个位置上，插入一个新结点 x，使长度为 n 的线性表 变成长度为 n+1 的线性表注意：注意： 由于向量空间大小在声明时确定，当 L-lengthListSize 时，表

24、空间已满，不可再做插入操作（2） 顺序表插入操作过程顺序表插入操作过程在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此将表中位置为 n 上的结点，依次后移到位置 n+1 上，空出第 i 个位置，然后在该位置上插入新结点 x。仅当插入位置 i=n+1 时，才无须移动结点，直接将 x 插入表的末尾。（3）具体算法描述）具体算法描述void InsertList(SeqList *L，DataType x，int i)/将新结点 x 插入 L 所指的顺序表的第 i 个结点 ai 的位置上int j;if (iL-length+1)Error(“position error“);/非法位置

25、，退出运行if (L-length=ListSize)Error(“overflow“); /表空间溢出，退出运行for(j=L-length-1;j=i-1;j-)L-dataj+1=L-dataj;/结点后移L-datai-1=x; /插入 xL-Length+; /表长加 1 （4）算法分析）算法分析 问题的规模： 表的长度 L-length（设值为 n）是问题的规模。 移动结点的次数由表长 n 和插入位置 i 决定：算法的时间主要花费在 for 循环中的结点后移语句上。该语句的执行次数是 n-i+1。当 i=n+1：移动结点次数为 0，即算法在最好时间复杂度是 0(1)当 i=1：移动

26、结点次数为 n，即算法在最坏情况下时间复杂度是 0(n) 移动结点的平均次数 Eis(n) ：其中：在表中第 i 个位置插入一个结点的移动次数为 n-i+1，pi 表示在表中第 i 个位置上插入一个结点的概率。不失一般性，假设在表中任何合法位置（1in+1）上的插入结点的机会是均等的，则 p1=p2=pn+1=1/(n+1)因此，在等概率插入的情况下，即在顺序表上进行插入运算，平均要移动一半结点即在顺序表上进行插入运算，平均要移动一半结点6 删除删除（1）删除运算的逻辑描述）删除运算的逻辑描述线性表的删除运算是指将表的第 i（1in）个结点删去，使长度为 n 的线性表变成长度为 n-1 的线性

27、表（2）顺序表删除操作过程）顺序表删除操作过程在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若 i=n，则只要简单地删除终端结点，无须移动结点；若 1in-1，则必须将表中位置 i+1，i+2，n 的结点，依次前移到位置 i，i+1，n-1 上，以填补删除操作造成的空缺。（3）具体算法描述）具体算法描述void DeleteList(SeqList *L,int i)/从 L 所指的顺序表中删除第 i 个结点 aiint j;if(iL-length)Error(“position error“); /非法位置for(j=i;jlength-1;j+).L-dataj-1=L-dataj; /结点前移L-length-; /表长减小 （4）算法分析）算法分析结点的移动次数由表长 n 和位置 i 决定：i=n 时，结点的移动次数为 0，即为 0(1)i=1 时，结点的移动次数为 n-1，算法