第8章　数据结构

数据结构是程序设计的重要理论和技术基础，它所讨论的内容和技术，对从事软件项目的开发有重要作用。学习数据结构要达到的目标是：学会从问题出发，分析和研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法，为提高应用计算机解决问题的效率服务。

数据结构是指数据元素的集合（或数据对象）及元素间的相互关系和构造方法。元素之间的相互关系是数据的逻辑结构，数据元素及元素之间关系的存储形式称为存储结构（或物理结构）。

数据结构按照逻辑关系的不同分为线性结构和非线性结构两大类，其中非线性结构又可分为树结构和图结构。

算法与数据结构密切相关，数据结构是算法设计的基础，合理设计的数据结构可使算法简单而高效。

8.1　线性结构

线性结构是一种基本的数据结构，主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。线性结构的特点是数据元素之间呈现一种线性关系，即元素“一个接一个地排列”。

8.1.1　线性表

线性表是最简单、最基本、也是最常用的一种线性结构。它有两种存储方法：顺序存储和链式存储，主要的基本操作是插入、删除和查找等。

1．线性表的定义

一个线性表是n（n≥0）个元素的有限序列，通常表示为（a₁，a₂，…，a_n）。非空线性表的特点如下。

（1）存在唯一的一个称作“第一个”的元素。

（2）存在唯一的一个称作“最后一个”的元素。

（3）除第一个元素外，序列中的每个元素均只有一个直接前驱。

（4）除最后一个元素外，序列中的每个元素均只有一个直接后继。

2．线性表的存储结构

线性表的存储结构分为顺序存储和链式存储。

1）线性表的顺序存储

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，如图8-1所示。在这种存储方式下，元素间的逻辑关系无须占用额外的空间来存储。

图8-1　线性表元素的顺序存储

一般地，以LOC（a₁）表示线性表中第一个元素的存储位置，在顺序存储结构中，第i个元素a_i的存储位置为

其中，L是表中每个数据元素所占空间的大小。根据该计算关系，可随机存取表中的任一个元素。

线性表采用顺序存储结构的优点是可以随机存取表中的元素，缺点是插入和删除操作需要移动元素。插入元素前要移动元素以挪出空的存储单元，然后再插入元素；删除元素时同样需要移动元素，以填充被删除的元素空出来的存储单元。

在表长为n的线性表中插入新元素时，共有n＋1个插入位置，在位置1（元素a₁所在位置）插入新元素，表中原有的n个元素都需要移动，在位置n＋1（元素a_n所在位置之后）插入新元素时不需要移动任何元素，因此，等概率下（即新元素在n＋1个位置插入的概率相同时）插入一个新元素需要移动元素的个数E_insert为

其中，P_i表示在表中的位置i插入新元素的概率。

在表长为n的线性表中删除元素时，共有n个可删除的元素，删除元素a₁时需要移动n－1个元素，删除元素a_n时不需要移动元素，因此，等概率下删除元素时需要移动元素的个数E_delete为

其中，q_i表示删除元素a_i的概率。

2）线性表的链式存储

线性表的链式存储是用节点来存储数据元素，基本的节点结构如下所示：

其中，数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继信息，指针域中的信息称为指针（或链）。

存储各数据元素的节点的地址并不要求是连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。另外，节点空间只有在需要的时候才申请，无须事先分配。

节点之间通过指针域构成一个链表，若节点中只有一个指针域，则称为线性链表（或单链表），如图8-2所示。

图8-2　线性表元素的单链表存储

设线性表中的元素是整型，则单链表节点类型的定义为：

在链式存储结构中，只需要一个指针（称为头指针，如图8-2中的head）指向第一个节点，就可以顺序访问到表中的任意一个元素。

在链式存储结构下进行插入和删除，其实质都是对相关指针的修改。在单链表中，若在p所指节点后插入新元素节点（s所指节点，已经生成），如图8-3（a）所示，其基本步骤如下。

即先将p所指节点的后继节点指针赋给s所指节点的指针域，然后将p所指节点的指针域修改为指向s所指节点。

图8-3　在单链表中插入、删除节点时的指针变化示意图

同理，在单链表中删除p所指节点的后继节点时（如图8-3（b）所示），步骤如下。

即先令临时指针q指向待删除的节点，然后修改p所指节点的指针域为指向p所指节点的后继的后继节点，从而将元素b所在的节点从链表中摘除，最后释放q所指节点的空间。

实际应用中，为了简化对链表状态的判定和处理，特别引入一个不存储数据元素的节点，称为头节点，将其作为链表的第一个节点并令头指针指向该节点。

下面给出单链表上查找、插入和删除运算的实现过程。

【函数】单链表的查找运算。

LinkList Find_List（LinkList L, intk）/L为带头节点单链表的头指针/

/在表中查找第k个元素，若找到，返回该元素节点的指针；否则，返回空指针NULL/

【函数】单链表的插入运算。

【函数】单链表的删除运算。

线性表采用链表作为存储结构时，不能对数据元素进行随机访问，但是插入和删除操作不需要移动元素。

根据节点中指针域的设置方式，还有其他几种链表结构。

●　双向链表。每个节点包含两个指针，分别指出当前节点元素的直接前驱和直接后继。其特点是可从表中任意的元素节点出发，从两个方向上遍历链表。

●　循环链表。在单向链表（或双向链表的基础上），令表尾节点的指针指向表中的第一个节点，构成循环链表。其特点是可从表中任意节点开始遍历整个链表。

●　静态链表。借助数组来描述线性表的链式存储结构。

若双向链表中节点的front和next指针域分别指示当前节点的直接前驱和直接后继，则在双向链表中插入节点*s时指针的变化情况如图8-4（a）所示，其操作过程可表示为：

在双向链表中删除节点时指针的变化情况如图8-4（b）所示，其操作过程可表示为：

图8-4　双向链表插入和删除节点时的指针变化示意图

8.1.2　栈和队列

栈和队列是软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算有所限制：栈按“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作，故称运算受限的线性表。

1．栈

1）栈的定义及基本运算

（1）栈的定义。

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说，栈的修改是按先进后出的原则进行的。因此，栈又称为后进先出（Last In First Out，LIFO）的线性表。在栈中进行插入和删除操作的一端称为栈顶（top），相应地，另一端称为栈底（bottom）。不含数据元素的栈称为空栈。

（2）栈的基本运算。

①　初始化栈InitStack（S）：创建一个空栈S。

②　判栈空StackEmpty（S）：当栈S为空时返回“真”值，否则返回“假”值。

③　入栈Push（S,x）：将元素x加入栈顶，并更新栈顶指针。

④　出栈Pop（S）：将栈顶元素从栈中删除，并更新栈顶指针。若需要得到栈顶元素的值，可将Pop（S）定义为一个返回栈顶元素值的函数。

⑤　读栈顶元素Top（S）：返回栈顶元素的值，但不修改栈顶指针。

应用中常使用上述5种基本运算实现基于栈结构的问题求解。

2）栈的存储结构

（1）顺序存储。

栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。采用顺序存储结构的栈也称为顺序栈。在该存储方式下，需要预先定义（或申请）栈的存储空间，也就是说，栈空间的容量是有限的。因此，在顺序栈中，当一个元素入栈时，需要判断是否栈满（栈空间中没有空闲单元），若栈满，则元素入栈会发生上溢现象。

（2）栈的链式存储。

为了克服顺序存储的栈可能存在上溢的不足，可以用链表存储栈中的元素。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必设置头节点，链表的头指针就是栈顶指针。链栈的表示如图8-5所示。

（3）栈的应用。

栈的典型应用包括表达式求值、括号匹配等，在计算机语言的实现以及将递归过程转变为非递归过程的处理中，栈有重要的作用。

图8-5　链栈示意图

2．队列

1）队列的定义及基本运算。

（1）队列的定义。

队列是一种先进先出（First In First Out，FIFO）的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾（rear），允许删除元素的一端称为队头（front）。

（2）队列的基本运算。

①　初始化队InitQueue（Q）：创建一个空的队列Q。

②　判队空Empty（Q）：当队列为空时返回“真”值，否则返回“假”值。

③　入队EnQueue（Q,x）：将元素x加入到队列Q的队尾，并更新队尾指针。

④　出队DeQueue（Q）：将队头元素从队列Q中删除，并更新队头指针。

⑤　读队头元素FrontQue（Q）：返回队头元素的值，但不更新队头指针。

2）队列的存储结构

（1）队列的顺序存储。

队列的顺序存储结构又称为顺序队列，它也是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指示出当前的队首元素和队尾元素。

下面设顺序队列Q的容量为6，其队头指针为front，队尾指针为rear，头、尾指针和队列中元素之间的关系如图8-6所示。

在顺序队列中，为了降低运算的复杂度，元素入队时只修改队尾指针，元素出队时只修改队头指针。由于顺序队列的存储空间是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到该上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。此时，可通过整除取余运算将顺序队列假想成一个环状结构，如图8-7所示，称之为循环队列。

图8-6　队列的头、尾指针与队列中元素之间的关系

图8-7　循环队列的头、尾指针示意图

设循环队列Q的容量为MAXSIZE，初始时队列为空，且Q.rear和Q.front都等于0，如图8-8（a）所示。

元素入队时，修改队尾指针Q.rear＝（Q.rear+1）%MAXSIZE，如图8-8（b）所示。

元素出队时，修改队头指针Q.front＝（Q.front+1）%MAXSIZE，如图5-8（c）所示。

根据出队列操作的定义，当出队操作导致队列变为空时，则有Q.rear＝＝Q.front，如图8-8（d）所示；若队列满，则Q.rear＝＝Q.front，如图8-8（e）所示。

在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的，此时仅仅根据Q.rear和O.front之间的关系无法断定队列的状态。为了区别队空和队满的情况，可采用以下两种处理方式：其一是设置一个标志位，以区别头、尾指针的值相同时队列是空还是满；其二是牺牲一个存储单元，约定以“队列的尾指针所指位置的下一个位置是队头指针”表示队列满，如图8-8（f）所示，而头、尾指针的值相同时表示队列为空。

设队列中的元素类型为整型，则循环队列的类型定义为。

图8-8　循环队列的头、尾指针示意图

【函数】创建一个空的循环队列。

【函数】元素入循环队列。

【函数】元素出循环队列。

（2）队列的链式存储。

队列的链式存储也称为链队列。这里为了便于操作，给链队列添加一个头节点，并令头指针指向头节点。因此，队列为空的判定条件是：头指针和尾指针的值相同，且均指向头节点。队列的链式存储结构如图8-9所示。

3）队列的应用

队列结构常用于处理需要排队的场合，如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。

图8-9　链队列示意图

8.1.3　串

串（字符串）是一种特殊的线性表，其数据元素为字符。计算机中非数值问题处理的对象经常是字符串数据，例如，在汇编和高级语言的编译程序中，源程序和目标程序都是字符串数据；在事务处理程序中，姓名、地址等一般也是作为字符串处理的。串具有自身的特性，运算时常常把一个串作为一个整体来处理。这里介绍串的定义、基本运算、存储结构及串的模式匹配算法。

1．串的定义及基本运算

1）串的定义

串是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为其中S是串名，单引号括起来的字符序列是串值。

2）串的几个基本概念

●　空串：长度为零的串，空串不包含任何字符。

●　空格串：由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符，计算串长度时要将其计算在内。

●　子串：由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。

●　串相等：指两个串长度相等且对应位置上的字符也相同。

●　串比较：两个串比较大小时以字符的ASCⅡ码值（或其他字符编码集合）作为依据。实质上，比较操作从两个串的第一个字符开始进行，字符的码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。

3）串的基本操作

（1）赋值操作StrAssign（s,t）：将串s的值赋给串t。

（2）联接操作Concat（s,t）：将串t接续在串s的尾部，形成一个新串。

（3）求串长StrLength（s）：返回串s的长度。

（4）串比较StrCompare（s,t）：比较两个串的大小。返回值-1、0和1分别表示s＜t、s＝t和s＞t三种情况。

（5）求子串SubString（s,start,len）：返回串s中从start开始的、长度为len的字符序列。

以上5种最基本的串操作构成了串的最小操作子集，利用它们可以实现串的其他运算。

2．串的存储结构

（1）串的定长存储结构。串的静态存储结构就是串的顺序存储结构，用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符，所以可通过程序语言提供的字符数组定义串的存储空间，也可以根据串长的需要动态申请字符串的空间。

（2）串的链式存储。字符串也可以采用链表作为存储结构，当用链表存储串中的字符时，每个节点中可以存储一个字符，也可以存储多个字符，此时要考虑存储密度问题。

在链式存储结构中，节点大小的选择和顺序存储方法中数组空间大小的选择一样重要，它直接影响对串的处理效率。

3．串的模式匹配

子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。

1）朴素的模式匹配算法

该算法也称为布鲁特—福斯算法，其基本思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐对字符进行后续的比较，否则从主串第二个字符起与模式串的第一个字符重新比较，直至模式串中每个字符依次和主串中一个连续的字符序列相等时为止，此时称为匹配成功。如果不能在主串中找到与模式串相同的子串，则匹配失败。

【函数】以字符数组存储字符串，实现朴素的模式匹配算法。

假设主串和模式串的长度分别为n和m，位置序号从0开始计算，下面分析朴素模式匹配算法的时间复杂度。设从主串的第i个位置开始与模式串匹配成功，在前i趟匹配中（位置0～i－1），每趟不成功的匹配都是模式串的第一个字符与主串中相应的字符不相同，则在前i趟匹配中，字符的比较共进行了i次，而第i＋1趟（从位置i开始）成功匹配的字符比较次数为m，所以总的字符比较次数为i＋m（0≤i≤n－m）。若在主串的n－m个起始位置上匹配成功的概率相同，则在最好情况下，匹配成功时字符问的平均比较次数为

因此，在最好情况下匹配算法的时间复杂度为Ο（n＋m）。

而在最坏情况下，每一趟不成功的匹配都是模式串的最后一个字符与主串中相应的字符不相等，则主串中新一趟的起始位置为i－m＋2。若设从主串的第i个字符开始匹配时成功，则前i趟不成功的匹配中，每趟都比较了m次，总共比较了i×m次。因此，最坏情况下的平均比较次数为

由于n>>m，所以该算法在最坏情况下的时间复杂度为Ο（n×m）。

2）改进的模式匹配算法

改进的模式匹配算法又称为KMP算法，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的字符位置指针，而是利用已经得到的“部分匹配”结果，将模式串向右“滑动”尽可能远的距离，再继续进行比较。

设模式串为″p₀…p_m－1″，KMP匹配算法的思想是：当模式串中的字符p_j与主串中相应的字符S_i不相等时，因其前j个字符（″p₀…p_j－1″）已经获得了匹配，所以若模式串中的″p₀…p_k－1″与″p_j－k…p_j－1″相同，这时可令p_k与S_i进行比较，从而使i无须回退。

在KMP算法中，依据模式串的next函数值实现子串的滑动。若令next[j]＝k，则next[j]表示当模式串中的p_j与主串中相应字符不相等时，令模式串的p_k与主串的相应字符进行比较。

next函数的定义如下：

【函数】求模式串的next函数。

例如，设主串为“abacbcabababbcbc”，模式串为“abababb”，且模式串的next函数值如下表所示，则KMP算法的匹配过程如图8-10所示。

【函数】KMP模式匹配算法，设模式串第一个字符的下标为0。

（a）i是主串字符的下标，j是模式串字符的下标

（b）若S[i]==P[j]，则i++、j++；否则，j=next[j]，即S[i]与P[next[j]]比较，重复该步，若j等于-1，则令i++、j=0

（c）重复（b）直到完全匹配或达到主串结尾匹配失败

图8-10　KMP模式匹配过程示意图

8.2　数组、矩阵和广义表

数组与广义表可看作是线性表的推广，其特点是数据元素仍然是一个表。这里讨论多维数组的逻辑结构和存储结构，特殊矩阵和矩阵的压缩存储，广义表的逻辑结构、存储结构和基本运算。

8.2.1　数组

1．数组的定义及基本运算

1）数组的定义

数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。n维数组是一种“同构”的数据结构，其每个数据元素类型相同，结构一致。

设有n维数组A[b₁，b₂，…，b_n]，其每一维的下界都为1，b_i是第i维的上界。从数据结构的逻辑关系角度来看，A中的每个元素A[j₁，j₂，…，j_n]（1≤j_i≤b_i）都被n个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，仍是线性的。

以二维数组A[m，n]为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。

A可看成一个行向量形式的线性表：

或列向量形式的线性表：

数组结构的特点如下。

（1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素个数的增减变化。

（2）数据元素具有相同的类型。

（3）数据元素的下标关系具有上下界的约束且下标有序。

2）数组的两个基本运算

（1）给定一组下标，存取相应的数据元素。

（2）给定一组下标，修改相应的数据元素中某个数据项的值。

几乎所有的高级程序设计语言都提供了数组类型。实际上，在程序语言中把数组看成是具有共同名字的同一类型多个变量的集合。

2．数组的顺序存储

数组一般不作插入和删除运算，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。

由于计算机的内存结构是一维线性的，因此存储多维数组时必须按某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。因为多维数组是由较低一维的数组来定义的，依此类推，通过这种递推关系将多维数组的数据元素排成一个线性序列。

对于数组，一旦确定了其维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置，即在数据的顺序存储结构中，数据元素的位置是其下标的线性函数。

二维数组的存储结构可分为以行为主序和以列为主序的两种方法，如图8-11所示。

图8-11　二维数组的两种存储方式

设每个数据元素占用L个单元，m、n为数组的行数和列数，Loc（a₁₁）表示元素a₁₁的地址，那么以行为主序优先存储的地址计算公式为

同理，以列为主序优先存储的地址计算公式为

推广至多维数组，按下标顺序存储时，先排最右的下标，从右向左直到最左下标，而逆下标顺序则正好相反。

8.2.2　矩阵

矩阵是很多科学与工程计算问题中研究的数学对象。在数据结构中，主要讨论如何在节省存储空间的情况下，使矩阵的各种运算能高效地进行。

在一些矩阵中，存在很多值相同的元素或者是0元素。为了节省存储空间，可以对这类矩阵进行压缩存储，即为多个值相同的元素只分配一个存储单元，对0元不分配存储单元。假如值相同的元素或0元在矩阵中的分布有一定的规律，则称此类矩阵为特殊矩阵，否则称为稀疏矩阵。

1．特殊矩阵

若矩阵中元素（或非0元素）的分布有一定的规律，则称之为特殊矩阵。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵，由于其非0元的分布有一定的规律，所以可将其压缩存储在一维数组中，并建立起每个非0元在矩阵中的位置与其在一维数组中的位置之间的对应关系。

若矩阵A_n×n中的元素特点为a_ij＝a_ji（1≤i，j≤n），则称之为n阶对称矩阵。

若对称矩阵中的每一对元素仅占用一个存储单元，那么就可将n²个元素压缩存储到能存放n（n＋1）/2个元素的存储空间中。不失一般性，以行为主序存储下三角（包括对角线）中的元素。假设以一维数组B[n（n＋1）/2]作为n阶对称矩阵A的压缩存储空间，则B[k]（1≤k≤n（n＋1）/2）与矩阵元素a_ij之间存在着一一对应的关系。

对角矩阵是指矩阵中的非0元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为0。一个n阶的三对角矩阵如图8-12所示。

若以行为主序将n阶三对角矩阵A_n×n的非0元素存储在一维数组B[k]（1≤k≤3×n－2）中，则元素位置之间的对应关系为

其他特殊矩阵可作类似的推算，这里不再一一说明。

2．稀疏矩阵

在一个矩阵中，若非0元素的个数远远少于0元素的个数，且非0元素的分布没有规律，则称之为稀疏矩阵。对于稀疏矩阵，存储非0元素时必须同时存储其位置（即行号和列号），所以三元组（i，j，a_ij）可唯一确定矩阵A中的一个元素。由此，一个稀疏矩阵可由表示非0元素的三元组及其行、列数唯一确定。图8-13所示的是一个6行7列的稀疏矩阵，其三元组表为（（1，2，12），（1，3，9），（3，1，-3），（3，6，14），（4，3，24），（5，2，18），（6，1，15），（6，4，-7））。

图8-12　三对角矩阵示意图

图8-13　稀疏矩阵示意图

稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。

8.2.3　广义表

1．广义表的定义

广义表是线性表的推广，是由0个或多个单元素或子表组成的有限序列。

广义表与线性表的区别在于：线性表的元素都是结构上不可分的单元素，而广义表的元素既可以是单元素，也可以是有结构的表。

广义表一般记为

其中，α_i（1≤i≤n）既可以是单个元素，又可以是广义表，分别称为原子和子表。

广义表的长度是指广义表中元素的个数。广义表的深度是指广义表展开后所含的括号的最大层数。

2．广义表的基本操作

与线性表类似，广义表也有查找、插入和删除等操作。由于广义表的结构较复杂，其各种运算的实现也不如线性表简单，这里只讨论两个重要的运算。

（1）取表头head（LS）。非空广义表LS的第一个元素称为表头，它可以是一个单元素，也可以是一个子表。

（2）取表尾tail（LS）。在非空广义表中，除表头元素之外，由其余元素所构成的表称为表尾。非空广义表的表尾必定是一个表。

3．广义表的特点

（1）广义表可以是多层次的结构，因为广义表的元素可以是子表，而子表的元素还可以是子表。

（2）广义表中的元素可以是已经定义的广义表的名字，所以一个广义表可被其他广义表所共享。

（3）广义表可以是一个递归的表，即广义表中的元素也可以是本广义表的名字。

4．广义表的存储结构

由于广义表中的元素本身又可以具有结构，它是一种带有层次的非线性结构，因此难以用顺序存储结构表示，通常采用链式存储结构。由上面讨论可知，若广义表不空，则可分解为表头和表尾两部分。反之，一对确定的表头和表尾可唯一确定一个广义表。针对原子和子表可分别设计不同的节点结构，如图8-14所示。对于广义表LS＝（a，（b，c，d）），其链式存储结构如图8-15所示。

图8-14　广义表的链表节点结构

图8-15　广义表（a，（b，c，d））的存储结构示意图

8.3　树

树结构是一种非常重要的非线性结构，该结构中一个数据元素可以有两个或两个以上的直接后继元素，树可以用来描述客观世界中广泛存在的层次结构关系。

8.3.1　树与二叉树的定义

1．树的定义

树是n（n≥0）个节点的有限集合，当n＝0时称为空树。在任一非空树（n＞0）中，有且仅有一个称为根的节点；其余节点可分为m（m≥0）个互不相交的有限集T₁，T₂，…，T_m，其中每个T_i又都是一棵树，并且称为根节点的子树。

树的定义是递归的，它表明了树本身的固有特性，也就是一棵树由若干棵子树构成，而子树又由更小的子树构成。

该定义只给出了树的组成特点，若从数据结构的逻辑关系角度来看，树中元素之间有明显的层次关系。对树中的某个节点，它最多只和上一层的一个节点（即其双亲节点）有直接的关系，而与其下一层的多个节点（即其孩子节点）有直接关系，如图8-16所示。通常，凡是分等级的分类方案都可以用具有严格层次关系的树结构来描述。

图8-16　树结构示意图

2．树的基本概念

（1）双亲、孩子和兄弟：节点的子树的根称为该节点的孩子；相应地，该节点称为其子节点的双亲。具有相同双亲的节点互为兄弟。

（2）节点的度：一个节点的子树的个数记为该节点的度。

（3）叶子节点：也称为终端节点，指度为0的节点。

（4）内部节点：度不为0的节点称为分支节点或非终端节点。除根节点之外，分支节点也称为内部节点。

（5）节点的层次：根为第一层，根的孩子为第二层，依此类推，若某节点在第i层，则其孩子节点在第i＋1层。

（6）树的高度：一棵树的最大层次数记为树的高度（或深度）。

（7）有序（无序）树：若将树中节点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。

3．二叉树的定义

二叉树是n（n≥0）个节点的有限集合，它或者是空树（n＝0），或者是由一个根节点及两棵不相交的且分别称为左、右子树的二叉树所组成。可见，二叉树同样具有递归性质。

特别需要注意的是，尽管树和二叉树的概念之间有许多联系，但它们是两个不同的概念。树和二叉树之间最主要的区别是：二叉树节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。另外，二叉树节点最大度为2，而树中不限制节点的度数，如图8-17所示。

图8-17　二叉树与普通树

8.3.2　二叉树的性质与存储结构

1．二叉树的性质

（1）二叉树第i层（i≥1）上至多有2^i－1个节点。

此性质只要对层数i进行数学归纳证明即可。

（2）高度为k的二叉树至多有2^k－1个节点（k≥1）。

由性质1，每一层的节点数都取最大值即可。

（3）对任何一棵二叉树，若其终端节点数为n₀，度为2的节点数为n₂，则n₀＝n₂＋1。

（4）具有n个节点的完全二叉树的深度为log₂n＋1。

（5）对一棵有n个节点的完全二叉树的节点按层次自左至右进行编号，则对任一节点i（1≤i≤n）有：

①　若i＝1，则节点i是二叉树的根，无双亲；若i＞1，则其双亲为

②　若2i＞n，则节点i没有左孩子，否则其左孩子为2i。

③　若2i＋1＞n，则节点i没有右孩子，否则其右孩子为2i＋1。

若深度为k的二叉树有2^k－1个节点，则称其为满二叉树。可以对满二叉树中的节点进行连续编号：约定编号从根节点起，自上而下、自左至右依次进行。深度为k、有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称之为完全二叉树。满二叉树和完全二叉树的示意图如图8-18所示。

图8-18　满二叉树和完全二叉树示意图

2．二叉树的存储结构

1）二叉树的顺序存储结构

用一组地址连续的存储单元存储二叉树中的节点，必须把节点排成一个适当的线性序列，并且节点在这个序列中的相互位置能反映出节点之间的逻辑关系。

对于深度为k的完全二叉树，除第k层外，其余各层中含有最大的节点数，即每一层的节点数恰为其上一层节点数的两倍，由此从一个节点的编号可推知其双亲、左孩子和右孩子的编号。

假设有编号为i的节点，则有：

（1）若i＝1，该节点为根节点，无双亲。

（2）若i＞1，该节点的双亲节点为（i＋1）/2（取整数）。

（3）若2i≤n，则该节点的左孩子编号为2i，否则无左孩子。

（4）若2i＋1≤n，则该节点的右孩子编号为2i＋1，否则无右孩子。

（5）若i为奇数且不为1，则该节点左兄弟的编号为i－1，否则无左兄弟。

（6）若i为偶数且小于n，则该节点右兄弟的编号为i＋1，否则无右兄弟。

完全二叉树的顺序存储结构如图8-19（a）所示。

显然，完全二叉树采用顺序存储结构既简单又节省空间，对于一般的二叉树，则不宜采用顺序存储结构。因为一般的二叉树也必须按照完全二叉树的形式存储，也就是要添上一些实际并不存在的“虚节点”，这将造成空间的浪费，如图8-19（b）所示。

图8-19　二叉树的顺序存储结构

在最坏情况下，一个深度为k且只有k个节点的二叉树（单支树）却需要2^k－1个存储单元。

2）二叉树的链式存储结构

由于二叉树的节点中包含有数据元素、左子树的根、右子树的根及双亲等信息，因此可以用三叉链表或二叉链表（即一个节点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根节点，如图8-20所示。

图8-20　二叉树的链表存储结构

设节点中的数据元素为整型，则二叉链表的节点类型定义如下：

在不同的存储结构中，实现二叉树的运算方法也不同，具体应采用什么存储结构，除考虑二叉树的形态外还应考虑需要进行的运算特点。

8.3.3　二叉树的遍历

遍历是按某种策略访问树中的每个节点，且仅访问一次的过程。由于二叉树所具有的递归性质，一棵非空的二叉树可以看作是由根节点、左子树和右子树三部分构成的，因此若能依次遍历这三部分，也就遍历了整棵二叉树。按照先遍历左子树后遍历右子树的约定，根据访问根节点位置的不同，可得到二叉树的先序、中序和后序三种遍历方法。此外，对二叉树还可进行层序遍历。

【函数】二叉树的先序遍历。

【函数】二叉树的中序遍历。

【函数】二叉树的后序遍历。

从树根节点出发，三种方法的遍历路线如图8-21所示。该路线从根节点出发，逆时针沿着二叉树的外缘移动，对每个节点均途经三次。若第一次经过节点时进行访问，则是先序遍历；若第二次（或第三次）经过节点时访问节点，则是中序遍历（或后序遍历）。因此，只要将遍历路线上所有在第一次、第二次和第三次经过的节点信息分别输出，即可分别得到该二叉树的先序、中序和后序遍历序列。粗略地讲，若去掉三种遍历算法中的打印输出语句，则三种遍历方法基本相同。这说明三种遍历过程的路线相同。

图8-21　三种遍历过程执行示意图

遍历二叉树的基本操作就是访问节点，不论按照哪种次序遍历，对含有n个节点的二叉树，遍历算法的时间复杂度都为Ο（n）。因为在遍历的过程中，每进行一次递归调用，都是将函数的“活动记录”压入栈中，因此，栈的最大长度恰为树的高度。所以，在最坏情况下，二叉树是有n个节点且高度为n的单枝树，遍历算法的空间复杂度也为Ο（n）。

借助于一个栈，可将二叉树的递归遍历算法转换为非递归算法。下面以中序遍历为例给出中序遍历的非递归算法。

【函数】二叉树的中序非递归遍历算法。

遍历二叉树的过程实质上是按一定规则将树中的节点排成一个线性序列的过程，因此遍历操作得到的是树中节点的一个线性序列。在每一种序列中，有且仅有一个起始点和一个终节点，其余节点有且仅有唯一的直接前驱和直接后继。显然，关于节点的前驱和后继的讨论是针对某一个遍历序列而言的。

对二叉树还可以进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从树的根节点出发，首先访问第1层的树根节点，然后从左到右依次访问第二层上的节点，其次是第三层上的节点，依此类推，自上而下、自左至右逐层访问树中各节点的过程就是层序遍历。

【算法】二叉树的层序遍历算法。

8.3.4　线索二叉树

1．线索二叉树的定义

二叉树的遍历实质上是对一个非线性结构进行线性化的过程，它使得每个节点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。但在二叉链表存储结构中，只能找到一个节点的左、右孩子，而不能直接得到节点在任一遍历序列中的前驱和后继，这些信息只有在遍历的动态过程中才能得到，因此，引入线索二叉树来保存这些动态过程得到的信息。

2．建立线索二叉树

为了保存节点在任一序列中的前驱和后继信息，可以考虑在每个节点中增加两个指针域来存放遍历时得到的前驱和后继信息，这样就可以为以后的访问带来方便。但增加指针信息会降低存储空间的利用率，因此可考虑采用其他方法。

若n个节点的二叉树采用二叉链表作存储结构，则链表中必然有n＋1个空指针域，可以利用这些空指针域来存放节点的前驱和后继信息。线索链表的节点结构如下所示。

其中：

若二叉树的二叉链表采用以上所示的节点结构，则相应的链表称为线索链表，其中指向节点前驱、后继的指针称为线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其成为线索二叉树的过程称为线索化。中序线索二叉树及其存储结构如图8-22所示。

那么如何进行线索化呢？按某种次序将二叉树线索化，实质上是在遍历过程中用线索取代空指针。因此，若设指针p指向正在访问的节点，则遍历时设立一个指针pre，使其始终指向刚刚访问过的节点，这样就记下了遍历过程中节点被访问的先后关系。

在遍历的过程中，设指针p指向正在访问的节点。

图8-22　线索二叉树及其存储结构示意图

（1）若p所指向的节点有空指针域，则将相应的标志域置为1。

（2）若pre!=NULL且pre所指节点的rtag等于1，则令pre->rchild=p。

（3）若p所指向节点的ltag等于1，则令p->lchild=pre。

（4）使pre指向刚刚访问过的节点，即令pre=p。

需要说明的是，用这种方法得到的线索二叉树，其线索并不完整，也就是说，部分节点的前驱或后继信息还不能从其存储结构中直接得到。

3．访问线索二叉树

如何在线索二叉树中查找节点的前驱和后继呢？

以中序线索二叉树为例，令p指向树中的某个节点，查找p所指节点的后继节点的方法如下。

（1）若p->rtag==1，则p->rchild即指向其后继节点。

（2）若p->rtag==0，则p所指节点的中序后继必然是其右子树中进行中序遍历得到的第一个节点。也就是说，从p所指节点的右子树的根节点出发，沿左孩子指针链向下查找，直到找到一个没有左孩子的节点时为止，这个节点就是p所指节点的直接后继节点，也称其为p的右子树中“最左下”的节点。

令p指向中序线索树中的某个节点，则查找p所指节点的直接前驱的方法如下。

（1）若p->ltag==1，则p->lchild即指向其前驱节点。

（2）若p->ltag==0，则p所指节点的中序前驱必然是其左子树中进行中序遍历得到的最后一个节点。也就是说，从p所指节点的左子树的根节点出发，沿右孩子指针链向下查找，直到找到一个没有右孩子的节点时为止，这个节点就是p所指节点的直接前驱节点，也称其为p的左子树中“最右下”的节点。

8.3.5　最优二叉树

1．最优二叉树

最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树。路径是从树中一个节点到另一个节点之间的通路，路径上的分支数目称为路径长度。

树的路径长度是从树根到每一个叶子之间的路径长度之和。节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。

树的带权路径长度为树中所有叶子节点的带权路径长度之和，记为

其中，n为带权叶子节点数目，w_k为叶子节点的权值，l_k为叶子节点到根的路径长度。

哈夫曼树是指权值为w₁，w₂，…，w_n的n个叶子节点的二叉树中带权路径长度最小的二叉树。

例如，图8-23所示的具有4个叶子节点的二叉树，其中以图8-23（b）所示二叉树带权路径长度最小。

图8-23　不同带权路径长度的二叉树

那么如何构造最优二叉树呢？构造最优二叉树的哈夫曼算法如下。

（1）根据给定的n个权值｛w₁，w₂，…，w_n｝，构成n棵二叉树的集合F＝｛T₁，T₂，…，T_n｝，其中每棵树T_i中只有一个带权为w_i的根节点，其左右子树均空。

（2）在F中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树，置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。

（3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。

重复（2）、（3）步，直到F中只含一棵树时为止，这棵树便是最优二叉树（哈夫曼树）。

由此算法可知，以选中的两棵子树构成新的二叉树，谁作为左子树，谁作为右子树，并没有明确。所以具有n个叶子节点的权值为w₁，w₂，…，w_n的最优二叉树不唯一，但其WPL值是唯一确定的。

当给定了n个权值后，构造出的最优二叉树中的节点数目m就确定了，即m＝2×n－1，所以可用一维的结构数组来存储最优二叉树，下面举例说明。

【函数】创建最优二叉树。

2．哈夫曼编码

若对每个字符编制相同长度的二进制码，则称为等长编码。例如，英文字符集中的26个字符可采用5位二进制串表示，按等长编码格式构造一个字符编码表。发送方按照编码表对信息原文进行编码后送出电文，接收方对接收到的二进制代码按每5位一组进行分割，通过查字符的编码表即可得到对应字符，实现译码。

等长编码方案的实现方法比较简单，但对通信中的原文进行编码后，所得电文的码串过长，不利于提高通信效率，因此希望缩短码串的总长度。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，那么传送的电文码串总长度则可减少。

要设计长度不等的编码，必须满足下面的条件：任一字符的编码都不是另一个字符的编码的前缀，这种编码也称为前缀码。对给定的字符集D＝｛d₁，d₂，…，d_n｝及字符的使用频率W＝｛w₁，w₂，…，w_n｝，构造其最优前缀码的方法为：以d₁，d₂，…，d_n作为叶子节点，w₁，w₂，…，w_n作为叶子节点的权值，构造出一棵最优二叉树，然后将树中每个节点的左分支标上0，右分支标上1，则每个叶子节点代表的字符的编码就是从根到叶子的路径上的0、1组成的串。最优前缀编码方法如图8-24所示。

图8-24　前缀编码示例

【函数】从每个叶子节点出发追溯到树根，逆向找出最优二叉树中叶子节点的编码。

利用哈夫曼树译码的过程为：从根节点出发，按二进制位串中的0和1确定是进入左分支还是右分支，当到达叶子节点时译出一个字符。若位串未结束，则回到根节点继续上述译码过程。

【函数】用最优二叉树进行译码。

8.3.6　树和森林

1．树的存储结构

（1）树的双亲表示法：用一组地址连续的单元存储树的节点，并在每个节点中附设一个指示器，指出其双亲节点在该存储结构中的位置（节点所在数组元素的下标）。显然，这种表示对于求指定节点的双亲或祖先都十分方便，但对于求指定节点的孩子及后代则需要遍历整个数组，如图8-25所示。

（2）树的孩子表示法：在存储结构中用指针指示出节点的每个孩子，由于树中每个节点的子树数目不尽相同，因此在采用链式存储结构时可以考虑多重链表。因为每个节点的指针数目不好确定，对于定长的节点可依据树的度来设置节点中的指针，显然会造成极大的浪费；若设置节点中的指针数目不相等，则运算时又不方便，为此可以考虑为树中每个节点的孩子建立一个链表，即令每个节点的所有孩子节点构成一个用单链表表示的线性表，则n个节点的树具有n个单链表。将这n个单链表的头指针又排成一个线性表，如图8-26（a）所示。

也可以将双亲表示法和孩子表示法结合起来，形成树的双亲孩子表示结构，如图8-26（b）所示。

图8-25　树的双亲表示法示意图

图8-26　图8-25（a）中树的孩子表示法

（3）孩子兄弟表示法：又称为二叉链表表示法。在链表的节点中设置两个指针域分别指向该节点的第一个孩子和下一个兄弟，如图8-27所示。

树的孩子兄弟表示法为实现树、森林与二叉树之间的转换提供了基础，充分利用二叉树的有关算法来实现树及森林的操作，对难于把握规律的树和森林有着重要的现实意义。

图8-27　图8-25（a）中树的孩子兄弟表示法

2．树和森林的遍历

1）树的遍历

由于树中每个节点可以有两棵以上的子树，因此遍历树的方法有两种：先根遍历和后根遍历。

（1）树的先根遍历。树的先根遍历是先访问树的根节点，然后依次先根遍历根的各棵子树。对树的先序遍历等同于对转换所得的二叉树进行先序遍历。

（2）树的后根遍历。树的后根遍历是先依次后根遍历树根的各棵子树，然后访问树根节点。树的后根遍历等同于对转换所得的二叉树进行中序遍历。

2）森林的遍历

按照森林和树的相互递归定义，可以得出森林的两种遍历方法。

（1）先序遍历森林。若森林非空，访问森林中第一棵树的根节点，先序遍历第一棵子树根节点的子树森林，再先序遍历除第一棵树之外剩余的树所构成的森林。

（2）中序遍历森林。若森林非空，先中序遍历森林中第一棵树的子树森林，然后访问第一棵树的根节点，最后中序遍历除第一棵树之外剩余的树所构成的森林。

3．树、森林和二叉树之间的相互转换

树、森林和二叉树之间可以互相进行转换，即任何一个森林或一棵树可以对应一棵二叉树，而任一棵二叉树也能对应到一个森林或一棵树上。

（1）树、森林转换为二叉树。利用树的孩子兄弟表示法可导出树与二叉树的对应关系，在树的孩子兄弟表示法中，从物理结构上看与二叉树的二叉链表表示法相同，因此就可以用这种同一存储结构的不同解释将一棵树转换为一棵二叉树，如图8-28所示。一棵树可转换成唯一的一棵二叉树。

图8-28　树转换为二叉树

由于树根没有兄弟，所以树转换为二叉树后，二叉树的根一定没有右子树。这样，将一个森林转换为一棵二叉树的方法是：先将森林中的每一棵树转换为二叉树，再将第一棵树的根作为转换后的二叉树的根，第一棵树的左子树作为转换后二叉树根的左子树，第二棵树作为转换后二叉树的右子树，第三棵树作为转换后二叉树根的右子树的右子树，依此类推，森林就可以转换为一棵二叉树，如图8-29所示。

2）二叉树转换为树和森林。二叉树可转换为唯一的树或森林，如图8-30所示。

图8-29　森林转换为二叉树

图8-30　二叉树转换为树（或森林）

8.4　图

图是比树结构更复杂的一种数据结构。在线性结构中，除首节点没有前驱、末尾节点没有后继之外，一个节点只有唯一的一个直接前驱和唯一的一个直接后继。在树结构中，可认为除根节点没有前驱节点外，其余的每个节点只有唯一的一个前驱（双亲）节点和多个后继（子树）节点。而在图结构中，任意两个节点之间都可能有直接的关系，所以图中一个节点的前驱节点和后继节点的数目是没有限制的。

8.4.1　图的定义与存储

1．图的定义

图G是由集合V和E构成的二元组，记作G＝（V，E），其中V是图中顶点的非空有限集合，E是图中边的有限集合。从数据结构的逻辑关系角度来看，图中任一顶点都有可能与其他顶点有关系，而图中所有顶点都有可能与某一顶点有关系。在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示。

（1）有向图。若图中每条边都是有方向的，那么顶点之间的关系用＜v_i，v_j＞表示，它说明从v_i到v_j有一条有向边（也称为弧）。v_i是有向边的起点，称为弧尾；v_j是有向边的终点，称为弧头。所有边都有方向的图称为有向图。

（2）无向图。若图中的每条边都是无方向的，顶点v_i和v_j之间的边用（v_i，v_j）表示。因此，在有向图中＜v_i，v_j＞与＜v_j，v_i＞分别表示两条边，而在无向图中（v_i，v_j）与（v_j，v_i）表示的是同一条边。

（3）完全图。若一个无向图具有n个顶点，而每一个顶点与其他n－1个顶点之间都有边，则称之为无向完全图。显然，含有n个顶点的无向完全图共有条边。类似地，有n个顶点的有向完全图中弧的数目为n（n－1），即任意两个不同顶点之间都有方向相反的两条弧存在。

（4）度、出度和入度。顶点v的度是指关联于该顶点的边的数目，记作D（v）。若G为有向图，顶点的度表示该顶点的入度和出度之和。顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目，分别记为ID（v）和OD（v）。无论是有向图还是无向图，顶点数n、边数e与各顶点的度之间有以下关系

（5）路径。在无向图G中，从顶点v_p到顶点v_q的路径是指存在一个顶点序列v_p，v_i1，v_i2，…，v_in，v_q，使得（v_p，v_i1），（v_i1，v_i2），…，（v_in，v_q）均属于E（G）。若G是有向图，其路径也是有方向的，它由E（G）中的有向边＜v_p，v_i1＞，＜v_i1，v_i2＞，…，＜v_in，v_q＞组成。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。若一条路径上除了v_p和v_q可以相同外，其余顶点均不相同，则称其为简单路径。

（6）子图。若有两个图G＝（V，E）和G′＝（V′，E′），如果V′⊆V且E′⊆E，则称G′为G的子图。

（7）连通图与连通分量。在无向图G中，若从顶点v_i到顶点v_j有路径，则称顶点v_i和顶点v_j是连通的。如果无向图G中任意两个顶点都是连通的，则称其为连通图。无向图G的极大连通子图称为G的连通分量。

（8）强连通图与强连通分量。在有向图G中，如果对于每一对顶点v_i，v_j∈V且v_i≠v_j，从顶点v_i到顶点v_j和从顶点v_j到顶点v_i都存在路径，则称图G为强连通图。有向图中的极大连通子图称为有向图的强连通分量。

（9）网。边（或弧）带权值的图称为网。

（10）有向树。如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。

从图的逻辑结构的定义来看，图中的顶点之间不存在全序关系（即无法将图中的顶点排列成一个线性序列），任何一个顶点都可被看成第一个顶点；另一方面，任一顶点的邻接点之间也不存在次序关系。为了便于运算，给图中每个顶点赋予一个序号值。

2．图的存储结构

图的基本存储结构有邻接矩阵表示法和邻接链表表示法两种。

1）邻接矩阵表示法

图的邻接矩阵表示利用一个矩阵来表示图中顶点之间的关系。对于具有n个顶点的图G＝（V，E），其邻接矩阵是一个n阶方阵，且满足：

图8-31　所示的有向图和无向图的邻接矩阵分别为A和B。

图8-31　有向图和无向图及其邻接矩阵

由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵则不一定对称。借助于邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相连，并且容易求得各个顶点的度。对于无向图，顶点v_i的度是邻接矩阵第i行（或列）中值不为0的元素个数；对于有向图，第i行（或列）中值不为0的元素个数是顶点v_i的出度OD（v_i），第j列的非0元素个数是顶点v_j的入度ID（v_j）。

网（赋权图）的邻接矩阵可定义为：

其中，W_ij是边上的权值。

图8-32所示的是网及其邻接矩阵C。

图8-32　一个网及其邻接矩阵表示

若用邻接矩阵表示图，则对应的数据类型可定义为：

或

2）邻接链表表示法

邻接链表指的是为图的每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点v_i的边（对于有向图是以v_i为尾的弧）。邻接链表中的节点有表节点和表头节点两种类型，如下所示。

表节点

表头节点

其含义如下。

●　adjvex：指示与顶点v_i邻接的顶点的序号。

●　nextarc：指示下一条边或弧的节点。

●　info：存储与边或弧有关的信息，如权值等。

●　data：存储顶点v_i的名或其他有关信息。

●　firstarc：指示链表中的第一个节点（邻接顶点）。

这些表头节点通常以顺序的形式存储，以便随机访问任一顶点的邻接链表。若图用邻接链表来表示，则对应的数据类型可定义如下：

显然，对于有n个顶点、e条边的无向图来说，其邻接链表需用n个头节点和2e个表节点。

对于无向图的邻接链表，顶点v_i的度恰为第i个邻接链表中表节点的数目，而在有向图中，为求顶点的入度，必须扫描逐个邻接表，这是因为第i个邻接链表中表节点的数目只是顶点v_i的出度。为此，可以建立一个有向图的逆邻接链表。有向图的邻接表和逆邻接表如图8-33所示。

图8-33　一个有向图及其邻接表和逆邻接表表示

8.4.2　图的遍历

与树的遍历相似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点进行访问且只访问一次。图的遍历算法是求解图的连通性问题、拓扑排序及求关键路径等算法的基础。

图的遍历要比树的遍历复杂得多。因为图的任一个节点都可能与其余顶点相邻接，所以在访问了某个顶点之后，可能沿着某路径又回到该节点上，为了避免顶点的重复访问，在图的遍历过程中，必须记下每个已访问过的顶点。深度优先遍历和广度优先遍历是两种遍历图的基本方法。

1．深度优先搜索（Depth First Search，DFS）

此种方法类似于树的先根遍历，在第一次经过一个顶点时就进行访问操作。从图G中任一节点v出发按深度优先搜索法进行遍历的步骤如下。

（1）设置搜索指针p，使p指向顶点v；

（2）访问p所指顶点，并使p指向与其相邻接的且尚未被访问过的顶点。

（3）若p所指顶点存在，则重复步骤（2），否则执行步骤（4）。

（4）沿着刚才访问的次序和方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p指向这个未被访问的顶点，然后重复步骤（2），直至所有的顶点均被访问为止。

该算法的特点是尽可能先对纵深方向搜索，因此可以得到其递归遍历算法。

【函数】以邻接链表表示图的深度优先搜索算法。

从函数Dfs（）之外调用Dfs可以访问到所有与一个指定顶点有路径相通的其他顶点。若图是不连通的，则下一次应从另一个未被访问过的顶点出发，再次调用Dfs进行遍历，直到将图中所有的顶点都访问到为止。深度优先的搜索过程如图8-34所示。

深度优先遍历图的过程实质上是对某个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时，查找所有顶点的邻接点所需时间为Ο（n²）。若以邻接表作为图的存储结构，则需要Ο（e）的时间复杂度查找所有顶点的邻接点。因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为Ο（n＋e）。

2．广度优先搜索（Breadth First Search，BFS）

图的广度优先搜索方法为：从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时还有未被访问的顶点，则另选图中的一个未被访问的顶点作为起点，重复上述过程，直至图中所有的顶点都被访问到为止。对图8-35所示的图进行广度优先搜索，得到的序列为1，2，3，4，5，6。

图8-34　深度优先搜索遍历过程

图8-35　一个不连通的无向图

广度优先遍历图的特点是尽可能先进行横向搜索，即最先访问的顶点的邻接点也先被访问。为此，引入队列来保存已访问过的顶点序列，即每当一个顶点被访问后，就将其放入队中，当队头顶点出队时，就访问其未被访问的邻接点并令这些邻接顶点入队。

【算法】以邻接链表表示图的广度优先搜索算法。

在广度优先遍历算法中，每个顶点至多进一次队列。

遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图和深度优先搜索遍历图的时间复杂度相同，其不同之处仅仅在于对顶点访问的次序不同。

8.4.3　生成树及最小生成树

1．生成树的概念

一个连通图的生成树是一个极小连通子图，它包含图中的全部顶点，但只有构成一棵树的n－1条边。图8-36所示的是图及其生成树和非生成树。

图8-36　一个无向图的生成树和非生成树

按深度和广度优先搜索进行遍历将得到不同的生成树，分别称为深度优先生成树和广度优先生成树。例如，图8-37所示的是图的一棵深度优先生成树和一棵广度优先生成树。

对于有n个顶点的连通图，至少有n－1条边，而生成树中恰好有n－1条边，所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边，则必然形成回路。

图8-37　图的搜索生成树

图的生成树不是唯一的。从不同的顶点出发，选择不同的存储方式，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。

2．最小生成树

一个图的生成树不唯一，从不同的顶点出发可得到不同的生成树。对于连通网来说，边是带权值的，生成树的各边也带权值，因此把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。

常用的最小生成树算法有普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。

（1）普里姆（Prim）算法。

假设N＝（V，E）是连通网，TE是N上最小生成树中边的集合。算法从顶点集合U＝｛u₀｝（u₀∈V）、边的集合TE＝｛｝开始，重复执行下述操作：在所有u∈U，v∈V－U的边（u，v）∈E中找一条代价最小的边（u₀，v₀），把这条边并入集合TE，同时将v₀并入集合U，直至U＝V时为止。此时TE中必有n－1条边，T＝（V，｛TE｝）为N的最小生成树。

由此可知，普里姆算法构造最小生成树的过程是以一个顶点集合U＝｛u₀｝作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U集合直至U＝V时为止。

用普里姆算法构造最小生成树的过程如图8-38所示。

图8-38　普里姆算法构造最小生成树的过程

普里姆算法的时间复杂度为Ο（n²），与图中的边数无关，因此该算法适合于求边稠密的网的最小生成树。

（2）克鲁斯卡尔（Kruskal）算法。

克鲁斯卡尔求最小生成树的算法思想为：假设连通网N＝（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T＝（V，｛｝），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点都在同一连通分量上为止。

用克鲁斯卡尔算法构造最小生成树的过程如图8-39所示。

图8-39克　斯卡尔算法构造最小生成树的过程

克鲁斯卡尔算法的时间复杂度为Ο（eloge），与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。

8.4.4　拓扑排序和关键路径

1．AOV网

在工程领域，一个大的工程项目通常被划分为许多较小的子工程（称为活动）。显然，当这些子工程都完成时，整个工程也就完成了。在有向图中，若以顶点表示活动，用有向边表示活动之间的优先关系，则称这样的有向图为以顶点表示活动的网（Activity On Vertex network，AOV网）。在网中，若从顶点v_i到顶点v_j有一条有向路径，则顶点v_i是v_j的前驱，顶点v_j是v_i的后继。若＜v_i，v_j＞是网中的一条弧，则顶点v_i是v_j的直接前驱，顶点v_j是v_i的直接后继。AOV网中的弧表示了活动之间的优先关系，也可以说是一种活动进行时的制约关系。

在AOV网中不应出现有向环，若存在的话，则意味着某项活动必须以自身任务的完成为先决条件，显然这是荒谬的。因此，若要检测一个工程是否可行，首先就应检查对应的AOV网是否存在回路。不存在回路的AOV网称为有向无环图，或DAG（Directed Acycline Graph）图。检测的方法是对有向图构造其顶点的拓扑有序序列。若图中所有顶点都在它的拓扑有序序列中，则该AOV网中必定不存在环。

2．拓扑排序及其算法

拓扑排序是将AOV网中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点v_i到v_j有一条路径，则在该线性序列中，顶点v_i必然在顶点v_j之前。

拓扑排序即指对AOV网构造拓扑序列的操作。一般情况下，假设AOV图代表一个工程计划，则AOV网的一个拓扑排序就是一个工程顺利完成的可行方案。

对AOV网进行拓扑排序的方法如下。

（1）在AOV网中选择一个入度为0（没有前驱）的顶点且输出它。

（2）从网中删除该顶点及其与该顶点有关的所有边。

（3）重复上述两步，直至网中不存在入度为0的顶点为止。

执行的结果会有两种情况：一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。图8-40所示的是拓扑排序过程，得到的拓扑序列为6，1，4，3，2，5。

图8-40　拓扑排序过程

当有向图中无环时，也可以利用深度优先遍历进行逆拓扑排序。由于图中无环，从图中某点出发进行深度优先搜索遍历时，最先退出DFS函数的顶点即是出度为0的顶点，它是拓扑有序序列中最后的一个顶点。由此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。拓扑排序算法的时间复杂度为Ο（n＋e）。

3．AOE网

若在带权有向图G中以顶点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则这种带权有向图称为用边表示活动的网（Activity On Edge network，AOE网）。通常在AOE网中列出了完成预定工程计划所需进行的活动、每项活动的计划完成时间、要发生哪些事件以及这些事件和活动间的关系，从而可以分析该项工程是否实际可行并估计工程完成的最短时间，以及影响工程进度的关键活动；进一步可以进行人力、物力的调度和分配，以达到缩短工期的目的。

用AOE网表示一项工程计划时，顶点所表示的事件实际上就是某些活动已经完成、某些子活动可以动工的标志。具体地说，顶点所表示的事件是指该顶点所有进入边所表示的活动均已完成、从它出发的边所表示的活动均可以开始的一种状态。

一般情况下，每项工程都有一个开始状态和一个结束状态，所以在AOE网中至少有一个入度为0的开始顶点，称为源点。另外，应有一个出度为0的结束顶点，称为汇点。AOE网中不应存在有向回路，否则整个工程无法完成。

与AOV网不同，AOE网所关心的问题如下。

（1）完成该工程至少需要多少时间？

（2）哪些活动是影响整个工程进度的关键？

由于AOE网中的某些活动能够并行地进行，因此完成整个工程所需的时间是从开始顶点到结束顶点的最长路径的长度。这里的路径长度是指该路径上的权值之和。

4．关键路径和关键活动

从源点到汇点的路径中，长度最长的路径称为关键路径。关键路径上的所有活动均是关键活动。如果任何一项关键活动没有按期完成，则会影响整个工程的进度，而提高关键活动的速度通常可以缩短整个工程的工期。假设在n个顶点的AOE网中，顶点v₀表示源点、顶点v_n－1表示汇点，则引入顶点事件的最早、最晚发生时间，活动的最早、最晚开始时间等术语。

（1）顶点事件的最早发生时间ve（j）。ve（j）是指从源点v₀到v_j的最长路径长度（时间）。这个时间决定了所有从v_j发出的弧所表示的活动能够开工的最早时间。

ve（j）计算方法为

其中，T是所有到达顶点j的弧的集合，dut（＜i，j＞）是弧＜i，j＞上的权值，n是网中的顶点数，如图8-41（a）所示。

显然，上式是一个从源点开始的递推公式。必须在v_j的所有前驱顶点事件的最早发生时间全部得出后才能计算ve（j）。这样必须对AOE网进行拓扑排序，然后按拓扑有序序列逐个求出各顶点事件的最早发生时间。

（2）顶点事件的最晚发生时间vl（i）。vl（i）是指在不推迟整个工期的前提下，事件v_i的最晚发生时间。对一个工程来说，计划用几天时间完成是可以从AOE网求得的，其数值就是汇点v_n－1的最早发生时间ve（n－1），而这个时间也就是vl（n－1）。其他顶点事件的vl应从汇点开始，逐步向源点方向递推才能求得，所以vl（i）的计算公式为

其中，S是所有从顶点i发出的弧的集合，如图8-41（b）所示。

图8-41　推导事件的最早、最晚发生时间示意图

显然，必须在顶点v_i的所有后继顶点事件的最晚发生时间全部得出后才能计算vl（i）。这样必须对AOE网逆拓扑排序，由逆拓扑序列递推计算各顶点的vl值。

（3）活动a_k的最早开始时间e（k）。e（k）是指弧＜i，j＞所表示的活动a_k最早可开工时间。

这说明活动a_k的最早开始时间等于事件v_i的最早发生时间。

（4）活动a_k的最晚开始时间l（k）。l（k）是指在不推迟整个工期的前提下，该活动的最晚开始时间。若活动a_k由弧＜i，j＞表示，则

对于活动a_k来说，若e（k）＝l（k），则表示活动a_k是关键活动，它说明该活动最早可开工时间与整个工程计划允许该活动最晚的开工时间一致，施工期一点也不能拖延。若活动a_k不能按期完成，则工程将延期；若活动a_k提前完成，则可能使整个工程提前完工。

由关键活动组成的路径是关键路径。依照上述计算关键活动的方法，就可形成求AOE网的关键路径。

8.4.5　最短路径

1．单源点最短路径

所谓单源点最短路径，是指给定带权有向图G和源点v₀，求从v₀到G中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）提出了按路径长度递增的次序产生最短路径的算法，其思想是：把网中所有的顶点分成两个集合S和T，S集合的初态只包含顶点v₀，T集合的初态为网中除v₀之外的所有顶点。凡以v₀为源点，已经确定了最短路径的终点并入S集合中，顶点集合T则是尚未确定最短路径的顶点的集合。按各顶点与v₀间最短路径长度递增的次序，逐个把T集合中的顶点加入到S集合中去，使得从v₀到S集合中各顶点的路径长度始终不大于从v₀到T集合中各顶点的路径长度。

为了能方便地求出从v₀到T集合中各顶点最短路径的递增次序，引入一个辅助向量dist。它的某一个分量dist[i]表示当前求出的从v₀到终点v_i的最短路径长度。这个路径长度并不一定是真正的最短路径长度。它的初始状态为：若从v₀到v_i有弧，则dist[i]为弧上的权值；否则，置dist[i]为∞。显然，长度为dist[u]＝min｛dist[i]｜v_i∈V（G）｝的路径就是从v₀出发的长度最短的一条最短路径。此路径为（v₀，u），这时顶点u应从集合T中删除，将其并入集合S。

设网用邻接矩阵arcs存储，那么每次选出一个顶点u并使之并入集合S后，就根据情况修改T集合中各顶点的路径长度dist。对于T集合中的某一个顶点i来说，其更短路径可能为（v₀，…，v_u，v_i）。也就是说，若dist[u]＋ares[u][i]＜dist[i]，则修改dist[i]，使dist[i]＝dist[u]＋ares[u][i]。

对T集合中各顶点的dist进行修改后，再从中挑选出一个路径长度最小的顶点，从T集合中删除并将其并入S集合。依此类推，就能求出源点到其余各顶点的最短路径长度。

对于图8-42所示的有向网，用迪杰斯特拉算法求解顶点V₀到达其余顶点的最短路径的过程如表8-1所示。

图8-42　有向网G及其邻接矩阵

表8-1　迪杰斯特拉算法求解图8-46中顶点V₀到V₁、V₂、V₃、V₄、V₅最短路径的过程

2．每对顶点间的最短路径

若每次以一个顶点为源点，重复执行迪杰斯特拉算法n次，便可求得网中每一对顶点之间的最短路径。下面介绍弗洛伊德（Floyd）提出的求最短路径的算法，该算法在形式上要简单一些。

弗洛伊德算法思想是：假设图采用邻接矩阵的方式存储，需要求从顶点v_i到v_j的最短路径。arcs[i][j]表示弧（v_i，v_j）的权值，若此弧不存在，则权值为区别于有效权值的一个数。如果存在v_i到v_j的弧，则从v_i到v_j存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径（v_i，v₀，v_j）是否存在（即判别路径（v_i，v₀）和（v₀，v_j）是否存在），若存在，则比较（v_i，v_j）与（v_i，v₀，v_j）的路径长度，取较短者为从v_i到v_j的中间顶点的序号不大于0的最短路径。假如在路径上再增加一个顶点v₁，也就是说，如果（v_i，…，v₁）和（v₁，…，v_j）分别是当前找到的中间顶点的序号不大于0的v_i到v₁以及v₁到v_j的最短路径，那么（v_i，…v₁，…，v_j）就有可能是从v_i到v_j的中间顶点的序号不大于1的最短路径。将它与已经得到的从v_i到v_j的中间顶点的序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v₂继续进行试探，依此类推。在一般情况下，若（v_i，…，v_k）和（v_k，…，v_j）分别是从v_i到v_k和v_k到v_j的中间顶点的序号不大于k－1的最短路径，则将（v_i，…，v_k，…，v_j）与已经得到的从v_i到v_j的中间顶点的序号不大于k－1的最短路径相比较，长度较短者便是从v_i到v_j的中间顶点的序号不大于k的最短路径。这样，在经过n次试探后，最后求得的必是从v_i到v_j的最短路径。按此方法，可以同时求得各对顶点间的最短路径。

8.5　查找

8.5.1　查找的基本概念

1．基本概念

查找是一种常用的基本运算。查找表是指由同一类型的数据元素（或记录）构成的集合。由于“集合”这种数据结构中的数据元素之间存在着完全松散的关系，因此，查找表是一种非常灵活的数据结构。

对查找表经常要进行的两种操作如下。

（1）查询某个“特定”的数据元素是否在查找表中。

（2）检索某个“特定”的数据元素的各种属性。

通常将只进行这两种操作的查找表称为静态查找表。

对查找表经常要进行的另外两种操作如下。

（1）在查找表中插入一个数据元素。

（2）从查找表中删除一个数据元素。

若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找为动态查找表。

关键字是数据元素（或记录）的某个数据项的值，用它来识别（标识）这个数据元素。主关键字是指能唯一标识一个数据元素的关键字。次关键字是指能标识多个数据元素的关键字。

根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找成功，此时给出整个记录的信息，或者指出记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时的查找结果用一个“空”记录或“空”指针表示。

2．平均查找长度

对于查找算法来说，其基本操作是“将记录的关键字与给定值进行比较”。因此，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。

为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度。

对于含有n个记录的表，查找成功时的平均查找长度定义为

其中，P_i为对表中第i个记录进行查找的概率，且一般情况下，均认为查找每个记录的概率是相等的，即P_i＝1/n；C_i为找到表中其关键字与给定值相等的记录时（为第i个记录），和给定值已进行过比较的关键字个数，显然，C_i随查找方法的不同而不同。

8.5.2　静态查找表的查找方法

1．顺序查找

顺序查找的基本思想是：从表中的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。

顺序查找的方法对于顺序存储方式和链式存储方式的查找表都适用。

从顺序查找的过程可见，C_i取决于所查记录在表中的位置。若需查找的记录正好是表中的第一个记录时，仅需比较一次；若查找成功时找到的是表中的最后一个记录，则需比较n次。从表尾开始查找时则正好相反，一般情况下，C_i＝n－i＋1，因此在等概率情况下，顺序查找成功的平均查找长度为

也就是说，成功查找的平均比较次数约为表长的一半。若所查记录不在表中，则必须进行n次（不设监视哨，设置监视哨时为n＋1次）比较才能确定失败。监视哨是指查找表用一维数组存储时，将待查找的记录放置在查找表的第一个记录之前或最后一个记录之后，从而在查找过程中避免对数组元素的下标合法性进行检查。

与其他查找方法相比，顺序查找方法在n值较大时，其平均查找长度较大，查找效率较低。但这种方法也有优点，那就是算法简单且适应面广，对查找表的结构没有要求，无论记录是否按关键字有序排列均可应用。

2．折半查找

设查找表的元素存储在一维数组r[1..n]中，在表中的元素已经按关键字递增（或递减）方式排序的情况下，进行折半查找的方法是：首先将待查元素的关键字（key）值与表r中间位置上（下标为mid）记录的关键字进行比较，若相等，则查找成功；若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1..n]中，下一步应在后半个子表中进行查找，若key>r[mid].key，说明待查记录只可能在前半个子表r[1..mid-1]中，下一步应在r的前半个子表中进行查找，这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。

【函数】设有一个整型数组中的元素是按非递减的方式排列的，在其中进行折半查找的算法为：

【函数】设有一个整型数组中的元素是按非递减的方式排列的，在其中进行折半查找的递归算法如下：

折半查找的性能分析如下。

折半查找的过程可以用一棵二叉树描述，方法是以当前查找区间的中间位置序号作为根，左半个子表和右半个子表中的记录序号分别作为根的左子树和右子树上的节点，这样构造的二叉树称为折半查找判定树。例如，具有11个节点的折半查找判定树如图8-43所示。

从折半查找判定树可以看出，查找成功时，折半查找的过程恰好走了一条从根节点到被查找节点的路径，与关键字进行比较的次数即为被查找节点在树中的层数。因此，折半查找在查找成功时进行比较的关键字数最多不超过树的深度，而具有n个节点的判定树的深度为，所以折半查找在查找成功时和给定值进行比较的关键字个数至多为。

给判定树中所有节点的空指针域加一个指向方型节点的指针，称这些方型节点为判定树的外部节点（与之相对，称那些圆形节点为内部节点），如图8-44所示。那么折半查找不成功的过程就是走了一条从根节点到外部节点的路径。与给定值进行比较的关键字个数等于该路径上内部节点个数，因此折半查找在查找不成功时和给定值进行比较的关键字个数最多也不会超过。

图8-43　具有11个节点的折半查找判定树

图8-44　加上外部节点的判定树

那么折半查找的平均查找长度是多少呢？为了方便起见，不妨设节点总数为n＝2^h－1，则判定树是深度为h＝log₂（n＋1）的满二叉树。在等概率情况下，折半查找的平均查找长度为

当n值较大时，ASL_bs≈log₂（n＋1）－1。

折半查找比顺序查找的效率要高，但它要求查找表进行顺序存储并且按关键字有序排列。因此，当需要对表进行元素的插入或删除操作时，需要移动大量的元素。所以折半查找适用于表不易变动，且又经常进行查找的情况。

3．分块查找

分块查找又称索引顺序查找，是对顺序查找方法的一种改进，其效率介于顺序查找与折半查找之间。

在分块查找过程中，首先将表分成若干块，每一块的关键字不一定有序，但块之间是有序的，即后一块中所有记录的关键字均大于前一个块中最大的关键字。此外，还建立了一个“索引表”，索引表按关键字有序，如图8-45所示。

图8-45　表及其索引表

因此，分块查找过程分为两步：第一步在索引表中确定待查记录所在的块；第二步在块内顺序查找。

由于分块查找实际上是两次查找的过程，因此其平均查找长度应该是两次查找的平均查找长度（块内查找与索引查找）之和，即

其中，L_b为查找索引表的平均查找长度，L_w为块内查找时的平均查找长度。

分块查找时，可将长度为n的表均匀地分成b块，每块含有s个记录，既有在等概率查找的情况下，块内查找的概率为每块的查找概率为若用顺序查找确定元素所在的块，则分块查找的平均查找长度为

可见，其平均查找长度不仅与表长n有关，而且与每一块中的记录数s有关。可以证明，当s取时，ASL_bs取最小值此时的查找效率较顺序查找要好得多，但远不及折半查找。考虑到索引表是一个有序表，因此可以用折半查找确定元素所在的块。

8.5.3　动态查找表

动态查找表的特点是表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字等于key的记录，则查找成功返回；否则插入关键字为key的记录。

1．二叉排序树

1）二叉排序树的定义

二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有如下性质的二叉树。

（1）若它的左子树非空，则左子树上所有节点的值均小于根节点的值。

（2）若它的右子树非空，则右子树上所有节点的值均大于根节点的值。

（3）左、右子树本身是二叉排序树。

图8-46　为二叉排序树的示意图。

2）二叉排序树的查找过程

因为二叉排序树中左子树上所有节点的关键字均小于根节点的关键字，右子树上所有节点的关键字均大于根节点的关键字，所以在二叉排序树上进行查找的过程为：二叉排序树非空时，将给定值与根节点的关键字值相比较，若相等，则查找成功；若不等，当根节点的关键字值大于给定值时，下一步到根的左子树中进行查找，否则到根的右子树中进行查找。若查找成功，则查找过程是走了一条从树根到所找到节点的路径；否则，查找过程终止于一棵空的子树。

图8-46　二叉排序树示意图

设二叉排序树采用二叉链表存储，节点的类型定义如下：

【函数】二叉排序树的查找算法。

3）二叉排序树中插入节点的操作

二叉排序树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的，具体的过程是：每读入一个元素，建立一个新节点。若二叉排序树非空，则将新节点的值与根节点的值相比较，如果小于根节点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空，则新节点作为二叉排序树的根节点。设关键字序列为｛46，25，54，13，29，91｝，则整个二叉排序树的构造过程如图8-47所示。

图8-47　二叉排序树的构造过程

【函数】二叉排序树的插入算法。

从上面的插入过程还可以看到，每次插入的新节点都是二叉排序树上新的叶子节点，因此插入节点时不必移动其他节点，仅需改动某个节点的孩子指针。这就相当于在一个有序序列上插入一个记录而不需要移动其他记录。它表明，二叉排序树具有类似于折半查找的特性，可采用链表存储结构，因此是动态查找表的一种适宜表示。

另外，由于一棵二叉排序树的形态完全由输入序列决定，所以在输入序列已经有序的情况下，所构造的二叉排序树是一棵单枝树。例如，对于关键字序列（12，18，23，45，60），建立的二叉排序树如图8-48所示，这种情况下的查找效率与顺序查找的效率相同。

图8-48　由关键字序列（12，18，23，45，60）创建的二叉排序树

4）二叉排序树中删除节点的操作

在二叉排序树中删除一个节点，不能把以该节点为根的子树都删除，只能删除这个节点并仍旧保持二叉排序树的特性。也就是说，删除二叉排序树上一个节点相当于删除有序序列中的一个元素。

假设在二叉排序树删除节点p（p指向被删除节点），f为其双亲节点，则该操作可分为三种情况：p节点为叶子节点；p节点只有左子树或者只有右子树；*p节点的左子树、右子树均存在。

（1）若p节点为叶子节点，即p->lchild及p->rchild均为空，则由于删去叶子节点后不破坏整棵树的结构，因此只需修改p节点的双亲节点*f的相应指针即可。

（2）若p节点只有左子树或者只有右子树，此时只要将p的左子树或右子树接成其双亲节点*f的左子树（或右子树），即令

或

（3）若p节点的左、右子树均不空，则删除p节点时应将其左子树、右子树连接到适当的位置，并保持二叉排序树的特性。可采用如下两种方法进行处理：一是令p的左子树为f的左子树（若p是f的左子树，否则为右子树），而将p的右子树下接到p的中序遍历的直接前驱节点s（s节点是p的左子树中最右下方的节点）的右孩子指针上；二是用p的中序直接前驱（或后继）节点s代替p节点，然后删除*s节点。如图8-49所示。

图8-49　删除二叉排序树中具有两个子树的节点示意图

从二叉排序树的定义可知，中序遍历二叉排序树可得到一个关键字有序的序列。这也说明，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程就是对无序序列进行排序的过程。

2．平衡二叉树

平衡二叉树又称为AVL树，它或者是一棵空树，或者是具有下列性质的二叉树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。若将二叉树节点的平衡因子（Balance Factor，BF）定义为该节点左子树的高度减去其右子树的高度，则平衡二叉树上所有节点平衡因子只可能是-1、0和1。只要树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

分析二叉排序树的查找过程可知，只有在树的形态比较均匀的情况下，查找效率才能达到最佳。因此，希望在构造二叉排序树的过程中，保持其为一棵平衡二叉树。

使二叉排序树保持平衡的基本思想是：每当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡。若是，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。所谓最小不平衡子树，是指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。

1）平衡二叉树上的插入操作

一般情况下，假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a，也就是说，a所指节点是离插入节点最近且平衡因子的绝对值超过1的祖先节点，那么，失去平衡后进行调整的规律可归纳为以下4种情况。

（1）单向右旋平衡处理。由于在a的左子树的左子树上插入新节点，使a的平衡因子由1增至2，导致以*a为根的子树失去平衡，因此需进行一次向右的顺时针旋转操作，如图8-50所示。

图8-50　单向右旋平衡处理示意图

（2）单向左旋平衡处理。由于在a的右子树的右子树上插入新节点，使a的平衡因子由-1变为-2，导致以*a为根的子树失去平衡，因此需进行一次向左的逆时针旋转操作，如图8-51所示。

图8-51　单向左旋平衡处理示意图

（3）先左后右双向旋转平衡处理。由于在a的左子树的右子树上插入新节点，使a的平衡因子由1增至2，导致以*a为根节点的子树失去平衡，因此需进行两次旋转（先左旋后右旋）操作，如图8-52所示。

（4）先右后左双向旋转平衡处理。由于在a的右子树的左子树上插入新节点，使a的平衡因子由-1变为-2，导致以*a为根节点的子树失去平衡，因此需进行两次旋转（先右旋后左旋）操作，如图8-53所示。

2）平衡二叉树上的删除操作

在平衡二叉树上进行删除操作比插入操作更复杂。若待删节点的两个子树都不为空，就用该节点左子树上的中序遍历的最后一个节点（或其右子树上的第一个节点）替换该节点，将情况转化为待删除的节点只有一个子树后再进行处理。当一个节点被删除后，从被删节点到树根的路径上所有节点的平衡因子都需要更新。对于每一个位于该路径上的平衡因子为±2的节点来说，都要进行平衡处理。

图8-52　先左后右双向平衡处理示意图

图8-53　先右后左双向平衡处理示意图

3．B_树

一棵m阶的B_树，或为空树，或为满足下列特性的m叉树。

（1）树中每个节点至多有m棵子树。

（2）若根节点不是叶子节点，则至少有两棵子树。

（3）除根之外的所有非终端节点至少有棵子树。

（4）所有的非终端节点中包含下列数据信息

其中，K_i（i＝1，2，…，n）为关键字，且K_i＜K_i＋1（i＝1，2，…，n－1）；A_i（i＝0，1，…，n）为指向子树根节点的指针，且指针A_i－1所指子树中所有节点的关键字均小于K_i（i＝1，2，…，n），A_n所指子树中所有节点的关键字均大于K_n，为节点中关键字的个数。

（5）所有的叶子节点都出现在同一层次上，并且不带信息（可以看作是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空）。

一棵4阶的B_树如图8-54所示。

图8-54　4阶B_树示意图

由B树的定义可知，在B树上进行查找的过程是：首先在根节点所包含的关键字中查找给定的关键字，若找到则成功返回；否则确定待查找的关键字所在的子树并继续进行查找，直到查找成功或查找失败（指针为空）时为止。

B_树上的插入和删除运算较为复杂，因为要保证运算后节点中关键字的个数大于等于因此涉及到节点的“分裂”及“合并”问题。

在B_树中插入一个关键字时，不是在树中增加一个叶子节点，而是首先在低层的某个非终端节点中添加一个关键字，若该节点中关键字的个数不超过m－1，则完成插入；否则，要进行节点的“分裂”处理。所谓“分裂”，就是把节点中处于中间位置上的关键字取出来插入到其父节点中，并以该关键字为分界线，把原节点分成两个节点。“分裂”过程可能会一直持续到树根。

同样，在B树中删除一个节点时，首先找到关键字所在的节点，若该节点在含有信息的最后一层，且其中关键字的数目不少于则完成删除；否则需进行节点的“合并”运算。若待删除的关键字所在节点不在含有信息的最后一层上，则将该关键字用其在B树中的后继替代，然后再删除其后继元素，即将需要处理的情况统一转化为在含有信息的最后一层再进行删除运算。

8.5.4　哈希表

1．哈希表的定义

前面讨论的几种查找方法，由于记录在存储结构中的相对位置是随机的，所以查找时都要通过一系列的关键字的比较才能确定被查记录在表中的位置。也就是说，这类查找都是以关键字的比较为基础的，而哈希表则通过一个以记录的关键字为自变量的函数（称为哈希函数）得到该记录的存储地址查找，所以在哈希表中进行查找操作时，须用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。

根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。

对于某个哈希函数H和两个关键字K₁和K₂，如果K₁≠K₂，而H（K₁）＝H（K₂），则称为冲突。具有相同哈希函数值的关键字对该哈希函数来说称为同义词。

一般情况下，冲突只能尽可能减少而不能完全避免，因为哈希函数是从关键字集合到地址集合的映像。通常关键字集合比较大，它的元素包含所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。假设关键字集合为某种高级语言的所有标识符，如果一个标识符对应一个存储地址，那就不会发生冲突了，但这是不可能也没有必要的，因为存储空间难以满足，而且任何一个源程序都不会使用这么多标识符。因此在一般情况下，哈希函数是一个压缩映像，冲突是不可避免的。

对哈希表，主要考虑两个问题：一是如何构造哈希函数，二是如何解决冲突。

2．哈希函数的构造方法

常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。

对于哈希函数的构造，应解决好两个主要问题。

（1）哈希函数应是一个压缩映像函数，它应具有较大的压缩性，以节省存储空间。

（2）哈希函数应具有较好的散列性，虽然冲突是不可避免的，但应尽量减少。

要减少冲突，就要设法使哈希函数尽可能均匀地把关键字映射到符号表存储区的各个存储地址上，这样就可以提高查找效率。构造哈希函数时，一般都要对关键字进行计算，且使关键字的所有组成部分都能起作用。

3．处理冲突的方法

解决冲突就是为出现冲突的关键字找到另一个“空”的哈希地址。在处理冲突的过程中，可能得到一个地址序列H_i（i＝1，2，…，k）。常见的处理冲突的方法有如下几种。

（1）开放定址法。

其中，H（key）为哈希函数；m为哈希表表长；d_i为增量序列。

常见的增量序列有如下三种。

①　d_i＝1，2，3，…，m－1，称为线性探测再散列。

②　d_i＝1²，-1²，2²，-2²，3²，…，称为二次探测再散列。

③　d_i＝伪随机序列，称为随机探测再散列。

最简单的产生探测序列的方法是进行线性探测。也就是发生冲突时，顺序地到存储区的下一个单元进行探测。

例如，某记录的关键字为key，哈希函数值H（key）＝j。若在哈希地址j发生了冲突（即此位置已存放了其他记录），则对哈希地址j＋1进行探测，若仍然有冲突，再对地址j＋2进行探测，依此类推，直到将元素存入哈希表。

例如，设关键码序列为47，34，13，12，52，38，33，27，3，哈希表表长为11，哈希函数为Hash（key）=key mod 11，则

使用线性探测法解决冲突构造的哈希表如下：

由哈希函数得到的关键字47，34，13，52，38，33的哈希地址没有冲突，元素直接存入。

对于元素12，其哈希地址为1，但是该地址中已经存入元素34，因此由H₁＝（Hash（12）＋1）mod 11＝2，再试探哈希地址2，但该地址已被元素13占用，发生冲突；再计算H₂＝（Hash（12）＋2）mod 11＝3，发生冲突（地址3被元素47占用）；再计算H₃＝（Hash（12）＋3）mod 11＝4，空闲，因此将元素12存入哈希地址为4的单元。元素27和3也是通过解决冲突后存入的。

线性探测法可能使第i个哈希地址的同义词存入第i＋1个哈希地址，这样本应存入第i＋1个哈希地址的元素变成了第i＋2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“聚集”起来的现象，大大降低了查找效率。为此，可采用二次探测法或随机探测再散列法，以改善“聚集”问题。

那么在查找时就有三种可能：第一种情况是在某一位置上查到了关键字等于key的记录，查找成功；第二种情况是按探测序列查不到关键字为key的记录而又遇到了空单元，这时表明元素不在表中，表示查找失败；第三种情况是查遍全表，未查到指定关键字且符号表存储区已满，需进行溢出处理。

线性探测法思路清楚，算法简单，但也存在以下缺点。

①　溢出处理需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。实现溢出表最简单的结构是顺序表，查找方法可用顺序查找。

②　线性探测法很容易产生聚集现象。所谓聚集现象，就是存入哈希表的记录在表中连成一片。当哈希函数不能把关键字很均匀地散列到哈希表中时，尤其容易产生聚集现象。产生聚集现象后，会增加探测的次数，从而降低了查找效率。

可以采取多种方法减少聚集现象的产生，二次探测再散列和随机探测再散列是两种有效的方法。

（2）链地址法。

链地址法（或拉链法）是一种经常使用且很有效的方法。它在查找表的每一个记录中增加一个链域，链域中存放下一个具有相同哈希函数值的记录的存储地址。利用链域，就把若干个发生冲突的记录链接在一个链表内。当链域的值为NULL时，表示已没有后继记录了。因此，对于发生冲突时的查找和插入操作就跟线性表一样了。

例如，哈希表表长为11、哈希函数为Hash（key）＝key mod 11，对于关键码序列47，34，13，12，52，38，33，27，3，使用链地址法构造的哈希表如图8-55所示。

在图8-55所示的哈希表中进行成功查找的平均查找长度ASL为

（3）再哈希法。

图8-55　用链地址法解决冲突构造哈希表

RH_i均是不同的哈希函数，即在同义词发生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生聚集现象，但增加了计算时间。

（4）建立一个公共溢出区。无论由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入到公共溢出区中。

4．哈希表的查找

在哈希表中进行查找操作时，用与存入元素时相同的哈希函数和冲突处理方法计算得到待查记录的存储地址，然后到相应的存储单元里去获得有关信息再判定查找是否成功。因此，哈希查找的特点如下。

（1）虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需以平均查找长度衡量哈希表的查找效率。

（2）查找过程中需和给定值进行比较的关键字的个数取决于下列三个因素：哈希函数、处理冲突的方法和哈希表的装填因子。

在一般情况下，冲突处理方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子定义为

α标志着哈希表的装满程度。直观地看，α越小，发生冲突的可能性就越小；反之，α越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。

8.6　排序

8.6.1　排序的基本概念

（1）排序。假设含n个记录的文件内容为｛R₁，R₂，…，R_n｝，相应的关键字为｛k₁，k₂，…，k_n｝。经过排序确定一种排列｛R_j1，R_j2，…，R_jn｝，使得它们的关键字满足如下递增（或递减）关系：k_j1≤k_j2≤…≤k_jn（或k_j1≥k_j2≥…≥k_jn）。

若在待排序的一组序列中，R_i和R_j的关键字相同，即k_i＝k_j，且在排序前R_i领先于R_j，那么当排序后，如果R_i和R_j的相对次序保持不变，R_i仍领先于R_j，则称此类排序方法为稳定的。若在排序后的序列中有可能出现R_j领先于R_i的情形，则称此类排序为不稳定的。

（2）内部排序。指待排序记录全部存放在内存中进行排序的过程。

（3）外部排序。指待排序记录的数最很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

在排序过程中需进行下列两种基本操作：比较两个关键字的大小；将记录从一个位置移动到另一个位置。前一种操作对大多数排序方法来说都是必要的，而后一种操作可以通过改变记录的存储方式来避免。

8.6.2　简单排序

1．直接插入排序

直接插入排序是一种简单的排序方法，具体做法是：在插入第i个记录时，R₁，R₂，…，R_i－1已经排好序，这时将R_i的关键字k_i依次与关键字k_i－1，k_i－2等进行比较，从而找到应该插入的位置并将R_i插入，插入位置及其后的记录依次向后移动。

直接插入排序法在最好情况下（待排序列已按关键码有序）每趟排序只需作1次比较且不需要移动元素，因此n个元素排序时的总比较次数为n－1次，总移动次数为0次。在最坏情况下（元素已经逆序排列），进行第j趟排序时，待插入的记录需要同前面的每个记录进行比较，比较次数为j（设置监视哨时，包括与监视哨的一次比较）或j－1（不设监视哨），移动记录的次数为j＋1。因此，总比较次数为总移动次数为

直接插入排序是一种稳定的排序方法，其时间复杂度为Ο（n²）。排序过程中仅需要一个元素的辅助空间，空间复杂度为Ο（1）。

2．冒泡排序

n个记录进行冒泡排序的方法是：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录的关键字，依此类推，直至第n－1个记录和第n个记录的关键字比较过为止。上述过程称作第一趟冒泡排序，其结果是关键字最大的记录被放置到第n个记录的位置上。然后进行第二趟冒泡排序，对前n－1个记录进行同样的操作，其结果是关键字次大的记录被放置到第n－1个记录的位置上。最多进行n－1趟，所有记录有序排列。若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。

冒泡排序法在最好情况下（待排序列已按关键码有序），只须作1趟排序，元素的比较次数为n－1且不需要交换元素，因此总比较次数为n－1次，总交换次数为0次。在最坏情况下（元素已经逆序排列），进行第j趟排序时，最大的j－1个元素已经排好序，其余的n－（j－1）个元素需要进行n－j次比较和n－j次交换，因此总比较次数为总交换次数为

冒泡排序是一种稳定的排序方法，其时间复杂度为Ο（n²）。排序过程中仅需要一个元素的辅助空间用于元素的交换，空间复杂度为Ο（1）。

3．简单选择排序

n个记录进行简单选择排序的基本方法是：通过n－i（1≤i≤n）次关键字之间的比较，从n－i＋1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有记录有序排列。

【算法】简单排序算法。

简单选择排序法在最好情况下（待排序列已按关键码有序），不需要移动元素，因此n个元素排序时的总移动次数为0次。在最坏情况下（元素已经逆序排列），每趟排序移动记录的次数都为3次（两个数组元素交换值），共进行n－1趟排序，总移动次数为3（n－1）。无论在哪种情况下，元素的总比较次数为

简单选择排序是一种不稳定的排序方法，其时间复杂度为Ο（n²）。排序过程中仅需要一个元素的辅助空间用于数组元素值的交换，空间复杂度为Ο（1）。

8.6.3　希尔排序

希尔排序又称“缩小增量排序”，是对直接插入排序方法的改进。

希尔排序的基本思想是：先将整个待排记录序列分割成若干序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。具体做法是：先取一个小于n的整数d₁作为第一个增量，把文件的全部记录分成d₁个组，即将所有距离为d₁倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d₂＜d₁，重复上述分组和排序工作，依此类推，直至所取的增量d_i＝1（d_i＜d_i－1＜…＜d₂＜d₁），即所有记录放在同一组进行直接插入排序为止。

增量序列为5，3，1时，希尔插入排序过程如下所示。

［初始关键字］：

第一趟排序结果：

第二趟排序结果：

第三趟排序结果：

【函数】用希尔排序方法对整型数组进行非递减排序。

希尔排序是一种不稳定的排序方法，据统计分析其时间复杂度为Ο（n^1.3），排序过程中仅需要一个元素的辅助空间用于数组元素值的交换，空间复杂度为Ο（1）。

8.6.4　快速排序

快速排序的基本思想是：通过一趟排序将待排的记录分割为独立的两部分，其中一部分记录的关键字均不大于另一部分记录的关键字，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。

用一维数组存储记录，一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别指向第一个记录和最后一个记录。设枢轴记录（通常是第一个记录）的关键字为pivotkey，则首先从high所指位置起向前搜索，找到第一个关键字小于pivotkey的记录与枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于piotkey的记录与枢轴记录互相交换，重复这两步直至low等于high时为止。

【函数】用快速排序方法对整型数组进行非递减排序。

快速排序是不稳定的排序方法，其平均时间复杂度为Ο（nlogn），空间复杂度为Ο（logn）。若初始记录序列按关键字有序或基本有序时，快速排序则退化为冒泡排序，此时，算法的时间复杂度为Ο（n²）。

8.6.5　堆排序

对于n个元素的关键字序列｛K₁，K₂，…，K_n｝，当且仅当满足下列关系时称其为堆。

若将此序列对应的一维数组（即以一维数组作为序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端节点的值均不小于（或不大于）其左、右孩子节点的值。因此，在一个堆中，堆顶元素（即完全二叉树的根节点）必为序列中的最大元素（或最小元素），并且堆中任一棵子树也都是堆。若堆顶为最小元素，则称为小根堆；若堆顶为最大元素，则称为大根堆。

堆排序的基本思想是：对一组待排序记录的关键字，首先按堆的定义排成一个序列（即建立初始堆），从而输出堆顶的最大关键字（对于大根堆而言），然后将剩余的关键字再调整成新堆，便得到次大的关键字，如此反复，直到全部关键字排成有序序列为止。

初始堆的建立方法是：将待排序的关键字分放到一棵完全二叉树的各个节点中（此时完全二叉树并不一定具备堆的特性），显然，所有的节点K_i都没有子节点，以这样的K_i为根的子树已经是堆，因此初始建堆可从完全二叉树的第个节点K_i开始，通过调整，逐步使以为根的子树满足堆的定义。

在对K_i为根的子树建堆的过程中，可能需要交换K_i和k_2i（或K_2i＋1）的值，如此一来，以K_2i（或K_2i＋1）为根的子树可能不再满足堆的定义，则应继续以K_2i（或K_2i＋1）为根进行调整，如此层层地递推下去，可能会一直延伸到树叶时为止。这种方法就像过筛子一样，把最大的关键字一层一层地筛选出来，最后输出堆顶的最大元素。

【函数】将一个整型数组中的元素调整成大根堆。

调整成新堆：假设输出堆顶元素之后，以堆中最后一个元素替代，那么根节点的左、右子树均为堆，此时只需自上至下进行调整即可。

【函数】用堆排序方法对整型数组进行非递减排序。

序列（55，60，40，10，80，65，15，5，75）建立初始堆的过程如图8-56所示，调整为新堆的过程如图8-57所示。

图8-56　初始堆建立过程示意图

图8-57　调整为新堆的过程示意图

对于记录数较少的文件来说，堆排序的优越性并不明显，但对大量的记录来说堆排序是很有效的。堆排序的整个算法时间是由建立堆和不断调整堆这两部分时间代价构成的。可以证明，堆排序算法的时间复杂度为Ο（n logn）。此外，堆排序只需要一个记录大小的辅助空间。堆排序是一种不稳定的排序方法。

8.6.6　归并排序

所谓“归并”，是将两个或两个以上的有序文件合并成为一个新的有序文件。归并排序是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，得到个长度为2或1的有序文件，再两两归并，如此重复，直至最后形成包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。

两路归并排序的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。

【算法】将分别有序的data1[s..m]和data1[m＋1..n]归并为有序的data2[s..n]。

一趟归并排序的操作是：调用n/2h次Merge算法，将数组data1[0..n-1]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，并存放在data2[0..n-1]中，整个归并排序需进行log₂n趟。可见，归并排序需要辅助空间n个（与待排记录数量相等），时间复杂度为Ο（n logn）。

【算法】递归形式的两路归并。

【算法】对一维数组data1[0..n-1]中的元素进行两路归并排序。

8.6.7　基数排序

基数排序的思想是按组成关键字的各个数位的值进行排序，它是分配排序的一种。该排序方法中把一个关键字K_i看成一个d元组，即

其中，0≤＜r，i＝1～n，j＝1～d。这里的r称为基数。若关键字是十进制，则r＝10；若关键字是八进制的，则r＝8。d是关键字的位数，d值取所有待排序的关键字位数的最大值，其他不足d位的关键字则在前面补零。

在，，…，中，称为最高有效位，称为次高有效位，称为最低有效位。基数排序可以从最高有效位开始，也可以从最低有效位开始。

基数排序的基本思想是：设立r个队列，队列的编号分别为0，1，2，…，r－1。首先按最低有效位的值，把n个关键字分配到这r个队列中；然后从小到大将各队列中关键字再依次收集起来；接着再按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程，直至最高有效位。这样得到了一个从小到大有序的关键字序列。为了减少记录移动的次数，队列可以采用链式存储分配，称为链队列。每个链队列设有两个指针，分别指向队头和队尾。

基数排序是一种稳定的排序方法。对于n个记录，执行一次分配和收集的时间为Ο（n＋r）。如果关键字有d位，则要执行d遍。所以总的运算时间为Ο（d（n＋r））。可见，对于不同的基数r所用的时间是不同的。当r或d较小时，这种排序方法较为节省时间。另外，基数排序适用于链式分配的记录的排序，其要求的附加存储量是r个队列的头、尾指针，所以附加存储量为2r个存储单元。由于待排序记录是以链表方式存储的，相对于顺序分配而言，还增加了n个指针域的空间。

8.6.8　内部排序方法小结

综合比较所讨论的各种排序方法，大致结果如表8-2所示。

表8-2　各种排序方法的性能比较

迄今为止，已有的排序方法远远不止上述几种，人们之所以热衷于研究各种排序方法，不仅是由于排序在计算机运算中所处的重要位置，而且还因为不同的方法各有优缺点，可根据需要运用到不同的场合。选取排序方法时需要考虑的因素有待排序的记录个数n；记录本身的大小；关键字的分布情况；对排序稳定性的要求；语言工具的条件和辅助空间的大小。

依据这些因素，可以得到以下几点结论。

（1）若待排序的记录数目n较小时，可采用插入排序和选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因而当记录本身信息量较大时，用简单选择排序方法较好。

（2）若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序。

（3）当n很大且关键字的位数较少时，采用链式基数排序较好。

（4）若n较大，则应采用时间复杂度为Ο（nlogn）的排序方法，例如快速排序、堆排序或归并排序。快速排序目前被认为是内部排序方法中最好的方法，当待排序的关键字为随机分布时，快速排序的平均运行时间最短；但堆排序只需1个辅助存储空间，并且不会出现在快速排序中可能出现的最坏情况。这两种排序方法都是不稳定的排序方法。若要求排序稳定，可选择归并排序。通常可将归并排序和直接插入排序结合起来使用。先利用直接插入排序求得较长的有序子序列，然后再两两归并。因为直接插入排序是稳定的，所以改进的归并排序是稳定的。

前面讨论的内部排序算法（除基数排序外）都是在一维数组上实现的。当记录本身信息量较大时，为避免耗费大量的时间移动记录，可以采用链表作为存储结构，在这种情况下，希尔排序、快速排序和堆排序就不适用了。

8.6.9　外部排序

外部排序就是对大型文件的排序，待排序的记录存放在外存。在排序的过程中，内存只存储文件的一部分记录，整个排序过程需要进行多次内外存间的数据交换。

常用的外部排序方法是归并排序，一般分为两个阶段：在第一阶段，把文件中的记录分段读入内存，利用某种内部排序方法对记录段进行排序并输出到外存的另一个文件中，在新文件中形成许多有序的记录段，称为归并段；在第二阶段，对第一阶段形成的归并段用某种归并方法进行一趟趟地归并，使文件的有序段逐渐加长，直到将整个文件归并为一个有序段时为止。下面简单介绍常用的多路平衡归并方法。

k路平衡归并是指文件经外部排序的第一个阶段后，已经形成了由若干个初始归并段构成的文件。在这个基础上，反复将每次确定的k个归并段归并为一个有序段，将一个文件上的记录归并到另一个文件上。重复这个过程，直到文件中的所有记录都归并为一个有序段。

设已经得到8个初始归并段，如图8-58所示，其中b_i表示第i个归并段。

图8-58　初始归并段

在树形选择排序中，首先对n个记录的关键字进行两两比较，然后在个较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止，该过程可用一棵有n个叶子节点的完全二叉树表示，如图8-59（a）所示。在树中，每个非终端节点中的关键字等于其左、右孩子节点中较小的关键字，则树根节点中的关键字即为所有叶子中的最小关键字。在输出最小关键字之后，更新最小关键字所在的叶子节点数据，然后从该叶子节点出发，与其左（兄弟）节点的关键字进行比较，修改从叶子节点到根的路径上各节点的关键字，则根节点的关键字即为次小关键字，如图8-59（b）所示。重复该过程，就可完成对所有记录的排序。

图8-59　树形选择排序

在图8-59所示的树中，每个非终端节点记录了其左、右孩子中的“优胜者”，所以称其为“胜者树”。反之，若在双亲节点中记录比较后的失败者，而让胜者去参加更上一层的比较，便可得到一棵“败者树”。这样一来，当优胜者到达父节点时，立刻就知道原先在此比较的失败者并与失败者进行比较，再次记录新的失败者并让优胜者去进行更上一层的比较。在败者树中，每个节点只需和其父节点进行比较，而在胜者树中，向上调整时节点需与兄弟节点比较，那么就需得到兄弟节点的位置信息，因此败者树更易于编程。

为了简便起见，设每个记录为一个整数，败者树用数组ls[]表示，ls[i]的值为败者所在归并段的段号，令ls[1]是树根节点，ls[0]是ls[1]（根）的父节点，ls[0]中存储每次选出的优胜者所在归并段的段号，输出时则取ls[0]指示的归并段的当前记录。例如，图8-60所示的是一棵实现8路归并的败者树，叶子节点的数据来自各个归并段；败者树的根节点ls[1]的父节点ls[0]中存储了优胜者（最小记录）所在的归并段。图8-61所示的是输出一个记录后，重新调整后的败者树。

图8-60　利用败者树找出8路归并段的最小关键字

图8-61　利用败者树找出8路归并段的次小关键字

【算法】利用败者树实现k路平衡归并。

【函数】败者树的调整：从叶子节点到根节点进行调整。