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

数据结构是指数据元素的集合及元素间的相互关系和构造方法。元素之间的相互关系是数据的逻辑结构，数据元素及元素之间关系的存储称为存储结构（或物理结构）。数据结构按照逻辑关系的不同分为线性结构和非线性结构两大类，其中，非线性结构又可分为树结构和图结构。

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

3.1 线性结构

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

3.1.1 线性表

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

1. 线性表的定义

一个线性表是 $n$（$n \ge 0$）个元素的有限序列，通常表示为 $(a_1, a_2, \cdots, a_n)$。非空线性表的特点如下。

（1）存在唯一的一个称作”第一个”的元素。 （2）存在唯一的一个称作”最后一个”的元素。 （3）除第一个元素外，序列中的每个元素均只有一个直接前驱。 （4）除最后一个元素外，序列中的每个元素均只有一个直接后继。

2. 线性表的存储结构

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

1）线性表的顺序存储

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

一般地，以 $\text{LOC}(a_1)$ 表示线性表中第一个元素的存储位置，在顺序存储结构中，第 $i$ 个元素 $a_i$ 的存储位置为：

$\text{LOC}(a_i) = \text{LOC}(a_1) + (i-1) \times L$

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

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

在表长为 $n$ 的线性表中插入新元素时，共有 $n+1$ 个插入位置，在位置1（元素 $a1$ 所在位置）插入新元素，表中原有的 $n$ 个元素都需要移动，在位置 $n+1$（元素 $a_n$ 所在位置之后）插入新元素时不需要移动任何元素，因此，等概率下（即新元素在 $n+1$ 个位置插入的概率相同时）插入一个新元素需要移动的元素个数期望值 $E{\text{insert}}$ 为

$E{\text{insert}} = \sum{i=1}^{n+1} Pi \times (n-i+1) = \frac{1}{n+1} \sum{i=1}^{n+1} (n-i+1) = \frac{n}{2}$

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

在表长为 $n$ 的线性表中删除元素时，共有 $n$ 个可删除的元素，删除元素 $a1$ 时需要移动 $n-1$ 个元素，删除元素 $a_n$ 时不需要移动元素，因此，在等概率下删除元素时需要移动的元素个数期望值 $E{\text{delete}}$ 为

$E{\text{delete}} = \sum{i=1}^{n} qi \times (n-i) = \frac{1}{n} \sum{i=1}^{n} (n-i) = \frac{n-1}{2}$

其中，$q_i$ 表示删除第 $i$ 个元素（即 $a_i$）的概率。

2）线性表的链式存储

线性表的链式存储是用通过指针链接起来的结点来存储数据元素，基本的结点结构包含数据域和指针域。

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

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

结点之间通过指针域构成一个链表，若结点中只有一个指针域，则称为线性链表（或单链表）。

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

typedef struct node{
    int data;              /*结点的数据域，此处假设为整型*/
    struct node *next;     /*结点的指针域*/
}NODE,*LinkList;

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

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

（1）s->next = p->next; （2）p->next = s;

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

同理，在单链表中删除 $p$ 所指结点的后继结点时，步骤如下。

（1）q = p->next; （2）p->next = p->next->next; （3）free(q);

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

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

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

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

LinkList Find_List(LinkList L, int k) /*L 为带头结点单链表的头指针*/
/*在表中查找第 k 个元素，若找到，返回该元素结点的指针；否则，返回空指针 NULL*/
{   LinkList p;  int i;
    i = 1; p = L->next;     /*初始时，令 p 指向第一个元素结点，i 为计数器*/
    while (p && i < k) {    /*顺指针链向后查找，直到 p 指向第 k 个元素结点或 p 为空指针*/
        p = p->next;  i++;
    }
    if (p && i == k) return p;  /*存在第 k 个元素且指针 p 指向该元素结点*/
    return NULL;                /*第 k 个元素不存在，返回空指针*/
} /*Find_List*/

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

int Insert_List (LinkList L, int k, int newElem) /*L 为带头结点单链表的头指针*/
/*将元素 newElem 插入表中的第 k 个元素之前，若成功则返回 0，否则返回-1*/
/*该插入操作等同于将元素 newElem 插入在第 k-1 个元素之后*/
{   LinkList p,s;           /*p、s 为临时指针*/
    if (k == 1) p = L;      /*元素 newElem 要插入到第 1 个元素之前*/
    else  p = Find_List(L,k-1);  /*查找表中的第 k-1 个元素并令 p 指向该元素结点*/
    if (!p) return -1;      /*表中不存在第 k-1 个元素，不满足运算要求*/
    s = (NODE *)malloc(sizeof(NODE));  /*创建新元素的结点空间*/
    if (!s) return -1;
    s->data = newElem;
    s->next = p->next;  p->next = s;   /*将元素 newElem 插入第 k-1 个元素之后*/
    return 0;
} /* Insert_List */

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

int Delete_List (LinkList L, int k) /*L 为带头结点单链表的头指针*/
/*删除表中的第 k 个元素结点，若成功则返回 0，否则返回-1*/
/*删除第 k 个元素相当于令第 k-1 个元素结点的指针域指向第 k+1 个元素所在结点*/
{   LinkList p,q;           /*p、q 为临时指针*/
    if (k == 1) p = L;      /*删除的是第一个元素结点*/
    else  p = Find_List(L,k-1);  /*查找表中的第 k-1 个元素并令 p 指向该元素结点*/
    if (!p||!p->next) return -1;  /*表中不存在第 k 个元素*/
    q = p->next;            /*令 q 指向第 k 个元素结点*/
    p->next = q->next;   free(q);   /*删除结点*/
    return 0;
} /* Delete_List */

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

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

• 双向链表。 每个结点包含两个指针，分别指出当前元素的直接前驱和直接后继。其特点是可以从表中任意的结点出发，从两个方向上遍历链表。
• 循环链表。 在单向链表（或双向链表）的基础上令表尾结点的指针指向链表的第一个结点，构成循环链表。其特点是可以从表中任意结点开始遍历整个链表。
• 静态链表。 借助数组来描述线性表的链式存储结构，用数组元素的下标表示元素所在结点的指针。

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

（1）s->front = p->front; （2）p->front->next = s; //或者表示为 s->front->next = s; （3）s->next = p; （4）p->front = s;

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

（1）p->front->next = p->next; （2）p->next->front = p->front; free(p);

3.1.2 栈和队列

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

1. 栈

1）栈的定义及基本运算

（1）栈的定义。

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

（2）栈的基本运算。

① 初始化栈 InitStack($S$)：创建一个空栈 $S$。
② 判栈空 isEmpty($S$)：当栈 $S$ 为空时返回”真”，否则返回”假”。
③ 入栈 Push($S,x$)：将元素 $x$ 加入栈顶，并更新栈顶指针。
④ 出栈 Pop($S$)：将栈顶元素从栈中删除，并更新栈顶指针。若需要得到栈顶元素的值，可将 Pop($S$) 定义为一个返回栈顶元素值的函数。
⑤ 读栈顶元素 Top($S$)：返回栈顶元素的值，但不修改栈顶指针。

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

2）栈的存储结构

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

（2）栈的链式存储。 用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。

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

2. 队列

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

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

（2）队列的基本运算。

① 初始化队列 InitQueue($Q$)：创建一个空的队列 $Q$。
② 判队空 isEmpty($Q$)：当队列为空时返回”真”，否则返回”假”。
③ 入队 EnQueue($Q,x$)：将元素 $x$ 加入到队列 $Q$ 的队尾，并更新队尾指针。
④ 出队 DelQueue($Q$)：将队头元素从队列 $Q$ 中删除，并更新队头指针。
⑤ 读队头元素 FrontQue($Q$)：返回队头元素的值，但不更新队头指针。

2）队列的存储结构

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

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

设循环队列 $Q$ 的容量为 MAXSIZE，初始时队列为空，且 Q.rear 和 Q.front 都等于0。

元素入队时，修改队尾指针 Q.rear = (Q.rear+1) % MAXSIZE。

元素出队时，修改队头指针 Q.front = (Q.front+1) % MAXSIZE。

根据队列操作的定义，当出队操作导致队列变为空时，则有 Q.rear == Q.front；若入队操作导致队列满，则 Q.rear == Q.front。

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

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

#define MAXQSIZE 100
typedef struct {
    int *base;      /*循环队列的存储空间，假设队列中存放的是整型数*/
    int front;      /*指示队头，称为队头指针*/
    int rear;       /*指示队尾，称为队尾指针*/
}SqQueue;

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

int InitQueue(SqQueue *Q)
/*创建容量为 MAXQSIZE 的空队列，若成功返回 0，否则返回-1*/
{   Q->base = (int *)malloc(MAXQSIZE*sizeof(int));
    if (!Q->base) return -1;
    Q->front = 0; Q->rear = 0; return 0;
}/*InitQueue*/

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

int EnQueue(SqQueue *Q, int e) /*元素 e 入队，若成功返回 0，否则返回-1*/
{   if ((Q->rear+1) % MAXQSIZE == Q->front) return -1;
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXQSIZE;
    return 0;
}/*EnQueue*/

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

int DelQueue(SqQueue *Q, int *e)
/*若队列不空，则删除队头元素，由参数 e 带回其值并返回 0，否则返回-1*/
{   if (Q->rear == Q->front) return -1;
    *e = Q->base[Q->front];
    Q->front = (Q->front + 1) % MAXQSIZE;
    return 0;
}/*DelQueue*/

（2）队列的链式存储。 队列的链式存储也称为链队列。这里为了便于操作，给链队列添加一个头结点，并令头指针指向头结点。因此，队列为空的判定条件是头指针和尾指针的值相同，且均指向头结点。

3）队列的应用

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

3.1.3 串

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

1. 串的定义及基本运算

1）串的定义

串是仅由字符构成的有限序列，是一种线性表。一般记为 $S=’a_1a_2\cdots a_n’$，其中，$S$ 是串名，单引号括起来的字符序列是串值。

2）串的几个基本概念

• 空串： 长度为零的串称为空串，空串不包含任何字符。
• 空格串： 由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符，在计算串长度时要将其计算在内。
• 子串： 由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
• 串相等： 指两个串长度相等且对应序号的字符也相同。
• 串比较： 两个串比较大小时以字符的 ASCII 码值（或其他字符编码集合）作为依据。实质上，比较操作从两个串的第一个字符开始进行，字符的码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。

3）串的基本操作

（1）赋值操作 StrAssign($s,t$)：将串 $s$ 的值赋给串 $t$。
（2）连接操作 Concat($s,t$)：将串 $t$ 接续在串 $s$ 的尾部，形成一个新串。
（3）求串长 StrLength($s$)：返回串 $s$ 的长度。
（4）串比较 StrCompare($s,t$)：比较两个串的大小。返回值-1、0 和 1 分别表示 $st$ 三种情况。
（5）求子串 SubString($s,\text{start},\text{len}$)：返回串 $s$ 中从 start 开始的、长度为 len 的字符序列。

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

2. 串的存储结构

串可以进行顺序存储或链式存储。

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

（2）串的链式存储。 当用链表存储串中的字符时，每个结点中可以存储一个字符，也可以存储多个字符，此时要考虑存储密度问题。在链式存储结构中，结点大小的选择会直接影响对串的处理效率。

3. 串的模式匹配

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

1）朴素的模式匹配算法

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

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

int Index(char S[], char T[], int pos)
/*查找并返回模式串 T 在主串 S 中从 pos 开始的位置（下标），若 T 不是 S 的子串，则返回-1*/
/*模式串 T 和主串 S 第一个字符的下标为 0*/
{   int i, j, slen, tlen;
    i = pos;  j = 0;                  /*i、j 分别用于指出主串字符和模式串字符的位置*/
    slen = strlen(S); tlen = strlen(T);  /*计算主串和模式串的长度*/
    while (i < slen && j < tlen){
        if (S[i] == T[j]) {i++;  j++;}
        else {
            i = i - j + 1;            /*主串字符的位置指针回退*/
            j = 0;
        }
    } /*while*/
    if (j >= tlen)  return i - tlen;
    return -1;
}/* Index */

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

$\sum{i=0}^{n-m} p_i(i+m) = \frac{1}{n-m+1} \sum{i=0}^{n-m} (i+m) = \frac{1}{2}(n+m)$

因此，在最好情况下匹配算法的时间复杂度为 $O(n+m)$。

而在最坏情况下，每一趟不成功的匹配都是模式串的最后一个字符与主串中相应的字符不相等，则主串中新一趟匹配过程的起始位置为 $i-m+2$。设从主串的第 $i$ 个字符开始匹配时成功，

2）改进的模式匹配算法

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

设模式串为 “$p0 \cdots p{m-1}$”，KMP 匹配算法的思想是：当模式串中的字符 $pj$ 与主串中相应的字符 $S_i$ 不相等时，因其前 $j$ 个字符（”$p_0 \cdots p{j-1}$”）已经获得了成功的匹配，所以若模式串中的 “$p0 \cdots p{k-1}$” 与 “$p{j-k} \cdots p{j-1}$” 相同，这时可令 $p_k$ 与 $S_i$ 进行比较，从而使 $i$ 无须回退。

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

next 函数的定义如下：

$$ \text{next}[j] = \begin{cases} -1 & \text{当 } j=0 \text{ 时} \[6pt] \max\ {k \mid 0 < k < j \text{ 且 } “p0 \cdots p{k-1}” = “p{j-k} \cdots p{j-1}”} \[6pt] 0 & \text{其他情况} \end{cases} $$

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

void Get_next(char *p, int next[])
/*求模式串 p 的 next 函数值并存入数组 next*/
{
    int i, j, slen;
    slen = strlen(p); i = 0;
    next[0] = -1; j = -1;
    while(i < slen) {
        if (j == -1 || p[i] == p[j]) {++i; ++j; next[i] = j;}
        else j = next[j];
    }/*while*/
}/*Get_next*/

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

int Index_KMP(char *s, char *p, int pos, int next[])
/*利用模式串 p 的 next 函数，求 p 在主串 s 中从第 pos 个字符开始的位置*/
/*若匹配成功，返回模式串在主串中的位置（下标），否则返回 -1*/
{
    int i, j, slen, plen;
    i = pos - 1;
    j = -1;
    slen = strlen(s); plen = strlen(p);
    while (i < slen && j < plen) {
        if (j == -1 || s[i] == p[j]) {++i; ++j;}
        else j = next[j];
    }/*while*/
    if (j >= plen) return i - plen;
    else return -1;
}/*Index_KMP*/

例如，设主串为 “abacbcabababbcbc”，模式串为 “abababb”，且模式串的 next 函数值如下表所示，则 KMP 算法的匹配过程如图 3-10 所示。其中，$i$ 是主串字符的下标，$j$ 是模式串字符的下标。

第一趟匹配从 $S[0]$ 与 $P[0]$ 开始。由于 $S[0]=P[0]$、$S[1]=P[1]$、$S[2]=P[2]$，所以接下来比较 $S[3]$ 与 $P[3]$，由于 $S[3]$ 与 $P[3]$ 不相等，所以第一趟结束，要进行第二趟匹配，令 $j=\text{next}[3]$（即 $j=1$）。第二趟从 $S[3]$ 与 $P[1]$ 开始比较，仍不相等，因此第二趟结束，要进行第三趟匹配，所以令 $j=\text{next}[1]$（即 $j=0$）。第三趟从 $S[3]$ 与 $P[0]$ 开始比较。由于 $S[3]$ 与 $P[0]$ 不相等，所以令 $j=\text{next}[0]$（即 $j=-1$），此时满足条件 “$j == -1$”，显然不能令 $S[3]$ 与 $P[-1]$ 进行比较，说明主串中从 $i=3$ 开始的子串不可能与模式串相同，因此需要将 $i$ 的值递增后再继续进行匹配过程，即令 $i{++}$、$j{++}$，然后下一趟从 $S[4]$ 与 $P[0]$ 开始比较，继续匹配过程。直到某一趟匹配成功，或者由于在主串中找不到模式串而以失败结束。

3.2 数组、矩阵和广义表

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

3.2.1 数组

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

1）数组的定义

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

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

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

$$ A{m \times n} = \begin{bmatrix} a{11} & a{12} & a{13} & \cdots & a{1n} \ a{21} & a{22} & a{23} & \cdots & a{2n} \ \vdots & \vdots & \vdots & \ddots & \vdots \ a{m1} & a{m2} & a{m3} & \cdots & a_{mn} \end{bmatrix} $$

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

$$ A{m,n} = [[a{11}a{12}\cdots a{1n}], [a{21}a{22}\cdots a{2n}], \cdots, [a{m1}a{m2}\cdots a{mn}]] $$

或列向量形式的线性表：

$$ A{m,n} = [[a{11}a{21}\cdots a{m1}], [a{12}a{22}\cdots a{m2}], \cdots, [a{1n}a{2n}\cdots a{mn}]] $$

数组结构的特点如下。

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

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

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

2）数组的两个基本运算

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

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

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

2. 数组的顺序存储

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

二维数组的存储结构可分为以行为主序和以列为主序的两种方法。

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

$$ Loc(a{ij}) = Loc(a{11}) + ((i-1) \times n + (j-1)) \times L $$

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

$$ Loc(a{ij}) = Loc(a{11}) + ((j-1) \times m + (i-1)) \times L $$

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

3.2.2 矩阵

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

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

1. 特殊矩阵

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

若矩阵 $A{n \times n}$ 中的元素特点为 $a{ij} = a_{ji}$（$1 \leq i, j \leq n$），则称之为 $n$ 阶对称矩阵。

若对称矩阵中的每一对元素仅占用一个存储单元，那么可将 $n^2$ 个元素压缩存储到能存放 $n(n+1)/2$ 个元素的存储空间中。不失一般性，以行为主序存储下三角（包括对角线）中的元素。假设以一维数组 $B[n(n+1)/2]$ 作为 $n$ 阶对称矩阵 $A$ 中元素的存储空间，

则 $B[k]$（$1 \leq k < n(n+1)/2$）与矩阵元素

$a{ij}$（$a{ji}$）之间存在着一一对应的关系，如下所示。

$$ k = \begin{cases} \dfrac{i(i-1)}{2} + j & \text{当 } i \geq j \[8pt] \dfrac{j(j-1)}{2} + i & \text{当 } i < j \end{cases} $$

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

若以行为主序将 $n$ 阶三对角矩阵 $A{n \times n}$ 的非 0 元素 $a{ij}$ 存储在一维数组 $B[k]$（$1 \leq k \leq 3 \times n - 2$）中，则元素位置之间的对应关系为

$$ k = 3 \times (i-1) - 1 + j - i + 1 + 1 = 2i + j - 2 \quad (1 \leq i, j \leq n) $$

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

2. 稀疏矩阵

在一个矩阵中，若非 0 元素的个数远远少于 0 元素的个数，且非 0 元素的分布没有规律，则称之为稀疏矩阵。对于稀疏矩阵，存储非 0 元素时必须同时存储其位置（即行号和列号），所以三元组 $(i, j, a_{ij})$ 可唯一确定矩阵 $A$ 中的一个元素。由此，一个稀疏矩阵可由表示非 0 元素的三元组及其行、列数唯一确定。图 3-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))$。

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

3.2.3 广义表

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

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

广义表一般记为

$$ LS = (\alpha_1, \alpha_2, \cdots, \alpha_n) $$

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

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

1. 广义表的基本操作

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

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

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

2. 广义表的特点

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

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

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

3. 广义表的存储结构

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

3.3 树

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

3.3.1 树与二叉树的定义

1. 树的定义

树是 $n$（$n \geq 0$）个结点的有限集合，当 $n=0$ 时称为空树。在任一非空树（$n>0$）中，有且仅有一个称为根的结点；其余结点可分为 $m$（$m \geq 0$）个互不相交的有限子集 $T_1, T_2, \cdots, T_m$，其中，每个 $T_i$ 又都是一棵树，并且称为根结点的子树。

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

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

2. 树的基本概念

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

（2）结点的度。一个结点的子树的个数记为该结点的度。例如，图 3-16 中，A 的度为 3，B 的度为 2，C 的度为 0，D 的度为 1。

（3）叶子结点。叶子结点也称为终端结点，指度为 0 的结点。例如，图 3-16 中，E、F、C、G 都是叶子结点。

（4）内部结点。度不为 0 的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。例如，图 3-16 中，B、D 都是内部结点。

（5）结点的层次。根为第一层，根的孩子为第二层，依此类推，若某结点在第 $i$ 层，则其孩子结点在第 $i+1$ 层。例如，图 3-16 中，A 在第 1 层，B、C、D 在第 2 层，E、F 和 G 在第 3 层。

（6）树的高度。一棵树的最大层数记为树的高度（或深度）。例如，图 3-16 所示树的高度为 3。

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

3. 二叉树的定义

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

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

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

1. 二叉树的性质

（1）二叉树第 $i$ 层（$i \geq 1$）上最多有 $2^{i-1}$ 个结点。

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

（2）高度为 $k$ 的二叉树最多有 $2^k - 1$ 个结点（$k \geq 1$）。

由性质 1，每一层的结点数都取最大值 $\sum_{i=1}^{k} 2^{i-1} = 2^k - 1$ 即可。

（3）对于任何一棵二叉树，若其终端结点数为 $n_0$，度为 2 的结点数为 $n_2$，则 $n_0 = n_2 + 1$。

（4）具有 $n$ 个结点的完全二叉树的深度为 $\lfloor \log_2 n \rfloor + 1$。

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

在一个高度为 $h$ 的完全二叉树中，除了第 $h$ 层（即最后一层），其余各层都是满的。在第 $h$ 层上的结点必须从左到右依次放置，不能留空。

2. 二叉树的存储结构

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

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

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

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

• 若 $i=1$，则该结点为根结点，无双亲；若 $i>1$，则该结点的双亲结点为 $\lfloor i/2 \rfloor$。
• 若 $2i \leq n$，则该结点的左孩子编号为 $2i$，否则无左孩子。
• 若 $2i+1 \leq n$，则该结点的右孩子编号为 $2i+1$，否则无右孩子。

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

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

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

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

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

typedef struct BiTnode {
    int data;
    struct BiTnode *lchild, *rchild;
} BiTnode, *BiTree;

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

3.3.3 二叉树的遍历

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

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

void PreOrder(BiTree root) {
    if (root != NULL) {
        printf("%d", root->data);    /*访问根结点*/
        PreOrder(root->lchild);      /*先序遍历根结点的左子树*/
        PreOrder(root->rchild);      /*先序遍历根结点的右子树*/
    }/*if*/
}/*PreOrder*/

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

void InOrder(BiTree root) {
    if (root != NULL) {
        InOrder(root->lchild);       /*中序遍历根结点的左子树*/
        printf("%d", root->data);    /*访问根结点*/
        InOrder(root->rchild);       /*中序遍历根结点的右子树*/
    }/*if*/
}/*InOrder*/

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

void PostOrder(BiTree root) {
    if (root != NULL) {
        PostOrder(root->lchild);     /*后序遍历根结点的左子树*/
        PostOrder(root->rchild);     /*后序遍历根结点的右子树*/
        printf("%d", root->data);    /*访问根结点*/
    }/*if*/
}/*PostOrder*/

从根结点出发，3 种方法的遍历路线均途经每个结点三次。若第一次经过结点时进行访问，则是先序遍历；若第二次（或第三次）经过结点时访问结点，则是中序遍历（或后序遍历）。因此，只要将遍历路线上所有在第一次、第二次和第三次经过的结点信息分别输出，即可分别得到该二叉树的先序、中序和后序遍历序列。所以，若去掉 3 种遍历算法中的打印输出语句，则 3 种遍历方法相同。这说明 3 种遍历过程的路线相同。

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

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

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

int InOrderTraverse(BiTree root)    /*二叉树的非递归中序遍历算法*/
{
    BiTree p;
    InitStack(St);                    /*创建一个空栈*/
    p = root;                         /*p 指向树根结点*/
    while (p != NULL || !isEmpty(St)) {
        if (p != NULL) {              /*不是空树*/
            Push(St, p);              /*根结点指针入栈*/
            p = p->lchild;            /*进入根的左子树*/
        }
        else {
            q = Top(St); Pop(St);     /*栈顶元素出栈*/
            printf("%d", q->data);    /*访问根结点*/
            p = q->rchild;            /*进入根的右子树*/
        }/*if*/
    }/*while*/
}/*InOrderTraverse*/

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

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

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

void LevelOrder(BiTree root)         /*二叉树的层序遍历算法*/
{
    BiTree p;
    InitQueue(Q);                     /*创建一个空队列*/
    EnQueue(Q, root);                 /*将根指针加入队列*/
    while (!isEmpty(Q)) {             /*队列不空*/
        DeQueue(Q, p);                /*队头元素出队，并使 p 取队头元素的值*/
        printf("%d", p->data);        /*访问结点*/
        if (p->lchild) EnQueue(p->lchild);
        if (p->rchild) EnQueue(p->rchild);
    }/*while*/
}/*LevelOrder*/

3.3.4 线索二叉树

1. 线索二叉树的定义

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

2. 建立线索二叉树

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

若 $n$ 个结点的二叉树采用二叉链表做存储结构，则链表中必然有 $n+1$ 个空指针域，可以利用这些空指针域来存放结点的前驱和后继信息。为此，需要在结点中增加标志 ltag 和 rtag，以区分孩子指针的指向，如下所示。

其中：

$$ \text{ltag} = \begin{cases} 0 & \text{lchild 域指示结点的左孩子} \ 1 & \text{lchild 域指示结点的直接前驱} \end{cases} $$

$$ \text{rtag} = \begin{cases} 0 & \text{rchild 域指示结点的右孩子} \ 1 & \text{rchild 域指示结点的直接后继} \end{cases} $$

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

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

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

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

（2）若 $\text{pre} \neq \text{NULL}$ 且 pre 所指结点的 rtag 等于 1，则令 $\text{pre->rchild} = p$。

（3）若 $p$ 所指向结点的 ltag 等于 1，则令 $\text{p->lchild} = \text{pre}$。

（4）使 pre 指向刚刚访问过的结点，即令 $\text{pre} = p$。

需要说明的是，用这种方法得到的线索二叉树，其线索并不完整。也就是说，部分结点的前驱或后继信息还需要通过进一步的运算来得到。

3. 访问线索二叉树

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

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

（1）若 $p->\text{rtag} == 1$，则 $p->\text{rchild}$ 即指向其后继结点。

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

3.3.5 最优二叉树

1. 最优二叉树

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

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

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

$$ WPL = \sum_{k=1}^{n} w_k l_k $$

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

哈夫曼树是指权值为 $w_1, w_2, \cdots, w_n$ 的 $n$ 个叶子结点的二叉树中带权路径长度最小的二叉树。

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

（1）根据给定的 $n$ 个权值 ${w_1, w_2, \cdots, w_n}$，构成 $n$ 棵二叉树的集合 $F = {T_1, T_2, \cdots, T_n}$，其中，每棵树 $T_i$ 中只有一个带权为 $w_i$ 的根结点，其左、右子树均空。

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

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

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

由此算法可知，以选中的两棵子树构成新的二叉树，哪个作为左子树，哪个作为右子树，并没有明确。所以，具有 $n$ 个叶子结点的权值为 $w_1, w_2, \cdots, w_n$ 的最优二叉树不唯一，但其 WPL 值是唯一确定的。

当给定了 $n$ 个权值后，构造出的最优二叉树中的结点数目 $m$ 就确定了，即 $m = 2 \times n - 1$，所以可用一维的结构数组来存储最优二叉树。

#define MAXLEAFNUM 50    /*最优二叉树中的最多叶子数目*/
typedef struct node {
    char ch;             /*结点表示的字符，对于非叶子结点，此域不用*/
    int weight;          /*结点的权值*/
    int parent;          /*结点的父结点的下标，为 0 时表示无父结点*/
    int lchild, rchild;  /*结点的左、右孩子结点的下标，为 0 时表示无孩子结点*/
} HuffmanTree[2*MAXLEAFNUM];
typedef char* HuffmanCode[MAXLEAFNUM+1];

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

void createHTree(HuffmanTree HT, char *c, int *w, int n)
/*数组 c[0..n-1] 和 w[0..n-1] 存放了 n 个字符及其概率，构造哈夫曼树 HT*/
{
    int i, s1, s2;
    if (n <= 1) return;
    for(i = 1; i <= n; i++) {    /*根据 n 个权值构造 n 棵只有根结点的二叉树*/
        HT[i].ch = c[i-1];  HT[i].weight = w[i-1];
        HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
    }
    for(; i < 2*n; ++i) {        /*初始化*/
        HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0;
    }
    for(i = n+1; i < 2*n; i++) {
        /*从 HT[1..i-1] 中选择 parent 为 0 且 weight 最小的两棵树，其序号为 s1 和 s2*/
        select(HT, i-1, s1, s2);
        HT[s1].parent = i;       HT[s2].parent = i;
        HT[i].lchild = s1;       HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }/*for*/
}/*createHTree*/

2. 哈夫曼编码

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

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

如果要设计长度不等的编码，必须满足下面的条件：任一字符的编码都不是另一个字符的编码的前缀，这种编码也称为前缀码。对给定的字符集 $D={d_1, d_2, \cdots, d_n}$ 及字符的使用频率 $W={w_1, w_2, \cdots, w_n}$，构造其最优前缀码的方法为：以 $d_1, d_2, \cdots, d_n$ 作为叶子结点，$w_1, w_2, \cdots, w_n$ 作为叶子结点的权值，构造出一棵最优二叉树，然后将树中每个结点的左分支标上 0，右分支标上 1，则每个叶子结点代表的字符的编码就是从根到叶子的路径上的 0、1 组成的串。

例如，设有字符集 ${a,b,c,d,e}$ 及对应的权值集合 ${0.30,0.25,0.15,0.22,0.08}$，按照构造最优二叉树的哈夫曼方法：先取字符 $c$ 和 $e$ 所对应的结点构造一棵二叉树（根结点的权值为 $c$ 和 $e$ 的权值之和），然后与 $d$ 对应的结点分别作为左、右子树构造二叉树，之后选 $a$ 和 $b$ 所对应的结点作为左、右子树构造二叉树，最后得到的最优二叉树（哈夫曼树）如图 3-24 所示。其中，字符 $a$ 的编码为 00，字符 $b$、$c$、$d$、$e$ 的编码分别为 01、100、11、101。

译码时就从树根开始，若编码序列中当前编码为 0，则进入当前结点的左子树；为 1 则进入右子树，到达叶子时一个字符就翻译出来了，然后再从树根开始重复上述过程，直到编码序列结束。例如，若编码序列 101110000100 对应的字符编码采用图 3-24 所示的树进行构造，则可翻译出字符序列 “edaac”。

【函数】根据给定的哈夫曼树，从每个叶子结点出发追溯到树根，逆向找出最优二叉树中叶子结点的编码。

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n)
/*n 个叶子结点在哈夫曼树 HT 中的下标为 1～n，第 i(1≤i≤n) 个叶子的编码存放 HC[i] 中*/
{
    char *cd;  int i, start, c, f;
    if (n <= 1) return;
    cd = (char *)malloc(n*sizeof(char));    cd[n-1] = '\0';
    for(i = 1; i <= n; i++) {
        start = n-1;
        for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
            if (HT[f].lchild == c)  cd[--start] = '0';
            else  cd[--start] = '1';
        HC[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy(HC[i], &cd[start]);
    }/*for*/
    free(cd);
}/*HuffmanCoding*/

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

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

void Decoding(HuffmanTree HT, int n, char *buff)
/*利用具有 n 个叶子结点的最优二叉树（存储在数组 HT 中）进行译码，叶子的下标为 1～n*/
/*buff 指向二进制位串编码序列*/
{
    int p = 2*n - 1;
    while (*buff) {
        if ((*buff) == '0')  p = HT[p].lchild;    /*进入左分支*/
        else p = HT[p].rchild;                    /*进入右分支*/
        if (HT[p].lchild == 0 && HT[p].rchild == 0) {  /*到达一个叶子结点*/
            printf("%c", HT[p].ch);
            p = 2*n - 1;                          /*回到树根*/
        }/*if*/
        buff++;
    }/*while*/
}/*Decoding*/

3.3.6 树和森林

1. 树的存储结构

常用的树的存储有双亲表示法、孩子表示法和孩子兄弟表示法。

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

（2）树的孩子表示法。该表示法在存储结构中用指针指示出结点的每个孩子，为树中每个结点的孩子建立一个链表，即令每个结点的所有孩子结点构成一个用单链表表示的线性表，则 $n$ 个结点的树具有 $n$ 个单链表。将这 $n$ 个单链表的头指针又排成一个线性表。显然，树的孩子表示法便于查找每个结点的子孙，若要找出指定结点的双亲则可能需要遍历所有的链表。

用户也可以将双亲表示法和孩子表示法结合起来，形成树的双亲孩子表示结构。

（3）孩子兄弟表示法，孩子兄弟表示法又称为二叉链表表示法，它在链表的结点中设置两个指针域分别指向该结点的第一个孩子和下一个兄弟。树的孩子兄弟表示法为实现树、森林与二叉树之间的转换提供了可能，充分利用二叉树的有关算法来实现树及森林的操作，对难以把握规律的树和森林有着重要的现实意义。

2. 树和森林的遍历

1）树的遍历

由于树中的每个结点可以有多个子树，因此遍历树的方法有两种，即先根遍历和后根遍历。

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

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

2）森林的遍历

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

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

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

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

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

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

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

（2）二叉树转换为树和森林。一棵二叉树可转换为唯一的树或森林。

3.4 图

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

3.4.1 图的定义与存储

1. 图的定义

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

（1）有向图。若图中每条边都是有方向的，那么顶点之间的关系用 $$ 表示，它说明从 $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)$ 表示的是同一条边。

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

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

$$ e = \frac{1}{2} \sum_{i=1}^{n} D(v_i) $$

（5）路径。在无向图 $G$ 中，从顶点 $vp$ 到顶点 $v_q$ 的路径是指存在一个顶点序列 $v_p, v{i1}, v{i2}, \cdots, v{im}, vq$，使得 $(v_p, v{i1}), (v{i1}, v{i2}), \cdots, (v{im}, v_q)$ 均属于 $E(G)$。若 $G$ 是有向图，其路径也是有方向的，它由 $E(G)$ 中的有向边 $<v_p, v{i1}>, , \cdots, $ 组成。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。若一条路径上除了 $v_p$ 和 $v_q$ 可以相同外，其余顶点均不相同，则称其为简单路径。

（6）子图。若有两个图 $G=(V,E)$ 和 $G’=(V’,E’)$，如果 $V’ \subseteq V$ 且 $E’ \subseteq E$，则称 $G’$ 为 $G$ 的子图。

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

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

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

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

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

2. 图的存储结构

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

1）邻接矩阵表示法

图的邻接矩阵表示法是指用一个矩阵来表示图中顶点之间的关系。对于具有 $n$ 个顶点的图 $G=(V,E)$，其邻接矩阵是一个 $n$ 阶方阵，且满足：

$$ A[i][j] = \begin{cases} 1 & \text{若 } (v_i, v_j) \text{ 或 } \text{ 是 } E \text{ 中的边} \ 0 & \text{若 } (v_i, v_j) \text{ 或 } \text{ 不是 } E \text{ 中的边} \end{cases} $$

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

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

$$ A[i][j] = \begin{cases} W_{ij} & \text{若 } (v_i, v_j) \text{ 或 } \text{ 属于 } E \ \infty & \text{若 } (v_i, v_j) \text{ 或 } \text{ 不属于 } E \end{cases} $$

其中，$W_{ij}$ 是边（弧）上的权值。

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

#define MaxN 30          /*图中顶点数目的最大值*/
typedef int AdjMatrix[MaxN][MaxN];
/* 或 */
typedef double AdjMatrix[MaxN][MaxN];    /*邻接矩阵*/
typedef struct {
    int Vnum;            /*图中的顶点数目*/
    AdjMatrix Arcs;
} Graph;

2）邻接链表表示法

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

表结点包含：adjvex、nextarc、info

表头结点包含：data、firstarc

其含义如下。

• adjvex：指示与顶点 $v_i$ 邻接的顶点的序号。
• nextarc：指示下一条边或弧的结点。
• info：存储与边或弧有关的信息，如权值等。
• data：存储顶点 $v_i$ 的名或其他有关信息。
• firstarc：指示链表中的第一个结点（邻接顶点）。

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

#define MaxN 50          /*图中顶点数目的最大值*/
typedef struct ArcNode {     /*邻接链表的表结点*/
    int adjvex;              /*邻接顶点的顶点序号*/
    double weight;           /*边（弧）上的权值*/
    struct ArcNode *nextarc; /*指向下一个邻接顶点的指针*/
} EdgeNode;
typedef struct VNode {       /*邻接链表的头结点*/
    char data;               /*顶点表示的数据，以一个字符表示*/
    struct ArcNode *firstarc; /*指向第一条依附于该顶点的边或弧的指针*/
} AdjList[MaxN];
typedef struct {
    int Vnum;                /*图中顶点的数目*/
    AdjList Vertices;
} Graph;

显然，对于有 $n$ 个顶点、$e$ 条边的无向图来说，其邻接链表需用 $n$ 个头结点和 $2e$ 个表结点。对于无向图的邻接链表，顶点 $v_i$ 的度恰为第 $i$ 个邻接链表中表结点的数目，而在有向图中，为求顶点的入度，必须扫描逐个邻接表，这是因为第 $i$ 个邻接链表中表结点的数目只是顶点 $v_i$ 的出度。为此，可以建立一个有向图的逆邻接链表。

3.4.2 图的遍历

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

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

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

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

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

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

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

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

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

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

int visited[MaxN] = {0};     /*调用遍历算法前设置所有的顶点都没有被访问过*/
void Dfs(Graph G, int i) {
    EdgeNode *t; int j;
    printf("%d", i);         /*访问序号为 i 的顶点*/
    visited[i] = 1;          /*序号为 i 的顶点已被访问过*/
    t = G.Vertices[i].firstarc;   /*取顶点 i 的第一个邻接顶点*/
    while(t != NULL) {       /*检查所有与顶点 i 相邻接的顶点*/
        j = t->adjvex;       /*顶点 j 为顶点 i 的一个邻接顶点*/
        if (visited[j] == 0) /*若顶点 j 未被访问则从顶点 j 出发进行深度优先搜索*/
            Dfs(G, j);
        t = t->nextarc;      /*取顶点 i 的下一个邻接顶点*/
    }/*while*/
}/*Dfs*/

从函数 Dfs() 之外调用 Dfs 可以访问到所有与起始顶点有路径相通的其他顶点。若图是不连通的，则下一次应从另一个未被访问过的顶点出发，再次调用 Dfs 进行遍历，直到将图中所有的顶点都访问到为止。

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

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

图的广度优先搜索方法为：从图中的某个顶点 $v$ 出发，在访问了 $v$ 之后依次访问 $v$ 的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时还有未被访问的顶点，则另选图中的一个未被访问的顶点作为起点，重复上述过程，直到图中所有的顶点都被访问到为止。

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

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

void Bfs(Graph G)            /*广度优先遍历图 G*/
{
    EdgeNode *t; int i, j, k;
    int visited[MaxN] = {0};   /*调用遍历算法前设置所有的顶点都没有被访问过*/
    InitQueue(Q);              /*创建一个空队列*/
    for(i = 0; i < G.Vnum; i++) {
        if (!visited[i]) {     /*顶点 i 未被访问过*/
            EnQueue(Q, i);
            printf("%d ", i); visited[i] = 1;   /*访问顶点 i 并设置已访问标志*/
            while(!isEmpty(Q)) {                /*若队列不空，则继续取顶点进行广度优先搜索*/
                DeQueue(Q, k);
                t = G.Vertices[k].firstarc;
                for(; t; t = t->nextarc) {      /*检查所有与顶点 k 相邻接的顶点*/
                    j = t->adjvex;              /*顶点 j 是顶点 k 的一个邻接顶点*/
                    if (visited[j] == 0) {      /*若顶点 j 未被访问过，将 j 加入队列*/
                        EnQueue(Q, j);
                        printf("%d ", j);       /*访问序号为 j 的顶点并设置已访问标志*/
                        visited[j] = 1;
                    }
                }/*for*/
            }/*while*/
        }/*if*/
    }/*for i*/
}/*Bfs*/

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

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

3.4.3 生成树及最小生成树

1. 生成树的概念

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

图的生成树不是唯一的。从不同的顶点出发，选择不同的存储方式，用不同的求解方法，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。按深度和广度优先搜索进行遍历将得到不同的生成树，分别称为深度优先生成树和广度优先生成树。

2. 最小生成树

对于连通网来说，边是带权值的，生成树的各边也带权值，因此把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。

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

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

假设 $N=(V,E)$ 是连通网，$TE$ 是 $N$ 上最小生成树中边的集合。算法从顶点集合 $U={u_0}$（$u_0 \in V$）、边的集合 $TE={}$ 开始，重复执行下述操作：在所有 $u \in U$，$v \in V-U$ 的边 $(u,v) \in E$ 中找一条代价最小的边 $(u_0, v_0)$，把这条边并入集合 $TE$，同时将 $v_0$ 并入集合 $U$，直到 $U=V$ 时为止。此时 $TE$ 中必有 $n-1$ 条边，$T=(V,{TE})$ 为 $N$ 的最小生成树。

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

普里姆算法的时间复杂度为 $O(n^2)$，与图中的边数无关，因此该算法适合于求边稠密的网的最小生成树。

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

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

克鲁斯卡尔算法的时间复杂度为 $O(e \log e)$，与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。

3.4.4 拓扑排序和关键路径

1. AOV 网

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

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

2. 拓扑排序及其算法

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

一般情况下，假设 AOV 图代表一个工程计划，则 AOV 网的一个拓扑排序就是一个工程顺利完成的可行方案。对 AOV 网进行拓扑排序的方法如下。

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

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

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

执行的结果会有两种情况：一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。

当有向图中无环时，也可以利用深度优先遍历进行逆拓扑排序。由于图中无环，从图中某点出发进行深度优先遍历时，最先退出 Dfs 函数的顶点即是出度为 0 的顶点，它是拓扑有序序列中最后的一个顶点。由此，按退出 Dfs 函数的先后顺序记录下来的顶点序列即为逆向的拓扑有序序列。

拓扑排序算法的时间复杂度为 $O(n+e)$。

3. AOE 网

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

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

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

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

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

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

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

4. 关键路径和关键活动

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

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

$ve(j)$ 计算方法为

$$ \begin{cases} ve(0) = 0 \[6pt] ve(j) = \max{ve(i) + dut()} & \in T,\ 1 \leq j \leq n-1 \end{cases} $$

其中，$T$ 是所有到达顶点 $j$ 的弧的集合，$dut()$ 是弧 $$ 上的权值，$n$ 是网中的顶点数。

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

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

$$ \begin{cases} vl(n-1) = ve(n-1) \[6pt] vl(i) = \min{vl(j) - dut()} & \in S,\ 1 \leq i \leq n-2 \end{cases} $$

其中，$S$ 是所有从顶点 $i$ 发出的弧的集合。

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

（3）活动 $a_k$ 的最早开始时间 $e(k)$。$e(k)$ 是指弧 $$ 所表示的活动 $a_k$ 最早可开工时间。

$$ e(k) = ve(i) $$

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

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

$$ l(k) = vl(j) - dut() $$

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

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

3.4.5 最短路径

1. 单源点最短路径

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

为了能方便地求出从 $v_0$ 到 $T$ 集合中各顶点最短路径的递增次序，算法实现时引入一个辅助向量 dist。它的分量 dist[i] 表示当前求出的从 $v_0$ 到终点 $v_i$ 的最短路径长度。这个路径长度并不一定是最后的最短路径长度。它的初始状态为：若从 $v_0$ 到 $v_i$ 有弧，则 dist[i] 为弧上的权值；否则，置 dist[i] 为 $\infty$。显然，长度为 $\min{\text{dist}[i] \mid v_i \in V(G)}$ 的路径就是从 $v_0$ 出发的长度最短的一条最短路径。此路径为 $(v_0, u)$，这时顶点 $u$ 应从集合 $T$ 中删除，将其并入集合 $S$。

设图采用邻接矩阵 arcs 存储，那么每次选出一个顶点 $u$ 并使之并入集合 $S$ 后，就根据情况修改 $T$ 集合中各顶点的路径长度 dist。对于 $T$ 集合中的某一个顶点 $i$ 来说，其更短路径可能为 $(v_0, \cdots, v_u, v_i)$。也就是说，若 $\text{dist}[u] + \text{arcs}[u][i] < \text{dist}[i]$，则修改 dist[i]，使 $\text{dist}[i] = \text{dist}[u] + \text{arcs}[u][i]$。

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

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_0, v_j)$ 是否存在（即判别路径 $(v_i, v_0)$ 和 $(v_0, v_j)$ 是否存在），若存在，则比较 $(v_i, v_j)$ 与 $(v_i, v_0, v_j)$ 的路径长度，取较短者为从 $v_i$ 到 $v_j$ 且中间顶点的序号不大于 0 的最短路径。假如在路径上再增加一个顶点 $v_1$，也就是说，如果 $(v_i, \cdots, v_1)$ 和 $(v_1, \cdots, v_j)$ 分别是当前找到的中间顶点的序号不大于 0 的 $v_i$ 到 $v_1$ 以及 $v_1$ 到 $v_j$ 的最短路径，那么 $(v_i, \cdots, v_1, \cdots, v_j)$ 就有可能是从 $v_i$ 到 $v_j$ 且中间顶点的序号不大于 1 的最短路径。将它与已经得到的从 $v_i$ 到 $v_j$ 的中间顶点的序号不大于 0 的最短路径相比较，从中选出中间顶点的序号不大于 1 的最短路径之后，再增加一个顶点 $v_2$ 继续进行试探，依此类推。一般情况下，若 $(v_i, \cdots, v_k)$ 和 $(v_k, \cdots, v_j)$ 分别是从 $v_i$ 到 $v_k$ 和 $v_k$ 到 $v_j$ 的中间顶点的序号不大于 $k-1$ 的最短路径，则将 $(v_i, \cdots, v_k, \cdots, v_j)$ 与已经得到的从 $v_i$ 到 $v_j$ 的中间顶点的序号不大于 $k-1$ 的最短路径相比较，长度较短者便是从 $v_i$ 到 $v_j$ 的中间顶点的序号不大于 $k$ 的最短路径。这样，经过 $n$ 次试探后，最后求得的必是从 $v_i$ 到 $v_j$ 的最短路径。按此方法，可以同时求得各对顶点间的最短路径。

3.5 查找

3.5.1 查找的基本概念

1. 基本概念

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

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

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

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

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

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

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

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

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

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

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

2. 平均查找长度

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

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

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

$$ ASL = \sum_{i=1}^{n} P_i C_i $$

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

3.5.2 静态查找表的查找方法

1. 顺序查找

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

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

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

$$ ASL{ss} = \sum{i=1}^{n} Pi C_i = \frac{1}{n} \sum{i=1}^{n} (n-i+1) = \frac{n+1}{2} $$

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

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

2. 折半查找

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

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

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

那么折半查找的平均查找长度是多少呢？为了方便起见，不妨设结点总数为 $n = 2^h - 1$，则判定树是深度为 $h = \log_2(n+1)$ 的满二叉树。在等概率情况下，折半查找的平均查找长度为

$$ ASL{bs} = \sum{j=1}^{n} Pi C_i = \frac{1}{n} \sum{j=1}^{n} j \times 2^{j-1} = \frac{n+1}{n} \log_2(n+1) - 1 $$

当 $n$ 值较大时，$ASL_{bs} \approx \log_2(n+1) - 1$。

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

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

int Bsearch(int r[], int low, int high, int key)
/*元素存储在数组 r[low..high]，用折半查找的方法在数组 r 中找值为 key 的元素*/
/*若找到返回该元素的下标，否则返回-1*/
{
    int mid;
    while(low <= high) {
        mid = (low+high)/2;
        if (key == r[mid]) return mid;
        else if (key < r[mid]) high = mid-1;
        else low = mid+1;
    }/*while*/
    return -1;
}/*Bsearch*/

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

int Bsearch_rec(int r[], int low, int high, int key)
/*元素存储在数组 r[low..high]，用折半查找的方法在数组 r 中找值为 key 的元素*/
/*若找到返回该元素的下标，否则返回-1*/
{
    int mid;
    if (low <= high) {
        mid = (low+high)/2;
        if (key == r[mid])
            return mid;
        else if (key < r[mid])
            return Bsearch_rec(r, low, mid-1, key);
        else
            return Bsearch_rec(r, mid+1, high, key);
    }/*if*/
    return -1;
}/*Bsearch_rec*/

3. 分块查找

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

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

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

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

$$ ASL_{bs} = L_b + L_w $$

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

分块查找时，可将长度为 $n$ 的表均匀地分成 $b$ 块，每块含有 $s$ 个记录，即有 $b = \lceil \frac{n}{s} \rceil$。在等概率查找的情况下，块内查找的概率为 $\frac{1}{s}$，每块的查找概率为 $\frac{1}{b}$，若用顺序查找确定元素所在的块，则分块查找的平均查找长度为

$$ ASL{bs} = L_b + L_w = \frac{1}{b} \sum{j=1}^{b} j + \frac{1}{s} \sum_{i=1}^{s} i = \frac{b+1}{2} + \frac{s+1}{2} = \frac{1}{2}\left(\frac{n}{s} + s\right) + 1 $$

可见，其平均查找长度不仅与表长 $n$ 有关，而且与每一块的记录数 $s$ 有关。可以证明，当 $s$ 取 $\sqrt{n}$ 时，$ASL_{bs}$ 取最小值 $\sqrt{n} + 1$，此时的查找效率较顺序查找要好得多，但远不及折半查找。

考虑到索引表是一个有序表，因此可以用折半查找确定元素所在的块。

3.5.3 动态查找表

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

1. 二叉排序树

1）二叉排序树的定义

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

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

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

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

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

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

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

typedef struct Tnode {
    int data;                    /*结点的关键字值*/
    struct Tnode *lchild, *rchild; /*指向左、右子树的指针*/
} BSTnode, *BSTree;

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

BSTree SearchBST(BSTree root, int key, BSTree *father)
/*在 root 指向根的二叉排序树中查找键值为 key 的结点*/
/*若找到，返回该结点的指针；否则返回空指针 NULL*/
{
    BSTree p = root; *father = NULL;
    while (p && p->data != key) {
        *father = p;
        if (key < p->data) p = p->lchild;
        else p = p->rchild;
    }/*while*/
    return p;
}/*SearchBST*/

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

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

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

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

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

int InsertBST(BSTree *root, int newkey)
/*在*root 指向根的二叉排序树中插入一个键值为 newkey 的结点，插入成功则返回 0，否则返回-1*/
{
    BSTree s, p, f;
    s = (BSTree)malloc(sizeof(BSTnode));
    if (!s) return -1;
    s->data = newkey; s->lchild = NULL; s->rchild = NULL;
    p = SearchBST(*root, newkey, &f);   /*寻找插入位置*/
    if (p) return -1;                     /*键值为 newkey 的结点已在树中，不再插入*/
    if (!f) *root = s;                    /*若为空树，键值为 newkey 的结点为树根*/
    else if (newkey < f->data) f->lchild = s; /*作为父结点的左孩子插入*/
    else f->rchild = s;                   /*作为父结点的右孩子插入*/
    return 0;
}/*InsertBST*/

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

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

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

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

f->lchild (或 f->rchild) = NULL;

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

f->lchild (或 f->rchild) = p->lchild;

或

f->lchild (或 f->rchild) = p->rchild;

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

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

2. 平衡二叉树

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

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

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

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

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

（1）LL 型单向右旋平衡处理。由于在 a（即结点 A）的左子树的左子树上插入新结点，使 a 的平衡因子由 1 增至 2，导致以 *a 为根的子树失去平衡，因此需进行一次向右的顺时针旋转操作。

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

（3）LR 型先左后右双向旋转平衡处理。由于在 a（即结点 A）的左子树的右子树上插入新结点，使 a 的平衡因子由 1 增至 2，导致以 *a 为根结点的子树失去平衡，因此需进行两次旋转（先左旋后右旋）操作。

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

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

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

3. B_树

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

（1）树中每个结点最多有 $m$ 棵子树。

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

（3）除根之外的所有非终端结点最少有 $\lceil \frac{m}{2} \rceil$ 棵子树。

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

$$ (n, A_0, K_1, A_1, K_2, A_2, \cdots, K_n, A_n) $$

其中，$Ki (i=1,2,\cdots,n)$ 为关键字，且 $K_i < K{i+1} (i=1,2,\cdots,n-1)$；$Ai (i=0,1,\cdots,n)$ 为指向子树根结点的指针，且指针 $A{i-1}$ 所指子树中所有结点的关键字均小于 $K_i (i=1,2,\cdots,n)$，$A_n$ 所指子树中所有结点的关键字均大于 $K_n$，$n$ 为结点中关键字的个数且满足 $(\lceil \frac{m}{2} \rceil - 1 \leq n \leq m-1)$。

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

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

B_树上的插入和删除运算较为复杂，因为要保证运算后结点中关键字的个数大于等于 $\lceil \frac{m}{2} \rceil - 1$，因此涉及结点的”分裂”及”合并”问题。

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

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

3.5.4 哈希表

1. 哈希表的定义

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

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

对于某个哈希函数 $H$ 和两个关键字 $K_1$ 和 $K_2$，如果 $K_1 \neq K_2$，而 $H(K_1) = H(K_2)$，则称为冲突。具有相同哈希函数值的关键字对该哈希函数来说称为同义词。

一般情况下，冲突只能尽可能减少而不能完全避免，因为哈希函数是从关键字集合到地址集合的映像。通常，关键字集合比较大，它的元素包含所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。

2. 哈希函数的构造方法

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

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

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

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

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

3. 处理冲突的方法

解决冲突就是为出现冲突的关键字找到另一个”空”的哈希地址。在处理冲突的过程中，可能得到一个地址序列 $H_i (i=1,2,\cdots,k)$。常见的处理冲突的方法有以下几种。

（1）开放定址法。

$$ H_i = (H(key) + d_i) \bmod m \quad i=1,2,\cdots,k (k \leq m-1) $$

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

常见的增量序列有以下 3 种。

① $d_i = 1, 2, 3, \cdots, m-1$，称为线性探测再散列。

② $d_i = 1^2, -1^2, 2^2, -2^2, 3^2, \cdots, \pm k^2 (k \leq \frac{m}{2})$，称为二次探测再散列。

③ $d_i =$ 伪随机数序列，称为随机探测再散列。

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

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

例如，设关键码序列为”47, 34, 13, 12, 52, 38, 33, 27, 3”，哈希表表长为 11，哈希函数为 $\text{Hash}(key) = key \bmod 11$，则

$$ \begin{aligned} \text{Hash}(47) &= 47 \bmod 11 = 3, \ \text{Hash}(34) &= 34 \bmod 11 = 1, \ \text{Hash}(13) &= 13 \bmod 11 = 2, \ \text{Hash}(12) &= 12 \bmod 11 = 1, \ \text{Hash}(52) &= 52 \bmod 11 = 8, \ \text{Hash}(38) &= 38 \bmod 11 = 5, \ \text{Hash}(33) &= 33 \bmod 11 = 0, \ \text{Hash}(27) &= 27 \bmod 11 = 5, \ \text{Hash}(3) &= 3 \bmod 11 = 3. \end{aligned} $$

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

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

对于元素 12，其哈希地址为 1，但是该地址中已经存入元素 34，因此由 $H_1 = (\text{Hash}(12)+1) \bmod 11 = 2$，再试探哈希地址 2，但该地址已被元素 13 占用，发生冲突；再计算 $H_2 = (\text{Hash}(12)+2) \bmod 11 = 3$，发生冲突（地址 3 被元素 47 占用）；再计算 $H_3 = (\text{Hash}(12)+3) \bmod 11 = 4$，空闲，因此将元素 12 存入哈希地址为 4 的单元。元素 27 和 3 也是通过解决冲突后存入的。

线性探测法可能使第 $i$ 个哈希地址的同义词存入第 $i+1$ 个哈希地址，这样本应存入第 $i+1$ 个哈希地址的元素变成了第 $i+2$ 个哈希地址元素的同义词，……，因此，可能出现很多元素在相邻的哈希地址上”聚集”起来的现象，大大降低了查找效率。

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

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

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

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

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

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

例如，哈希表表长为 11、哈希函数为 $\text{Hash}(key) = key \bmod 11$，对于关键码序列”47, 34, 13, 12, 52, 38, 33, 27, 3”，使用链地址法构造的哈希表如图 3-55 所示。

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

$$ ASL = (6 \times 1 + 3 \times 2) / 9 \approx 1.34 $$

（3）再哈希法。

$$ H_i = RH_i(key) \quad (i=1,2,\cdots,k) $$

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

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

4. 哈希表的查找

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

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

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

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

$$ \alpha = \frac{\text{表中装入的记录数}}{\text{哈希表的长度}} $$

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

3.6 排序

3.6.1 排序的基本概念

假设含 $n$ 个记录的文件内容为 ${R1, R_2, \cdots, R_n}$，相应的关键字为 ${k_1, k_2, \cdots, k_n}$。经过排序确定一种排列 ${R{j1}, R{j2}, \cdots, R{jn}}$，使得它们的关键字满足以下递增（或递减）关系：$k{j1} \leq k{j2} \leq \cdots \leq k{jn}$（或 $k{j1} \geq k{j2} \geq \cdots \geq 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$ 的情形，则称此类排序为不稳定的。

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

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

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

3.6.2 简单排序

1. 直接插入排序

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

【算法】直接插入排序算法。

void Insertsort(int data[], int n)
/*将数组 data[0]~data[n-1]中的 n 个整数按非递减有序的方式进行排列*/
{
    int i, j;
    int tmp;
    for(i = 1; i < n; i++) {
        if (data[i] < data[i-1]) {
            tmp = data[i]; data[i] = data[i-1];
            for(j = i-1; j >= 0 && data[j] > tmp; j--) data[j+1] = data[j];
            data[j+1] = tmp;
        }/*if*/
    }/*for*/
}/*Insertsort*/

直接插入排序法在最好情况下（待排序列已按关键码有序），每趟排序只需作 1 次比较且不需要移动元素，因此 $n$ 个元素排序时的总比较次数为 $n-1$ 次，总移动次数为 0 次。在最坏情况下（元素已经逆序排列），进行第 $i$ 趟排序时，待插入的记录需要同前面的 $i$ 个记录都进行 1 次比较，因此，总比较次数为 $\sum{i=1}^{n-1} i = \frac{n(n-1)}{2}$。排序过程中，第 $i$ 趟排序时移动记录的次数为 $i+1$（包括移进、移出 tmp），总移动次数为 $\sum{i=2}^{n} (i+1) = \frac{(n+3)(n-2)}{2}$。

直接插入排序是一种稳定的排序方法，其时间复杂度为 $O(n^2)$。在排序过程中仅需要一个元素的辅助空间，空间复杂度为 $O(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$ 次交换，因此总比较次数为 $\sum{j=1}^{n-1} (n-j) = \frac{n(n-1)}{2}$，总交换次数为 $\sum{j=1}^{n-1} (n-j) = \frac{n(n-1)}{2}$。

冒泡排序是一种稳定的排序方法，其时间复杂度为 $O(n^2)$。在排序过程中仅需要一个元素的辅助空间用于元素的交换，空间复杂度为 $O(1)$。

3. 简单选择排序

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

【算法】简单选择排序算法。

void SelectSort(int data[], int n)
/*将数组 data 中的 n 个整数按非递减有序的方式进行排列*/
{
    int i, j, k, tmp;
    for(i = 0; i < n-1; i++) {
        k = i;
        for(j = i+1; j < n; j++)    /*找出最小关键字的下标*/
            if (data[j] < data[k]) k = j;
        if (k != i) {
            tmp = data[i]; data[i] = data[k]; data[k] = tmp;
        }/*if*/
    }/*for*/
}/*SelectSort*/

简单选择排序法在最好情况下（待排序列已按关键码有序），不需要移动元素，因此 $n$ 个元素排序时的总移动次数为 0 次。在最坏情况下（元素已经逆序排列），前 $\frac{n}{2}$ 趟中，每趟排序移动记录的次数都为 3 次（两个数组元素交换值），其后不再移动元素，共进行 $n-1$ 趟排序，总移动次数为 $3(n-1)/2$。无论在哪种情况下，元素的总比较次数为 $\sum_{i=1}^{n-1} (n-i) = \frac{n(n-1)}{2}$。

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

3.6.3 希尔排序

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

希尔排序的基本思想是：先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。具体做法是：先取一个小于 $n$ 的整数 $d1$ 作为第一个增量，把文件的全部记录分成 $d_1$ 个组，即将所有距离为 $d_1$ 倍数序号的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量 $d_2 (d_2 < d_1)$，重复上述分组和排序工作，依此类推，直到所取的增量 $d_t = 1 (d_t < d{t-1} < \cdots < d_2 < d_1)$，即所有记录放在同一组进行直接插入排序为止。

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

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

void ShellSort(int data[], int n)
{
    int *delta, k, i, t, dk, j;
    k = n;
    /*从 k=n 开始，重复 k=k/2 运算，直到 k 等于 1，所得 k 值的序列作为增量序列存入 delta*/
    delta = (int *)malloc(sizeof(int)*(n/2));
    i = 0;
    do {
        k = k/2; delta[i++] = k;
    } while(k > 1);
    i = 0;
    while ((dk = delta[i]) > 0) {
        for(k = delta[i]; k < n; ++k)
            if (data[k] < data[k-dk]) {        /*将元素 data[k]插入到有序增量子表中*/
                t = data[k];                    /*备份待插入的元素，空出一个元素位置*/
                for(j = k-dk; j >= 0 && t < data[j]; j -= dk)
                    data[j+dk] = data[j];       /*寻找插入位置的同时元素后移*/
                data[j+dk] = t;                 /*找到插入位置，插入元素*/
            }/*if*/
        ++i;                                    /*取下一个增量值*/
    }/*while*/
}/*ShellSort*/

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

3.6.4 快速排序

快速排序的基本思想是：通过一趟排序将待排的记录划分为独立的两部分，称为前半区和后半区，其中，前半区中记录的关键字均不大于后半区记录的关键字，然后再分别对这两部分记录继续进行快速排序，从而使整个序列有序。

一趟快速排序的过程称为一次划分，具体做法是：附设两个位置指示变量 $i$ 和 $j$，它们的初值分别指向序列的第一个记录和最后一个记录。设枢轴记录（通常是第一个记录）的关键字为 pivot，则首先从 $j$ 所指位置起向前搜索，找到第一个关键字小于 pivot 的记录时将该记录向前移到 $i$ 指示的位置，然后从 $i$ 所指位置起向后搜索，找到第一个关键字大于 pivot 的记录时将该记录向后移到 $j$ 所指位置，重复该过程直至 $i$ 与 $j$ 相等为止。

【函数】快速排序过程中的划分。

int partition(int data[], int low, int high)
/*用 data[low]作为枢轴元素 pivot 进行划分*/
/*使得 data[low..i-1]均不大于 pivot，data[i+1..high]均不小于 pivot*/
{
    int i, j; int pivot;
    pivot = data[low]; i = low; j = high;
    while(i < j) {                          /*从数组的两端交替地向中间扫描*/
        while(i < j && data[j] >= pivot) j--;
        data[i] = data[j];                  /*比枢轴元素小者往前移*/
        while(i < j && data[i] <= pivot) i++;
        data[j] = data[i];                  /*比枢轴元素大者向后移*/
    }
    data[i] = pivot;
    return i;
}

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

void quickSort(int data[], int low, int high)
/*用快速排序方法对数组元素 data[low..high]作非递减排序*/
{
    if (low < high) {
        int loc = partition(data, low, high);   /*进行划分*/
        quickSort(data, low, loc-1);            /*对前半区进行快速排序*/
        quickSort(data, loc+1, high);           /*对后半区进行快速排序*/
    }
}/*quickSort*/

快速排序算法的时间复杂度为 $O(n \log_2 n)$，在所有算法复杂度为此数量级的排序方法中，快速排序被认为是平均性能最好的一种。但是，若初始记录序列按关键字有序或基本有序时，即每次划分都是将序列划分为某一半序列的长度为 0 的情况，此时快速排序的性能退化为时间复杂度是 $O(n^2)$。快速排序是不稳定的排序方法。

3.6.5 堆排序

对于 $n$ 个元素的关键字序列 ${K_1, K_2, \cdots, K_n}$，当且仅当满足下列关系时称其为堆，其中 $2i$ 和 $2i+1$ 应不大于 $n$。

$$ \begin{cases} Ki \leq K{2i} \ Ki \leq K{2i+1} \end{cases} \quad \text{或} \quad \begin{cases} Ki \geq K{2i} \ Ki \geq K{2i+1} \end{cases} $$

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

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

初始堆的建立方法是：将待排序的关键字分放到一棵完全二叉树的各个结点中（此时完全二叉树并不一定具备堆的特性），显然，所有 $i > \lfloor \frac{n}{2} \rfloor$ 的结点 $Ki$ 都没有子结点，以这样的 $K_i$ 为根的子树已经是堆，因此初始建堆可从完全二叉树的第 $i = \lfloor \frac{n}{2} \rfloor$ 个结点 $K_i$ 开始，通过调整，逐步使以 $K{\lfloor \frac{n}{2} \rfloor}$、$K{\lfloor \frac{n}{2} \rfloor - 1}$、$K{\lfloor \frac{n}{2} \rfloor - 2}$、…、$K_2$、$K_1$ 为根的子树满足堆的定义。

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

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

void HeapAdjust(int data[], int s, int m)
/*在 data[s..m]所构成的一个元素序列中，除了 data[s]外，其余元素均满足大顶堆的定义*/
/*调整元素 data[s]的位置，使 data[s..m]成为一个大顶堆*/
{
    int tmp, j;
    tmp = data[s];                          /*备份元素 data[s]，为其找到适当位置后再插入*/
    for(j = 2*s+1; j <= m; j = j*2+1) {    /*沿值较大的孩子结点向下筛选*/
        if (j < m && data[j] < data[j+1]) ++j; /*j 是值较大的元素的下标*/
        if (tmp >= data[j]) break;
        data[s] = data[j]; s = j;            /*用 s 记录待插入元素的位置（下标）*/
    }/*for*/
    data[s] = tmp;                          /*将备份元素插入由 s 所指出的插入位置*/
}/*HeapAdjust*/

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

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

void HeapSort(int data[], int n)            /*数组 data[0..n-1]中的 n 个元素进行堆排序*/
{
    int i;
    int tmp;
    for(i = n/2-1; i >= 0; --i)             /*将 data[0..n-1]调整为大根堆*/
        HeapAdjust(data, i, n-1);
    for(i = n-1; i > 0; --i) {
        tmp = data[0]; data[0] = data[i];
        data[i] = tmp;                      /*堆顶元素 data[0]与序列末的元素 data[i]交换*/
        HeapAdjust(data, 0, i-1);          /*待排元素的个数减 1，将 data[0..i-1]重新调整为大根堆*/
    }/*for*/
}/*HeapSort*/

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

3.6.6 归并排序

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

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

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

void Merge(int data[], int s, int m, int n)
{
    int i, start = s, k = 0;
    int *temp;
    temp = (int *)malloc((n-s+1)*sizeof(int));  /*辅助空间*/
    for(i = m+1; s <= m && i <= n; ++k)         /*将 data[s..m]与 data[m+1..n]归并后存入 temp*/
        if (data[s] < data[i]) temp[k] = data[s++];
        else temp[k] = data[i++];
    for(; s <= m; ++k)                          /*将剩余的 data[s..m]复制到 temp*/
        temp[k] = data[s++];
    for(; i <= n; ++k)                          /*将剩余的 data[i..n]复制到 temp*/
        temp[k] = data[i++];
    for(i=0; i<k; i++)
        data[start++] = temp[i];
    free(temp);
}/*Merge*/

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

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

void MSort(int data[], int s, int t)            /*对 data[s..t]进行归并排序*/
{
    int m;
    if (s < t) {
        m = (s+t)/2;                            /*将 data[s..t]均分为 data[s..m]和 data[m+1..t]*/
        MSort(data, s, m);                      /*递归地对 data[s..m]进行归并排序*/
        MSort(data, m+1, t);                    /*递归地对 data[m+1..t]进行归并排序*/
        Merge(data, s, m, t);                   /*将 data[s..m]和 data[m+1..t]归并为 data[s..t]*/
    }
}/*MSort*/
void MergeSort(int data[], int n)
{
    MSort(data, 0, n-1);
}/*MergeSort*/

3.6.7 基数排序

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

$$ K_i^1, K_i^2, \cdots, K_i^d $$

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

在”$K_i^1, K_i^2, \cdots, K_i^d$”中，$K_i^1$ 称为最高有效位，$K_i^2$ 称为次高有效位，$K_i^d$ 称为最低有效位。基数排序可以从最高有效位开始，也可以从最低有效位开始。

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

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

各种排序方法的性能比较

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

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

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

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

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

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

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

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

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

3.6.8 外部排序

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

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

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

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

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

图 3-60 所示的是一棵实现 8 路归并的败者树。

为了简便起见，设每个记录为一个整数，败者树用数组 ls[] 表示，ls[i] 的值为败者所在归并段的段号，令 ls[1] 是树根结点，ls[0] 是 ls[1]（根）的父结点，ls[0] 中存储每次选出的优胜者所在的归并段的段号，输出时则取 ls[0] 指示的归并段的当前记录。

图 3-61 所示的是输出一个记录后，重新调整后的败者树。

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

#define K 8
#define MINKEY -1        /*比所有关键字都小的一个值*/
#define MAXKEY 10000     /*比所有关键字都大的一个值*/
int b[K+1];
void K_merge(int ls[K])
/*ls[0]~ls[K-1]是败者树的内部结点。b[0]~b[K-1]分别存储 K 个初始归并段的当前记录*/
/*函数 Get_nextRec(i)从第 i 个归并段读取并返回当前记录，若归并段已空，返回 MAXKEY */
{
    int i, q;
    for(i = 0; i < K; i++)
        b[i] = Get_nextRec(i);              /*分别读取 K 个归并段的第一个关键字*/
    b[K] = MINKEY;
    for(i = 0; i < K; ++i) ls[i] = K;       /*创建败者树，设置 ls 中败者的初值*/
    for(i = K-1; i >= 0; --i)               /*依次从 b[K-1]、b[K-2]、…、b[0]出发调整败者树*/
        Adjust(ls, i);
    while (b[ls[0]] != MAXKEY) {           /*ls[0]记录本趟最小关键字所在的段号*/
        q = ls[0];                          /*q 是当前最小关键字所在的归并段*/
        printf("%d", b[q]);                 /*输出最小关键字*/
        b[q] = Get_nextRec(q);
        Adjust(ls, q);                      /*调整败者树，选择新的最小关键字*/
    }/*while*/
}/*K_merge*/

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

void Adjust(int ls[K], int s)               /*败者树存储在 ls[1]~ls[K-1]中，s 为记录所在的归并段号*/
{
    int t, temp;
    t = (s+K)/2;                            /*t 为 b[s]的父结点在败者树中的下标，K 是归并段数*/
    while (t > 0) {                         /*若没有到达树根，则继续*/
        if (b[s] > b[ls[t]]) {              /*与父结点指示的数据进行比较*/
            temp = s; s = ls[t];            /*s 指示胜者，胜者将去参加更上一层的比较*/
            ls[t] = temp;                   /*ls[t]记录败者所在的段号*/
        }/*if*/
        t = t/2;                            /*向树根回退一层*/
    }/*while*/
    ls[0] = s;                              /*ls[0]记录本趟最小关键字所在的段号*/
}/*Adjust*/