自学考试：数据结构考点复习

自学考试：数据结构考点复习 第一章概论 数据(Data)是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。随着计算机应用领域的扩大，数据的范畴包括:整数、实数、字符串、图像和声音等。 数据元素 Data Element是数据的基本单位。数据元素也称元素、结点、顶点、记录。 一个数据元素可以由若干个数据项(也可称为字段、域、属性)组成。数据项是具有独立含义的最小标识单位。 数据结构(Data Structure) 指的是数据之间的相互关系，即数据的组织形式。 1(数据结构一般包括以下三方面内容: ?数据元素之间的逻辑关系，也称数据的逻辑结构(Logical Structure);数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 抽象出来的数学模型。 ?数据元素及其关系在计算机存储器内的表示，称为数据的存储结构Storage Structure 数据的存储结构是逻辑结构用计算机语言的实现(亦称为映象)，它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。 ?数据的运算，即对数据施加的操作。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。 2(数据的逻辑结构分类 在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类: (1)线性结构 线性结构的逻辑特征是:若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。栈、队列、串等都是线性结构。 (2)非线性结构 非线性结构的逻辑特征是:一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 3(数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到: (1)顺序存储方法 该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 由此得到的存储表示称为顺序存储结构(Sequential Storage Structure)，通常借助程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 (2)链接存储方法 该方法不 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构(Linked Storage Structure),通常借助于程序语言的指针类型描述。 1 / 108 (3)索引存储方法 该方法通常在储存结点信息的同时，还建立附加的索引表。 索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引(Dense Index)。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(Spare Index)。索引项的一般形式是:(关键字、地址) 关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置;稀疏索引中索引项的地址指示一组结点的起始存储位置。 (4)散列存储方法 该方法的基本思想是:根据结点的关键字直接计算出该结点的存储地址 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 4(数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。 存储结构是数据结构不可缺少的一个方面:同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。 数据类型(DataType) 所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。 按"值"是否可分解，可将数据类型划分为两类: ?原子类型:其值不可分解。通常是由语言直接提供。 【例】C语言的整型、字符型等标准类型及指针等简单的导出类型; ?结构类型:其值可分解为若干个成分(或称为分量)。是用户借助于语言提供的描述机制自己定义的，它通常是由标准类型派生的，故它也是一种导出类型。例: C的数组、结构等类型。 抽象数据类型(AbstractType简称ADT) ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 ADT ADT-Name{ Data://数据说明 数据元素之间逻辑关系的描述 Operations://操作说明 Operation1://操作1，它通常可用C或C，，的函数原型来描述 Input:对输入数据的说明 Preconditions:执行本操作前系统应满足的状态//可看作初始条件 Process:对数据执行的操作 Output:对返回数据的说明 Postconditions:执行本操作后系统的状态//"系统"可看作某个数据结构 2 / 108 Operation2://操作2 „„ }//ADT 抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在C，，中，我们可以用类(包括模板类)的说明来表示ADT，用类的实现来实现ADT。因此，C，，中实现的类相当于是数据的存储结构及其在存储结构上实现的对数据的操作。 ADT和类的概念实际上反映了程序或软件设计的两层抽象:ADT相当于是在概念层(或称为抽象层)上描述问题，而类相当于是在实现层上描述问题。此外，C，，中的类只是一个由用户定义的普通类型，可用它来定义变量(称为对象或类的实例)。因此，在C，，中，最终是通过操作对象来解决实际问题的，所以我们可将该层次看作是应用层。例如，main程序就可看作是用户的应用程序。 由于C语言中没有提供"类"这一数据类型，因此无法实现ADT，故我们不采用ADT的形式来描述数据结构，以节省篇幅。大家只要记住，它实际上等价于我们定义的数据的逻辑结构以及在逻辑结构上定义的抽象操作。 学习数据结构的意义 各种应用问题可以大致分为数值计算问题和非数值计算问题两大类。 1(处理数值计算问题时，数据元素之间的相互关系一般用数学方程式加以描述; 2(处理非数值性问题时，要设计出合适的数据结构，才能有效地解决问题。 算法分析 1(评价算法好坏的标准 求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢, 选用的算法首先应该是"正确"的。此外，主要考虑如下三点: ?执行算法所耗费的时间; ?执行算法所耗费的存储空间，其中主要考虑辅助存储空间; ?算法应易于理解，易于编码，易于调试等等。 2(算法性能选择 一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触:要节约算法的执行时间往往要以牺牲更多的空间为代价;而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重: ?若该程序使用次数较少，则力求算法简明易懂; ?对于反复多次使用的程序，应尽可能选用快速的算法; ?若待解决的问题数据量极大,机器的存储空间较小,则相应算法主要考虑如何节省空间 3(算法的时间性能分析 (1)算法耗费的时间和语句频度 一个算法所耗费的时间=算法中每条语句的执行时间之和 每条语句的执行时间=语句的执行次数(即频度(FrequencyCount))×语 句执行一次所需时间 算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。 3 / 108 若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。 (2)问题规模和算法的时间复杂度 算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。 一个算法的时间复杂度(TimeComplexity,也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。 3这表明，当n充分大时，T(n)和n之比是一个不等于零的常数。即T(n)和333n是同阶的，或者说T(n)和n的数量级相同。记作T(n)=O(n)是算法MatrixMultiply的渐近时间复杂度。 数学符号"O"的严格的数学定义: 若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0，使得当n?n0时都满足0?T(n)?C?f(n)。 (3)渐进时间复杂度评价算法时间性能 主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能 【例3(7】有两个算法A和A求解同一问题，时间复杂度分别是1223T(n)=100n，T(n)=5n。 12(1)当输入量n,20时，有T(n),T(n)，后者花费的时间较少。 1232(2)随着问题规模n的增大，两个算法的时间开销之比5n/100n=n/20亦随着增大。即当问题规模较大时，算法A比算法A要有效地多。 1223它们的渐近时间复杂度O(n)和O(n)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。 (4)算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。 (5)最坏时间复杂度和平均时间复杂度 最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间 常见的时间复杂度按数量级递增排列依次为:常数0(1)、对数阶230(logn)、线形阶0(n)、线形对数阶0(nlogn)、平方阶0(n)立方阶0(n)、„、22knk次方阶0(n)、指数阶0(2)。 n显然，时间复杂度为指数阶0(2)的算法效率极低，当n值稍大时就无法应用。 4 / 108 类似于时间复杂度的讨论，一个算法的空间复杂度 (SpaceComplexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。 第二章线性表 线性表的逻辑定义 线性表(LinearList)是由n(n?0)个数据元素(结点)a，a，„，a组成的有限序列。 12n?数据元素的个数n定义为表的长度(n=0时称为空表)。 ?将非空的线性表(n,0)记作:(a，a，„，a) 12n?数据元素a(1?i?n)只是个抽象符号，其具体含义在不同情况下i可以不同。 线性表的逻辑结构特征 对于非空的线性表: ?有且仅有一个开始结点a，没有直接前趋，有且仅有一个直接后继a 12?有且仅有一个终结结点a，没有直接后继，有且仅有一个直接前趋a nn-1?其余的内部结点a(2?i?n-1)都有且仅有一个直接前趋a和一个a ii-1i+1常见的线性表的基本运算 1(InitList(L)构造一个空的线性表L，即表的初始化。 2(ListLength(L)求线性表L中的结点个数，即求表长。 3(GetNode(L，i)取线性表L中的第i个结点，这里要求1?i?ListLength(L) 4(LocateNode(L，x) 在L中查找值为x的结点，并返回该结点在L中的位置。若L中有多个结点的值和x相同，则返回首次找到的结点位置;若L中没有结点的值为x，则返回一个特殊值表示查找失败。 5(InsertList(L，x，i) 在线性表L的第i个位置上插入一个值为x的新结点，使得原编号为i，i+1，„，n的结点变为编号为i+1，i+2，„，n+1的结点。这里1?i?n+1，而n是原表L的长度。插入后，表L的长度加1。 6(DeleteList(L，i) 删除线性表L的第i个结点，使得原编号为i+1，i+2，„，n的结点变成编号为i，i+1，„，n-1的结点。这里1?i?n，而n是原表L的长度。删除后表L的长度减1。 注意:以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是"做什么"，至于"如何做"等实现细节，只有待确定了存储结构之后才考虑。 顺序存储结构 顺序表 1(顺序表的定义 (1)顺序存储方法 即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。 (2)顺序表(SequentialList) 用顺序存储方法存储的线性表简称为顺序表。 2(结点a的存储地址 i假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a的存储地址(简称为基地址)是1 5 / 108 LOC(a)，那么结点a的存储地址LOC(a)可通过下式计算:LOC(a)1iii=LOC(a)+(i-1)*c1?i?n 1注意:在顺序表中，每个结点a的存储地址是该结点在表中的位置ii的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。 3(顺序表类型定义 #define ListSize 100 //表空间的大小可根据实际需要而定，这里假设为100 typedef int DataType; //DataType的类型可根据实际情况而定，这里假设为int typedef struct { DataType data[ListSize];//向量data用于存放表结点 int length;//当前的表长度 }SeqList; 注意:?用向量这种顺序存储的数组类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构类型来定义顺序表类型。 ?存放线性表结点的向量空间的大小ListSize应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。 ?由于C语言中向量的下标从0开始，所以若L是SeqList类型的顺序表，则线性表的开始结点a和终端结点a分别存储在L(data[0]和L(Data[L(length-1]1n中。 ?若L是SeqList类型的指针变量，则a和a分别存储在L-,data[0]1n和L-,data[L-,length-1]中。 4(顺序表的特点 顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址。因此顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。 顺序表上实现的基本运算 1.表的初始化 Void InitList(SeqList*L){\\顺序表的初始化即将表的长度置为0 L-,length=0;} 2.求表长 Int ListLength(SeqList*L){\\求表长只需返回L-,length Return L-,length;} 3.取表中第i个结点 DataTypeGetNode(L，i){ \\取表中第i个结点只需返回和L-,data[i-1]即可 If (i<1||i>L-,length-1) Error("positionerror"); Return L-,data[i-1];} 4.查找值为x的结点 5.插入 (1)插入运算的逻辑描述 线性表的插入运算是指在表的第i(1?i?n+1)个位置上，插入一个新结点x，使长度为n的线性表:(a，„，a，a，„a)变成长度为n+1的线性表:(a，„，a，x，1i-1in1i-1a，„a) in 6 / 108 注意:?由于向量空间大小在声明时确定，当L-,length?ListSize时，表空间已满，不可再做插入操作 ?当插入位置i的值为i,n或i,1时为非法位置，不可做正常插入操作 (2)顺序表插入操作过程 在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n，n-1，„，i上的结点，依次后移到位置n+1，n，„，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。 (3)具体算法描述 void InsertList(SeqList *L，DataType x，int i) { //将新结点 x插入L所指的顺序表的第i个结点a的位置上 i int j; if (i<1||i>L->length+1) Error("position error");//非法位置，退出运行 if (L->length>=ListSize) Error("overflow"); //表空间溢出，退出运行 for(j=L->length-1;j>=i-1;j--) L->data[j+1]=L->data[j];//结点后移 L->data[i-1]=x; //插入x L->Length++; //表长加1 } (4)算法分析 ?问题的规模 表的长度L-,length(设值为n)是问题的规模。 ?移动结点的次数由表长n和插入位置i决定 算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。 当i=n+1:移动结点次数为0，即算法在最好时间复杂度是0(1) 当i=1:移动结点次数为n，即算法在最坏情况下时间复杂度是0(n) ?移动结点的平均次数 其中: 在表中第i个位置插入一个结点的移动次数为n-i+1 p表示在表中第i个位置上插入一个结点的概率。不失一般性，假设在i表中任何合法位置(1?i?n+1)上的插入结点的机会是均等的，则p=p=„=p=1/(n+1) 12n+1因此，在等概率插入的情况下，E=n/2 即在顺序表上进行插入运算，平均要移动一半结点。 6(删除 (1)删除运算的逻辑描述 线性表的删除运算是指将表的第i(1?i?n)个结点删去，使长度为n的线性表(a，„，a，a，a，„，a)变成长度为n-1的线性表(a，„，1i-1ii+1n1a，a，„，a) i-1i+1n注意:当要删除元素的位置i不在表长范围(即i,1或i,L-,length)时，为非法位置，不能做正常的删除操作 (2)顺序表删除操作过程 在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点;若1?i?n-1， 7 / 108 则必须将表中位置i+1，i+2，„，n的结点，依次前移到位置i，i+1，„，n-1上，以填补删除操作造成的空缺。(3)具体算法描述 void DeleteList(SeqList *L,int i) //从L所指的顺序表中删除第i个结点a i {int j; if(i<1||i>L->length) Error("position error"); //非法位置 for(j=i;j<=L->length-1;j++) L->data[j-1]=L->data[j]; //结点前移 L->length--; //表长减小 }} (4)算法分析 ?结点的移动次数由表长n和位置i决定: i=n时，结点的移动次数为0，即为0(1) i=1时，结点的移动次数为n-1，算法时间复杂度分别是0(n) ?移动结点的平均次数E(n) DE其中:删除表中第i个位置结点的移动次数为n-i p表示删除表中第i个位置上结点的概率。不失一般性，假设在表中任i何合法位置(1?i?n)上的删除结点的机会是均等的，则p=p=„=p=1/n 12n因此，在等概率插入的情况下，E=(n-1)/2 顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0(n)。 链式存储结构 单链表 1、链接存储方法 链接方式存储的线性表简称为链表(Linked List)。 链表的具体存储表示为: ?用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的，也可以是不连续的) ?链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link)) 注意:链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ???????data域--存放结点值的数据域 ?data?next?next域--存放结点的直接后继的地址(位置)的指针域(链域??????? 注意:?链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。?每个结点只有一个链域的链表称为单链表(Single Linked List)。 3、头指针head和终端结点指针域的表示 单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。 注意:链表由头指针唯一确定，单链表可以用头指针的名字来命名。 终端结点无后继，故终端结点的指针域为空，即NULL。 4、单链表的一般图示法 5、单链表类型描述 8 / 108 typedef char DataType; //假设结点的数据域类型为字符 typedef struct node{ //结点类型定义 DataType data; //结点的数据域 struct node *next;//结点的指针域 }ListNode; typedef ListNode *LinkList; ListNode *p; LinkList head; 注意:?LinkList和ListNode*是不同名字的同一个指针类型(命名的不同是为了概念上更明确)?LinkList类型的指针变量head表示它是单链表的头指针 ?ListNode*类型的指针变量p表示它是指向某一结点的指针 6、指针变量和结点变量 ? ? 指针变量 ? 结点变量 ???????????????????????????????? ? 定义 ?在变量说明部分显式定义 ?在程序执行时，通过标准 ? ? ? ?函数malloc生成 ???????????????????????????????? ? 取值 ?非空时，存放某类型结点 ?实际存放结点各域内容 ? ? ?的地址 ? ???????????????????????????????? ?操作方式? 通过指针变量名访问 ? 通过指针生成、访问和释放 ? ?生成结点变量的标准函数 p=(ListNode*)malloc(sizeof(ListNode)); //函数malloc分配一个 类型为ListNode的结点变量的空间,并将其首 地址放入指针变量p中 ?释放结点变量空间的标准函数 free(p);//释放p所指的结点变量空间 ?结点分量的访问 利用结点变量的名字*p访问结点分量 方法一:(*p).data和(*p).next 方法二:p-，data和p-，next ?指针变量p和结点变量*p的关系 指针变量p的值——结点地址 结点变量*p的值——结点内容 (*p).data的值——p指针所指结点的data域的值 (*p).next的值——*p后继结点的地址 *((*p).next)——*p后继结点 注意:?若指针变量p的值为空(NULL)，则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。 ?有关指针类型的意义和说明方式的详细解释， 单链表的运算 1、建立单链表 假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符'\n'为输入条件结束标志符。动态地建立单链表的常用方法有如下两种: (1)头插法建表 ?算法思路 从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。 9 / 108 注意:该方法生成的链表的结点次序与输入顺序相反。 ?具体算法实现 LinkList CreatListF(void) //返回单链表的头指针 { char ch; LinkList head;//头指针 ListNode *s; //工作指针 head=NULL; //链表开始为空 ch=getchar(); //读入第1个字符 while(ch!='\n'){ s=(ListNode *)malloc(sizeof(ListNode));//生成新结点 s->data=ch; //将读入的数据放入新结点的数据域中 s->next=head; head=s; ch=getchar(); //读入下一字符 } return head; } (2)尾插法建表 ?算法思路 从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。注意: ?采用尾插法建表，生成的链表中结点的次序和输入顺序一致 ?必须增加一个尾指针r,使其始终指向当前链表的尾结点 ?具体算法实现 LinkList CreatListR(void) //返回单链表的头指针 { char ch; LinkList head;//头指针 ListNode *s,*r; //工作指针 head=NULL; //链表开始为空 r=NULL;//尾指针初值为空 ch=getchar(); //读入第1个字符 while(ch!='\n'){ s=(ListNode *)malloc(sizeof(ListNode));//生成新结点 s->data=ch; //将读入的数据放入新结点的数据域中 if (head!=NULL) head=s;//新结点插入空表 else r->next=s;//将新结点插到*r之后 r=s;//尾指针指向新表尾 ch=getchar(); //读入下一字符 }//endwhile if (r!=NULL) r->next=NULL;//对于非空表，将尾结点指针域置空head=s; return head; } 注意:?开始结点插入的特殊处理 由于开始结点的位置是存放在头指针(指针变量)中,而其余结点的位置是在其前趋结点的指针域中，插入开始结点时要将头指针指向开始结点。 10 / 108 ?空表和非空表的不同处理 若读入的第一个字符就是结束标志符,则链表head是空表,尾指针r亦为空,结点*r不存在;否则链表head非空,最后一个尾结点*r是终端结点,应将其指针域置空。 (3)尾插法建带头结点的单链表 ?头结点及作用 头结点是在链表的开始结点之前附加一个结点。它具有两个优点: ?由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理; ?无论链表是否为空，其头指针都是指向头结点的非空指针(空表中头结点的指针域空)，因此空表和非空表的处理也就统一了。 ?带头结点的单链表注意:头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。 ?尾插法建带头结点链表算法 LinkList CreatListR1(void) {//用尾插法建立带头结点的单链表 char ch; //生成头结点 LinkList head=(ListNode *)malloc(sizeof(ListNode)); ListNode *s,*r; //工作指针 r=head; // 尾指针初值也指向头结点 while((ch=getchar())!='\n'){ s=(ListNode *)malloc(sizeof(ListNode));//生成新结点 s->data=ch; //将读入的数据放入新结点的数据域中 r->next=s; r=s; } r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空 return head; } 注意:上述算法里，动态申请新结点空间时未加错误处理，这对申请空间极少的程序而言不会出问题。但在实用程序里，尤其是对空间需求较大的程序，凡是涉及动态申请空间，一定要加入错误处理以防系统无空间可供分配。 (4)算法时间复杂度 以上三个算法的时间复杂度均为0(n)。 2.单链表的查找运算 (1)按序号查找 ?链表不是随机存取结构 在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。 ?查找的思想方法 计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。而当p指针指为null且j?i时，则表示找不到第i个结点。 注意:头结点可看做是第0个结点。 ?具体算法实现 ListNode* GetNode(LinkList head,int i) {//在带头结点的单链表head中查找第i个结点，若找到(0?i?n)， //则返回该结点的存储位置，否则返回NULL。 11 / 108 int j; ListNode *p; p=head;j=0;//从头结点开始扫描 while(p->next&&jnext为NULL或i=j为止 p=p->next; j++; } if(i==j) return p;//找到了第i个结点 else return NULL;//当i<0或i>0时，找不到第i个结点 } ?算法分析 算法中，while语句的终止条件是搜索到表尾或者满足j?i，其频度最多为i，它和被寻找的位置有关。在等概率假设下，平均时间复杂度为:O(n) (2)按值查找 ?思想方法 从开始结点出发，顺着链逐个将结点的值和给定值key作比较，若有结点的值与key相等，则返回首次找到的其值为key的结点的存储位置;否则返回NULL。 ?具体算法实现 ListNode* LocateNode (LinkList head,DataType key) {//在带头结点的单链表head中查找其值为key的结点 ListNode *p=head->next;//从开始结点比较。表非空，p初始值指向开始结点 while(p&&p->data!=key)//直到p为NULL或p->data为key为止 p=p->next;//扫描下一结点 return p;//若p=NULL，则查找失败，否则p指向值为key的结点 } ?算法分析该算法的执行时间亦与输入实例中key的取值相关，其平均时间复杂度分析类似于按序号查找，为O(n)。 3.插入运算 (1)思想方法 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到a与a之间。具体步骤:(1)找到a存储位置p i-1ii-1(2)生成一个数据域为x的新结点*s (3)令结点*p的指针域指向新结点 (4)新结点的指针域指向结点a。 i(2)具体算法实现 void InsertList(LinkList head,DataType x,int i) {//将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上 ListNode *p; p=GetNode(head,i-1);//寻找第i-1个结点 if (p==NULL)//i<1或i>n+1时插入位置i有错 Error("position error"); s=(ListNode *)malloc(sizeof(ListNode)); s->data=x;s->next=p->next;p->next=s; } (3)算法分析 算法的时间主要耗费在查找操作GetNode上，故时间复杂度亦为O(n)。 4.删除运算 (1)思想方法删除运算是将表的第i个结点删去。 12 / 108 具体步骤:(1)找到a的存储位置p(因为在单链表中结点a的存储i-1i地址是在其直接前趋结点a的指针域next中) i-1(2)令p-,next指向a的直接后继结点(即把a从链上摘下) ii(3)释放结点a的空间，将其归还给"存储池"。 i(2)具体算法实现 void DeleteList(LinkList head,int i) {//删除带头结点的单链表head上的第i个结点 ListNode *p,*r; p=GetNode(head,i-1);//找到第i-1个结点 if (p==NULL||p->next==NULL)//i<1或i>n时，删除位置错 Error("position error");//退出程序运行 r=p->next;//使r指向被删除的结点a i p->next=r->next;//将a从链上摘下 i free(r);//释放结点a的空间给存储池 } i注意:设单链表的长度为n，则删去第i个结点仅当1?i?n时是合法的。 当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在(即p～=NULL)且*p不是终端结点(即p-,next～=NULL)时，才能确定被删结点存在。 (3)算法分析算法的时间复杂度也是O(n)。链表上实现的插入和删除运算，无须移动结点，仅需修改指针。 循环链表(CircularLinkedList)循环链表是一种首尾相接的链表。 1、循环链表 (1)单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。(2)多重链的循环链表--将表中结点链在多个环上 2、带头结点的单循环链表注意:判断空链表的条件是head==head->next 3、仅设尾指针的单循环链表 用尾指针rear表示的单循环链表对开始结点a和终端结点a查找时间1n都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。带尾指针的单循环链表可见下图。 注意:判断空链表的条件为rear==rear->next; 4、循环链表的特点 循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。 分析:若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点a，然后将结点b链到a的后面，其执行时间n1n是O(n)。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。相应的算法如下: LinkList Connect(LinkList A,LinkList B) {//假设A，B为非空循环链表的尾指针 LinkList p=A->next;//?保存A表的头结点位置 A->next=B->next->next;//?B表的开始结点链接到A表尾 free(B->next);//?释放B表的头结点 B->next=p;//? return B;//返回新循环链表的尾指针 } 13 / 108 注意:?循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-,next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。?在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。 双链表 1、双向链表(DoubleLinkedList) 双(向)链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。 注意:?双链表由头指针head惟一确定的。?带头结点的双链表的某些运算变得方便。 ?将头结点和尾结点链接起来，为双(向)循环链表。 2、双向链表的结点结构和形式描述 ?结点结构 ?形式描述 typedef struct dlistnode{ DataType data; struct dlistnode *prior,*next; }DListNode; typedef DListNode *DLinkList; DLinkList head; 3、双向链表的前插和删除本结点操作 由于双链表的对称性，在双链表能能方便地完成各种插入、删除操作。 ?双链表的前插操作 void DInsertBefore(DListNode *p,DataType x) {//在带头结点的双链表中，将值为x的新结点插入*p之前，设p?NULL DListNode *s=malloc(sizeof(DListNode));//? s->data=x;//? s->prior=p->prior;//? s->next=p;//? p->prior->next=s;//? p->prior=s;//? } ?双链表上删除结点*p自身的操作 Void DDeleteNode(DlistNode *p) {//在带头结点的双链表中，删除结点*p，设*p为非终端结点 p->prior->next=p->next;//? p->next->prior=p->prior;//? free(p);//? } 注意:与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。 顺序表和链表的比较 顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢,这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑: ? ? 顺序表 ? 链表 14 / 108 ???????????????????????????????????? ?基?分?静态分配。程序执行之前必须明确?动态分配只要内存空间尚有空闲，? ?于?配?规定存储规模。若线性表长度n变?就不会产生溢出。因此，当线性表? ?空?方?化较大，则存储规模难于预先确定?的长度变化较大，难以估计其存储? ?间?式?估计过大将造成空间浪费，估计太?规模时，以采用动态链表作为存储? ?考? ?小又将使空间溢出机会增多。 ?结构为好。 ? ?虑?????????????????????????????????? ? ?存?为1.当线性表的长度变化不大， ? <1 ? ? ?储?易于事先确定其大小时，为了节约? ? ? ?密?存储空间，宜采用顺序表作为存储? ? ? ?度?结构。 ? ? ???????????????????????????????????? ?基?存?随机存取结构，对表中任一结点都?顺序存取结构，链表中的结点，需? ?于?取?可在O(1)时间内直接取得 ?从头指针起顺着链扫描才能取得 ? ?时?方?线性表的操作主要是进行查找，很? ? ?间?法?少做插入和删除操作时，采用顺序? ? ?考? ?表做存储结构为宜。 ? ? ?虑?????????????????????????????????? ? ?插?在顺序表中进行插入和删除，平均?在链表中的任何位置上进行插入和? ? ?入?要移动表中近一半的结点，尤其是?删除，都只需要修改指针。对于频? ? ?删?当每个结点的信息量较大时，移动?繁进行插入和删除的线性表，宜采? ? ?除?结点的时间开销就相当可观。 ?用链表做存储结构。若表的插入和? ? ?操? ?删除主要发生在表的首尾两端，则? ? ?作? ?采用尾指针表示的单循环链表为宜 存储密度(StorageDensity)是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即存储密度=(结点数据本身所占的存储量)/(结点结构所占的存储总量) 第三章栈和队列 栈的定义及基本运算 1、栈的定义 栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表。 (1)通常称插入、删除的这一端为栈顶(Top)，另一端称为栈底(Bottom)。 (2)当表中没有元素时称为空栈。 (3)栈为后进先出(LastInFirstOut)的线性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈中"最新"的元素，即最后插入(进栈)的元素，而最先插入的是被放在栈的底部，要到最后才能删除。 2、栈的基本运算 (1)InitStack(S)构造一个空栈S。 (2)StackEmpty(S)判栈空。若S为空栈，则返回TRUE，否则返回FALSE (3)StackFull(S)判栈满。若S为满栈，则返回TRUE，否则返回FALSE 注意:该运算只适用于栈的顺序存储结构 (4)Push(S，x)进栈。若栈S不满，则将元素x插入S的栈顶。 (5)Pop(S)退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。 (6)StackTop(S)取栈顶元素.若栈S非空,则返回栈顶元素,但不改变栈的状态 顺序栈栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。 1、顺序栈的类型定义 15 / 108 #define StackSize 100 //假定预分配的栈空间最多为100个元素 Typedef char DataType; //假定栈元素的数据类型为字符 Typedef struct { DataType data[StackSize]; Int top; }SeqStack; 注意:?顺序栈中元素用向量存放?栈底位置是固定不变的，可设置在向量两端的任意一个端点?栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top(通常称top为栈顶指针)来指示当前栈顶位置 2、顺序栈的基本操作 前提条件:设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S-,data[0]是栈底元素。(1)进栈操作 进栈时，需要将S-,top加1 注意:?S-,top==StackSize-1表示栈满 ?"上溢"现象--当栈满时，再做进栈运算产生空间溢出的现象。上溢是一种出错状态，应设法避免。 (2)退栈操作 退栈时，需将S-,top减1 注意:?S-,top<0表示空栈 ?"下溢"现象——当栈空时，做退栈运算产生的溢出现象。下溢是正常现象，常用作程序控制转移的条件。 3、顺序栈的基本运算 (1) 置栈空 void InitStack(SeqStack *S){//将顺序栈置空 S->top=-1; } (2) 判栈空 int StackEmpty(SeqStack *S){ return S->top==-1; } (3) 判栈满 int StackFull(SeqStack *S){ return S->top==StackSize-1; } (4) 进栈 void Push(S，x){ if (StackFull(S)) Error("Stack overflow"); //上溢，退出运行 S->data[++S->top]=x;// 栈顶指针加1后将x入栈} (5) 退栈 DataType Pop(S){ if(StackEmpty(S)) Error("Stack underflow"); //下溢,退出运行 return S->data[S->top--];//栈顶元素返回后将栈顶指针减1 } (6) 取栈顶元素 DataType StackTop(S){ if(StackEmpty(S)) Error("Stack is empty"); return S->data[S->top]; } 4、两个栈共享同一存储空间 当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。 只有当整个向量空间被两个栈占满(即两个栈顶相遇)时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为?m/2?和?m/2?的向量空间比较，前者发生上溢的概率比后者要小得多。 链栈栈的链式存储结构称为链栈。 1、链栈的类型定义 链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。 链栈的类型说明如下: typedef struct stacknode{ DataType data struct stacknode *next }StackNode; 16 / 108 typedef struct{ StackNode *top; //栈顶指针 }LinkStack; 注意:?LinkStack结构类型的定义是为了方便在函数体中修改top指针本身?若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。 2、链栈的基本运算 (1) 置栈空 Void InitStack(LinkStack *S) { S->top=NULL; } (2) 判栈空int StackEmpty(LinkStack *S) { return S->top==NULL; } (3) 进栈void Push(LinkStack *S,DataType x) {//将元素x插入链栈头部 StackNode *p=(StackNode *)malloc(sizeof(StackNode)); p->data=x; p->next=S->top; //将新结点*p插入链栈头部 S->top=p; } (4) 退栈 DataType Pop(LinkStack *S) { DataType x; StackNode *p=S->top;//保存栈顶指针 if(StackEmpty(S)) Error("Stack underflow."); //下溢 x=p->data; //保存栈顶结点数据 S->top=p->next; //将栈顶结点从链上摘下 free(p); return x; } (5) 取栈顶元素 DataType StackTop(LinkStack *S) { if(StackEmpty(S)) Error("Stack is empty.") return S->top->data; } 注意:链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义 StackFull运算。 队列的定义及基本运算 1、定义队列(Queue)是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表(1)允许删除的一端称为队头(Front)。(2)允许插入的一端称为队尾(Rear)。(3)当队列中没有元素时称为空队列。(4)队列亦称作先进先出(FirstInFirstOut)的线性表，简称为FIFO表。 2、队列的基本逻辑运算 (1)InitQueue(Q)置空队。构造一个空队列Q。 (2)QueueEmpty(Q)判队空。若队列Q为空，则返回真值，否则返回假值。 (3)QueueFull(Q)判队满。若队列Q为满，则返回真值，否则返回假值。 (4)EnQueue(Q，x)若队列Q非满，则将元素x插入Q的队尾。此操作简称入队(5)DeQueue(Q)若队列Q非空，则删去Q的队头元素，并返回该元素。此操作称出队。 (6)QueueFront(Q)若队列Q非空， 则返回队头元素，但不改变队列Q的状态。 顺序队列 1、顺序队列 (1)顺序队列的定义队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。(2)顺序队列的表示?和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。?由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。 (3)顺序队列的基本操作 ?入队时:将新元素插入rear所指的位置，然后将rear加1。 17 / 108 ?出队时:删去front所指的元素，然后将front加1并返回被删元素。 注意:?当头尾指针相等时，队列为空。?在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。 (4)顺序队列中的溢出现象 ?"下溢"现象当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。 ?"真上溢"现象当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。 ?"假上溢"现象由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。 2、循环队列 为充分利用向量空间，克服"假上溢"现象的方法是:将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。 (1)循环队列的基本操作 循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界(QueueSize-1)时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为:?方法一:f(i+1==QueueSize)//i表示front或rear i=0; else i++; ?方法二--利用"模运算" i=(i+1)%QueueSize; (2)循环队列边界条件处理 循环队列中，由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。解决这个问题的方法至少有三种: ?另设一布尔变量以区别队列的空和满; ?少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满(注意:rear所指的单元始终为空); ?使用一个计数器记录队列中元素的总数(即队列长度)。 (3)循环队列的类型定义 #define QueurSize 100//应根据具体情况定义该值 Typedef char DataType;//DataType的类型依赖于具体的应用 Typedef Sturet{ Int front; //头指针，队非空时指向队头元素置 Int rear; //尾指针，队非空时指向队尾元素的下一位 Int count; //计数器，记录队中元素总数 DataType data[QueueSize] }CirQueue; (4)循环队列的基本运算用第三种方法，循环队列的六种基本运算: ?置队空void InitQueue(CirQueue*Q){ Q->front=Q->rear=0; Q->count=0;//计数器置0 } ?判队空int QueueEmpty(CirQueue *Q){ return Q->count==0;//队列无元素为空} ?判队满int QueueFull(CirQueue *Q){ Return Q->count == QueueSize;//队中元素个数等于QueueSize时队满 } 18 / 108 ?入队void EnQueue(CirQueuq *Q,DataType x){ If (QueueFull((Q)) Error("Queueoverflow");//队满上溢 Q->count++;//队列元素个数加1 Q->data[Q->rear]=x;//新元素插入队尾 Q->rear=(Q->rear+1)%QueueSize;//循环意义下将尾指针加1 } ?出队DataTypeDeQueue(CirQueue *Q){ DataType temp; If (QueueEmpty((Q)) Error("Queueunderflow");//队空下溢 temp=Q->data[Q->front]; Q->count--;//队列元素个数减1 Q->front=(Q->front+1)&QueueSize;//循环意义下的头指针加1 Return temp;} ?取队头元素DataType QueueFront(CirQueue *Q){ If (QueueEmpty(Q)) Error("Queueifempty."); Return Q->data[Q->front];} 链队列 1、链队列的定义队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。typedef struct queuenode{ //链队列中的结点类型 DataType data; struct queuenode *next; }QueueNode; typedef struct{ QueueNode *front; //队头指针 QueueNode *rear; //队尾指针 }LinkQueue; 2、链队列的结构类型说明 注意:增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作。链队列示意图见上图，图中Q为LinkQueue型的指针。 3、链队列的基本运算 (1)置空队 void Init Queue(LinkQueue *Q){ Q->front=Q->rear=NULL;} (2)判队空int QueueEmpty(LinkQueue *Q){ Return Q->front==NULL&&Q->rear==Null;//实际上只须判断队头指针是否为空即可 } (3)入队Void EnQueue(LinkQueue *Q,DataType x) {//将元素x插入链队列尾部 QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点 p->data=x; p->next=NULL; if(QueueEmpty(Q)) Q->front=Q->rear=p; //将x插入空队列 else { //x插入非空队列的尾 Q->rear->next=p; //*p链到原队尾结点后 19 / 108 Q->rear=p; //队尾指针指向新的尾 } } (4) 出队 DataType DeQueue (LinkQueue *Q) { DataType x; QueueNode *p; if(QueueEmpty(Q)) Error("Queue underflow");//下溢 p=Q->front; //指向对头结点 x=p->data; //保存对头结点的数据 Q->front=p->next; //将对头结点从链上摘下 if(Q->rear==p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空 Q->rear=NULL; free(p); //释放被删队头结点 return x; //返回原队头数据 } (5) 取队头元素 DataType QueueFront(LinkQueue *Q) { if(QueueEmpty(Q)) Error("Queue if empty."); return Q->front->data; } 注意:?和链栈类似，无须考虑判队满的运算及上溢。 ?在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。?以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算 第四章串 本章简介串(又称字符串)是一种特殊的线性表，它的每个结点仅由一个字符组成。在早期的程序设计语言中，串仅在输入或输出中以直接量的形式出现，并不参与运算。随着计算机的发展，串在文字编辑、词法扫描、符号处理以及定理证明等许多领域得到越来越广泛的应用。在高级语言中开始引入了串变量的概念，如同整型、实型变量一样，串变量也可以参加各种运算。本章将讨论串的有关概念，存储方法和串的基本运算及其实现。 串的基本概念 1、串串(String)是零个或多个字符组成的有限序列。一般记为 S="aa„„a"其中?S是串名 ?双引号括起的字符序列是串值;将12n串值括起来的双引号本身不属于串,它的作用是避免串与常数或与标识符混淆。 ?a(1?i?n)可以是字母、数字或其它字符; ?串中所包含的字i符个数称为该串的长度。 2、空串和空白串 长度为零的串称为空串(EmptyString)，它不包含任何字符。 仅由一个或多个空格组成的串称为空白串(BlankString)。 注意:空串和空白串的不同。 3、子串和主串串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号定义为子串在主串中的序号(或位置)。 注意:?空串是任意串的子串?任意串是其自身的子串。 20 / 108 4、串变量和串常量通常在程序中使用的串可分为:串变量和串常量。 (1)串变量串变量和其它类型的变量一样，其取值是可以改变的。 (2)串常量串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。 串的基本运算 对于串的基本运算，很多高级语言均提供了相应的运算符或标准的库函数来实现为叙述方便，先定义几个相关的变量: char s1[20]="dir/bin/appl",s2[20]="file.asm",s3[30],*p; int result; 下面以C语言中串运算介绍串的基本运算 1、求串长 int strlen(char *s);//求串s的长度 2、串复制 char *strcpy(char *to,*from);//将from串复制到to串中，并返回to开始处指针 3、联接 char *strcat(char *to,char *from);//将from串复制到to串的末尾， 并返回to串开始处的指针 4、串比较 int strcmp(char *s1,char *s2);//比较s1和s2的大小， //当s1s2和s1=s2时，分别返回小于0、大于0和等于0的值 5、字符定位 char *strchr(char *s,char c);//找c在字符串s中第一次出现的位置， 若找到，则返回该位置，否则返回NULL 注意:?上述操作是最基本的，其中后 4个操作还有变种形式:strncpy，strncath和strnchr。 ?其它的串操作见C的。在不同的高级语言中，对串运算的种类及符号都不尽相同 ?其余的串操作一般可由这些基本操作组合而成 【例】求子串的操作可如下实现: void substr(char *sub,char *s,int pos,int len){ //s和sub是字符数组，用sub返回串s的第pos个字符起长度为len的子串 //其中0<=pos<=strlen(s)-1,且数组sub至少可容纳len+1个字符。 if (pos<0||pos>strlen(s)-1||len<0) Error("parameter error!"); strncpy(sub,&s[pos],len);//从s[pos]起复制至多len个字符到sub }//substr 串的顺序存储 1、顺序串 串的顺序存储结构简称为顺序串。 与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列。因此可用高级语言的字符数组来实现，按其存储分配的不同可将顺序串分为如下两类: (1)静态存储分配的顺序串 (2)动态存储分配的顺序串 2、静态存储分配的顺序串 (1)直接使用定长的字符数组来定义 该种方法顺序串的具体描述: #define MaxStrSize 256//该值依赖于应用，由用户定义 Typedef char SeqString[MaxStrSize];//SeqString是顺序串类型 SeqString S;//S是一个可容纳255个字符的顺序串 注意?串值空间的大小在编译时刻就已确定，是静态的。难以适应插入、链接等操作?直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。所以串空间最大值 21 / 108 为MaxStrSize时，最多只能放MaxStrSize-1个字符。 (2)类似顺序表的定义 直接使用定长的字符数组存放串内容外，可用一个整数来表示串的长度。此时顺序串的类型定义完全和顺序表类似: Typedef struct{ Char ch[MaxStrSize];//可容纳256个字符，并依次存储在ch[0..n]中 Int length; }SeqString; 注意:?串的长度减1的位置就是串值的最后一个字符的位置。 ?这种表示的优点是涉及串长的操作速度快。 3、动态存储分配的顺序串 顺序串的字符数组空间可使用C语言的malloc和free等动态存储管理函数，来根据实际需要动态地分配和释放。这样定义的顺序串类型亦有两种形式。 (1)较简单的定义 Typedef char *string;//C中的串库相当于使用此类型定义串(2)复杂定义 Typedef struct{ Char *ch;//若串非空，则按实际的串长分配存储区，否则ch为NULL Int length; }HString; 1、链串 用单链表方式存储串值，串的这种链式存储结构简称为链串。 2、链串的结构类型定义 Typedef struct node{ Char data; Struct node *next; }LinkStrNode;//结点类型 Typedef LinkStrNode *LinkString;//LinkString为链串类型 LinkString S;//S是链串的头指针 注意:?链串和单链表的差异仅在于其结点数据域为单个字符: ?一个链串由头指针唯一确定。 3、链串的结点大小 通常，将结点数据域存放的字符个数定义为结点的大小。结点的大小的值越大，存储密度越高。(1)结点大小为1的链串 这种结构便于进行插入和删除运算，但存储空间利用率太低。 (2)结点大小>1的链串 注意:?为了提高存储密度，可使每个结点存放多个字符。 ?当结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。 ?虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。 子串定位运算 串是特殊的线性表，故顺序串和链串上实现的运算分别与顺序表和单链表上进行的操作类似。 下面讨论在顺序串和链串上实现的子串定位运算。 1、子串定位运算 子串定位运算类似于串的基本运算中的字符定位运算。只不过是找子串而不是找字符在主串中首次出现的位置。此运算的应用非常广泛。 22 / 108 子串定位运算又称串的模式匹配或串匹配。 2、目标(串)和模式(串) 在串匹配中，一般将主串称为目标(串)，子串称为模式(串)。假设T为目标串，P为模式串，且不妨设:T="ttt„t" P="ppp„p"(0012n-1012m-1,m?n) 3、串匹配 串匹配就是对于合法的位置(又称合法的位移)0?i?n-m，依次将目标串中的子串"tt„t"和模式串"ppp„p"进行比较: ii+1i+m-1012m-1?若"tt„t","ppp„p"，则称从位置i开始的匹配成功，或ii+1i+m-1012m-1称i为有效位移。 ?若"tt„t"?"ppp„p"，则称从位置i开始的匹配失败，或ii+1i+m-1012m-1称i为无效位移。 因此,串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移 注意:有些应用中要求求出P在T中所有出现的有效位移。 4、顺序串上的子串定位运算 (1)朴素的串匹配算法的基本思想 即用一个循环来依次检查n-m+1个合法的位移i(0?i?n-m)是否为有效位移。 (2)顺序串上的串匹配算法 以下以第二种定长的顺序串类型作为存储结构。给出串匹配的算法: #define MaxStrSize 256 //该值依赖于应用，由用户定义 typedef struct{ char ch[MaxStrSize]; //可容纳256个字符，并依次存储在ch[0..n]中 int length; }SeqString; int Naive StrMatch(SeqString T,SeqString P) {//找模式P在目标T中首次出现的位置，成功返回第1个有效位移，否则返回-1 int i,j,k; int m=P.length; //模式串长度 int n=T.length; //目标串长度 for(i=0;i<=n-m;i++){ //0<=i<=n-m是合法的位移 j=0;k=i; //下面用while循环判定i是否为有效位移 while(jdata==p->data){ //继续比较后续结点中字符 t=t->next; p=p->next; } else{ //已确定shift为无效位移 shift=shift->next; //模式右移，继续判定shift是否为有效位移 t=shift; p=P; } }//endwhile if(p==NULL) return shift; //匹配成功 else return NULL; //匹配失败 } 该算法的时间复杂度与顺序表上朴素的串匹配算法相同。 第五章多维数组和广义表 多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是:一个数据元素可能有多个直接前驱和多个直接后继。 多维数组 1、数组(向量)——常用数据类型 一维数组(向量)是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。 同一数组的不同元素通过不同的下标标识。(a,a,„,a) 12n2、二维数组 二维数组A可视为由m个行向量组成的向量，或由n个列向量组成的mn向量。二维数组中的每个元素a既属于第i行的行向量，又属于第j列的ij列向量。 3、多维数组 三维数组A可视为以二维数组为数据元素的向量。四维数组可视为以mnp三维数组为数据元素的向量„„三维数组中的每个元素a都属于三个向ijk量。四维数组中的每个元素都属于四个向量„„ 4、数组的顺序存储方式 由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。 数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。 (1)行优先顺序 将数组元素按行向量排列，第i+1个行向量紧接在第i 24 / 108 个行向量后面。【例】二维数组A的按行优先存储的线性序列为:mna,a,„,a,a,a,„,a,„，a,a,„，a注意:?PASCAL和C语言11121n21222nm1m2mn 中，数组按行优先顺序存储。 ?行优先顺序推广到多维数组，可规定为先排最右的下标。 (2)列优先顺序 将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。【例】二维数组A的按列优先存储的线性序列为:mna,a,„,a,a,a,„,a,„，a,a,„，a注意:?FORTRAN语言中，1121m11222m21n2nmn 数组按列优先顺序存储。 ?列优先顺序推广到多维数组，可规定为先排最左的下标。 5、数组元素的地址计算公式 (1)按行优先顺序存储的二维数组Amn地址计算公式LOC(a)=LOC(a)+[(i-1)×n+j-1]×d ij11其中:?LOC(a)是开始结点的存放地址(即基地址) 11?d为每个元素所占的存储单元数 ?由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。 (2)按列优先顺序存储的二维数组Amn地址计算公式LOC(a)=LOC(a)+[(j-1)×m+i-1]×d ij11(3)按行优先顺序存储的三维数组Amnp地址计算公式 LOC(a)=LOC(a)+[(i-1)×n×p+(j-1)×p+k-1]×d ijk111(4)下界不为1的二维数组的地址计算公式 ?二维数组A[c1..d1,c2..d2]的地址计算公式: LOC(a)=LOC(a)+[(i-c1)×(d2-c2+1)+j-c2]×d ijc1c2?下界为0的二维数组的地址计算公式(C语言中使用) LOC(a)=LOC(a)+[i×(d2+1)+j]×d ij00注意:以下讨论的数组存储结构都以C语言下标表示。 矩阵是科学与 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 计算问题中常用的数学对象之一。 矩阵的存储 1、矩阵的二维数组描述 矩阵用二维数组描述时，存储的密度为1。可以对其元素进行随机存取，各种矩阵运算也非常简单。 2、矩阵的压缩存储 矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩存储:即为多个相同的非零元素只分配一个存储空间;对零元素不分配空间。 特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。 1(对称矩阵 (1)对称矩阵 在一个n阶方阵A中，若元素满足下述性质:a=a0?i，j?n-1 则ijji称A为对称矩阵。 (2)对称矩阵的压缩存储 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。 ?按"行优先顺序"存储主对角线(包括对角线)以下的元素即按a,a,a,„„，a,a„，a次序存放在一个向量sa[0((n(n+1)001011n-1,0n-1,1n-1,n-1,2-1]中(下三角矩阵中，元素总数为n(n+1),2)。 25 / 108 其中:sa[0]=a,sa[1]=a,„„，sa[n(n+1),2-1]=a 0010n-1,n-1?元素a的存放位置 ija元素前有i行(从第0行到第i-1行)，一共有: ij1+2+„+i=i×(i+1),2个元素; 在第i行上，aij之前恰有j个元素(即a，a，„，a)，因此有: i0ili,j-1sa[i×(i+1),2+j]=a ij?a和sa[k]之间的对应关系: ij若i?j，k=i×(i+1),2+j0?k1时，元素a=0。 i+1，iij由此可知，一个k对角线矩阵(k为奇数)A是满足下述条件的矩阵:若|i-j|>(k-1),2，则元素a=0。对角矩阵可按行优先顺序或对角线的顺序，ij将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。 稀疏矩阵 设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数(即s<data置换为B的三元组表b->data。 ?三元组表的转置 27 / 108 方法一:简单地交换a->data中i和j中的内容，得到按列优先顺序存储倒b->data;再将b->data重排成按行优先顺序的三元组表。 方法二:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。 按这种方法设计的算法，其基本思想是:对A中的每一列col(0?col?a->n-1)，通过从头至尾扫描三元组表a->data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。 ?具体算法: Void TransMatrix(TriTupleTable *b，TriTupleTable *a) {//*a，*b是矩阵A、B的三元组表表示，求A转置为B Int p，q，col; b->m=a->n;b->n=a->m;//A和B的行列总数互换 b->t=a->t;//非零元总数 if(b->t<=0) Error("A=0");//A中无非零元，退出 q=0; for (col=0;coln;col++)//对A的每一列 for(p=0;pt;p++)//扫描A的三元组表 if(a->data[p](j==col) {//找列号为col的三元组 b->data[q)(i=a->data[p].j; b->data[q](j=a->data[p].i; b->data[q](v=a->data[p].v;q++; } } //TransMatrix ?算法分析 该算法的时间主要耗费在col和p的二重循环上:若A的列数为n，非零元素个数t，则执行时间为O(n×t)，即与A的列数和非零元素个数的乘积成正比。 通常用二维数组表示矩阵时，其转置算法的执行时间是O(m×n)，它正比于行数和列数的乘积。 由于非零元素个数一般远远大于行数，因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间。 3、带行表的三元组表 为了方便某些矩阵运算，在按行优先存储的三元组表中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。这就是带行表的三元组表。 (1)类型描述 #define MaxRow l00//在三元组表定义前加入此最大行定义 Typedef struct{ TriTupleNode data[MaxSize]; Int RowTab[MaxRow];//行表，应保证m?MaxRow Int m，n，t; }RTriTupleTable; (2)带行表的三元组表的操作 ?对于任给行号i(0?i?m-1)，能迅速地确定该行的第一个非零元在三元组表中的存储位置为RowTab[i] ?RowTab[i](0?i?m-1)表示第i行之前的所有行的非零元数。 28 / 108 ?第i行上的非零元数目为RowTab[i+1]-RowTab[i](0?i?m-2) ?最后一行(即第m-l行)的非零元数目为t-RowTab[m-1](t为矩阵的非零元总数) 注意:若在行表中令RowTab[m]=t(要求MaxRow>m)会更方便些，且t可省略。 带行表的三元组表可改进矩阵的转置算法，具体【参阅其它参考 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 】。 4(稀疏矩阵压缩存储方式分析 (1)三元组表和带行表的三元组表的特点 相应的算法描述较为简单，但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵运算就显得不太适合。【例】执行将矩阵B相加到矩阵A上的运算时，某位置上的结果可能会由非零元变为零元，但也可能由零元变为非零元，这就会引起在A的三元组表中进行删除和插人操作，从而导致大量结点的移动。对此类运算采用链式存储结构为宜。 (2)稀疏矩阵的链式结构稀疏矩阵的链式结构有十字链表等方法，适用于非零元变化大的场合，比较复杂。 广义表的概念 广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。1、广义表定义广义表是n(n?0)个元素a，a，„，a，„，a的有限序列。 12in其中:?a--或者是原子或者是一个广义表。?广义表通常记作:iLs=(a,a,„,a，„，a) 12in?Ls是广义表的名字，n为它的长度。?若a是广义表，则称它为Lsi的子表。 注意:?广义表通常用圆括号括起来，用逗号分隔其中的元素。 ?为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 ?若广义表Ls非空(n?1)，则a是LS的表头，其余元素组成的表(a，l1a，„，a)称为Ls的表尾。?广义表是递归定义的 2n2、广义表表示 (1)广义表常用表示 ?E=() E是一个空表，其长度为0 ?L=(a，b)L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表 ?A=(x，L)=(x，(a，b))A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。 ?B=(A，y)=((x，(a，b))，y)B是长为2的广义表，第一个元素是子表A，第二个元素是原子y。 ?C=(A，B)=((x，(a，b))，((x，(a，b))，y))C的长度为2，两个元素都是子表。 ?D=(a，D)=(a，(a，(a，(„))))D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。 (2)广义表的深度一个表的"深度"是指表展开后所含括号的层数。 【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为?。 (3)带名字的广义表表示 如果规定任何表都是有名字的，为了既表明每个表的名字，又说明它的组成，则可以在每个表的前面冠以该表的名字，于是上例中的各表又可以写成: 29 / 108 ?E() ?L(a，b) ?A(x，L(a，b)) ?B(A(x，L(a，b))，y) ?C(A(x，l(a，b))，B(A(x，L(a，b))，y)) ?D(a，D(a，D(„))) (4)广义表的图形表示 (a)广义表的图形表示: ?图中的分支结点对应广义表 ?非分支结点一般是原子 ?但空表对应的也是非分支结点。 【例】下图给出了几个广义 表的图形表示。 (b)广义表的图形形状划分: ?与树对应的广义表称为纯表，它限制了表中成分的共享和递归 ?允许结点共享的表称再入表【例】上图(d),子表A是共享结点，它既是C的一个元素，又是子表B 的元素;?允许递归的表称为递 归表【例】上图(e)，表D是其自身的子表。(5)递归表、再人表、纯表、线性表之间的关系满足: 广义表不仅是线性表的推广，也是树的推广。 3、广义表运算 由于广义表是对线性表和树的推广，并且具有共享和递归特性的广义表可以和有向图(见第7章)建立对应，因此广义表的大部分运算与这些数据结构上的运算类似。 在此，只讨论广义表的两个特殊的基本运算:取表头head(Ls)和取表尾tail(Ls)。 根据表头、表尾的定义可知:任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。 【例】head(L)=a，tail(L)=(b) head(B)=A，tail(B)=(y) 由于tail(L)是非空表，可继续分解得到:head(tail(L))=b，tail(tail(L))=() 对非空表A和(y)，也可继续分解。 注意:广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算;而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。 第六章树 树的概念 1.家族树 2.树的定义 树的递归定义:树(Tree)是n(n?0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件:(1)有且仅有一个特定的称为根(Root)的结点;(2)其余的结点可分为m(m?0)个互不相交的子集T，lT，„，T，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。 2m注意:树的递归定义刻画了树的固有特性:一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。 3.树的表示 30 / 108 (1)树形图表示树形图表示是树结构的主要表示方法。 树的树形图表示中:结点用圆圈表示，结点的名字写在圆圈旁边(有时亦可写在圆圈内) (2)树的其他表示法 ?嵌套集合表示法是用集合的包含关系来描述树结构。?凹入表表示法类似于书的目录?广义表表示法用广义表的形式表示的。 4.树结构的基本术语 (1)结点的度(Degree)树中的一个结点拥有的子树数称为该结点的度(Degree)。 一棵树的度是指该树中结点的最大度数。度为零的结点称为叶子(Leaf)或终端结点。度不为零的结点称分支结点或非终端结点。除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。 (2)孩子(Child)和双亲(Parents) 树中某个结点的子树之根称为该结点的孩子(Child)或儿子，相应地，该结点称为孩子的双亲(Parents)或父亲。同一个双亲的孩子称为兄弟(Sibling)。 (3)祖先(Ancestor)和子孙(Descendant) ?路径(path)若树中存在一个结点序列k，k，„，k，使得k是k12iii+1的双亲(1?i2-1。 kk-1k另一方面，由性质2可得:n?2-1，即:2-l1，则k的双亲编号为;若i=1，则K是根结点，无双亲。 ii?若2i?n，则K的左孩子的编号是2i;否则，K无左孩子，即K必定iii是叶子。因此完全二叉树中编号的结点必定是叶结点。 ?若2i+1?n，则K的右孩子的编号是2i+1;否则，K无右孩子。 ii?若i为奇数且不为1，则K的左兄弟的编号是i-1;否则，K无左兄ii弟。 ?若i为偶数且小于n，则K的右兄弟的编号是i+1;否则，K无右兄ii弟。 33 / 108 2(完全二叉树的顺序存储 将完全二叉树中所有结点按编号顺序依次存储在一个向量bt[0..n]中。 其中:bt[1((n]用来存储结点 bt[0]不用或用来存储结点数目。 3(一般二叉树的顺序存储 (1)具体方法 ?将一般二叉树添上一些"虚结点"，成为"完全二叉树" ?为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给结点编号?将结点按编号存入向量对应分量，其中"虚结点"用"?"表示 (2)优点和缺点 ?对完全二叉树而言，顺序存储结构既简单又节省存储空间。 ?一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。 最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间 ?在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。 链式存储结构 1(结点的结构 二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点的 结构为: 2(结点的类型说明 Typedef char DataType;//用户可根据具体应用定义DataType的实际类型 Typedef struct node{ DataType data; Struct node *lchild，*rchild;//左右孩子指针 }BinTNode;//结点类型 Typedef BinTNode *BinTree;//BinTree为指向BinTNode类型结点的指针类型 3(二叉链表(二叉树的常用链式存储结构) 在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root，就构成了二叉树的链式存储结构，并将其称为二叉链表。注意:?一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL;若结点的某个孩子不存在，则相应的指针为空。 ?具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。 4(带双亲指针的二叉链表 经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。 注意:二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。 遍历概念 所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。 34 / 108 遍历 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 1(遍历方案 从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操 作: (1)访问结点本身(N)，(2)遍历该结点的左子树(L)，(3)遍历该结点的右子树(R)。 以上三种操作有六种执行次序:NLR、LNR、LRN、NRL、RNL、RLN。 注意:前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。 2(三种遍历的命名根据访问结点操作发生位置命名: ?NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ?LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ?LRN:后序遍历(PostorderTraversal) ——访问结点的操作发生在遍历其左右子树之后。 注意:由于被访问的结点必是某子树的根，所以N(Node)、L(Leftsubtlee) 和R(Rightsubtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 遍历算法 1(中序遍历的递归算法定义:若二叉树非空，则依次执行如下操作: (1)遍历左子树;(2)访问根结点;(3)遍历右子树。 2(先序遍历的递归算法定义:若二叉树非空，则依次执行如下操作: (1)访问根结点;(2)遍历左子树;(3)遍历右子树。 3(后序遍历得递归算法定义:若二叉树非空，则依次执行如下操作: (1)遍历左子树;(2)遍历右子树;(3)访问根结点。 4(中序遍历的算法实现 用二叉链表做为存储结构，中序遍历算法可描述为: Void InOrder(BinTreeT) {//算法里?~?是为了说明执行过程加入的标号 ?if (T){ //如果二叉树非空 ?InOrder(T->lchild); ?printf(",c"，T->data);//访问结点 ?InOrder(T->rchild); ?} ?}//InOrder 遍历序列 1(遍历二叉树的执行踪迹 三种递归遍历算法的搜索路线相同(如下图虚线所示)。具体线路为: 从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后 回到根结点。 2(遍历序列 (1)中序序列 中序遍历二叉树时，对结点的访问次序为中序序列 【例】中序遍历上图所示的二叉树时，得到的中序序列为:DBAECF (2)先序序列 先序遍历二叉树时，对结点的访问次序为先序序列 【例】先序遍历上图所示的二叉树时，得到的先序序列为:ABDCEF (3)后序序列 后序遍历二叉树时，对结点的访问次序为后序序列 35 / 108 【例】后序遍历上图所示的二叉树时，得到的后序序列为:DBEFCA 注意:(1)在搜索路线中，若访问结点均是第一次经过结点时进行的，则是前序遍历;若访问结点均是在第二次(或第三次)经过结点时进行的，则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。 (2)上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念，对上述三种线性序列，要在某结点的前趋和后继之前冠以其遍历次序名称。 二叉链表的构造 1(基本思想 基于先序遍历的构造，即以二叉树的先序序列为输入构造。 注意:先序序列中必须加入虚结点以示空指针的位置。 【例】建立上图所示二叉树，其输入的先序序列是: ABD??CE??F??。 2(构造算法 假设虚结点输入时以空格字符表示，相应的构造算法为: Void CreateBinTree(BinTree *T) {//构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身 Char ch; if((ch=getchar())=='') *T=NULL;//读人空格，将相应指针置空 else{ //读人非空格 *T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点 (*T)->data=ch; CreateBinTree(&(*T)->lchild);//构造左子树 CreateBinTree(&(*T)->rchild);//构造右子树 } }注意:调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。O(n) 线索二叉树概念 1(定义n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为"线索")。 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 注意:线索链表解决了二叉链表找左、右孩子困难的问题，出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题。 2(线索链表的结点结构 线索链表中的结点结构为: 其中:ltag和rtag是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。 36 / 108 3(线索二叉树的表示 【例】下面(a)图所示的中序线索二叉树，其线索链表如下面(b)图所示。 注意:图中的实线表示指针，虚线表示线索。 结点C的左线索为空，表示C是中序序列的开始结点，无前趋; 结点E的右线索为空，表示E是中序序列的终端结点，无后继。 线索二叉树中，一个结点是叶结点的充要条件为:左、右标志均是1。 二叉树的线索化 1(线索化和线索化实质 将二叉树变为线索二叉树的过程称为线索化。 按某种次序将二叉树线索化的实质是:按该次序遍历二叉树，在遍历过程中用线索取代空指针。 2(二叉树的中序线索化 (1)分析 算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。 该算法应附设一个指针pre始终指向刚刚访问过的结点(pre的初值应为NULL)，而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。 (2)将二叉树按中序线索化的算法 Typedef enum{Link，Thread } PointerTag;//枚举值Link和Thread分别为0，1 Typedef struct node{ DataType data; PointerTag ltag，rtag;//左右标志 Struct node *lchild，*rchild; }BinThrNode;\\线索二叉树的结点类型 Typedef BinThrNode *BinThrTree; BinThrNode *pre=NULL;//全局量 Void InorderThreading(BinThrTree p) {//将二叉树p中序线索化 If (p){ //p非空时，当前访问结点是*p InorderThreading(p->lchild);//左子树线索化 //以下直至右子树线索化之前相当于遍历算法中访问结点的操作 p->ltag=(p->lchild)?Link:Thread;//左指针非空时左标志为Link (即0)，否则为Thread(即1) p->rtag=(p->rchild)?Link:Thread; if (pre){//若*p的前趋*pre存在 if(pre->rtag==Thread) //若*p的前趋右标志为线索 37 / 108 pre->rchild=p; //令*pre的右线索指向中序后继 if(p->ltag==Thread) //*p的左标志为线索 p->lchild=pre; //令*p的左线索指向中序前趋 } //完成处理*pre的线索 pre=p;//令pre是下一访问结点的中序前趋 InorderThreeding(p->rehild);//右子树线索化 }//endif }//InorderThreading (3)算法分析 和中序遍历算法一样，递归过程中对每结点仅做一次访问。因此对于n个结点的二叉树，算法的时间复杂度亦为O(n)。 3(二叉树的前序线索化和后序线索化 线索二叉树的运算 1(查找某结点*p在指定次序下的前趋和后继结点 (1)在中序线索二叉树中，查找结点*p的中序后继结点 在中序线索二叉树中，查找结点*p的中序后继结点分两种情形: ?若*p的右子树空(即p->rtag为Thread)，则p->rchild为右线索，直接指向*p的中序后继。 ?若*p的右子树非空(即p->rtag为Link)，则*p的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止，该结点是*p的右子树中"最左下"的结点，即*P的中序后继结点。 在中序线索二叉树中求中序后继结点的具体算法如下: BinThrNode *InorderSuccessor(BinThrNode *p) { //在中序线索树中找结点*p的中序后继，设p非空 BinThrNode *q; If (p->rtag==Thread) //*p的右子树为空 Returnp->rchild;//返回右线索所指的中序后继 else{ q=p->rchild; //从*p的右孩子开始查找 while(q->ltag==Link) q=q->lchild; //左子树非空时，沿左链往下查找 return q; //当q的左子树为空时，它就是最左下结点 }//endif } 该算法的时间复杂度不超过树的高度h，即O(h)。 (2)在中序线索二叉树中查找结点*p的中序前趋结点 中序是一种对称序，故在中序线索二叉树中查找结点*p的中序前趋结点与找中序后继结点的方法完全对称。具体情形如下: ?若*p的左子树为空，则p->1child为左线索，直接指向*p的中序前趋结点; ?若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。该结点是*p的左子树中"最右下"的结点，它是*p的左子树中最后一个中序遍历到的结点，即*p的中序前趋结点。 由上述讨论可知:对于非线索二叉树，仅从*p出发无法找到其中序前趋(或中序后继)，而必须从根结点开始中序遍历，才能找到*p的中序前趋(或中序后继)。线索二叉树中的线索使得查找中序前趋和中序后继变得简单有效。(3)在后序线索二叉树中，查找指定结点*p的后序前趋结点 在后序线索二叉树中，查找指定结点*p的后序前趋结点的具体规律是: 38 / 108 ?若*p的左子树为空，则p->lchild是前趋线索，指示其后序前趋结点。 ?若*p的左子树非空，则p->lchild不是前趋线索。由于后序遍历时，根是在遍历其左右子树之后被访问的，故*p的后序前趋必是两子树中最后一个遍历结点。 当*p的右子树非空时，*p的右孩子必是其后序前趋 当*p无右子树时，*p的后序前趋必是其左孩子 (4)在后序线索二叉树中，查找指定结点*p的后序后继结点具体的规律:?若*p是根，则*p是该二叉树后序遍历过程中最后一个访问到的结点。*p的后序后继为空 ?若*p是其双亲的右孩子，则*p的后序后继结点就是其双亲结点 ?若*p是其双亲的左孩子，但*P无右兄弟，*p的后序后继结点是其双亲结点 ?若*p是其双亲的左孩子，但*p有右兄弟，则*p的后序后继是其双亲的右子树中第一个后序遍历到的结点，它是该子树中"最左下的叶结点" 注意:F是孩子树中"最左下"结点，但它不是叶子。 由上述讨论中可知:在后序线索树中，仅从*p出发就能找到其后序前趋结点;要找*p的后序后继结点，仅当*p的右子树为空时，才能直接由*p的右线索p->rchild得到。否则必须知道*p的双亲结点才能找到其后序后继。因此，如果线索二叉树中的结点没有指向其双亲结点的指针，就可能要从根开始进行后序遍历才能找到结点*P的后序后继。由此，线索对查找指定结点的后序后继并无多大帮助。 (5)在前序线索二叉树中，查找指定结点*p的前序后继结点 (6)在前序线索二叉树中，查找指定结点*p的前序前趋结点 在前序线索二叉树中，找某一点*p的前序后继也很简单，仅从*p出发就可以找到;但找其前序前趋也必须知道*p的双亲结点。当树中结点未设双亲指针时，同样要进行从根开始的前序遍历才能找到结点*p的前序前趋。 2(遍历线索二叉树 遍历某种次序的线索二叉树，只要从该次序下的开始结点开发，反复找到结点在该次序下的后继，直至终端结点。遍历中序线索二叉树算法: Void TraverseInorderThrTree(BinThrTree p) { //遍历中序线索二叉树 If (p) { //树非空 while(p->ltag==Link) p=p->lchild;//从根往下找最左下结点，即中序序列的开始结点 do{ printf(",c"，p->data); p=InorderSuccessor(p);//找*p的中序后继 }while(p) }//endif }//TraverselnorderThrTree 分析:?中序序列的终端结点的右线索为空，所以do语句的终止条件是p==NULL。 ?该算法的时间复杂性为O(n)。因为是非递归算法，常数因子上小于递归的遍历算法。因此，若对一棵二叉树要经常遍历，或查找结点在指定次序下的前趋和后继，则应采用线索链表作为存储结构为宜。?以上介绍的线索二叉树是一种全线索树(即左右线索均要建立)。许多应用中只要建立左右线索中的一种。 39 / 108 ?若在线索链表中增加一个头结点，令头结点的左指针指向根，右指针指向其遍历序列的开始或终端结点会更方便。 树、森林与二叉树的转换 树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树;反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。 1(树、森林到二叉树的转换 (1)将树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树:?在所有兄弟结点之间加一连线;?对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。 注意:由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。 (2)将一个森林转换为二叉树 具体方法是:?将森林中的每棵树变为二叉树?因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。 2.二叉树到树、森林的转换 把二叉树转换到树和森林自然的方式是:若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，„，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。 树的存储结构本节仅讨论树的三种常用表示法。 1.双亲链表表示法 双亲链表表示法利用树中每个结点的双亲唯一性，在存储结点信息的同时，为每个结点附设一个指向其双亲的指针parent，惟一地表示任何-棵树。 (1)双亲链表表示法的实现 方法?用动态链表实现 方法?用向量表示——更为方便 (2)双亲链表向量表示的形式说明 #define MaxTreeSize 100//向量空间的大小，由用户定义 Typedef char DataType;//应由用户定义 Typedef struct{ DataType data;//结点数据 Int parent;//双亲指针，指示结点的双亲在向量中的位置 }PTreeNode; Typedef struct{ PtreeNode nodes[MaxTreeSize]; Int n;//结点总数 }PTree; Ptree T; //T是双亲链表 注意:若T.nodes[i].parent=j，则T.nodes[i]的双亲是T.nodes[j]。 注意:?根无双亲，其parent域为-1。 ?双亲链表表示法中指针parent向上链接，适合求指定结点的双亲或祖先(包括根);求指定结点的孩子或其它后代时，可能要遍历整个数组。 2.孩子链表表示法 (1)结点结构 ?定长结点 即树中每个结点均按树的度k来设置指针。 n个结点的树一共有n*k个指针域，而树中只有n-1条边，故树中的空指针数目为 40 / 108 kn-(n-1)=n(k-1)+1(k越大，浪费的空间越多)。 ?不定长结点 即树中每个结点按本结点的度来设置指针数，并在结点中增设一个度数域degree指出该结点包含的指针数。 各结点不等长，虽然节省了空间，但是给运算带来不便。 (2)孩子链表表示法 孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。 ?孩子链表表示法的类型说明 //以下的DataType和MaxTreeSize由用户定义 Typedef struct CNode{//子链表结点 Int child;//孩子结点在向量中对应的序号 Struct Cnode *next; }CNode; Typedef struct{ DataType data;//存放树中结点数据 Cnode *firstchild;//孩子链表的头指针 }PTNode; Typedef struct{ PTNodenodes[MaxTreeSize]; Intn，root;//n为结点总数，root指出根在向量中的位置 }CTree; Ctree T;//T为孩子链表表示 注意:当结点T.nodes[i]为叶子时，其孩子链表为空，即T.nodes[i].firstchild=NULL。 ?孩子链表表示法实例 注意:?孩子结点的数据域仅存放了它们在向量空间的序号。 ?与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。?将双亲链表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。 3.孩子兄弟链表表示法 (1)表示方法 在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域leftmostchild和rightsibling，即可得树的孩子兄弟链表表示。 (2)注意:这种存储结构的最大优点是:它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。 树的遍历 设树结点R是根，根的子树从左到右依次为T，T，„，T。 12k1(树T的前序遍历定义:若树T非空则:?访问根结点R;?依次前序遍历根R的各子树T，T，„,T 12k2.树T的后序遍历定义:若树T非空则:?依次后序遍历根T的各子树T，T„T;?访问根结点R l2k注意:?前序遍历一棵树恰好等价于前序遍历该树对应的二叉树 ?后序遍历树恰好等价于中序遍历该树对应的二叉树。 森林的两种遍历方法 1(前序遍历森林 若森林非空，则:?访问森林中第一棵树的根结点;?前序遍历第一棵树中根结点的各子树所构成的森林 ?前序遍历除第一棵树外其它树构成的森林。 41 / 108 2(后序遍历森林 若森林非空，则: ?后序遍历森林中第一棵树的根结点的各子树所构成的森林; ?访问第一棵树的根结点; ?后序遍历除第一棵树外其它树构成的森林。 注意:?前序遍历森林等同于前序遍历该森林对应的二叉树 ?后序遍历森林等同于中序遍历该森林对应的二叉树 ?当用二叉链表作树和森林的存储结构时，树和森林的前序遍历和后遍历，可用二叉树的前序遍历和中序遍历算法来实现。 最优二叉树概念 1(树的路径长度 树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。 2(树的带权路径长度(WeightedPathLengthofTree，简记为WPL) 结点的权:在一些应用中，赋予树中结点的一个有某种意义的实数。 结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。 树的带权路径长度(WeightedPathLengthofTree):定义为树中所有叶结点的带权路径长度之和，通常记为: 其中: n表示叶子结点的数目 w和l分别表示叶结点k的权值和根到结点k之间的路径长度。 iiii树的带权路径长度亦称为树的代价。 3(最优二叉树或哈夫曼树 在权为w，w，„，w的n个叶子所构成的所有二叉树中，带权路径长l2n度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。 注意:?叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。?最优二叉树中，权越大的叶子离根越近。?最优二叉树的形态不唯一，WPL最小 构造最优二叉树 1(哈夫曼算法 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，故称其为哈夫曼算法。其基本思想是: (1)根据给定的n个权值w，w，„，w构成n棵二叉树的森林F={T，l2n1T，„，T}，其中每棵二叉树T中都只有一个权值为w的根结点，其左右2nii子树均空。 (2)在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时，可以从中任选两棵)，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子(谁左，谁右无关紧要)，将这两个孩子的权值之和作为新树根的权值。(3)对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是哈夫曼树。 注意?初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子 ?n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。?哈夫曼树是严格的二叉树，没有度数为1的分支结点。 2(哈夫曼树的存储结构及哈夫曼算法的实现 (1)哈夫曼树的存储结构 42 / 108 用一个大小为2n-1的向量来存储哈夫曼树中的结点，其存储结构为: #define n 100 //叶子数目 #define m 2*n-1 //树中结点总数 Typedef struct{ //结点类型 Float weight; //权值，不妨设权值均大于零 Int lchild，rchild，parent;//左右孩子及双亲指针 }HTNode; Typedef HTNode HuffmanTree[m];//HuffmanTree是向量类型 注意:因为C语言数组的下界为0，故用-1表示空指针。树中某结点的lchild、rchild和parent不等于-1时，它们分别是该结点的左、右孩子和双亲结点在向量中的下标。 这里设置parent域有两个作用:其一是使查找某结点的双亲变得简单;其二是可通过判定parent的值是否为-1来区分根与非根结点。 (2)哈夫曼算法的简要描述 在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree): (1)初始化将T[0((m-1]中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。 (2)输人读人n个叶子的权值存于向量的前n个分量(即T[0((n-1])中。它们是初始森林中n个孤立的根结点上的权值。 (3)合并对森林中的树共进行n-1次合并，所产生的新结点依次放人向量T的第i个分量中(n?i?m-1)。每次合并分两步: ?在当前森林T[0((i-1]的所有结点中，选取权最小和次小的两个根结点[p1]和T[p2]作为合并对象，这里0?p1，p2?i-1。 ?将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点T[i]。具体操作:将T[p1]和T[p2]的parent置为i，将T[i]的lchild和rchild分别置为p1和p2 新结点T[i]的权值置为T[p1]和T[p2]的权值之和。 注意:合并后T[pl]和T[p2]在当前森林中已不再是根，因为它们的双亲指针均已指向了T[i]，所以下一次合并时不会被选中为合并对象。 (3)哈夫曼算法的求精 Void CreateHuffmanTree(HuffmanTree T) { //构造哈夫曼树，T[m-1]为其根结点 Int i，p1，p2; InitHuffmanTree(T); //将T初始化 InputWeight(T); //输入叶子权值至T[0((n-1]的weight域 for(i=n;i=0){ //直至上溯到T[c]是树根为止,若T[c]是T[p]的左孩子，则生成代码0;否则生成代码1 Cd[--start]=(T[p).1child==C)?'0':'1'; c=p; //继续上溯 } strcpy(H[i].bits，&cd[start]);//复制编码位串 }//endfor } //CharSetHuffmanEncoding 文件的编码和解码 有了字符集的哈夫曼编码表之后，对数据文件的编码过程是:依次读人文件中的字符c，在哈夫曼编码表H中找到此字符，若H[i].ch=c，则将字符c转换为H[i].bits中存放的编码串。 对压缩后的数据文件进行解码则必须借助于哈夫曼树T，其过程是:依次读人文件的二进制码，从哈夫曼树的根结点(即T[m-1])出发，若当前读人0，则走向左孩子，否则走向右孩子。一旦到达某一叶子T[i]时便译出相应的字符H[i].ch。然后重新从根出发继续译码，直至文件结束 第七章图 图的二元组定义 图G由两个集合V和E组成，记为:G=(V，E) 其中: V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。 通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。 若E(G)为空，则图G只有顶点而没有边。 有向图和无向图 1(有向图若图G中的每条边都是有方向的，则称G为有向图(Digraph)。 在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧 45 / 108 头(Head)。表示一条有向边，v是边的始点(起点)，v是边的终点。ijij因此，和是两条不同的有向边。 ijji2(无向图若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。 无向图中的边均是顶点的无序对，无序对通常用圆括号表示。无序对(v，iv)和(v，v)表示同一条边 jji注意:在以下讨论中，不考虑顶点到其自身的边。即若(v，v)或12l2是E(G)中的一条边，则要求v?v。此外，不允许一条边在图中重复出现，12即只讨论简单的图。 3(图G的顶点数n和边数e的关系 (1)若G是无向图，则0?e?n(n-1)/2 恰有n(n-1)/2条边的无向图称无向完全图 (Undireet-edCompleteGraph) (2)若G是有向图，则0?e?n(n-1)。 恰有n(n-1)条边的有向图称为有向完全图(DirectedCompleteGraph)。 注意:完全图具有最多的边数。任意一对顶点间均有边相连。 图的边和顶点的关系 1.无向边和顶点关系 若(v,v)是一条无向边，则称顶点v和v互为邻接点(Adjacent)，或ijij称v和v相邻接;并称(v,v)依附或关联(Incident)于顶点v和v，或称ijijij(v，v)与顶点v和v相关联。 ijij2(有向边和顶点关系 若是一条有向边，则称顶点v邻接到v，顶点v邻接于顶点v;ijijij并称边关联于v和v或称与顶点v和v相关联 ijijijij3(顶点的度(Degree) (1)无向图中顶点v的度(Degree) 无向图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v)。 (2)有向图顶点v的入度(InDegree) 有向图中，以顶点v为终点的边的数目称为v的入度(Indegree)，记为ID(v)。 (3)有向图顶点v的出度(Outdegree) 有向图中，以顶点v为始点的边的数目，称为v的出度(Outdegree)，记为OD(v) 注意:?有向图中，顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。 ?无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系: 子图 设G=(V，E)是一个图，若V'是V的子集，E'是E的子集，且E'中的边所关联的顶点均在V'中，则G'=(V'，E')也是一个图，并称其为G的子图(Subgraph)。 注意:设V'={v，v，v}，E'={(v，v)，(v，v)}，显然，V'属于V(G)，123l2242E'属于E(G)，但因为E'中序偶对(v，v)所关联的顶点v不在V'中，所以2244(V'，E')不是图，也就不可能是G的子图。 2路径(Path) 1(无向图的路径 46 / 108 在无向图G中，若存在一个顶点序列v,v，v,„，v，v，使得(v，pi1i2imqpv)，(v，v)，„，(v，v)均属于E(G)，则称顶点v到v存在一条路径i1i1i2imqpq(Path)。 2(有向图的路径 在有向图G中，路径也是有向的,它由E(G)中的有向边，，„，组成。 i2imq3(路径长度路径长度定义为该路径上边的数目。 4(简单路径若一条路径上除了v和v可以相同外,其余顶点均不相同,pq则称此路径为一条简单路径 5(简单回路或简单环(Cycle) 起点和终点相同(v=v)的简单路径称为简单回路或简单环(Cycle)。 pq6(有根图和图的根 在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。 连通图和连通分量 1(顶点间的连通性 无向图G中，若从顶点v到顶点v有路径(当然从v到v也一定有路径)，ijji则称v和v是连通的 ij2(连通图 若V(G)中任意两个不同的顶点v和v都连通(即有路径),则称G为连通图 ij3(连通分量 无向图G的极大连通子图称为G的连通分量(ConnectedComponent)。 注意:?任何连通图的连通分量只有一个，即是其自身 ?非连通的无向图有多个连通分量。 强连通图和强连通分量 1(强连通图 有向图G中，若对于V(G)中任意两个不同的顶点v和v，都存在从viji到v以及从v到v的路径，则称G是强连通图。 jji2(强连通分量 有向图的极大强连通子图称为G的强连通分量。 注意:?强连通图只有一个强连通分量，即是其自身。 ?非强连通的有向图有多个强连分量。 网络(Network) 若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。 注意:权是表示两个顶点之间的距离、耗费等具有某种意义的数。 图的存储 图的存储表示方法很多，这里介绍两种最常用的方法。至于具体选择哪一种表示法，主要取决于具体的应用和欲施加的操作。 为了适合用C语言描述，以下假定顶点序号从0开始，即图G的顶点集的一般形式是V(G)={v，v，„，V}。 0in-1图的邻接矩阵表示法 1(图的邻接矩阵表示法 在图的邻接矩阵表示法中:?用邻接矩阵表示顶点间的相邻关系?用一个顺序表来存储顶点信息 2(图的邻接矩阵(AdacencyMatrix) 设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n 47 / 108 阶方阵: 3(网络的邻接矩阵 若G是网络，则邻接矩阵可定义为: 其中:w表示边上的权值;?表示一个计算机允许的、大于所有边上权ij值的数。 4(图的邻接矩阵存储结构形式说明 #define MaxVertexNuml00//最大顶点数，应由用户定义 Typedef char VertexType;//顶点类型应由用户定义 Typedef int EdgeType;//边上的权值类型应由用户定义 Typedef struct{ VextexType vexs[MaxVertexNum]//顶点表 EdeType edges[MaxVertexNum][MaxVertexNum];//邻接矩阵， 可看作边表 Int n，e;//图中当前的顶点数和边数 }MGragh; 注意:?在简单应用中，可直接用二维数组作为图的邻接矩阵(顶点表 及顶点数等均可省略)。?当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型 ?无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。 2?邻接矩阵表示法的空间复杂度S(n)=0(n)。 5(建立无向网络的算法。 Void CreateMGraph(Mgraph *G) {//建立无向网的邻接矩阵表示 Int i，j，k，w; scanf(",d,d"，&G->n，&G->e);//输入顶点数和边数 for (i=0;in;i++)//读人顶点信息，建立顶点表 G->vexs[i]=getchar(); for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0;//邻接矩阵初始化 for(k=0;ke;k++){//读入e条边，建立邻接矩阵 scanf(",d,d,d"，&i，&j，&w);//输入边(v,v)上的权w ijG->edges[i][j]=w; G->edges[j][i]=w; } }//CreateMGraph 222该算法的执行时间是0(n+n+e)。由于en，&G->e); //读人顶点数和边数 for(i=0;in;i++){//建立顶点表 G->adjlist[i].vertex=getchar(); //读入顶点信息 G->adjlist[i].firstedge=NULL;//边表置为空表 } 49 / 108 for(k=0;ke;k++){//建立边表 scanf(",d,d"，&i,&j);读入边(v，v)的顶点对序号 ij s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点 s->adjvex=j; //邻接点序号为j s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; //将新结点*s插入顶点v的边表i头部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i; //邻接点序号为i s->next=G->adjlist[j].firstedge; G->adjlistk[j].firstedge=s; //将新结点*s插入顶点v的边j表头部 }//end for }CreateALGraph 该算法的时间复杂度是O(n+e)。 注意: ?建立有向图的邻接表更简单，每当读人一个顶点对序号时，仅需生成一个邻接序号为j的边表结点，将其插入到v的出边表头部即j可。 ?建立网络的邻接表时，需在边表的每个结点中增加一个存储边上权的数据域。 图的两种存储结构比较 邻接矩阵和邻接表是图的两种最常用的存储结构，它们各有所长。下面从及执行某些常用操作的时间这两方面来作一比较。 邻接矩阵 邻接链表 存储表惟一 不惟一，各边表结点的链接次序取决于建示 立邻接表的算法和边的输入次序 空间复O(n2)稠密图，考虑邻接S(n，e)=O(n+e)。稀疏图用邻接表表示比杂度表中要附加链域，应取用邻接矩阵表示节省存储空间 S(n，e) 邻接矩阵表示法为宜 求顶点无向图:第i行(或第i无向图:顶点vi的度则是第i个边表中的的度 列)上非零元素的个数结点个数 即为顶点Vi的度 有向图:邻接表表示中，第I个边表(即 有向图:第i行上非零出边表)上的结点个数是顶点Vi的出度，元素的个数是顶点Vi求Vi的人度较困难，需遍历各顶点的边 的出度OD(Vi)，第i列表。若有向图采用逆邻接表表示，则与邻 上非零元素的个数是顶接表表示相反，求Vi的人度容易，而求点Vi的人度ID(Vi)，顶顶点的出度较难。在有向图中求顶点的 点Vi的度即是二者之度。采用邻接矩阵表示比邻接表表示更方 和。 便 判定 那个元素是否为零 判最坏情况下要耗费O(n)时间在邻接表表(Vi，Vj)定矩阵中的第i行第j示中，需扫描第i个边表 或是 否是图 的一条 边 50 / 108 求边的必须检测整个矩阵，所与e的大小无关只要对每个边表的结点数目 耗费的时间是O(n2) 个数计数即可求得e，所耗费的时间，是 O(e+n)。当e?n2时，采用邻接表表示更节省空间。 图的遍历概念 1、图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。 度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用 注意:以下假定遍历过程中访问顶点的操作是简单地输出顶点。 2、布尔向量visited[0((n-1]的设置 图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited[0((n-1]，其初值为假，一旦访问了顶点V之后，便将visited[i]置为真。 i深度优先遍历(Depth-FirstTraversal) 1(图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下:首先访问出发点v，并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 2、深度优先搜索的过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过;然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。 3、深度优先遍历的递归算法 (1)深度优先遍历算法 Typedef enum{FALSE，TRUE}Boolean;//FALSE为0，TRUE为1 Boolean visited[MaxVertexNum];//访问标志向量是全局量 Void DFSTraverse(ALGraph *G) {//深度优先遍历以邻接表表示的图G,而以邻接矩阵表示G时,算法完全与此相同 Int i; 51 / 108 for(i=0;in;i++) visited[i]=FALSE;//标志向量初始化 for(i=0;in;i++) if(!visited[i])//v未访问过 DFS(G，i);//以v为源点ii开始DFS搜索 }//DFSTraverse (2)邻接表表示的深度优先搜索算法 Void DFS(ALGraph *G，int i) { //以v为出发点对邻接表表示的图G进行深度优先搜索 iEdgeNode *p; printf("visitvertex:,c"，G->adjlist[i].vertex);//访问顶点v ivisited[i]=TRUE;//标记v已访问 ip=G->adjlist[i].firstedge;//取v边表的头指针 iwhile (p){ //依次搜索v的邻接点v，这里j=p->adjvex ijif(!visited[p->adjvex])//若v尚未被访问 iDFS(G，p->adjvex);//则以V为出发点向j纵深搜索 p=p->next;//找v的下一邻接点 i} }//DFS (3)邻接矩阵表示的深度优先搜索算法 Void DFSM(Mgraph *G，int i) {//以vi为出发点对邻接矩阵表示的图G进行DFS搜索,设邻接矩阵是0,l矩阵 Int j; printf("visitvertex:,c"，G->vexs[i]);//访问顶点v ivisited[i]=TRUE; for(j=0;jn;j++)//依次搜索v的邻接点 iif(G->edges[i][j]==1&&!visited[j]) DFSM(G，j)//(v，v)?E，且v未访问过，故vijjj为新出发点 }//DFSM 注意:遍历操作不会修改图G的内容，故上述算法中可将G定义为ALGraph或MGraph类型的参数，而不一定要定义为ALGraph和MGraph的指针类型。但基于效率上的考虑，选择指针类型的参数为宜。 4、深度优先遍历序列 对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或简称为DFS序列。 (1)一个图的DFS序列不一定惟一 当从某顶点x出发搜索时，若x的邻接点有多个尚未访问过,则我们可任选一个访问之 (2)源点和存储结构的内容均已确定的图的DFS序列惟一 ?邻接矩阵表示的图确定源点后，DFS序列惟一 DFSM算法中，当从v出发搜索时，是在邻接矩阵的第i行上从左至右i选择下一个未曾访问过的邻接点作为新的出发点，若这样的邻接点多于一个，则选中的总是序号较小的那一个。 ?只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列 邻接表作为给定图的存储结构时，其表示不惟一。因为邻接表上边表里的邻接点域的内容与建表时的输入次序相关。 52 / 108 因此，只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列。 (3)栈在深度优先遍历算法中的作用 深度优先遍历过程中，后访问的顶点其邻接点被先访问，故在递归调用过程中使用栈(系统运行时刻栈)来保存已访问的顶点。 5、算法分析 对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。从DFSTraverse中调用DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n。 当访问某顶点v时，DFS(或DFSM)的时间主要耗费在从该顶点出发搜索i它的所有邻接点上。用邻接矩阵表示图时，其搜索时间为O(n);用邻接表表示图时，需搜索第i个边表上的所有结点。因此，对所有n个顶点访问，2在邻接矩阵上共需检查n个矩阵元素，在邻接表上需将边表中所有O(e)个结点检查一遍。 2所以，DFSTraverse的时间复杂度为O(n)(调用DFSM)或0(n+e)(调用DFS)。 广度优先遍历(Breadth-FirstTraversal) 1、广度优先遍历的递归定义 设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为:首先访问出发点v，接着依次访问v的所有邻接点w，w，„，w，然后再依次访问与w，w，„，w邻接的所有未曾访问过12tl2t的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。 若G是连通图，则遍历完成;否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。 广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。 2、广度优先搜索过程 在广度优先搜索过程中，设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x，x，„，x和y，y，„，y。 12s12t为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时，我们分别从x和y出发搜索其邻接点x，x，„，x12s和y，y，„，y，对其中未访者进行访问并将其人队。这种方法是将每个12t已访问的顶点人队，故保证了每个顶点至多只有一次人队。 3、广度优先搜索算法 (1)邻接表表示图的广度优先搜索算法 void BFS(ALGraph*G，int k) {// 以v为源点对用邻接表表示的图G进行广度优先搜索 k int i; CirQueue Q; //须将队列定义中DataType改为int EdgeNode *p; InitQueue(&Q);//队列初始化 printf("visit vertex:,e"，G->adjlist[k].vertex);//访问源点vk visited[k]=TRUE; EnQueue(&Q，k);//v已访问，将其人队。(实际上是将其序号人队) k while(!QueueEmpty(&Q)){//队非空则执行 i=DeQueue(&Q); //相当于v出队 i p=G->adjlist[i].firstedge; //取v的边表头指针 i 53 / 108 while(p){//依次搜索v的邻接点v(令p->adjvex=j) ij if(!visited[p->adivex]){ //若v未访问过 j printf("visitvertex:,c"， C->adjlistlp->adjvex].vertex);//访问v j visited[p->adjvex]=TRUE; EnQueue(&Q，p->adjvex);//访问过的v人队 j }//endif p=p->next;//找v的下一邻接点 i }//endwhile }//endwhile }//end of BFS (2)邻接矩阵表示的图的广度优先搜索算法 void BFSM(MGraph *G，int k) {以v为源点对用邻接矩阵表示的图G进行广度优先搜索 k int i，j; CirQueue Q; InitQueue(&Q); printf("visit vertex:,c"，G->vexs[k]); //访问源点v k visited[k]=TRUE; EnQueue(&Q，k); while(!QueueEmpty(&Q)){ i=DeQueue(&Q); //v出队 i for(j=0;jn;j++)//依次搜索v的邻接点v ij if(G->edges[i][j]==1&&!visited[j]){//v未访问 i printf("visit vertex:,c"，G->vexs[j]);//访问v i visited[j]=TRUE; EnQueue(&Q，j);//访问过的v人队 }endif i }//endwhile }//BFSM (3) 广度优先遍历算法 类似于DFSTraverse。 4、图的广度优先遍历序列 广度优先遍历图所得的顶点序列，定义为图的广度优先遍历序列，简称BFS序列。 (1)一个图的BFS序列不是惟一的 (2)给定了源点及图的存储结构时，算法BFS和BFSM所给出BFS序列就是惟一的。 5、算法分析 对于具有n个顶点和e条边的无向图或有向图，每个顶点均入队一次。广度优先遍历(BFSTraverse)图的时间复杂度和DFSTraverse算法相同。 当图是连通图时，BFSTraverse算法只需调用一次BFS或BFSM即可完2成遍历操作，此时BFS和BFSM的时间复杂度分别为O(n+e)和0(n)。 树(自由树)、无序树和有根树 自由树就是一个无回路的连通图(没有确定根)(在自由树中选定一顶点做根，则成为一棵通常的树)。 从根开始，为每个顶点(在树中通常称作结点)的孩子规定从左到右的次序，则它就成为一棵有序树。 在图的应用中，我们常常需要求给定图的一个子图，使该子图是一棵树。 生成树 1、生成树 54 / 108 如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree) 生成树是连通图的包含图中的所有顶点的极小连通子图。 图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。 2、深度优先生成树和广度优先生成树 (1)生成树的求解方法 设图G=(V，E)是一个具有n个顶点的连通图。则从G的任一顶点(源点)出发，作一次深度优先搜索(广度优先搜索)，搜索到的n个顶点和搜索过程中从一个已访问过的顶点v搜索到一个未曾访问过的邻接点v，所经ij过的边(v，v)(共n-1条)组成的极小连通子图就是生成树。(源点是生ij成树的根) 通常，由深度优先搜索得到的生成树称为深度优先生成树，简称为DFS生成树;由广度优先搜索得到的生成树称为广度优先生成树，简称为BPS生成树。 (2)求DFS生成树和BFS生成树算法 只要在DFS(或DFSM)算法的if语句中，在递归调用语句之前加入适当生成边(v，v)的操作(如将该边输出或保存)，即可得到求DFS生成树的算ij法。 在BFS(或BFSM)算法的if语句中，加入生成树边(v，v)的操作，可得ij到求BFS生成树的算法。注意: ?图的广度优先生成树的树高不会超过该图其它生成树的高度 ?图的生成树不惟一，从不同的顶点出发进行遍历，可以得到不同的生成树。 3、生成树的通用定义 若从图的某顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。(此定义不仅仅适用于无向图，对有向图同样适用。) (1)若G是强连通的有向图，则从其中任一顶点v出发，都可以访问遍G中的所有顶点，从而得到以v为根的生成树。 (2)若G是有根的有向图，设根为v，则从根v出发可以完成对G的遍历，得到G的以v为根的生成树。 (3)若G是非连通的无向图，则要若干次从外部调用DFS(或BFS)算法，才能完成对G的遍历。每一次外部调用，只能访问到G的一个连通分量的顶点集，这些顶点和遍历时所经过的边构成了该连通分量的一棵DFS(或BPS)生成树。G的各个连通分量的DFS(或BFS)生成树组成了G的DFS(或BFS)生成森林。 (4)若G是非强连通的有向图，且源点又不是有向图的根，则遍历时一般也只能得到该有向图的生成森林。 最小生成树 1、最小生成树 对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作: 这里: TE表示T的边集 w(u，v)表示边(u，v)的权。 权最小的生成树称为G的最小生成树(MinimumSpannirngTree)。最小生成树可简记为MST。 55 / 108 2、生成树和最小生成树的应用 生成树和最小生成树有许多重要的应用。 【例】网络G表示n各城市之间的通信线路网线路(其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。 3、最小生成树性质(MST性质) (1)MST性质 最小生成树性质:设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(u?U)里、另一个端点不在U(即v?V-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。 (2)MST性质的证明 为方便说明，先作以下约定: ?将集合U中的顶点看作是红色顶点，?而V-U中的顶点看作是蓝色顶点，?连接红点和蓝点的边看作是紫色边，?权最小的紫边称为轻边(即权重最"轻"的边)。于是，MST性质中所述的边(u，v)就可简称为轻边。 用反证法证明MST性质: 假设G中任何一棵MST都不含轻边(u，v)。则若T是G的一棵MST，则它不含此轻边。 由于T是包含了G中所有顶点的连通图，所以T中必有一条从红点u到蓝点v的路径P，且P上必有一条紫边(u'，v')连接红点集和蓝点集，否则u和v不连通。当把轻边(u，v)加入树T时，该轻边和P必构成了一个回路。删去紫边(u'，v')后回路亦消除，由此可得另一生成树T'。 T'和T的差别仅在于T'用轻边(u，v)取代了T中权重可能更大的紫边(u'，v')。因为w(u，v)?w(u'，v')，所以 w(T')=w(T)+w(u，v)-w(u'，v')?w(T) 故T'亦是G的MST，它包含边(u，v)，这与假设矛盾。 所以，MST性质成立。 4、求MST的一般算法描述 求MST的一般算法可描述为:针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边(u，v)，最终生成一棵含n-1条边的MST。 当一条边(u，v)加入T时，必须保证T?{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。 用伪代码可将算法描述为: GenerieMST(G){//求G的某棵MST T〈-,; //T初始为空，是指顶点集和边集均空 While T 未形成G的生成树 do{ 找出T的一条安全边(u，v); //即T?{(u，v)}仍为MST的子集 T=T?{(u，v)};//加入安全边，扩充T } returnT; //T为生成树且是G的一棵MST } 注意:下面给出的两种求MST的算法均是对上述的一般算法的求精，两算法的区别仅在于求安全边的方法不同。 为简单起见，下面用序号0，1，„，n-1来表示顶点集，即:V(G)={0，1，„，n-1}， G中边上的权解释为长度，并设T=(U，TE)。 56 / 108 5、普里姆(Prim)算法 (1)算法思想 T=(U，TE)是存放MST的集合。 ?T的初值是({r}，,) 即最小生成树初始时只有一个红点r，没有红边。 ?T经过n-1次如下步骤操作，最后得到一棵含n个顶点，n-1条边的最小生成树 ?选择紫边集中一条轻边并扩充进T ?将轻边连接的蓝点改红点 ?将轻边改红边 ?修改紫边集 (2)较小紫边集的构造 若当前形成的T中有k个顶点，|U|=k，|V-u|=n-k，故可能的紫边数目是k(n-k)。从如此大的紫边集中选择轻边是低效的。因此，必须构造较小的紫边集。 对于每个蓝点v?V-U，从v到各红点的紫边中，只有最短的那一条才有可能是轻边。因此，只须保留所有n-k个蓝点所关联的最短紫边作为轻边的候选集即可。 (3)候选紫边集合的修改 当把轻边(u，v)扩充到T时，因为v由蓝变红，故对每个剩余的蓝点j，边(v，j)就由非紫边变为紫边，这条新紫边的长度可能小于蓝点j原来所关联的最短紫边的长度。因此，用长度更小的新紫边取代那些原有的最短紫边。 (4)Prim算法的伪代码描述 PrimMST(G，T，r){ //求图G的以r为根的MST，结果放在T=(U，TE)中 InitCandidateSet(„);//初始化:设置初始的轻边候选集，并置T=({r}，,) for(k=0;k和边上表示行驶时间的权值也不同。即和应该是两条不同的边。 3、源点和终点 习惯上称路径的开始顶点为源点(Source)，路径的最后一个顶点为终点(Destination)。 为了讨论方便，设顶点集V={0，1，„，n-1}，并假定所有边上的权值均是表示长度的非负实数 单源最短路径问题(Single-SourceShortest-PathsProblem) 58 / 108 单源最短路径问题:已知有向带权图(简称有向网)G=(V，E)，找出从某个源点s?V到V中其余各顶点的最短路径。 1、边上权值相等的有向网的单源最短路径 用求指定源点的BFS生成树的算法可解决 2、迪杰斯特拉(Dijkstra)算法求单源最短路径 由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。 (1)按路径长度递增序产生各顶点最短路径 若按长度递增的次序生成从源点s到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成(将源点的最短路径看作是已生成的源点到其自身的长度为0的路径)。 (2)算法基本思想 设S为最短距离已确定的顶点集(看作红点集)，V-S是最短距离尚未确定的顶点集(看作蓝点集)。 ?初始化初始化时,只有源点s的最短距离是已知的(SD(s)=0)，故红点集S={s},蓝点集为空 ?重复以下工作，按路径长度递增次序产生各顶点最短路径 在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。 当蓝点集中仅剩下最短距离为?的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。 注意:?若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。?从源点s到终点v的最短路径简称为v的最短路径;s到v的最短路径长度简称为v的最短距离，并记为SD(v)。 (3)在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集 根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是: 源点，红点1，红点2，„，红点n，蓝点k 距离为:源点到红点n最短距离+<红点n,蓝点k>边长 为求解方便，设置一个向量D[0((n-1]，对于每个蓝点v?V-S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的"最短"路径长度(简称估计距离)。 若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i]i?V-S}，则D[k]=SD(k)。 初始时，每个蓝点v的D[c]值应为权w，且从s到v的路径上没有中间点，因为该路径仅含一条边。 注意在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键 (4)k扩充红点集s后，蓝点集估计距离的修改 将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。 对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径:P=。且D[j]减小的新路径P只可能是由于路径和边组成。 所以，当length(P)=D[k]+w小于D[j]时，应该用P的长度来修改D[j]的值。 (5)Dijkstra算法 59 / 108 Dijkstra(G，D，s){//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度 //以下是初始化操作 S={s};D[s]=0;//设置初始的红点集及最短距离 For ( all i?V-S )do //对蓝点集中每个顶点i D[i]=G[s][i];//设置i初始的估计距离为w //以下是扩充红点集 for(i=0;iD[k]+G[k][j]) //新红点k使原D[j]值变小时，用新路径的长度修改D[j]，使j离s更近。 D[j]=D[k]+G[k][j]; } } (6)保存最短路径的Dijkstra算法 设置记录顶点双亲的向量P[0((n-1]保存最短路径:当顶点i无双亲时，令P[i]=-1。 当算法结束时，可从任一P[i]反复上溯至根(源点)求得顶点i的最短路径，只不过路径方向正好与从s到i的路径相反。具体的求精算法【参见2教材】。Dijkstra算法的时间复杂度为O(n) 其他最短路径问题 最短路径问题的提法很多，其它的最短路径问题均可用单源最短路径算法予以解决: ?单目标最短路径问题 (Single-DestinationShortest-PathsProblem):找出图中每一顶点v到某指定顶点u的最短路径。只需将图中每条边反向，就可将这一问题变为单源最短路径问题，单目标u变为单源点u。 ?单顶点对间最短路径问题(Single-PairShortest-PathProblem):对于某对顶点u和v，找出从u到v的一条最短路径。显然，若解决了以u为源点的单源最短路径问题，则上述问题亦迎刃而解。而且从数量级来说，两问题的时间复杂度相同。 ?所有顶点对间最短路径问题(All-PairsShortest-PathsProblem):对图中每对顶点u和v，找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题算法予以解决。 拓扑排序(TopologicalSort) 对一个有向无环图(DirectedAcyclicGraph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若?E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(TopoiSicaiOrder)的序列，简称拓扑序列。 注意:?若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 60 / 108 ?若图中存在有向环，则不可能使顶点满足拓扑次序。 ?一个DAG的拓扑序列通常表示某种方案切实可行。 ?一个DAG可能有多个拓扑序列。 ?当有向图中存在有向环时，拓扑序列不存在 无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为: NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G中有人度为0的顶点)do{ 从G中选择一个人度为0的顶点v且输出之; 从G中删去v及其所有出边; } if(输出的顶点数目<|V(G)|) //若此条件不成立，则表示所有顶点均已输出，排序成功。 Error("G中存在有向环，排序失败～"); } 注意:无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的人度，可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点: 在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。 无后继的顶点优先拓扑排序方法 1、思想方法 该方法的每一步均是输出当前无后继(即出度为0)的顶点。对于一个DAG，按此方法输出的序列是逆拓扑次序。因此设置一个栈(或向量)T来保存输出的顶点序列，即可得到拓扑序列。若T是栈，则每当输出顶点时，只需做人栈操作，排序完成时将栈中顶点依次出栈即可得拓扑序列。若T是向量，则将输出的顶点从T[n-1]开始依次从后往前存放，即可保证T中存储的顶点是拓扑序列。 2、抽象算法描述 算法的抽象描述为: NonSuccFirstTopSort(G){//优先输出无后继的顶点 while(G中有出度为0的顶点)do{ 从G中选一出度为0的顶点v且输出v; 从G中删去v及v的所有人边 } if(输出的顶点数目<|V(G)|) Error("G中存在有向环，排序失败!"); } 3、算法求精 在对该算法求精时，可用逆邻接表作为G的存储结构。设置一个向量outdegree[0..n-1]或在逆邻接表的顶点表结点中增加1个出度域来保存各顶点当前的出度;设置一个栈或队列来暂存所有出度为零的顶点。除了增加一个栈或向量T来保存输出的顶点序列外，该算法完全类似于NonPreFirstTopSort 利用深度优先遍历对DAG拓扑排序 当从某顶点v出发的DFS搜索完成时，v的所有后继必定均已被访问过(想像它们均已被删除)，此时的v相当于是无后继的顶点，因此在DFS算法返回之前输出顶点v即可得到DAG的逆拓扑序列。 61 / 108 其中第一个输出的顶点必是无后继(出度为0)的顶点，它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列，同样可增加T来保存输出的顶点。若假设T是栈，并在DFSTraverse算法的开始处将T初始化， 利用DFS求拓扑序列的抽象算法可描述为: Void DFSTopSort(G，i，T){//在DisTraverse中调用此算法，i是搜索的出发点，T是栈 Int j; visited[i]=TRUE;//访问i for(所有i的邻接点j)//即?E(G) if(!visited[j]) DFSTopSort(G，j，T); //以上语句完全类似于DFS算法 Push(&T，i);//从i出发的搜索已完成，输出i } 只要将深度优先遍历算法DFSTraverse中对DFS的调用改为对DFSTopSort的调用，即可求得拓扑序列T。其具体算法不难从上述抽象算法求精后得到。 若G是一个DAG，则用DFS遍历实现的拓扑排序与NonSuccFirstTopSort算法完全类似;但若C中存在有向环，则前者不能正常工作。 第八章排序 排序(sort)或分类 所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下:输入:n个记录R，R，„，R，其相应的关12n键字分别为K，K，„，K。 12n输出:R，R，„，R，使得K?K?„?K。(或K?K?„?K)。 ili2ini1i2ini1i2in1(被排序对象--文件 被排序的对象--文件由一组记录组成。 记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。 注意:在不易产生混淆时，将关键字项简称为关键字。 2(排序运算的依据--关键字 用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。 关键字的选取应根据问题的要求而定。 排序的稳定性 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。 在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。 注意:排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。 排序方法的分类 1(按是否涉及数据的内、外存交换分 62 / 108 在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序);反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。 注意:?内排序适用于记录个数不很多的小文件 ?外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。 2(按策略划分内部排序方法 可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。 排序算法分析 1(排序算法的基本操作 大多数排序算法都有两个基本的操作: (1)比较两个关键字的大小; (2)改变指向记录的指针或移动记录本身。 注意:第(2)种基本操作的实现依赖于待排序记录的存储方式。 2(待排文件的常用存储方式 (1)以顺序表(或直接用向量)作为存储结构 排序过程:对记录本身进行物理重排(即通过关键字之间的比较判定，将记录移到合适的位置) (2)以链表作为存储结构 排序过程:无须移动记录，仅需修改指针。通常将这类排序称为链表(或链式)排序; (3)用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表) 排序过程:只需对辅助表的表目进行物理重排(即只移动辅助表的表目，而不移动记录本身)。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。 3(排序算法性能评价 (1)评价排序算法好坏的标准 价排序算法好坏的标准主要有两条: ?执行时间和所需的辅助空间 ?算法本身的复杂程度 (2)排序算法的空间复杂度 若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。 非就地排序一般要求的辅助空间为O(n)。 (3)排序算法的时间开销 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。 文件的顺序存储结构表示 #define n l00//假设的文件长度，即待排序的记录数目 Typedef int KeyType;//假设的关键字类型 Typedef struct{//记录类型 KeyType key;//关键字项 InfoType otherinfo;//其它数据项，类型InfoType依赖于具体应用而定义 }RecType; Typedef RecType SeqList[n+1];//SeqList为顺序表类型，表中第0个单元一般用作哨兵 63 / 108 注意:若关键字类型没有比较算符，则可事先定义宏或函数来表示比较运算。 插入排序(InsertionSort)的基本思想是:每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 本节介绍两种插入排序方法:直接插入排序和希尔排序。 直接插入排序基本思想 1、基本思想 假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。 2、第i-1趟直接插入排序: 通常将一个记录R[i](i=2，3，„，n-1)插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。 排序过程的某一中间时刻，R被划分成两个子区间R[1((i-1](已排好序的有序区)和R[i((n](当前未排序的部分，可称无序区)。 直接插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1((i-1]中适当的位置上，使R[1((i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。 插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。 一趟直接插入排序方法 1(简单方法 首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1?k?i-1);然后将R[k((i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。 注意:若R[i]的关键字大于等于R[1((i-1]中所有记录的关键字，则R[i]就是插入原位置。 2(改进的方法一种查找比较操作和记录移动操作交替地进行的方法。 具体做法:将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，„，1)的关键字进行比较: ?若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置; ?若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。 关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。 直接插入排序算法 1(算法描述 Void InsertSort(SeqList R) {//对顺序表R中的记录R[1..n]按递增序进行插入排序 Int i，j; for(i=2;i<=n;i++)//依次插入R[2]，„，R[n] if(R[i].key=1")。 注意:?实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。 【例】单链表中的头结点实际上是一个哨兵 ?引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。 算法分析 1(算法的时间性能分析 对于具有n个记录的文件，要进行n-1趟排序。 各种状态下的时间复杂?????????????????????????????? ?初始文件状态 ?正序 ?反序 ?无序(平均) ? ??????????????????????????????? 2?总关键字比较次数 ?n-1 ?(n+2)(n-1)/2??n/4 ? ??????????????????????????????? 2?总的记录移动次数 ?0 ?(n-1)(n+4)/2??n/4 ? ??????????????????????????????? 22?时间复杂度 ?0(n) ?O(n) ?O(n) ? 注意:初始文件按关键字递增有序，简称"正序"。初始文件按关键字递减有序，简称"反序"。 2(算法的空间复杂度分析 算法所需的辅助空间是一个监视哨，辅助空间复杂度S(n)=O(1)。是一个就地排序。 3(直接插入排序的稳定性 直接插入排序是稳定的排序方法。 希尔排序(ShellSort)是插入排序的一种。因D(L(Shell于1959年提出而得名。 希尔排序基本思想 65 / 108 基本思想: 先取一个小于n的整数d作为第一个增量，把文件的全部记录分成d11个组。所有距离为d的倍数的记录放在同一个组中。先在各组内进行直接插l人排序;然后，取第二个增量d0&&R[0].key0 do { increment=increment/3+1; //求下一增量 ShellPass(R，increment); //一趟增量为increment的Shell 插入排序 }while(increment>1) } //ShellSort 注意:当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。 算法分析 1(增量序列的选择 Shell排序的执行时间依赖于增量序列。 好的增量序列的共同特征: ?最后一个增量必须为1;?应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 有人通过大量的实验，给出了目前较好的结果:l.251.25当n较大时，比较和移动的次数约在n到1.6n之间。 2(Shell排序的时间性能优于直接插入排序 希尔排序的时间性能优于直接插入排序的原因: ?当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 2?当n值较小时，n和n的差别也较小，即直接插入排序的最好时间复2杂度O(n)和最坏时间复杂度0(n)差别不大。 ?在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量d逐渐缩小，分组数逐渐减少，而各组的记录数i目逐渐增多，但由于已经按d作为距离排过序，使文件较接近于有序状态，i-1所以新的一趟排序过程也较快。 因此，希尔排序在效率上较直接插人排序有较大的改进。 3(稳定性 希尔排序是不稳定的。 66 / 108 的基本思想是:两两比较待排序记录的关键字，发现两个记录的交换排序 次序相反时即进行交换，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。 冒泡排序 1、排序方法 将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R:凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 (1)初始 R[1..n]为无序区。 (2)第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，„，(R[2]，R[1]);对于每对气泡(R[j+1]，R[j])，若R[j+1].key=i;j--) //对当前无序区R[i..n]自下向上扫描 if(R[j+1].key=pivot.key) //pivot相当于在位置i上 j--; //从右向左扫描，查找第1个关键字小于pivot.key的记录R[j] if(ipivot.key R[j--]=R[i]; //相当于交换R[i]和R[j]，交换后j指针减1 } //endwhile R[i]=pivot; //基准记录已被最后定位 return i; } //partition 4、分析: (1)递归执行的路线如图中带箭头的包络线所示。(2)递归树上每一结点左旁方括号表示当前待排序的区间，结点内的关键字是划分的基准关键字 注意: 叶结点对应的子区间只有一个关键字，无须划分，故叶结点内没有基准关键字 (3)划分后得到的左、右两个子区间分别标在该结点的左、右两个孩子结点的左边方括号内。(4) 每个分支结点右旁圆括号中的内容表示对该结点左旁区间的排序过程结束之后返回的结果。它是其左右孩子对应的区间排序完成之后，将左右孩子对应的排序结果分别放在该分支结点的关键字前后所得到的关键字序列。 (5) 算法的执行顺序是递归树中的箭头顺序，实际上当把划分操作视为访问结点的操作时，快速排序的执行过程相当于是先序遍历其递归树。 注意:任何递归算法均可用递归树来描述其执行过程。 5、算法分析 快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。(1)最坏时间复杂度 最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。 因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1?i?n-1)，故总的比较次数达到最大值:2C=n(n-1)/2=O(n) max如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。 (2)最好时间复杂度 70 / 108 在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数:0(nlgn) 注意:用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn)。 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏2时间复杂度应为0(n)，最好时间复杂度为O(nlgn)。 (3)基准关键字的选取 在当前无序区中选取划分的基准关键字是决定算法性能的关键。 ?"三者取中"的规则 "三者取中"规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区伺的第1个记录进行交换，此后的划分过程与上面所给的Partition算法完全相同。 ?取位于low和high之间的随机数k(low?k?high)，用R[k]作为基准 选取基准最好的方法是用一个随机函数产生一个取位于low和high之间的随机数k(low?k?high)，用R[k]作为基准，这相当于强迫R[low..high]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序 注意:随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提高了，尤其是对初始有序的文件，一般不可能导致最坏情况的发生。算法的随机化不仅仅适用于快速排序，也适用于其它需要数据随机分布的算法。 (4)平均时间复杂度 2尽管快速排序的最坏时间为O(n)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。 (5)空间复杂度 快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。 (6)稳定性快速排序是非稳定的 选择排序(SelectionSort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。 常用的选择排序方法有直接选择排序和堆排序。 直接选择排序(StraightSelectionSort) 1、直接选择排序的基本思想 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:?初始状态:无序区为R[1..n]，有序区为空。 ?第1趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。„„ ?第i趟排序 71 / 108 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1?i?n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 2、算法描述 直接选择排序的具体算法如下: Void SelectSort(SeqList R) {int，j，k; for(i=1;i1;i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。 R[0]=R[1];R[1]=R[i];R[i]=R[0]; //将堆顶和堆中最后一个记录交换 Heapify(R，1，i-1); //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质 } //endfor } //HeapSort (4) BuildHeap和Heapify函数的实现 因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。 73 / 108 ? Heapify函数思想方法 每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R[i]交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。 "筛选法"调整堆 R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整;否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。 ?BuildHeap的实现 要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。 显然只有一个结点的树是堆，而在完全二叉树中，所有序号 的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为 ， -1，„，1的结点作为根的子树都调整为堆即可。 5算法分析 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。 堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)， 它是不稳定的排序方法。 归并排序 归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。 两路归并算法 1、算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。 (1)合并过程 合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。 重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。 (2)动态申请R1 74 / 108 实现时，R1是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。 2、归并算法 void Merge(SeqList R，int low，int m，int high) {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 //子文件R[low..high] int i=low，j=m+1，p=0; //置初始值 RecType *R1; //R1是局部向量，若p定义为此类型指针速度更快 R1=(ReeType *)malloc((high-low+1)*sizeof(RecType)); if(! R1) //申请空间失败 Error("Insufficient memory available!"); while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上 R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++]; while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中 R1[p++]=R[i++]; while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中 R1[p++]=R[j++]; for(p=0，i=low;i<=high;p++，i++) R[i]=R1[p];//归并完成后将结果复制回R[low..high] } //Merge 归并排序有两种实现方法:自底向上和自顶向下。 1、自底向上的方法 (1)自底向上的基本思想 自底向上的基本思想是:第1趟归并排序时，将待排序的文件R[1..n]看作是n个长度为1的有序子文件，将这些子文件两两归并，若n为偶数，则得到个长度为2的有序子文件;若n为奇数，则最后一个子文件轮空(不参与归并)。故本趟归并完成后，前个有序子文件长度为2，但最后一个子文件长度仍为1;第2趟归并则是将第1趟归并所得到的个有序的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止。 上述的每次归并操作，均是将两个有序的子文件合并成一个有序的子文件，故称其为"二路归并排序"。类似地有k(k>2)路归并排序。 (2)一趟归并算法 分析:在某趟归并中，设各子文件长度为length(最后一个子文件的长度可能小于length)，则归并前R[1..n]中共有个有序的子文件:R[1..length]，R[length+1..2length]，„， 。 注意:调用归并操作将相邻的一对子文件进行归并时，必须对子文件的个数可能是奇数、以及最后一个子文件的长度小于length这两种特殊情况进行特殊处理: ?若子文件个数为奇数，则最后一个子文件无须和其它子文件归并(即本趟轮空); ?若子文件个数为偶数，则要注意最后一对子文件中后一子文件的区间上界是n。 具体算法如下: Void MergePass(SeqList R，int length) {//对R[1..n]做一趟归并排序 75 / 108 Int i; for(i=1;i+2*length-1<=n;i=i+2*length) Merge(R，i，i+length-1，i+2*length-1); //归并长度为length的两个相邻子文件 if(i+length-1K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间是左子表R[1..mid-1]。 ?类似地，若R[mid].keyK) high=mid-1;//继续在R[low..mid-1]中查找 else low=mid+1;//继续在R[mid+1..high]中查找 } Return 0;//当low>high时表示查找区间为空，查找失败 }//BinSeareh 4、二分查找判定树 二分查找过程可用二叉树来描述:把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到 82 / 108 的二叉树，称为描述二分查找的判定树(DecisionTree)或比较树(ComparisonTree)。 注意:判定树的形态只与表结点个数n相关，而与输入实例中R[1..n].keys的取值无关。 (1)二分查找判定树的组成 ?圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。 ?外部结点:圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。 ?树中某结点i与其左(右)孩子连接的左(右)分支上的标记"<"、"("、">"、")"表示:当待查关键字KR[i].key)时，应走左(右)分支到达i的左(右)孩子，将该孩子的关键字进一步和K比较。若相等，则查找过程结束返回，否则继续将K与树中更下一层的结点比较。 (2)二分查找判定树的查找 二分查找就是将给定值K与二分查找判定树的根结点的关键字进行比较。若相等，成功。否则若小于根结点的关键字，到左子树中查找。若大于根结点的关键字，则到右子树中查找。【例】对于有11个结点的表，若查找的结点是表中第6个结点，则只需进行一次比较;若查找的结点是表中第3或第9个结点，则需进行二次比较;找第1，4，7，10个结点需要比较三次;找到第2，5，8，11个结点需要比较四次。 由此可见，成功的二分查找过程恰好是走了一条从判定树的根到被查结点的路径，经历比较的关键字次数恰为该结点在树中的层数。若查找失败，则其比较过程是经历了一条从判定树根到某个外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。 【例】待查表的关键字序列为:(05，13，19，21，37，56，64，75，80，88，92)，若要查找K=85的记录，所经过的内部结点为6、9、10，最后到达方形结点"9-10"，其比较次数为3。 实际上方形结点中"i-i+1"的含意为被查找值K是介于R[i].key和R[i+1].key之间的，即R[i].keyT?key，则将它插入根的右子树中。 子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。 ?二叉排序树插入新结点的非递归算法 Void InsertBST(BSTree *Tptr，KeyType key) {//若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回 BSTNode *f，*p=*TPtr;//p的初值指向根结点 while(p){//查找插入位置 if(p->key==key) return;//树中已有key，无须插入 f=p;//f保存当前查找的结点 p=(keykey)?p->lchild:p->rchild; //若keykey，则在左子树中查找，否则在右子树中查找 }//endwhile p=(BSTNode*)malloc(sizeof(BSTNode)); p->key=key;p->lchild=p->rchild=NULL;//生成新结点 if(*TPtr==NULL)//原树为空 *Tptr=p;//新插入的结点为新的根 else//原树非空时将新结点*p作为*f的左孩子或右孩子插入 if(keykey) f->lchild=p; else f->rchild=p; }//InsertBST ?二叉排序树的生成 二叉排序树的生成，是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插入到当前已生成的二叉排序树中。生成二叉排序树的算法如下: BSTree CreateBST(void) {//输入一个结点序列，建立一棵二叉排序树，将根结点指针返回 BSTreeT=NULL;//初始时T为空树 KeyType key; scanf(",d"，&key);//读人一个关键字 while(key){//假设key=0是输人结束标志 InsertBST(&T，key);//将key插入二叉排序树T scanf(",d"，&key);//读人下一关键字 } Return T;//返回建立的二叉排序树的根指针 }//BSTree 注意:输入序列决定了二叉排序树的形态。 二叉排序树的中序序列是一个有序序列。所以对于一个任意的关键字序列构造一棵二叉排序树，其实质是对此关键字序列进行排序，使其变为有序序列。"排序树"的名称也由此而来。通常将这种排序称为树排序(TreeSort)，可以证明这种排序的平均执行时间亦为O(nlgn)。 对相同的输入实例，树排序的执行时间约为堆排序的2至3倍。因此在一般情况下，构造二叉排序树的目的并非为了排序，而是用它来加速查找， 86 / 108 这是因为在一个有序的集合上查找通常比在无序集合上查找更快。因此，人们又常常将二叉排序树称为二叉查找树。 (2)二叉排序树的删除 从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足BST性质。 ?删除操作的一般步骤 (1)进行查找 查找时，令p指向当前访问到的结点，parent指向其双亲(其初值为NULL)。若树中找不到被删结点则返回，否则被删结点是*p。 (2)删去*p。 删*p时，应将*p的子树(若有)仍连接在树上且保持BST性质不变。按*p的孩子数目分三种情况进行处理。 ?删除*p结点的三种情况 (1)*p是叶子(即它的孩子数为0) 无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。 (2)*p只有一个孩子*child 只需将*child和*p的双亲直接连接后，即可删去*p。 注意: *p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4种状态。 (3)*p有两个孩子 先令q=p，将被删结点的地址保存在q中;然后找*q的中序后继*p，并在查找过程中仍用parent记住*p的双亲位置。*q的中序后继*p一定是*q的右子树中最左下的结点，它无左子树。因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q。 ?二叉排序树删除算法 分析:上述三种情况都能统一到情况(2)，算法中只需针对情况(2)处理即可。 注意边界条件:若parent为空，被删结点*p是根，故删去*p后，应将child置为根。 算法: Void DelBSTNode(BSTree *Tptr，KeyType key) {//在二叉排序树*Tptr中删去关键字为key的结点 BSTNode *parent=NUll，*p=*Tptr，*q，*child; while(p){//从根开始查找关键字为key的待删结点 if(p->key==key) break;//已找到，跳出查找循环 parent=p;//parent指向*p的双亲 p=(keykey)?p->lchild:p->rchild;//在关p的左或右子树中继续找 } if(!p) return;//找不到被删结点则返回 q=p;//q记住被删结点*p if(q->lchild&&q->rchild)//*q的两个孩子均非空，故找*q的中序后继*p for(parent=q，p=q->rchild;p->lchild;parent=p，p=p=->lchild); //现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中child=NULL的状况 child=(p->lchild)?p->lchild:p->rchild;//若是情况(2)，则child非空;否则child为空 87 / 108 if(!parent)//*p的双亲为空，说明*p为根，删*p后应修改根指针 *Tptr=child;//若是情况(1)，则删去*p后，树为空;否则child变为根 else{//*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下 if(p==parent->lchild)//*p是双亲的左孩子 parent->lchild=child;//*child作为*parent的左孩子 else parent->rchild=child;//*child作为parent的右孩子 if(p!=q)//是情况(3)，需将*p的数据复制到*q q->key=p->key;//若还有其它数据域亦需复制 }//endif free(p);/释放*p占用的空间 }//DelBSTNode (3)二叉排序树上的查找 ?查找递归算法 在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。 递归的查找算法: BSTNode *SearchBST(BSTree T，KeyType key) {//在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NUll if(T==NULL||key==T->key)//递归的终结条件 return T;//T为空，查找失败;否则成功，返回找到的结点位置 if(keykey) return SearchBST(T->lchild，key); else return SearchBST(T->rchild，key);//继续在右子树中查找 }//SearchBST ?算法分析 在二叉排序树上进行查找时，若查找成功，则是从根结点出发走了一条从根到待查结点的路径。若查找不成功，则是从根结点出发走了一条从根到某个叶子的路径。 (1)二叉排序树查找成功的平均查找长度 在等概率假设下， 注意: 与二分查找类似，和关键字比较的次数不超过 树的深度。 2)在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关 二分查找法查找长度为n的有序表，其判定树是惟一的。含有n个结点的二叉排序树却不惟一。对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同 在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关: ?在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树蜕化为棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，亦是(n+1)/2。 88 / 108 ?在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是lgn。 ?插入、删除和查找算法的时间复杂度均为O(lgn)。 (3)二叉排序树和二分查找的比较 就平均时间性能而言，二叉排序树上的查找和二分查找差不多。 就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为O(lgn)，因此更有效。二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价是O(n)。当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作;若有序表里动态查找表，则应选择二叉排序树作为其存储结构。 (4)平衡二叉树 为了保证二叉排序树的高度为lgn，从而保证然二叉排序树上实现的插入、删除和查找等基本操作的平均时间为O(lgn)，在往树中插入或删除结点时，要调整树的形态来保持树的"平衡。使之既保持BST性质不变又保证树的高度在任何情况下均为O(lgn)，从而确保树上的基本操作在最坏情况下的时间均为O(lgn)。 注意: ?平衡二叉树(BalancedBinaryTree)是指树中任一结点的左右子树的高度大致相同。 ?任一结点的左右子树的高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为O(1gn)，就可看作是平衡的。 ?平衡的二叉排序树指满足BST性质的平衡二叉树。 ?AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树度高约为lgn，AVL树是接近最优的。 当查找的文件较大，且存放在磁盘等直接存取设备中时，为了减少查找过程中对磁盘的读写次数，提高查找效率，基于直接存取设备的读写操作以"页"为单位的特征。 B-树 1972年R.Bayer和E.M.McCreight提出了一种称之为B-树的多路平衡查找树。它适合在磁盘等直接存取设备上组织动态的查找表。 1、B-树的定义 一棵m(m?3)阶的B-树是满足如下性质的m叉树: (1)每个结点至少包含下列数据域:(j，P，K，P，K，„，K，P) 0l12ii其中:j为关键字总数 K(1?i?j)是关键字，关键字序列递增有序:Kkeynum;Kkey[i];i--);//从后向前找第1个小于等于K的关键字 if(i>0&&T->key[i]==1){//查找成功，返回T及i *pos=i; Return T; }//结点内查找失败，但T->key[i]key[i+1]，下一个查找的结点应为son[i] if(!T->son[i])//*T为叶子，在叶子中仍未找到K，则整个查找过程失败 return NULL; //查找插入关键字的位置，则应令*pos=i，并返回T，见后面的插入操作 DiskRead(T->son[i]);//在磁盘上读人下一查找的树结点到内存中 Return SearchBTree(T->Son[i]，k，pos);//递归地继续查找于树T->son[i] } (3)查找操作的时间开销 B-树上的查找有两个基本步骤: ?在B-树中查找结点，该查找涉及读盘DiskRead操作，属外查找; ?在结点内查找，该查找属内查找。 查找操作的时间为: ?外查找的读盘次数不超过树高h，故其时间是O(h); ?内查找中，每个结点内的关键字数目keynumkeynum>Min，则只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作结束。 注意: 情形二:若x->keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。若*x的左(或右)邻兄弟结点*y中的关键字数目大于Min，则将*y中的最大(或最小)关键字上移至双亲结点*parent中，而将*parent中相应的关键字下移至x中。显然这种移动使得双亲中关键字数目不变;*y被移出一个关键字，故其keynum减1，因它原大于Min，故减少1个关键字后keynum仍大于等于Min;而*x中已移入一个关键字，故删K后*x中仍有Min个关键字。涉及移动关键字的三个结点均满足B-树的性质(3)。请读者验证，上述操作后仍满足B-树的性质(1)。移动完成后，删除过程亦结束。 情形三:若*x及其相邻的左右兄弟(也可能只有一个兄弟)中的关键字数目均为最小值Min，则上述的移动操作就不奏效，此时须*x和左或右兄弟合并。不妨设*x有右邻兄弟*y(对左邻兄弟的讨论与此类似)，在*x中删去K及其右子树后，将双亲结点*parent中介于*x和*y之间的关键字K，作为中间关键字，与并x和*y中的关键字一起"合并"为一个新的结点取代*x和 92 / 108 *y。因为*x和*y原各有Min个关键字，从双亲中移人的K'抵消了从*x中删除的K，故新结点中恰有2Min(即2「m/2」-2?m-1)个关键字，没有破坏B-树的性质(3)。但由于K'从双亲中移到新结点后，相当于从*parent中删去了K'，若parent->keynum原大于Min，则删除操作到此结束;否则，同样要通过移动*parent的左右兄弟中的关键字或将*parent与其左右兄弟合并的方法来维护B-树性质。最坏情况下，合并操作会向上传播至根，当根中只有一个关键字时，合并操作将会使根结点及其两个孩子合并成一个新的根，从而使整棵树的高度减少一层。 删除5阶B-树的h、r、p、d等关键字的过程分析: 第1个被删的关键字h是在叶子中，且该叶子的keynum>Min(5阶B-树的Min=2)，故直接删去即可。第2个删去的r不在叶子中，故用中序后继s取代r，即把s复制到r的位置上，然后从叶子中删去s。第3个删去的p所在的叶子中的关键字数目是最小值Min，但其右兄弟的keynum>Min，故可以通过左移，将双亲中的s移到p所在的结点，而将右兄弟中最小(即最左边)的关键字t上移至双亲取代s。当删去d时，d所在的结点及其左右兄弟均无多余的关键字，故需将删去d后的结点与这两个兄弟中的一个(图中是选择左兄弟(ab))及其双亲中分隔这两个被合并结点的关键字c合并在一起形成一个新结点(abce)。但因为双亲中失去c后keynum1，所以m较大时O(mlogtn)比平衡的二叉排序树上相应操作的时间O(lgn)大得多。因此，仅在内存中使用的B-树必须取较小的m。(通常取最小值m=3，此时B-树中每个内部结点可以有2或3个孩子，这种3阶的B-树称为2-3树)。 93 / 108 散列技术 散列方法不同于顺序查找、二分查找、二叉排序树及B-树上的查找。它不以关键字的比较为基本操作，采用直接寻址技术。在理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为O(1)。 散列表的概念 1、散列表 设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K(|K|比|U|小得多)。 散列方法是使用函数h将U映射到表T[0..m-1]的下标上(m=O(|U|))。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。 其中: ?h:U?{0，1，2，„，m-1}，通常称h为散列函数(HashFunction)。散列函数h的作用是压缩待处理的下标范围，使待处理的|U|个值减少到m个值，从而降低空间开销。 ?T为散列表(HashTable)。 ?h(K)(K?U)是关键字为K结点存储地址(亦称散列值或散列地址)。 iii?将结点按其关键字的散列地址存储到散列表中的过程称为散列(Hashing) 3、散列表的冲突现象 (1)冲突 两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。 (2)安全避免冲突的条件 最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件:?其一是|U|?m ?其二是选择合适的散列函数。 这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。 (3)冲突不可能完全避免 通常情况下，h是一个压缩映像。虽然|K|?m，但|U|>m，故无论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。 (4)影响冲突的因素 冲突的频繁程度除了与h相关外，还与表的填满程度相关。 设m和n分别表示表长和表中填人的结点数，则将α=n/m定义为散列表的装填因子(LoadFactor)。α越大，表越满，冲突的机会也越大。通常取α?1。 散列函数的构造方法 1、散列函数的选择有两条标准:简单和均匀。 简单指散列函数的计算简单快速; 均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集K随机均匀地分布在表的地址集{0，1，„，m-1}上，以使冲突最小化。 2、常用散列函数 为简单起见，假定关键字是定义在自然数集合上。 (1)平方取中法 94 / 108 具体方法:先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。【例】将一组关键字(0100，0110，1010，1001，0111)平方后得 (0010000，0012100，1020100，1002001，0012321) 若取表长为1000，则可取中间的三位数作为散列地址集: (100，121，201，020，123)。 相应的散列函数用C实现很简单: Int Hash(int key){//假设key是4位整数 Key *=key;key/=100;//先求平方值，后去掉末尾的两位数 Return key,1000;//取中间三位数作为散列地址返回 } (2)除余法 该方法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址，即h(key)=key,m 该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数。 (3)相乘取整法 该方法包括两个步骤:首先用关键字key乘上某个常数A(00) printf("duplicatekey!");//重复的关键字 else//sign<0 Error("hashtableoverflow!");//表满错误，终止程序执行 }//Hashlnsert Void CreateHashTable(HashTable T，NodeType A[]，int n) {//根据A[0..n-1]中结点建立散列表T[0..m-1] Int i if(n>m)//用开放定址法处理冲突时，装填因子α须不大于1 Error("Loadfactor>1"); for(i=0;i"三种可能，且每次比较后均能缩小下次的查找范围，故查找速度更快，其平均时间为O(lgn)。而散列法是根据关键字直接求出地址的查找方法，其查找的期望时间为O(1)。 第十章文件 文件概念文件(File)是性质相同的记录的集合。 注意:?文件的数据量通常很大，被放置在外存上。 ?数据结构中讨论的文件主要是数据库意义上的文件，不是操作系统意义上的文件。 100 / 108 ?操作系统中研究的文件是一维的无结构连续字符序列。数据库中所研究的文件是带有结构的记录集合，每个记录可由若干个数据项构成。 记录是文件中存取的基本单位，数据项是文件可使用的最小单位。数据项有时也称为字段(Field)，或者称为属性(Attribute)。 其值能惟一标识一个记录的数据项或数据项的组合称为主关键字项。其它不能惟一标识一个记录的数据项则称为次关键字项。主关键字项(或次关键字项)的值称为主关键字(或次关键字)。 为讨论方便起见，一般不严格区分关键字项和关键字。即在不易混淆时，将主(或次)关键字项简称为主(或次)关键字，并且假定主关键字项只含一个数据项。 2(文件分类 (1)单关键字文件和多关键字文件 文件可以按照记录中关键字的多少，分成单关键字文件和多关键字文件。?单关键字文件 文件中的记录只有一个惟一标识记录的主关键字。 ?多关键字文件 文件中的记录除了含有一个主关键字外，还含有若干个次关键字的文件 (2)定长文件和不定长文件 ?由定长记录组成的文件称做定长文件 含有的信息长度相同的记录称定长记录。 ?文件中记录含有的信息长度不等，则称其为不定长文件。 文件的逻辑结构及操作 1(文件的逻辑结构 文件可看成是以记录为数据元素的一种线性结构。 2(文件上的操作主要有两类:检索和维护。 (1)检索 检索即在文件中查找满足给定条件的记录。它既可以按记录的逻辑号(即记录存入文件时的顺序编号)查找，也可以按关键字查找。按检索条件的不同，可将检索分为四种询问: ?简单询问:只询问单个关键字等于给定值的记录。 ?范围询问:只询问单个关键字属于某个范围内的所有记录。 ?函数询问:规定单个关键字的某个函数，询问该函数的某个值。 ?布尔询问:以上三种询问用布尔运算(与、或、非)组合起来的询问。 (2)维护操作 维护操作主要是指: ?对文件进行记录的插入、删除及修改等更新操作。 ?为提高文件的效率，进行再组织操作， ?文件被破坏后的恢复操作，以及文件中数据的安全保护等。 (3)文件操作的处理方式 文件上的检索和更新操作，都可有实时和批量两种不同的处理方式。 ?实时处理:响应时间要求严格，要求在接受询问后几秒种内完成检索和更新。 ?批量处理:响应时间要求宽松一些，不同的文件系统有不同的要求。 文件的存储结构(亦称物理结构) 1(文件的存储结构 文件的存储结构是指文件在外存上的组织方式。 文件在外存上的基本的组织方式有四种:顺序组织，索引组织，散列组织和链组织;对应的的文件名称分别为:顺序文件、索引文件、散列文件和多关键字文件。 文件组织的各种方式往往是这四种基本方式的结合。 2(文件组织方式的选择 101 / 108 选择哪一种文件组织方式，取决于对文件中记录的使用方式和频繁程度、存取要求、外存的性质和容量。注意:常用外存设备有:?磁带是顺序存取设备，只适用于存储顺序文件?磁盘是直接存取设备，适用于存储顺序文件、索引文件、散列文件和多关键字文件等 3(文件组织效率的评价标准 评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。通常文件组织的主要目的，是为了能高效、方便地对文件进行操作，而检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志，因此，如何提高检索的效率，是研究各种文件组织方式首先要关注的问题。 顺序文件概念 1(顺序文件顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。注意:一切存储在顺序存取存储器(如磁带)上的文件，都只能是顺序文件。 2(顺序文件分类 (1)顺序有序文件 记录按其主关键字有序的顺序文件为顺序有序文件。 (2)顺序无序文件 记录未按其主关键字有序排列的顺序文件为顺序有序文件。 注意: 为提高检索效率，常将顺序文件组织成有序文件。 顺序有序文件存取的查找方法 1(顺序存取存储器(磁带)上文件存取的查找方法 顺序查找法即顺序扫描文件，按记录的主关键字逐个查找。要检索第i个记录，必须检索前i-1个记录。注意:?这种查找法对于少量的检索是不经济的，但适合于批量检索。 ?顺序存取存储器上的文件只能用顺序查找法存取 2(直接存取存储(磁盘)上文件存取的查找方法 (1)顺序查找法 (2)分块查找法 具体方法:设文件按主关键字的递增序，每100个记录为一块，各块的最后一个记录的主关键字为K，K，„，K，„: l00200100i查找时，将所要查找的记录的主关键字K，依次和各块的最后一个记录的主关键字比较，当K大于K且小于或等于K时，则在第i块内进行100(i-1)100i扫描。 注意:分块查找法在查找时不必扫描整个文件中的记录。 (3)二分查找法 ?二分查找法只适合对较小的文件或一个文件的索引进行查找。 ?当文件很大，在磁盘上占有多个柱面时，二分查找将引起磁头来回移动，增加寻查时间。 ?对磁盘等直接存取设备，还可以对顺序文件进行插值查找和跳步查找。 顺序文件的修改 1(顺序文件的修改操作 由于文件中的记录不能像向量空间的数据那样"移动"，故只能通过复制整个文件的方法实现插人、删除和修改等更新操作。 2(批量处理方式实现顺序文件的更新 (1)批量处理方式工作原理: ?把所有对顺序文件(以下称主文件)的更新请求，都放入一个较小的事务文件中。 ?当事务文件变得足够大时，将事务文件按主关键字排序， 102 / 108 ?再按事务文件对主文件进行一次全面的更新，产生一个新的主文件。 ?最后，清空事务文件，以便积累此后的更新内容。 (2)工作原理如下图所示。注意: 批量处理方式可减少更新操作的代价 索引文件构成 1(索引文件 索引文件由主文件和索引表构成。?主文件:文件本身。?索引表:在文件本身外建立的一张表，它指明逻辑记录和物理记录之间的一一对应关系。 2(索引表组成索引表由若干索引项组成。一般索引项由主关键字和该关键字所在记录的物理地址组成。注意:索引表必须按主关键字有序，而主文件本身则可以按主关键字有序或无序。 3(索引顺序文件和索引非顺序文件 (1)索引顺序文件(IndexedSequentialFile) 主文件按主关键字有序的文件称索引顺序文件。 在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。 (2)索引非顺序文件(IndexedNonSequentailFile) 主文件按主关键字无序得文件称索引非顺序文件。 在索引非顺序文件中，必须为每个记录建立一个索引项，这样建立的索引表称为稠密索引。 注意:?通常将索引非顺序文件简称为索引文件。 ?索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。 ?索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。 ?索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。 ?最常用的索引顺序文件:ISAM文件和VSAM文件。 索引文件的存储 1(索引文件的存储索引文件在存储器上分为两个区:索引区和数据区。索引区存放索引表，数据区存放主文件。 2(索引文件的建立 建立索引文件的过程:(1)按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的 (2)待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成了索引文件。 索引文件的操作 1(检索操作 检索分两步进行: ?将外存上含有索引区的页块送人内存，查找所需记录的物理地址 ?将含有该记录的页块送人内存 注意:?索引表不大时，索引表可一次读入内存，在索引文件中检索只需两次访问外存:一次读索引，一次读记录。 ?由于索引表有序，对索引表的查找可用顺序查找或二分查找等方法。 2(更新操作 (1)插入:将插入记录置于数据区的末尾，并在索引表中插入索引项; (2)删除:删去相应的索引项; 注意:修改主关键字时，要同时修改索引表。 利用查找表建立多级索引 103 / 108 1(查找表对索引表建立的索引，称为查找表。查找表的建立可以为占据多个页块的索引表的查阅减少外存访问次数。 2(多级索引 当查找表中项目仍很多，可建立更高一级的索引。通常最高可达四级索引: 数据文件一索引表一查找表一第二查找表一第三查找表。 注意:?多级索引是一种静态索引 ?多级索引的各级索引均为顺序表，结构简单，修改很不方便，每次修改都要重组索引。 3(动态索引 当数据文件在使用过程中记录变动较多时，利用二叉排序树(或AVL树)、B_树(或其变型)等树表结构建立的索引，为动态索引。 (1)树表特点 ?插入、删除方便 ?本身是层次结构，无须建立多级索引 ?建立索引表的过程即为排序过程。 (2)树表结构选择 ?当数据文件的记录数不很多，内存容量足以容纳整个索引表时，可采用二叉排序树(或AVL树)作索引; ?当文件很大时，索引表(树表)本身也在外存，查找索引时访问外存的次数恰为查找路径上的结点数。采用m阶B-树(或其变型)作为索引表为宜(m的选择取决于索引项的多少和缓冲区的大小)。 (3)外存的索引表的查找性能评价 由于访问外存的时间比内存中查找的时间大得多，所以外存的索引表的查找性能主要着眼于访问外存的次数，即索引表的深度。 顺序文件主要优点是连续存取的速度较快 顺序文件具有连续存取特点。当文件中第i个记录刚被存取过，而下一个要存取的是第i+1个记录，则这种存取将会很快完成。 注意:?对存放在单一存储设备(如磁带)上的顺序文件连续存取速度快 ?顺序文件存放在多路存储设备(如磁盘)上时，在多道程序的情况下，由于别的用户可能驱使磁头移向其它柱面，会降低连续存取的速度。顺序文件多用于磁带。 ISAM文件和VSAM文件是常用的索引顺序文件。 ISAM文件 ISAM为IndexedSequentialAccessMethed(索引顺序存取方法)的缩写，它是一种专为磁盘存取文件设计的文件组织方式，采用静态索引结构。由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面和磁道多级索引，下面只讨论在同一个盘组上建立的ISAM文件。 1、ISAM文件的组成 ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。 文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上。对同一柱面，则应按盘面的次序顺序存放。其中: ?C表示柱面; ?T表示磁道; ?CT表示i号柱面，j号磁道; ii?R表示主关键字为i的记录。 i分析:从图中可看出，主索引是柱面索引的索引，这里只有一级主索引。若文件占用的柱面索引很大，使得一级主索引也很大时，可采用多级主索引。当然，若柱面索引较小时，则主索引可省略。 通常主索引和柱面索引放在同一个柱面上(如图10.4是放在0号柱面上)，主索引放在该柱面最前的-个磁道上，其后的磁道中存放柱面索引。每个存放主文件的柱面都建立有一个磁道索引，放在该柱面的最前面的磁道 104 / 108 To上，其后的若干个磁道是存放主文件记录的基本区，该柱面最后的若干个磁道是溢出区。基本区中的记录是按主关键字大小顺序存储的，溢出区被整个柱面上的基本区中各磁道共享，当基本区中某磁道溢出时，就将该磁道的溢出记录，按主关键字大小链成一个链表(以下简称溢出链表)放人溢出区。 2、各级索引中的索引项结构 注意:磁道索引中的每一个索引项，都由两个子索引项组成:基本索引和溢出索引项。 3、ISAM文件的检索 在ISAM文件上检索记录时，从主索引出发，找到相应的柱面索引;从柱面索引找到记录所在柱面的磁道索引;从磁道索引找到记录所在磁道的起始地址，由此出发在该磁道上进行顺序查找，直到找到为止。若找遍该磁道均不存在此记录，则表明该文件中无此记录;若被查找的记录在溢出区，则可从磁道索引项的溢出索引项中得到溢出链表的头指针，然后对该表进行顺序查找。 4、ISAM文件的插入操作 当插人新记录时，首先找到它应插入的磁道。若该磁道不满，则将新记录插入该磁道的适当位置上即可;若该磁道已满，则新记录或者插在该磁道上，或者直接插入到该磁道的溢出链表上。插入后，可能要修改磁道索引中的基本索引项和溢出索引项。 5、ISAM文件中删除记录的操作 ISAM文件中删除记录的操作，比插入简单得多，只要找到待删除的记录，在其存储位置上作删除标记即可，而不需要移动记录或改变指针。在经过多次的增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出区，而基本区中又浪费很多的空间。因此，通常需要周期性地整理ISAM文件，把记录读入内存重新排列，复制成一个新的ISAM文件，填满基本区而空出溢出区。 VSAM文件 VSAM是VirtualStorageAccessMethod(虚拟存储存取方法)的缩写，它也是一种索引顺序文件的组织方式，采用B+树作为动态索引结构。 1、B+树B+树是一种常用于文件组织的B-树的变型树。一棵m阶的B+树和m阶的B-树的差异是:?有k个孩子的结点必有k个关键字; ?所有的叶结点，包含了全部关键字的信息及指向相应的记录的指针，且叶子结点本身依照关键字的大小，自小到大顺序链接; ?上面各层结点中的关键字，均是下一层相应结点中最大关键字的复写(当然也可采用"最小关键字复写"的原则)，因此，所有非叶结点可看作是索引部分。 注意:?通常在B+树上有两个头指针root和sqt，前者指向根结点，后者指向关键字最小的叶子结点。?对B+树可进行两种查找运算:一种是从最小关键字起进行顺序查找;另一种是从根结点开始进行随机查找。 2、B+树的运算 在B+树上进行随机查找、插入和删除的过程，基本上与B-树类似。 (1)B+树的查找运算 在查找时，若非叶结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。 105 / 108 B+树查找的分析类似于B-树。B+树的插入也仅在叶子结点上进行，当结点中的关键字个数大于m时要分裂成两个结点，它们所含关键字的个数分别为: 并且它们的双亲结点中应同时包含这两个结点的最大关键字。 (2)B+树的删除 B+树的删除仅在叶子结点进行，当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个"分界关键字"存在。若因删除而使结点中关键字的个数少于时，则可能要和该结点的兄弟结点合并，合并过程和B-树类似。 3、VSAM文件 B+树的每个叶结点中的关键字均对应一个记录，适宜于作为稠密索引。但若让叶结点中的关键字对应一个页块，则B+树可用来作为稀疏索引。IBM公司VSAM文件是用B+树作为文件的稀疏索引的一个典型例子。 这种文件组织的实现，使用了IBM370系列的操作系统的分页功能，这种存取方法与存储设备无关，与柱面、磁道等物理存储单位没有必然的联系。例如，可以在一个磁道中放n个控制区间，也可以一个控制区间跨n个磁道。 (1)VSAM文件的结构 VSAM文件的结构由三部分组成:索引集，顺序集和数据集(如下图所示)。 ?数据集文件的记录均存放在数据集中。数据集中的一个结点称为控制区间，它是一个I/0操作的基本单位，每个控制区间含有一个或多个数据记录。 ?顺序集和索引集 顺序集和索引集一起构成一棵B+树，作为文件的索引部分。 顺序集中存放的每个控制区间的索引项由两部分信息组成:该控制区间中的最大关键字和指向控制区间的指针。若干相邻的控制区间的索引项，形成顺序集中的一个结点。结点之间用指针相链接，而每个结点又在其上一层的结点中建有索引，且逐层向上建立索引，所有的索引项都由最大关键字和指针两部分信息组成。这些高层的索引项形成B+树的非终端结点。 VSAM文件既可在顺序集中进行顺序存取，又可从最高层的索引(B+树的根结点)出发，进行按关键字的随机存取。顺序集中一个结点连同其对应的所有控制区间形成一个整体，称做控制区域(ControlRange)，它相当于ISAM文件中的一个柱面，而控制区间相当于一个磁道。 (2)VSAM文件中控制区间的结构 在VSAM文件中，记录可以是不定长的。因而在控制区间中，除了存放记录本身之外，还有每个记录的控制信息(如记录的长度等)和整个区间的控制信息(如区间中存放的记录数等)，控制区间的结构如下表所示。 (3)VSAM文件的插入方法 VSAM文件中没有溢出区，解决插入的方法是在初建文件时留出空间:一是每个控制区间内并未填满记录，而是在最末一个记录和控制信息之间留有空隙;二是在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。 当插入新记录时，大多数的新记录能插入到相应的控制区间内，但要注意:为了保持区间内记录的关键字从小至大有序，则需将区间内关键字大于插入记录关键字的记录，向控制信息的方向移动。若在若干记录插入之后控制区间已满，则在下一个记录插入时，要进行控制区间的分裂，即把近乎一半的记录移到同一控制区域内全空的控制区间中，并修改顺序集中相应索 106 / 108 引。倘若控制区域中已经没有全空的控制区间，则要进行控制区域的分裂，此时顺序集中的结点亦要分裂，由此需要修改索引集中的结点信息。但由于控制区域较大，通常很少发生分裂的情况。 (4)VSAM文件的删除 在VSAM文件中删除记录时，需将同一控制区间中，比删除记录关键字大的记录向前移动，把空间留给以后插人的新记录。若整个控制区间变空，则回收作空闲区间用，且需删除顺序集中相应的索引项。 (5)VSAM文件的优点 和ISAM文件相比，基于B+树的VSAM文件有如下优点:能保持较高的查找效率，查找一个后插入记录和查找一个原有记录具有相同的速度;动态地分配和释放存储空间，可以保持平均75,的存储利用率;而且永远不必对文件进行再组织。因而基于B+树的VSAM文件，通常被作为大型索引顺序文件的标准组织。 散列文件的组织方式 散列文件是利用散列存储方式组织的文件，亦称直接存取文件。即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上。 1( 散列表与散列文件比较 ?比较项目 ?散列表 ?散列文件 ? ?存储单位 ?若干记录为一组 ?桶 ? ?处理冲突办法?开放地址法、拉链法?拉链法 ? 2(基桶和溢出桶 在散列文件的存储单位叫桶(Bucket)。假如一个桶能存放m个记录，则当桶中已有m个同义词的记录时，存放第m+1个同义词会发生"溢出"。需要将第m+1个同义词存放到另一个桶中，通常称此桶为"溢出桶"。相对地，称前m个同义词存放的桶为"基桶"。 注意:?溢出桶和基桶大小相同，相互之间用指针相链接。 ?当在基桶中没有找到待查记录时，就沿着指针到所指溢出桶中进行查找，因此，希望同一散列地址的溢出桶和基桶，在磁盘上的物理位置不要相距太远，最好在同一柱面上。 散列文件的查找操作在散列文件中查找的过程: (1)根据给定值求出散列桶地址 (2)将基桶的记录读人内存，进行顺序查找 3)若找到关键字等于给定值的记录，则检索成功;否则，读人溢出桶的记录继续进行查找 散列文件的删除操作 在散列文件中删去一个记录，仅需对被删记录作删除标记即可。 1(散列文件的优点 (1)文件随机存放，记录不需进行排序。(2)插入、删除方便。(3)存取速度快;不需要索引区，节省存储空间。 2(散列文件的缺点 (1)不能进行顺序存取，只能按关键字随机存取(2)询问方式限于简单询问 (3)在经过多次插入、删除后，可能造成文件结构不合理，需要重新组织文件。 多关键字文件 1(多关键字文件包含有多个次关键字索引的文件称为多关键字文件。 107 / 108 注意:次关键字索引本身可以是顺序表或树表。 2(多关键字文件和其他文件的区别 多重表文件 1(多重表文件的组织方式 多重表文件是将索引方法和链接方法相结合的一种组织方式。 具体组织方式:对每个需要查询的次关键字建立一个索引，同时将具有相同次关键字的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字，作为索引表的一个索引项。通常多重表文件的主文件是一个顺序文件。2(多重表文件的查询操作 (1)单关键字简单查询基本思想 据给定值，在对应次关键字索引表中找到对应索引项，从头指针出发，列出该链表上所有记录。 (2)多关键字组合查询基本思想 注意:在查找同时满足两多个关键字条件得记录时，可先比较两(多)个索引链表的长度，然后选较短的链表进行查找。 多重表的更新操作 1(插入新记录 相同次关键字链表不按主关键字大小链接时，在主文件中插入新记录后，将记录在各个次关键字链表中插在链表的头指针之后即可。 2(删除记录在删去一个记录的同时，需在每个次关键字的链表中删去该记录。 倒排文件 1(倒排文件的组织方式和特点 倒排文件和多重表文件不同。在次关键字索引中，具有相同次关键字的记录之间不进行链接，而是列出具有该次关键字记录的物理地址。 倒排文件中的次关键字索引称做倒排表。倒排表和主文件一起就构成了倒排文件。 2(倒排文件的查询 倒排表的主要优点是:在处理复杂的多关键字查询时，可在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对记录进行存取。这样不必对每个记录随机存取，把对记录的查询转换为地址集合的运算，从而提高查找速度。 3(倒排文件的更新在插入和删除记录时，还要修改倒排表。 4(列出主关键字的倒排表 特点: ?存取速度较慢 ?主关键字可看成是记录的符号地址，对于存储具有相对独立性。 【例】下面的表就是按上述方法对多重表文件所组织的职务倒排表。 5(倒排文件与一般文件组织的区别 在一般的文件组织中，是先找记录，然后再找到该记录所含的各次关键字;而倒排文件中，是先给定次关键字，然后查找含有该次关键字的各个记录，这种文件的查找次序正好与一般文件的查找次序相反，因此称之为"倒排"。 注意:多重表文件实际上也是倒排文件，只不过索引的方法不同。 108 / 108