数据结构及基本算法

目录

第一章 概论

第一节 引言

第二节 基本概念和常用术语

第三节 算法的描述与分析

第二章 线性表

第一节 线性表定义和基本运算个

一、线性表的逻辑定义

二、线性表的基本运算

第二节 线性表的顺序存储和基本运算的实现

一、线性表的顺序存储

二、顺序表上基本运算的实现

第三节 线性表的链式存储结构

一、单链表

二、单链表的基本运算

三、循环链表

四、双向链表 （补）

第四节 顺序表和链表的比较

一、顺序表的优缺点：

二、链表的优缺点

三、顺序表和链表比较

第三章 栈和队列

第一节 栈

一、栈的定义及其运算

1、栈的定义

2、栈的基本运算

二、栈的顺序存储结构

1、顺序栈

2、栈的顺序实现

3、栈的链式存储结构

4、链栈的基本运算

第二节 栈的应用举例

一、圆括号匹配的检验

二、字符串回文的判断

四、栈与递归

第三节 队列

一、队列的定义及其运算

1.队列的定义

2.队列的基本运算

二、顺序队列的概念

1.顺序队列的概念

2.顺序循环队列

3.循环队的顺序存储的类型定义

4.循环队列基本运算的各算法

三、链队

1.链队的定义：

2.链队的数据类型定义

3.链队的基本运算实现

4.循环链队列

四、栈和队列 的应用实例

1、中缀表达式和后缀表达式

2、中缀表达式到后缀表达式的转换

3.后缀表达式的计算

第四章 多维数组和广义表 (需要重新听几遍)

第一节 多维数组和运算

一、多维数组的定义

二、数组的顺序存储

三、 数组运算举例

第二节 矩阵的压缩存储

一、特殊矩阵

1.对称矩阵

2.三角矩阵

二、稀疏矩阵

1.稀疏矩阵的定义

2.三元组表

第三节 广义表基础

一、广义表的定义

二、广义表的基本运算

三、广义表的存储结构

第五章 树和二叉树

第一节 树的基本概念和术语

一、引言

二、树的定义

三、树的表示法

四、树结构的基本术语

五、树的性质

第二节 二叉树

一、二叉树的定义和性质

二、二叉树的存储结构

第三节 二叉树的运算

一、二叉树的生成

二、二叉树的遍历

三、二叉树应用举例

第四节 线索二叉树

一、线索二叉树的概念

二、二叉树线索化算法

三、二叉线索链表上的运算

第五节 森林和树

一、树的存储结构

二、树、森林与二叉树的转换

三、树和森林的遍历

第六节 哈夫曼树及其应用

一、最优二叉树(哈夫曼树)

二、哈夫曼算法

第六章 图

第一节 图的基本定义和术语

一、图的定义

二、图的有关名词术语

第二节 图的存储结构

一、邻接矩阵表示法

二、邻接表表示法

第三节 图的遍历

一、深度优先搜索遍历

二、广度优先搜索遍历

第四节 图的生成树和最小生成树

一、图的生成树

二、最小生成树

第五节 最短路径

第六节 拓扑排序

第七章 排序

第一节 基本概念

第二节 插入排序

一、直接插入排序

二、希尔排序

第三节 交换排序

一、冒泡排序

二、快速排序

第四节 选择排序

一、直接选择排序

二、堆排序

第五节 归并排序

第六节 分配排序

第七节 内部排序方法的分析比较

第八章 查找

第一节 基本概念

第二节 顺序表的查找

一、顺序查找

二、二分查找法

三、索引顺序查找

四、三种查找方法比较

第三节 树表的查找

一、二叉排序树

二、B树

第四节 散列表查找

一、散列表的概念

二、散列函数的构造方法

三、处理冲突的方法

四、散列表的查找

---

第一章 概论

知识结构：

第一节 引言

数据分为线性结构和非线性结构

定义：数据结构指的是数据元素之间的逻辑结构、存储结构及其数据的抽象运算，即按某种逻辑关系组织起来的一组数据，再按一定的存储表示方式把它们存储在计算机的存储器中，并在这些数据定义一个运算集合，这就叫做一个数据结构。

第二节 基本概念和常用术语

1、数据(data)

是描述客观事物的数、字符以及能输入计算机中并被计算机处理的符号的集合。

2、数据元素(data element)

也称为结点，是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。

3、数据对象(data object)

是具有相同性质的数据元素的集合，是数据的一个子集。

4、数据结构(data structure)

是带有结构的数据元素的集合.包括数据的逻辑结构、数据的存储结构和数据的运算三个方面。结构指的是元素之间的相互关系，即数据的组织形式。

5、数据的逻辑结构

是数据元素之间的逻辑(或抽象)关系，与数据元素的存储结构无关，独立于计算机。数据的逻辑结构分为线性结构和非线性结构两大类。

线性结构：数据元素(结点)之间存在着一对一的关系，且结构中仅有一个开始结点和一个终端结点，其余结点都是仅有一个直接前趋和一个直接后继。如：线性表、栈和队列。

非线性结构：数据元素之间存在着一对多或多对多的关系，即一个结点可能有多个直接前趋和多个直接后缀。该结构包括树形结构、图形结构和网状结构等。

6、数据的存储结构：

是数据在计算机中的存储表示(映像)， 亦称为数据的物理结构。它包括数据元素和关系的表示，是依赖于计算机语言的。数据的存储结构有以下四种：

①顺序存储结构：把逻辑上相邻的结点存储在物理位置上也相邻的连续存储单元里。顺序存储主要应用于线性的数据结构，但非线性的数据结构也可通过某种线性化的方法来实现顺序存储。

②链式存储结构：用一组不一定连续的存储单元存储逻辑上相邻的元素，元素间的逻辑关系是由附加的指针或表示的，它通常是借助于程序设计语言中的指针来描述的。

③索引存储结构：在存储元素信息的同时，还群建立附加的索引表。

④散列存储结构: 根据元素的关键字直接计算出访元素的存储地址。

7、数据的运算：

是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合，最常用的运算有：检索、插入、删除、更新、排序等.

8、数据类型(data type)

是一个值的集合和定义在这个值集上的一组操作的总称

9、抽象数据类型(abstract data type, ADT):

是抽象数据的组织和与之相关的操作。一个ADT可以看作是定义了相关操作运算的一个数学模型。它的特点是将数据定义和数据操作封装在一起实现了信息隐藏。

第三节 算法的描述与分析

一、算法的描述

算法：是对问题求解步骤的一种描述。算法是由若干条指令组成的有穷序列，其中每条指令表示一个或多个操作。算法还必须满足以下五个准则：

(1)输入。算法开始前必须给算法中用到的变量初始化，一个算法的输入可以包含零个或多个数据。

(2)输出。算法至少有一个或多个输出。

(3)有穷性。算法中每一个指令的执行次数都是有限的，而且每一步都在有穷时间内完成，即算法必须在执行有限步后结束。

(4)确定性。算法中每一条指令的含义都必须明确，无二义性。

(5)可性性。算法是可行的，即算法中描述的操作都可以通过有限次的基本运算来实现。

二、算法分析

【例】: 百钱百鸡问题。100个钱买100只鸡，其中公鸡5钱1只，母鸡3钱1只，小鸡1钱3只，求公鸡、母鸡、小鸡各买多少只？

分析： 设公鸡、母鸡、小鸡分别买a、b、c只，则

//函数返回值为满足问题的解数， g[], m[], s[]分别存放不同解的公鸡、母鸡和小鸡数

int ChickenQuestion(int g[], int m[], int s[])
{int a, b, c, k = 0;for (a = 0; a <= 100; a++){for (b = 0; b <= 100; b++){for (c = 0; c <= 100; c++){if ((a + b + c == 100) && (5 * a + 3 * b + c / 3 == 100) && (c % 3 == 0)){g[k] = a;m[k] = b;s[k] = c;//printf("第%d组：公鸡：%d, 母鸡: %d, 小鸡: %d\n", k, a, b, c);k = k + 1;}}}}return k;
}

算法需要执行101 * 101 * 101 约 100 万次。

对上述算法是完全可以改进的。

int ChickenQuestion1(int x[], int y[], int z[])
{int a, b, c, k = 0;for (a = 0; a <= 20; a++){for (b = 0; b <= 33; b++){c = 100 - a - b;if((5*a + 3 * b + c/3==100) && (c % 3==0)){x[k] = a;y[k] = b;z[k] = c;k = k + 1;}}}return k;
}

改进过后的算法需要执行 21 * 34 = 714 次。因此，设计一个好的算法，对提高程序的执行效率至关重要。

1、评介算法的指标

(1) 算法的正确性，是指对于一切合法的输入数据，该算法经过有限时间的执行都能得到正确的结果。

(2)执行算法所耗费的时间，即时间复杂性。

(3)执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性。

(4)算法应易于理解、易于编程，易于高度等，即可读性和可操作性。

2、算法的时间复杂度

时间复杂度： 是某个算法的时间耗费， 它是该算法所求解问题规模n的函数。记作T(n) = O(f(n)).

例: 求下面程序段的算法时间复杂度。

x = 0;
for(i = 2; i < n; i++)
{for(j = 2; j < i -1；j++){x = x + 1;}
}

算法时间复杂度只需要求出它关于n的增长率或阶即可。上述语句x = x + 1执行次数关于n的增长率为n^2,所以该程序段的算法时间复杂度为0(n^2)。

如果一个算法的执行时间是一个与"问题规模"无关的常数，即使是一个较大的常数，该算法的时间复杂度都为常数阶，记作T(n) =O(1)

例： 主= 10000；while(y > 0) y--; 该程序段的时间复杂度就是O(1)

时间复杂度按数量级递增排列依次为： 常数阶O(1)、对数阶O(log₂n )、线性阶O(n)、线性对数阶O(nlog₂n)、平方阶O(n^2)、立方阶O(n^3)、…… k次方阶O(n^k)、指数阶O(2^n).

3、空间复杂度： 是某个算法的空间耗费，它是该算法所求解问题规模n的函数。

4、算法复杂度: 算法的时间复杂度和空间复杂度合称算法复杂度。

第二章 线性表

第一节 线性表定义和基本运算个

一、线性表的逻辑定义

1.线性表的定义

线性表(Linear_List)是一种典型的线性结构，它是由n个数据元素(结点)a1, a2, ..., an组成的有限序列。其中，数据元素的个数n为表的长度。当n为零时称为空表， 非空的线性表通常记为(a1, a2, ... , ai-1, a, ai+1, ..., an)

2、线性表的特征

对于一个非空的线性表：

①有且仅有一处称为开始元素的a1,它没有前趋，仅有一个直接后缑a2;

②有且仅有一个称为终端元素的an, 它没有后继，仅有一个直接前趋；

③其余元素ai(s <= i <=n-1)称为内元素，它们都有且仅有一个直接前趋ai-1和一个直接后继ai + 1。

二、线性表的基本运算

(1)置空表(initList(L))：构造一个空的线性L.

(2)求表长ListLength(L)， 返回线性表L中元素个数，即表长。

(3)取表中第i个元素GetNode(L, i), 若 1 < i <= ListLength(L), 则返回第i个元素ai。

(4)按值查找LocateNode(L, x)， 在表L 查找第一个值为x的元素，并返回该元素在表L中的位置，若表中没有元素的值为x,则返回0值。

(5)插入InsertList(L, i, x), 在表L第i元素之前插入一个值为x的新元素，表L的长度加1。

(6)删除DeleteList(L, i)，删除表L的每i个元素，表的长度减1.

实际遇到的复杂运算可以由有各种基本运算组合实现。

第二节 线性表的顺序存储和基本运算的实现

一、线性表的顺序存储

1.顺序表的概念

线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。

当顺序表中每个结点占用d(d >=1)个存储单元，而且已知起始结点ai的存储地址是Loc(a1), 则可以通过下列公式求得任一结点ai的存储地址Loc(ai): loc(ai) = loc(a1) + (i - 1) *d

线性表的这种机内 表示称为线性表的顺序存储结构，它的特点是，元素在表中的相邻关系，在计算机内也存在着相邻的关系。

2.顺序表数据类型的定义

#define ListSize 100 //表的大小根据实际需要定义，这里假设为100typedef int DataType； //DataType的数据类型根据实际情况而定，这里定义为inttypedef struct{ DataType data[ListSize]; //数组data用来存放表结点int length; //线性表的当前长度(实际元素的个数} SeqList; //定义变量L为顺序表类型的变量

3.顺序表在内存中的表示

SeqList L: //定义变量L为顺序表类型的变量

二、顺序表上基本运算的实现

1、插入运算

线性表的插入运算是指在线性表的第i-1个元素和第i个元素之间插入一个新元素x。算法的基本步骤是: ①将结点ai, ..., an 各后移一位以便腾出第i个位置；②将x置入该空位；③表加1。此外,必须在上述各步之前判断参数i即插入位置是否合法。

算法描述：

void InsertSeqList(SeqList* L, int i, DataType x) {//在顺序表中L中第i个位置之前插入一个新元素xint j;if (i < 1 || i > L->length + 1) {  //判断i值是否合法? 当 i < l 或 i > length +1时，i值不合法printf("position error");return;}if (L->length >= ListSize) {   //判断L是否已满？ 当L->length >= ListSize时， 表示L已满。printf("overflow");return;}for (j = L->length - 1; j >= i - 1; j--) {  //从最后一个元素开始逐一指后移L->data[j + 1] = L->data[j];}L->data[i - 1] = x;   //插入新元素L->length++;          //实际表长加1}

算法分析: (设表的长度为n)

①合法的插入位置共n+1个，即第1个位置到第n+1个位置。

②最坏情况是插入到第1个位置，共需要移动n个元素。故插入算法的最坏情况时间复杂性是o(n).

③最好情况下是插入到第n+1个元素，不需要移动元素。

④在插入位置等概率情况下，平均移动元素的个数为: (n + (n - 1) + (n - 2) + ... + 2 + 1 + 0) / (n + 1) = n/2。故插入算法平均时间复杂性是O(n)。

【例】在长度为n的顺序表的第i(1<=i<=n+1)个位置上插入一个元素，元素的移动次数为( )。

A. n-i+1 B. n-i C. i D. i-1

【答案】 A 【解析】 在长度为n的顺序表上插入， 有n+1个可供插入的位置 ，设插入位置为i,当i=n+1时，不需要移动元素，即移动次数为0； 当i=n时，需将位置n上的元素即表尾元素向后移动一个位置，即移动次数为1; 当i=n-1时，需将n号元素和n-1号元素依次向后移动一个位置，即移动次数为2; ...; 当i=1时， 需将全部元素依次向生移动一个位置，即移动次数为n。显然移动次数为: n - i + 1.

2、删除运算

线性表的删除运算是指将表的第i个结点删去，使其长度为变成n-1。

算法的基本步骤是: ①从ai+1, ... , an依次向前移一个位置； ② 表长减1。

算法描述:

ataType DeleteSeqList(SeqList* L, int i) {  //删除顺序表L中第i个元素int j;//判断i值是否合法? 当 i < l 或 i > length 时, i值不合法。if (i < 1 || i > L->length) {printf("position error");exit(0);   //不合法退出}DataType x = L->data[i - 1];// 保存被删除的元素for (j = i; j <= L->length - 1; j++){L->data[j - 1] = L->data[j];   //元素前移}L->length--;return x;
}

算法分析： (设表的长度为n)

①合法的删除位置共n个，即第一个位置到第n个位置。

②最坏的情况是删除第1个位置上的元素，共需要移动n-1个元素。故插删除算法的最坏情况时简复杂性是O(n)。

③最好情况是删除第n个位置上的元素，不需要移动元素。

④在删除元素的位置等概率情况下，平均移动元素的个数为: ((n-1) + (n-2) + ... + 2 + 1 + 0) /n = (n-1) /2。故删除算法平均时间复杂性是O(n)。

3、顺序表上的其他运算举例

例: 已知一长度为n顺序存储的线性表，试写一算法将该线性表逆置。

分析： 线性表为(a1, a2, ..., an),逆置之后为(an, an-1, ..., a1),实现其算法的基本转想是：先以表长的一半为循环控制次数，将表中最后一个元素同顺数第一个元素交换，将倒数第二个元素同顺数第二个元素交换， ... ,依此类推，直至交换完成为止。

算法描述

SeqList ConVerts(SeqList L)
{DataType x;int i, k;k = L.length / 2;for (i = 0; i < k; i++) {  //元素相互交换x = L.data[i];L.data[i] = L.data[L.length - i - 1];}return L;
}

算法分析: 该算法的时间复杂度为O(n);

例: 试写一算法， 实现在顺序表中找出最大小值和最小值的元素及其所在位置。

分析： 扫描一次顺序表找出最大和最小值的元素。算法中要求带回求得的最大值和最小值元素及其所在位置，可用4个指针变量参数间接得到。

算法描述：

void MaxMin(SeqList L, DataType* max, DataType* min, int* k, int* j)
{int i;*max = L.data[0];*min = L.data[0];*k = *j = 1;    //先假设第一个元素既是最大值， 也是最小值for (i = 1; i < L.length; i++)   //扫描除第一个外的其他元素{if (L.data[i] > *max){*max = L.data[i];*k = i + 1;}else if (L.data[i] < *min){*min = L.data[i];*j = i + 1;}}
}

算法分析:

①最坏情况：线性表元素递减有序排列，每次都和*max及*min比较，共比较2(n-1)次。

②最好情况，线性表元素递增有序排列，每次只和*max比较，共比较(n-1)次。

③该算法的平均比较次数为: (2(n-1) + (n-1)) /2 = 3(n -1)/2.该算法的时间复杂度为O(n)。

第三节 线性表的链式存储结构

一、单链表

1.单链表的概念

结点的结构：

单链表：

链表不同于顺序表，顺序表占用的存储空间必须是连续的，而链表的各结点占用的存储空间之间可以是连续的，也可以是不连续的；但每一个链结点内部占用的存储单元的地址必须是连续的。因此链表中结点的逻辑次序和物理次序不一定相同，通过指针来反映结点之间的逻辑关系。

2.单链表数据类型的定义

#include <stdio.h>
#include <stdlib.h>
#define ListSize 100   //表的大小根据实际需要定义， 这里假设为100
typedef int DataType;   //DataType的数据类型根据实际情况而定，这里定义为inttypedef struct node    //结点类型定义
{DataType data;    //结点数据域struct node* next;    //结点指针域;
} ListNode;typedef ListNode* LinkList;
ListNode* p;             //定义一个指向结点的指针变量
LinkList head;           //定义指向链表的头指针

p->data 若出现在表达式中，它表示由p所指的链结点的数据域内容；否则，表示由p所指的那个结点的数据域(位置)。

p-next若出现在表达式中，它表示由p所指的链结点的指针域内容，也就是p所指的链结点的下一个链结点的存储地址；否则，表示由p所指的那个链结点的指针域(位置)对于表达式中的 p->next-data,表示p所指的链结点的下一个链结点的数据域中的信息。

二、单链表的基本运算

1.单链表的建立

动态建立单链表的常用方法有两种： 一种是头插法，另一种是尾插法。

(1)头插法建表：从一个空表开始，重复读入数据，生成新结点，将读入的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志中止。

算法描述：

LinkList CreateListFirst(int a[])
{LinkList head;ListNode* p;head = NULL;     //置空单链表for (int i = 0; i < 10; i++) {p = (ListNode*)malloc(sizeof(ListNode));   //分配一个类型为ListNode的结点的地址空间，并将其首地址存入指针变量p中。p->data = a[i]; // ch;     //数据域赋值p->next = head;   //指针域赋值head = p;         //头指针指向新结点 }return head;     //返回链表的头指针 
}

(2) 尾插法：将新结点插入在当前链表的表尾上，因此需要增设一个尾指针rear,使其始终指向链表的尾结点。

算法描述：

LinkList CreateListRear(int a[]) {LinkList head, rear;ListNode* p;head = NULL; rear = NULL;   //置空单链表for (int i = 0; i < 10; i++){p = (ListNode*)malloc(sizeof(ListNode));   //申请新结点p->data = a[i];//ch;    //数据域赋值if (head == NULL){head = p;    //新结点*p插入空表}else{rear->next = p;   //新结点*p插入到非空表的表尾结点*rear之后}rear = p;         //表尾指针指向新表尾结点}if (rear != NULL)   //终端结点指针域置空  {rear->next = NULL;}return head;
}

带头结点的单链表：作用是可以简化单链表的算法

在引入头结点之后，尾插法建立单链表的算法可简化为：

LinkList CreateListRearHead(int a[]) //尾插法建立带头结点的单链表算法
{LinkList head = (ListNode*)malloc(sizeof(ListNode)); //申请头结点ListNode* p, * r;r = head;  //尾指针初始指向头结点for (int i = 0; i < 10; i++){p = (ListNode*)malloc(sizeof(ListNode));   //申请新结点p->data = a[i];    //ch;   r->next = p;     //新结点连接到尾结点之后r = p;  //尾指针指向新结点}r->next = NULL;    //终端结点指针置空return head;
}

2.查找运算

(1) 在单链表中要查找第i个结点

算法描述

ListNode* GetNode(LinkList head, int i)
{//head为带头结点的单链表的头指针，i为要查找的结点序号ListNode* p; int j;p = head->next; j = 1;   //使p指向第一个结点， j置1while (p != NULL && j < i)  //顺序针向后查找，直到p指向第i个结点或p为空为止{p = p->next;++j;}if (j == i)  //若查找成功，则返回查找结点的存储地址(位置)， 否则返回NULL{return p;}else{return NULL;}
}

算法分析

①最好情况是查找第1个元素，循环执行0次

②最坏情况是查找第n+1个元素，循环执行n次。

③在等概率情况下，循环执行次数为: (n + (n-1) + (n-2) + ... + 2 + 1 + 0) /(n+1) = n/2.故算法平均时间复杂性是O(n)。

(2)在单链表中查找值为k的结点

算法描述

ListNode* locateNodek(LinkList head, DataType k)
{//head为带着头结点的单链表的头指针， k为要查找的结点值ListNode* p = head->next; //p指向开始结点while (p && p->data != k)   //循环直到p等于NULL或p->data等于k为止    {p = p->next;  //指针指向下一个结点}return p;  //或找到值为k的结点，则p指向该结点， 否则p为NULL
}

算法分析

① 最好情况是第1个元素的值为k, 循环执行0次

②最坏情况是链表中没有值为k的这个元素，循环执行n次。

③在等概率情况下,循环执行次数为: (n + (n-1) + (n-2) + ... + 2 + 1 + 0) /(n+1) = n / 2。 故算法平均时间复杂性是O(n)。

3、插入运算

将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间.

算法思想：先使p指向ai-1的位置，然后生成一个数据域值为x的新结点*s,再进行插入操作.

算法描述

void InsertList(LinkList head, int i, DataType x)
{//在以head为头的指针的带头结点的单链表中第i个结点的位置上，//插入一个数据域值为X的新结点ListNode* p, * s; int j;p = head->next;j = 1;while (p != NULL && j < i - 1)        //使p指向第i-1个结点{p = p->next;++j;}if (p == NULL){printf("ERROR\n");return;}else{s = (ListNode*)malloc(sizeof(ListNode));s->data = x;s->next = p->next;p->next = s;}
}

算法分析: 算法的时间复杂性是O(n)

4、删除运算

将链表的第i个结点从表中删去。

算法思想: 先使p指向ai-1的位置，然后执行p->next指向第i+1个结点,再将第i个结点释放掉.

算法描述

DataType DeleteList(LinkList head, int i)
{//在以head为头指针的带头结点的单链表中删除第i个结点ListNode* p, * s;DataType x;int j;p = head->next;j = 1;while (p != NULL && j < i - 1) //使p指向第i-1结点{p = p->next;j++;}if (p == NULL)    //删除位置错误{printf("位置错误\n");return 0;}else{s = p->next;p->next = s->next;x = s->data;free(s);return x;}
}

算法分析： 算法的时间复杂性是O(n)

5、单链表上的运算举例

例: 试写一个算法，将一个头结点指针为a的带头结点的单链表A分解成两个单链表A和B，其中头结点指针分别为a和b,使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，并保持原来的相对顺序。

分析：遍整个链表A, 当遇到序号为奇数的结点时将其链接到A表上，序号为偶数结点时，将其链接到B表中，一直到遍历结束。

void split(LinkList a, LinkList b)
{//按序号奇偶分解单链表，注意b在调用该算法前是一个带头结点的空链表ListNode* p, * r, * s;p = a->next;       //p指向表头结点p负责扫描整个链表r = a;             //r指向A表的当前结点  s = b;             //s指向B表的当前结占while (p != NULL){r->next = p;   //序号为奇数的结点链接到A表上r = p;         //r总是指向A链表的最后一个结点p = p->next;   //p指向原链表A中的偶数序号的结点if (p){s->next = p;   //序号为偶数的结点链接到B表上s = p;         //s总是指向B链表的最后一个结点p = p->next;   //p指向原链表A中的奇数序号的的结点}}r->next = s->next = NULL;
}

算法分析：

算法要从头到尾扫描整个链表，算法的时间复杂性是O(n)

例: 假设头指针为La和Lb的单链表(带头结点)分别为线性表A和B的存储结构， 两个链表都是按结点数据值递增有序的。试写一个算法，将这两个单链表合并为一个有序链表Lc。

分析： 设立三个指针pa、pb和pc, 其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc则指向Lc表当前的最后一个结点，若pa->data<=pb->data,则将pa所指向的结点链接到pc所指的结点之后，否则将pb所指向的结点链接到pc所指向的结点之后。

算法描述

LinkList MergelinkList(LinkList La, LinkList Lb)
{//归并两个有序链表La和Lb为有序链表LcListNode* pa, * pb, * pc;LinkList Lc;pa = La->next; pb = Lb->next;    //pa和pb分别指向两个链表的开始结点Lc = pc = La;                    //用La的头结点作为Lc头结点while (pa != NULL && pb != NULL){if (pa->data <= pb->data){pc->next = pa;            //将pa所指向的结点链接到pc所指的结点之后。pc = pa;pa = pa->next;}else{pc->next = pb;            //将pb所指向的结点链接到pc所指的结点之后pc = pb;pb = pb->next;}}pc->next = pa != NULL ? pa : pb;    //插入链表剩余部分free(Lb);                   //释放Lb的头结点return Lc;                  //返回合并后的表
}

算法分析： 算法要从头至尾扫描两个链表，算法的时间复杂性是o(n)。

三、循环链表

循环链表与单链表的区别仅仅在于其尾结点的链域值不是NULL,而是一个指向头结点的指针。

循环链表的主要优点是： 从表中任意一结点出发都能通过后移操作而遍历整个循环链表。

在循环表中，将头指针改设为尾指针(rear)后，无论是找头结点、开始结点还是终端点都很方便，它们的存储位置分别是rear->next、rear->next->next、和rear,这样可以简化某些操作。

例： 已知有一个结点数据域为整形的，且按从大到小顺序排列的头结点指针为L的非空单循环表，试写一算法插入一个结点(其数据域为x)至循环链表的适当位置，使之保持链表的有序性。

分析：要解决这个算法问题，首先就是要解决查找插入位置，方法：使用指针q扫描循环链表，循环条件应该是(q->data->x&&q!=L),同时使用指针p记录q的直接前驱，以方便进行插入操作。

算法描述

void insertList(LinkList L, int x)
{//将值为x的新结点插入到有序循环链表中适当的位置ListNode* s, * p, * q;s = (ListNode*)malloc(sizeof(ListNode));     //申请结点存储空间s->data = x; p = L;q = p->next;                               //q指向开始结点while (q->data > x && q != NULL)           //查找插入位置{p = p->next;                          //p指向q的前趋结点q = p->next;                          //q指向当前结点}p->next = s;           //插入*s结点s->next = q;
}

算法分析：

①该算法在最好情况下，也就是插入在第一个结点前面，循环一次也不执行；

②在最坏情况下，即插在最后一个结点之后，当循环需要执行n次;

③该算法的时间复杂度为O(n)。

例：假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为o(n)的算法，删除表中所有数值相同的多元素，并释放结点空间。例如：(7,10,10,21,30,42,42,42,51,70)经算法操作后变为： (7,10,21,30,42,51,70)

void deletelklist(LinkList head)
{ListNode* p, * q;p = head->next;while (p != head)             //使用p扫描整个链表{q = p->next;while (q != head && q->data == p->data)       //发现相等元素，删除并释放该结点。     {p->next = q->next;free(q);q = p->next;}p = p->next;}
}

【解析】题目要求单循环链表中所有数据相同的多余元素，需要设置指针变量p从第一个结点出发，再用指针变量q从p的直接后继结点开始检测与p结点的值相等的结点。若相等，则删除q结点,若不等，则p移向后继。如此重复，直到p==head,即直到所有结点都被p扫描处理完毕为止。

四、双向链表 （补）

双向循环链表示意图

双向链表结点：

双向链表及其结点的类型描述

typedef int DataType;
typedef struct dlnode
{DataType data;struct dlnode* prior, * next;
} DLNode;typedef DLNode* DLinkList;
DLinkList head;  //head为指向双向链表的指针

双链表结构是一种对称结构，既有前向链，又有后向链，这就使得插入操作及删除操作都非常方便。设指针p指向双链表的某一结点，则双链表结构的对称性可用下式来描述:

p->prior->next==p->next->prior==p

在双链表上实现求表长，按序号查找、定位、插入和删除等运算与单链表上的实现方法基本相同，不同的主要是插入和删除操作。

1.删除操作

分析：操作过程如图所示

① p->prior -> next = p ->next;

② p->next->prior=p->prior;

算法描述 

DataType DLDelete(DLNode* p)
{  //删除带头结点的双向链表中指定结点*pDataType x;p->prior->next = p->next;p->next->prior = p->prior;                  //上面两条语句的顺序可以调换， 不影响操作结果x = p->data;free(p);return x;
}

算法分析： 算法的时间复杂度为O(1)

2、插入操作

将值为x的新结点插入到带头结点的双向链表中指定结点*p之前。

分析：操作过程如务所示

算法描述 

void DLInsert(DLinkList p, DataType x)
{  //将值为x的新结点插入到带头结点的双向链表中指定的结点*p之前DLNode* s = (DLNode*)malloc(sizeof(DLNode));   //申请新结点s->data = x;s->prior = p->prior;s->next = p;p->prior->next = s;p->prior = s;
}

算法分析：算法的时间复杂度为O(1)

补充： 在p所指结点的后面链入一个新结点*s,则需要修改四个指针：

① s->prior = p; ② s->next = p->next; ③ p->next->prior=s; ④ p->next = s;

注: ③和④两条语句的顺序不能调换，否则操作结果错误。下面四条语句也可以完成插入操作.

① s->prior = p; ② s->next = p->next; ③ p->next->=s; ④ s->next->prior = s;

【例】假设有一个头结点指针为head的循环双向链表，其结点类型结构包括三个域: prior、data和next。其中data为数据域，next为指针域，指向其后继结点，prior也为指针域，其值为空(NULL), 因此该双向链表其实是一个单循环链表。试写一算法，将其表修改为真正的双向循环链表。

分析： 链表初始状态如下图所示

修改后的链表如下图所示

方法：以p指向头结点开始，循环使用语句 p->next->prior = p; 和 p = p->next; 即可实现题目要求。

算法描述

void trans(DLinkList head)
{DLNode *p;p = head;   //使p指向头结点while(p->next != head)    //依次从左向右，对每个结点的prior赋值{ p->next->prior=p;   //p所指结点的直接后继结点的前趋就是pp=p->next;          //p指针指向下一个结点}head->prior=p;        //head的前趋指向表的终端结点
}

算法分析： 算法要从头到尾扫描两个链表，算法的时间复杂度是o(n)。

第四节 顺序表和链表的比较

一、顺序表的优缺点：

优点：①空间利用率高 ② 可以实现随机存取

缺点：①插入、删除操作中要大量移动结点，时间性能差

②需要事先确定顺序表的大小，估计小了会发生溢出现象，估计大了以将造成空间的浪费。

二、链表的优缺点

优点：①插入、删除操作中无需移动结点，时间性能好。

②因为是动态分配存储空间，所以只要有空闲空间就不会发生溢出现象。

缺点：因为每个结点都要额外设置指针域，因此空间利用率低。

三、顺序表和链表比较

通过上述比较，可以看出算法的时间性能与空间性能往往是一对矛盾，时间性能的改善要以牺牲空间性能为代价，反之亦然。因此在实际中，要根据具体情况来确定采用哪种存储结构。

①对线性表的操作是经常性的查找运算，以顺序表形式存储为宜。因为顺序存储可以随机访问任一结点，访问每个结点的复杂度均为o(1)。而链式存储结构必须从表头开始沿链逐一访问各结点，其时间复杂度为O(n)。②如果经常进行的运算是插入和删除运算，以链式存储结构为宜。因为顺序表作插入和删除操作需要移动大量结点，而链式结构只需要修改相应的指针。③对于线性表结点的存储密度问题，也是选择存储结构的一处重要依据。所谓存储密度就是结点利用率。它的计算公式为

存储密度=(结点数据域所占空间)/(整个结点所占空间)

结点存储密度越大，存储空间的利用率就越高。

【例】 已知链表结点定义如下：

typedef struct node {char data [16];struct node *next;
} LinkStrNode;

如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是( )。

【答案】 0.8 【解析】 存储密度=(结点数据域所占空间) / 整个结点所占空间 = 16 /(16+4)=0.8

【例】与线性表的顺序存储不相符的特性是( )

A. 不便于插入和删除 B. 需连续的存储空间 C. 可随机访问 D. 存储密度大 E. 存储容量固定

F. 需另外开辟空间来保存元素间的关系

【答案】 F 【解析】 线性表的顺序存储是用一片地址连续的空间来存储数据元素，其特点是逻辑上相邻的元素在物理位置上也相邻，数据元素之间逻辑上的先后关系自动隐含在物理位置的相邻之中，因此不需要另外开辟空间来保存元素之间的关系。

第三章 栈和队列

第一节 栈

一、栈的定义及其运算

1、栈的定义

栈(stack)，是限定在表的一端进行插入和删除运算的线性表，通常将插入、删除的一端称为栈顶(top), 另一端称为栈底(bottom)。不含元素的空表称为空栈。

栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(Last in First Out)的线性表，简称为LIFO表。

2、栈的基本运算

(1) 置空栈InitStack(&s): 构造一个空栈S.

(2)判空栈StackEmpty(S): 若栈S为空栈，则返回TRUE,否则返回FALSE。

(3)判栈满StackFull(S): 若栈S为满栈，则返回TRUE,否则返回FALSE。

(4)进栈(以称入栈或插入)：Push(&S, x):将元素x插入S栈的栈顶。

(5)退栈(又称出栈或删除)Pop(&s):若栈为非空，则将S的栈项元素删除，并返回栈顶元素。

(6)取栈顶元素GetTop(S): 若S栈为非空，则返回栈顶元素，但不改变栈的状态。

二、栈的顺序存储结构

1、顺序栈

(1)栈的顺序存储结构称为顺序栈。顺序栈也是用数组实现的，栈底位置是固定不变的，将栈底位置设置在数组的最低端(即下标为0);栈顶位置是随着进栈和退栈操作而变化的，一个整型量top来指示当前栈顶位置，通常称top为栈顶指针。

(2)顺序栈的类型描述

#define StackSize 100      //栈空间的大小应根据实际需要来定义，这里假设为100
typedef char DataType;    //DataType的类型可根据实际情况而定，这里假设为char
typedef struct {                //顺序栈的定义DataType data[StackSize];   //数组data用来存放表结点int top;                    //表示栈顶指针
} SeqStack;                     //栈的数据类型SeqStack s;

【例】 对于一个栈， 给出输入序列abc, 试写出全部可能的输出序列。

【答案】 abc, acb, bac, bca, cba

【分析】根据 堆栈“先进后出”的原则，本题有以下几种情况：

① a 进 a 出 b 进 b 出 c 进 c 出 产生输出序列abc

② a 进 a 出 b 进 c 进 c 出 b 出 产生输出序列acb

③ a 进 b 进 b 出 a 出 c 进 c 出 产生输出序列bac

④ a 进 b 进 b 出 c 进 c 出 a 出 产生输出序列bca

⑤ a 进 b 进 c 进 c 出 b 出 a 出 产生输出序列cba

不可能产生的输出序列cab。

2、栈的顺序实现

(1) 置空栈

void InitStack(SeqStack* S)
{//置空栈，数组元素下标是从0开始，所以栈中元素亦从0开始存储，因此空栈时栈顶指针不能是0，而只能是-1S->top = -1;
}

(2)判栈空

int StackEmpty(SeqStack* S)
{//判栈空return S->top == -1;  //如果栈空则 S->top == -1 的值为1， 返回1， 返之，返回0
}

(3) 判栈满

int StackFull(SeqStack* S)
{//判栈满return S->top == StackSize - 1;//如果栈满则  S->top == StackSize -1 的值为1， 返回1， 反之，返回0
}

(4)进栈(入栈)

void Push(SeqStack* S, DataType x)
{   //进栈(入栈)if (StackFull(S))      //调用判满函数{printf("stack overflow");}else{S->top = S->top + 1;     //栈顶指针加1S->data[S->top] = x;     //将x入栈}
}

(5)退栈(出栈)

DataType Pop(SeqStack* S)
{   // 退栈(出栈)if (StackEmpty(S))      //调用判空函数{printf("Stack underflow");//exit(0);            //出错退出处理return -1;}else{return S->data[S->top--];   //返回栈顶元素， 栈顶指针减1}
}

(6) 取栈顶元素(不改变栈项指针)

DataType GetTop(SeqStack* S)
{   //取栈顶元素if (StackEmpty(S))            //调用判空函数{printf("stack empty");//exit(0);                  //出错退出处理return -1;}else{return S->data[S->top];    //返回栈顶元素，注意： 栈顶指针不动}
}

别外，同时使用多个栈时，多个栈分配在同一顺序存储空间内，即让多个栈共享存储空间，则可以相互进行调节，即节约了空间，又可降低发生溢出的频率。当程序中同时使用两个栈时，可以将两个栈的栈底分别设在顺序存储空间的两端，让两个栈顶各自向中间延伸。

3、栈的链式存储结构

(1)栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除除操作仅限制在表头位置上(栈项)进行，因此不必设置头结点，将单链表的头指针head改为栈项指针top即可。

(2)链栈的类型定义

typedef char DataType;
typedef struct stacknode
{   //链栈的定义DataType data;struct stacknode* next;
} StackNode;            //定义结点typedef StackNode* LinkStack;

4、链栈的基本运算

(1) 判栈空

int StackEmpty(LinkStack top)
{  //判栈空return top == NULL;   //栈空top==NULL的值为1, 返回1,否则返回0
}

(2)进栈(入栈)

LinkStack Push(LinkStack top, DataType x)     //  将x插入栈顶
{//链栈  进栈(入栈)    无需判满StackNode* p;p = (StackNode*)malloc(sizeof(StackNode));  //申请新的结点p->data = x;    p->next = top;    //新结点*p插入栈顶top = p;   //更新栈顶指针topreturn top;
}

(3)退栈(出栈)

Stack Pop(Stack top, DataType* x)
{   //链栈出栈StackNode* p = top;     //保存栈顶指针if (StackEmpty(top))     //栈为空{printf("stack empty");   //出错退出处理exit(0);}else{*x = p->data;   //保存删除结点值，并带回top = p->next;  //栈顶指针指向下一个结点free(p);        //删除P指向的结点return top;     //并返回删除后的栈顶指针}
}

(4) 取栈顶元素

DataType GetTop(Stack top)
{   //取栈顶元素if (StackEmpty(top))             //栈为空{printf("stack empty"); exit(0);                 //出错退出处理}return top->data;      //返回栈顶结点值
}

第二节 栈的应用举例

一、圆括号匹配的检验

对于输入的一个算术表达式字符串，试写一算法判断其中括号是否匹配，若匹配则返回true, 否则返回FALSE。

【分析】利用栈的操作来实现：循环读入表达式中的字符，如遇左括号"("就进栈；循环结束后再判断是否为空，若栈空则说明括号匹配，否则说明不匹配。

【算法描述】

int Expr(char str[]) {
//圆括号检查匹配SeqStack S;DataType  x;InitStack(&S);      //初始化栈S//ch = getchar();//while (ch != '\n')int l = strlen(str);for(int i = 0; i < l; i++){if (str[i] == '('){Push(&S, str[i]);}else{if (str[i] == ')'){if (StackEmpty(&S))    //遇右括号如果栈空，说明不匹配，返回0{return 0;}else{x = Pop(&S);   //遇在括号退栈}}}//ch = getchar();    //读入下一个字符}if (StackEmpty(&S)){return 1;   //最后栈空，说明匹配，}else{return 0;}
}

二、字符串回文的判断

利用顺序栈的基本运算，试设计一个算法，判断一个输入字符串是否具有中心对称(也就是所谓的"回文"， 即正读和反读均相同的字符序)，例如ababbaba和abcba都是中心对称的字符串。

【分析】从中间向两头进行比较，若完全相同，则该字符串是中心对称，否则不是。这就要首先求出字符串串的长度，然后将前一半字符入栈，再利用退栈操作将其与后一半字符进行比较。

【算法描述】

int symmetry(char str[])
{SeqStack S;int j, k, i = 0;InitStack(&S);while (str[i] != '\0')           //求串长度{i++;}for (j = 0; j < i / 2; j++){Push(&S, str[j]);               //前一半字符入栈}k = (i + 1) / 2;                  //后一半字符在串中的起始位置，  特别注意这条命令怎么处理奇偶数个字符的for (j = k; j < i; j++)            //后一半字符与栈中字符比较{if (str[j] != Pop(&S)){return 0;}}return 1;
}

将一个非负的十进制整数N转换成d进制

【分析】将一个非负的十进制整数N转换成d进制的方法： N除以d, 求出每一步所得的余数，然后将所胡余数逆序书写就是十进制整数N对应的d进制数.

例如(3553) 10 = (6741) 8, 其运算过程如下:

【算法描述】

void conversion(int N, int d)
{//将一个非负的十进制数N转换成任意的d进制数SeqStack S;int i;InitStack(&S);while (N){Push(&S, N % d);          //N除以d的余数入栈N = N / d;                //N除以d的商}while (!StackEmpty(&S)){i = Pop(&S);printf("%d", i);          //出栈完成余数倒序输出}
}

四、栈与递归

栈还有一个非常重要的应用就是在程序设计语言中实现递归。一个直接调用自己或间接调用自己的函数，称为递归函数。

递归是程序设计中一个强有力的工具，递归算法有两个关键条件：一是有一个递归公式；二是有终止条件。例如：求n的阶乘可递归地定义为:

2阶的Fibinocci数列：

【例】试分析求阶乘的递归函数

【算法描述】

long int fact(int n)
{int  temp;if (n == 0){return 1;}else{temp = n * fact(n - 1);}return temp;
}void main()               //主函数
{long int n;n=fact(5);            //调用fact()函数求5 printf("5!=%ld", n);
}

【例】已知函数

试写一个递归算法，实现其功能。

【算法描述】

float fu(int n)
{if(n<2){return (n + 1);    //递归终止条件}else{return fu(n/2) * fu(n/4);  //递归公式}
}

或者为:

float fu(int n)
{float f1, f2;if(n < 2){return (n + 1);}else {f1=fu(n/2);f2=fu(n/4);return(f1*f2);}
}

第三节 队列

一、队列的定义及其运算

1.队列的定义

队列(Queue)是一种操作受限的线性表，它只允许在表的一端进行元素插入，而在另一端进行元素删除。允许插入的一端称为队尾(rear),允许删除的一端称为队头(front)。新插入的结点只能添加到队尾，被删除的只能是排在队头的结点，因此，队列又称为先进先出(First in First out) 的线性表，简称FIFO表。

【例】某队列初始为空，若它的输入序列为(a, b, c, d), 它的输出序列应为( ).

A. a, b, c, d B. d, c, b, a C. a, c, b, d D. d, a, c, b

【答案】 A 【解析】 队列的出队序列一定与入队序列完全一样。

2.队列的基本运算

(1)置空队列InitQueue(Q), 构造一个空队列。

(2)判队空QueueEmpty(Q), 若Q为空队列，则返回TRUE, 否则返回FALSE。

(3)入队列En(Jueue(Q, x)), 若队列不满，则将数据x插入到Q的队尾。

(4)出队列DeQueue(0), 若队列不空，则删除队头元素，并返回该元素。

(5) 取队头GetFront(Q), 若队列不空，则返回队头元素。

二、顺序队列的概念

1.顺序队列的概念

队列的顺序存储结构称为顺序队列。队列的顺序存储结构是利用一块连续的存储的单元存放队列中的元素的，设置两个指针front和rear分别指示队头和队尾元素在表中的位置。

【例】 设有一顺序队Q, 容量为5，初始状态时Q, front=Q; rear=0, 画出做完下列操作后队列及其头尾指针的半硫变化情况，若不能入队，请简述其理.

(1) d,e,b入队，(2) d, e 出队 (3) i, j 入队 (4) b出队， (5) n, o, p入队

【解答】 队列及其头尾指针的状态变化情况如图所示

第（5）步操作无法进行，因队列已满，再有元素入队，就会溢出，发生假溢。

2.顺序循环队列

为了解决顺序队列的“假溢”问题采用循环队列。约定循环队列的队头指针指向队头元素在数组 中实际位置的前一个位置，队尾指针指示队尾元素在数组中的实际位置。其次再约定队头指针指示的结点不用于存储队列元素，只起标志作用。这样当队尾指针“绕一圈”后赶上队头指针时视为队满。

【例】设Q是一个有11个元素存储空间的顺序循环队列，初始状态Q，front=Q, rear=0; 写出下列操作后头，尾指针的变化情况，若不能入队，请说明理由。

d，e，b，g，h入队，d，e出队， i，j，k，l，m入队，b出队， n，o，p，q，r入队

注意：p入队以后，队列就满了，不能再入队了，此时队列中的元素个数为10个（数组长度是11）

总结：：队中元素个数：

两种情况合并为： （QueueSize + rear - front) % QueueSize;

【例】设循环队列的容量为50(序号从0到49), 现经过一系列的入队和出队运算后，有front=11, rear=29, rear=11;在这两种情况下，循环队列中的元素个数分别是（ ）和（ ）

【解析】当front=11, rear=29时，循环队列中的元素个数=rear-front=29-11; 当front=29, rear=11时，循环队列中的元素个数50-(front-rear)=50+rear-front=50+11-29=32。

【答案】18 32

3.循环队的顺序存储的类型定义

#define QueueSize 100
typedef char DataType;    //假设数据为字符型
typedef struct
{DataType data[QueueSize];int front, rear;
} CirQueue;

4.循环队列基本运算的各算法

(1) 置空队列

void InitQueue(CirQueue* Q)
{Q->front = Q->rear = 0;
}

(2)判队空

int QueueEmpty(CirQueue* Q)
{return Q->rear == Q->front;
}

(3)判队满

int QueueFull(CirQueue* Q)
{return (Q->rear + 1) % QueueSize == Q->front;
}

(4)入队列

void EnQueue(CirQueue* Q, DataType x)
{//插入元素x为队列Q的新的队尾元素if (QueueFull(Q)){printf("Queue overflow");}else{Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % QueueSize;    //循环意义下的加1}
}

(5)取队头元素

DataType GetFront(CirQueue* Q)
{//获取Q的队头元素值if (QueueEmpty(Q)){printf("Queue empty");exit(0);}else{return Q->data[Q->front];}
}

(6)出队列

DataType DeQueue(CirQueue* Q)
{//删除Q的队头元素， 并返回其值DataType x;if (QueueEmpty(Q)){printf("Queue empty");}else{x = Q->data[Q->front];     //保存待删除元素值Q->front = (Q->front + 1) % QueueSize;       //头指针加1return x;                  //返回删除元素值}
}

三、链队

1.链队的定义：

队列的链式存储结构称为链队列。这是一种限制在表头删除和表尾插入操作的单链表。

2.链队的数据类型定义

typedef struct qNode
{DataType data;struct qNode* next;
} QueueNode;typedef struct {QueueNode* front;    //队头指针QueueNode* rear;     //队尾指针
} LinkQueue;LinkQueue Q;

3.链队的基本运算实现

(1)构造空队列

//构造空队列
void InitLinkQueue(LinkQueue* Q)
{Q->front = (QueueNode*)malloc(sizeof(QueueNode));   //申请头结点Q->rear = Q->front;                                 //尾指针也指向头结点Q->rear->next = NULL;
}

(2)判队空

int LinkQueueEmpty(LinkQueue* Q)
{return Q->rear == Q->front;   //头尾指针相等队列为空
}

(3)入队列

void EnLinkQueue(LinkQueue* Q, DataType x)
{//将元素x插入链队列尾部QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode)); //申请新结点p->data = x;p->next = NULL;Q->rear->next = p;  //*p链到原队尾结点之后Q->rear = p;     //队尾指针指向新的队尾结点
}

(4)取队头元素

DataType GetLinkQueueFront(LinkQueue* Q)
{  //取链队列的队头元素值if (LinkQueueEmpty(Q))     //判队空{printf("Queue underflow");exit(0);    //出错退出处理}else{return Q->front->next->data;  //返回原队头元素值}
}

(5)出队列

链队列的出队操作有两种不同情况要分别考虑。

①当队列的长度大于1时，则出队操作只面修改头结点的指针域即可，尾指针不变，类似于单链表删除首结点，操作步骤：

s=Q->front->next;
Q->front->next=s->next;
x=s->data;
free(s);        //确定这样没有错吗？ 不用 s->next = NULL; 吗？ 野指针不会带偏吗？
return x;                           //释放队头结点，并返回其值

②若队列长度等1， 则出队时不仅要修改头结点指针域，而且还需要修改尾指针。

s=Q->front->next;
Q->front->next = NULL;    //修改头指针
Q->rear=Q->front;   //修改尾指针
x = s->data;
free(s);
return x;            //释放队头结点，并返回其值

为了方便，直接删除头结点，将原队头结点当头结点使，这样算法就简单了。

链队列的出队算法描述：

DataTypeDeQueue(LinkQueue *Q)
{//删除链队列的头结点，并返回头结点的元素值QueueNode *P;if(QueueEmpty(Q)){printf("Queue underflow");exit(0);    //出错退出处理}else{p = Q->front;   //p指向头结点Q->front=Q->front->next;    //头指针指向原队头结点free(p);return (Q->front->data);   //返回原队头结点的数据值==}
}

【例】 算法f31的功能是清空带头结点的链队列Q,请在空缺处填入合适的内容，使其成为一个完整的算法。

typedef struct node
{DataType data;struct node *next;
}QueueNode;
typedef struct
{QueueNode *front;   //队头指针QueueNode *rear;    //队尾指针
} LinkQueue;
​
void f31(LinkQueue *Q)
{QueueNode *p, *s;p(                        );while(p!=NULL){s=p;p=p->next;free(s);}(                            )=NULL;Q->rear=(                                        ); 
}

【解析】 算法f31的功能是清空带头结点的链队列Q, 就是要删除除了头结点以外的所有结点，指针p负责扫描整个队列，所以第(1)空应该填Q->front->next。通过执行while循环，删除了除了头结点以外的所有结点，最后要将头结点的指针域填上NULL,队尾指针指向头结占。所以，第(2)空应该填上Q->front->next; 第(3)空填Q->front;

4.循环链队列

循环链队列的类型定义

typedef struct queuenode
{DataType data;struct queuenode *next;
} QueueNode;
QueueNode *rear;

(1) 初始化空队列

QueueNode *InitQueue(QueueNode *rear)
{rear=(QueueNode *)malloc(sizeof(QueueNode));rear->next=rear;return rear;
}

(2)入队列

void EnQueue(QueueNode *rear, DataType x)
{QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));  //申请新结点s->data = x;s->next = rear->next;rear->next = s;rear = s;
}

(3)出队列

DataType DelQueue(QueueNode *rear)
{QueueNode *s, *t;DataType x;if(rear->next == rear)           //判队空{printf("Queue Empty")exit(0);}else{s=rear->next;     //s指向头结点rear->next=s->next; //删除头节点t=s->next;          //t指向原队头结点x=t->data;          //保存原头结点数据free(s);            //释放被删除的原头结点return x;           //返回出队结点的数据}
}

四、栈和队列 的应用实例

1、中缀表达式和后缀表达式

中缀表达式: 9-(2+4*7)/5+3 ---- 适合人的习惯

后缀表达式: 9247*+5/-3 ----- 适合计算机操作的特点

后缀表达式特点:

(1) 从左向右数字的顺序与中缀表达式完全相同。

(2) 从左向右运算符的顺序与中缀表达式的计算顺序完全相同;

(3) 后缀表达式没有括号，运算规则简单，方法见后面讲解。

2、中缀表达式到后缀表达式的转换

中缀表达式转换为后缀表达式的算法思想:

顺序扫描中缀算术表达式

(1) 当读到数字时，直接将其送至输出队列中;

(2)当读到运算符时，将栈中所有优先级高于或等于该运算符的运算符弹出，送到输出队列中，再将当前运算符入栈

(3) 当读入左括号时，即入栈；

(4) 当读到右括号时，将靠近栈项的第一个左括号上面的运算符全部依次弹出，送到输出队列中，再删除栈中的左括号。

【算法描述】

int Priority(DataType op)
{//运算符优先级别判断函数switch(op){case '(':case '#': return 0;case '-':case '+': return 1;case '/': case '*': return 2;}return -1;
}void CTPostExp(CirQueue *Q)
{SeqStack S;char c, t;InitStack(&S);Push(&S, '#');     //预先将#压入栈方便算法do {c=getchar();switch(c){case ' ': break;case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9': EnQueue(Q, C);break;    //数字1-9入队case '(':Push(&S, c);break;      //左括号入栈case ')':case '#':     //右括号和#do{t= pop(&S); //出栈if(t!='(' && t != '#'){EnQueue(Q, t);    //如果是运算符则入队}}while(t != '(' && S.top != -1 );   //直到左括号出栈或栈空循环结束break; case '+': case '-':case '*':case '/':while(Priority <= Priority(GetTop(S)))   //当前运算符优先级小于等于栈顶运算符优先级{t=pop(&S);EnQueue(Q, t);  //运算符出栈, 入队}push(&S, c);     //当前运算符入栈break;}}while(c != '#');            //以'#'号结束表达式扫描
}

3.后缀表达式的计算

后缀表达式9247*+5/-3+的计算过程

【算法描述】

int CPostExp(CirQueue* Q)   //后缀表达式在队列Q中
{SeqStack S;char ch;int x, y;InitStack(&S);while (!QueueEmpty(Q)){ch = DeQueue(Q);if (ch >= '0' && ch <= '9'){Push(&S, ch - '0');     //入栈}else       //是运算符 {y = Pop(&S);           //两个操作数出栈x = Pop(&S);switch (ch){case '+':Push(&S, x + y);break;case '-':Push(&S, x - y);break;case '*':Push(&S, x * y);break;case '/':Push(&S, x / y);break;}}}return GetTop(&S);    //最后栈顶元素就是最终结果
}

【例】阅读下列算法，并回答问题

(1) 假设栈S=(3, 8, 6, 2, 5), 其中5为栈顶元素，写出执行函数f31(&S)后的S;

(2) 简述函数f31的功能

void f31(Stack *S)
{Queue Q;InitQueue(&Q);    //建立空队Qwhile(!StackEmpty(S)){EnQueue(&Q, Pop(&S));}while(!QueueEmpty(Q)){Push($S, DeQueue(&Q));}
}

【解析】 第一个while循环完成将栈S中的元素出栈后依次入队Q，则Q(5, 2, 6, 8, 3)其中5为队头; 第二个while循环将队Q中的元素出队后依次入栈S，则S(%, 2,6,8,3) 其中3为栈顶元素。

(2) 函数f31的功能是将栈S中的元素倒置。

第四章 多维数组和广义表 

第一节 多维数组和运算

一、多维数组的定义

1、一维数组 是一种元素个数固定的线性表

2、多维数组 是一种复杂的数据结构， 可以看成是线性表的推广， 一个n维数组可视为其数据元素为 n - 1 维数组的线性表。

二、数组的顺序存储

通常采用顺序存储结构 来存放数组。对二维数组可有两种存储方法；一种是以行序为主序的存储方式，另一种是以列序为主序的存储方式。在C语言中，采用以行为主序存储。

(1) 对于C语言的二维数组A[m][n], 下标从0开始，假设一个数组元素占d个存储单元，则二维数组中任一元素a[i][j]的存储位置可由下式确定: loc(A[i][j]) = loc(A[0][0]) + (i * n +j) *d

(2) 对于C 语言的三维数组A[m][n][p], 下标从0 开始， 假设一个数组元素占d个存储单元， 则三维数组中任一元素a[i][j][k]的存储位置可由下式确定:

loc(A[i][j][k]) = loc(A[0][0][0]) + (i * n *p + j * p +k) *d

三、 数组运算举例

【例】设计一个算法，实现矩阵A[m][n]的转置矩阵B[n][m]。

【分析】 对于一个m×n的矩阵A,其转置矩阵是一个n × M的矩阵B，而且B[i][j]=A[j][i], 0≤i≤n-1; 0 ≤ j ≤ m-1。 假设m = 5; n = 8。

【算法描述】

//转置
void trsmat(int a[][8], int b[][5], int m, int n)
{int i, j;for (j = 0; j < m; j++){for (i = 0; i < n; i++){b[i][j] = a[j][i];}}
}

【例】 如果矩阵A中存在这样的一个元素Ai, 满足： A[i][j]是第i行元素中最小值， 且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A[m]/[\n],试编写求出矩阵中所胡马鞍点的算法。

【分析】算法思想：先求出每行中的最小值元素，存入数组Min[m]之中，再求出每列的最大值元素，存入数组Max[n]之中，若某元素既在Min[i]中又在Max[j]中，则该元素A[i][j]就是马鞍点，找出所有这样的元素。

【算法描述】

//寻找马鞍点
void MinMax(int a[][8], int m, int n)
{int Max[8], Min[5];int i, j;for (i = 0; i < m; i++){Min[i] = a[i][0];for (int j = 1; j < n; j++){if(a[i][j] < Min[i]){Min[i] = a[i][j];}}}for (j = 0; j < n; j++){Max[j] = a[0][j];for (i = 1; i < m; i++){if (a[i][j] > Max[j]){Max[j] = a[i][j];}}}printf("马鞍点\n");for (i = 0; i < m; i++){for (j = 0; j < n; j++){if (Min[i] == Max[j]){printf("%d (%d, %d)", Min[i], i, j);}}}
}

第二节 矩阵的压缩存储

一、特殊矩阵

特殊矩阵： 是相同值的元素或者零元素在矩阵中的分布有一定规律的矩阵。

1.对称矩阵

若n阶方阵A中的元素满足下述性质： a[i][j] = a[j][i] (0≤i, j <n ); 则称为A为n阶的对称矩阵。对于一个n阶对称矩阵，可只存储其下三角矩阵。

将元素压缩存储到 1+2+3+…+n = n(n+1)/2个元素的存储空间中，假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角(包括对角线)中的元素，数组M[k]和a[i][j]的对应关系：

【例】设有一个10阶的对称矩阵A, 采用行优先压缩存储方式， a11为第一个元素，其存储地址为1，每个元素占用一个字节空间，则a85的地址为（ ） A. 13 B. 18 C. 33 D.40

【答案】 C 【解析】 a11为第一个元素，a85是第(1+2+3+4+5+6+7) +5 = 33个元素，则a85的地址为 1 + (33 - 1) * 1 =33。

【例】 已知A和B是两个n * n阶的对称矩阵， 因为是对称矩阵，所以仅需要输入下三角元素值存入一维数组。试写一算法，求对称矩阵A和B的乘积。

【分析】对称矩阵的第i行和第j列的元素数据在一维数组中的位置L=i(i+1)/2 + j 当i>=j时(A[i][j], Bi处在下三角中);

L=j(j+1)/2+i 当i<j时(A[i][j], B[i][j]处在上三角中); L代表AA[i][j]或B[i][j]在对称矩阵存储的一维中的位置，而且0<=L<n(n+1)/2

【算法描述】 (毛线他妈碰见毛线他爸带着毛线玩)

void matrlxmult(int a[], int b[], int c[][20], int n)
{//n为A、B矩阵下三角元素个娄， a,b分别为一维数组//存放矩阵A和B的下三角元素值，C存放A和B的乘积int i, j, s, k, L1, L2;for (i = 0; i < 20; j++){for (j = 0; j < 20; j++){s = 0;for (k = 0; k < n; k++){if (i >= k)         //表示元素为下三角的元素， 计算在a数组中的下标{L1 = i * (i + 1) / 2 + k;}else                //表示元素为上三角的元素，计算下标{L1 = k * (k + 1) / 2 + i;}if (k >= j)              //表示元素为下三角的元素，计算在b数组中的下标{L2 = k * (k + 1) / 2 + j;}else{L2 = j * (j + 1) / 2 + k;}s = s + a[L1] * b[L2];    //计算矩阵乘积}c[i][j] = s;}}
}

2.三角矩阵

下三角矩阵的主对角线上主均为常娄c或零, 上三角矩阵是指矩阵的下三角(不包括对角线)中的元素均为常数c或是零的n阶方阵。一般情况下,三角矩阵的常数c均为零.

三角矩阵可压缩存储到数组M[n(n+1)/2 + 1]中。

上三角矩阵中，主对角线上的第i行有n-i+1个元素，以行序为主序存放，M[k]和a[i][j]的对应关系是:

下三角矩阵中，以行序为主序存放，与对称矩阵类是, M[k]和a[i][j]的对应关系是:

二、稀疏矩阵

1.稀疏矩阵的定义

含有大量的零元素且零元素分布没有规律矩阵称为稀疏矩阵。

2.三元组表

(1)三元组表的含义：一个稀疏矩阵可用一个三 元组线性表表示，每个三元组元素对应稀疏矩阵中的一个非零元素，包含有该元素的行号、列号和元素值。每个三元组元素在线性表中是按照行号值的升序为主序、列号值的升序为辅序(即行号值相同再按列号值顺序)排列的。

【例】画出下列稀疏矩阵对应的三元组表

【解析】 根据前面三元组的含义很容易画出该矩阵的三元组表。

【答案】

(2)三元组表的类型定义

#define Maxsize 1000     //假设非零元素个数的最大为1000个
typedef int DataType;
typedef struct
{int i, j;       //非零元素的行号、列号(下标)DataType v;     //非零元素值
} TriTupleNode;typedef struct
{TriTupleNode data[Maxsize];    //存储三元组的数组int m, n, t;                   //矩阵的行数、列数和非零元素个数
} TSMatrix;                        //稀疏矩阵类型

【例】写一个算法，建立顺序存储稀疏矩阵的三元组表。

【分析】 假设A为一个稀疏矩阵，其数据存储在二维数组a中，b为一个存放对应于A矩阵生成的三元组表。在这个算法中，要进行二重循环来判断每个矩阵元素是否为零，若不为零，则将其行、列下标及其值存入b中。

【算法描述】

void CreateTriTable(TSMatrix* b, int a[][5], int m, int n)
{//建立稀疏矩阵的三元组表int i, j, k = 0;for (i = 0; i < m; i++){for (j = 0; j < n; j++){if (a[i][j] != 0)                     //找出非零元素{b->data[k].i = i;                 //记录非零元素行下标b->data[k].j = j;                 //记录非零元素列下标b->data[k].v = a[i][j];           //保存非零值k++;}}}b->m = m;                                     //记录矩阵行列数b->n = n;                                        b->t = k;                                     //保存非零个数
}

【例】试写一个算法，实现以三元组表结构存储的稀疏矩阵的转置运算。

【分析】对于一个m*n的矩阵M,它的转置矩阵T是一个n * m的矩阵，而且M[i][j]=T[j][i](0<=i<m, 0<=j<n), 即M的行是T的列，M的列是T的行。

(1) 一般的转置算法

【算法思想】 对M中的每一列col(0 <= col <=a.n-1) 从头到尾依次扫描三元组表，找出所有列号等col的那些元素组，并将它们的行号和列号互换后再依次存入b->data中，这样就可得到T的按行优先的三元组表。

【算法描述】

void TransMatrix(TSMatrix a, TSMatrix* b)
{  //a和*b是矩阵M、T的三元组表表示， 求稀疏矩阵M的转置Tint p, q, col;b->m = a.n;       //M和T行列数互换b->n = a.m;   b->t = a.t;if (b->t <= 0){printf("M中无非零元素!");}else{q = 0;for (col = 0; col < a.n; ++col){for (p = 0; p < a.t; ++p)          //扫描M的三元组表{if (a.data[p].j == col)        //找与col相等的三元组{b->data[q].i = a.data[p].j;b->data[q].j = a.data[p].i;b->data[q].v = a.data[p].v;++q;}}}}
}

【算法分析】该算法的时间复杂度为O(n*t)，即与稀疏矩阵M的和非零元素个数的乘积成正比。一般的矩阵转置算法的时间复杂度为O(m*n).该算法公适用于非零元素个数t远远小于矩阵元素个数的m*n的情况。

(2) 快速转置算法

【算法思想】创建两个数组num和rownext。num[j]存放矩阵第j列上非零元素个灵敏， rownext[i]代表转置矩阵第i行的下一个非零元素在b中的位置。

【算法描述】

void FastTran(TSMatrix a, TSMatrix* b)
{int col, p, t, q;int *num, * rownext;num = (int*)calloc(a.n + 1, 4);       //分配n+1个长度为4的连续空间rownext = (int*)calloc(a.m + 1, 4);   //分配m+1个长度为4的连续空间b->m = a.n; b->n = a.m;b->t = a.t;if (b->t){for (col = 0; col < a.n; ++col){num[col] = 0;                   //初始化}for (t = 0; t < a.t; ++t){++num[a.data[t].j];                  //计算每列非零元素数}rownext[0] = 0;for (col = 1; col < a.n; ++col)     //给出b中每一行的起始点{rownext[col] = rownext[col - 1] + num[col - 1];}for (p = 0; p < a.t; ++p)             //执行转置操作{col = a.data[p].j;q = rownext[col];b->data[q].i = a.data[p].j;b->data[q].j = a.data[p].i;b->data[q].v = a.data[p].v;++rownext[col];               //下一次再有该行元素，起始点就比上一个加1}}
}

【算法分析】 算法的时间复杂度为O(t);

3.带行表的三元组表

带行表的三元组表：又称为行逻辑链接的顺序表。在按行优先存储的三元组表中，增加一个存储每一行的第一个非零元素在三元组表中位置的数组。

【类型描述】

#define MaxSize 1000
#define MaxRow 100
typedef struct
{TriTupleNode data[MaxSize];int RowTab[MaxRow];               //每行第一个非零元素的位置表    int m, n, t;
} RLSMatrix;

带行表的三元组表的特点：

① 对于任给行号i(0≤i≤m-1)，能迅速地确定该行的第一个非零元在三元组表中的存储位置为RowTab[i] ② RowTabi表示第i行之前的所有行的非零元数。 ③ 第i行上的非零元数目为RowTab[i+1]-RowTabi ④ 最后一行(即第m-l行)的非零元数目为t-RowTabm-1 注意： 　若在行表中令RowTab[m]=t（要求MaxRow>m）会更方便 些，且t可省略。 　带行表的三元组表可改进矩阵的转置算法，具体【参阅其它参考书】。

【例】对于下列稀疏矩阵(注：矩阵元素的行列下标均从1开始)

(1) 画出三元组表， (2) 画出三元组表的行表。

【答案】 (1) 三元组表 (2) 三元组表的行表

第三节 广义表基础

一、广义表的定义

广义表是线性表的推广。是广义表中放松对表元素的原子限制，容许它们具有其自身结构。

1.广义表定义

广义表是n(n>=0)个元素a1,a2, ...,ai,...,an的有限序列。

其中：

①ai--或者是原子或者是一个广义表。

②广义表通常记作: Ls=(a1, a2, ..., ai, ..., an)。

③Ls是广义表的名字，n为它的长度。

④若ai是广义表，则称它为Ls的子表。

⑤一个表展开后所含括号的层数称为广义表的深度

注意：

①广义表通常用圆括号括起来，用逗号分隔其中的元素。

②为了区分原子和广义表，书写时用大与字母表示广义表，用小写字母表示原子。

③若广义表Ls非空(n>=1), 则al是Ls的表头(head), 其余元素组成的表(a1, a2,...,an)称为Ls的表尾(tail)。

④广义表是递归定义的

【例】

(1) A=() --- A是一空表， 其长度为零, 深度为1.

(2)B=(a)----B是一个只有一个原子的广义表，其长度为1， 深度为1

(3)C=(a, (b, c)) ---C是一个长度为2的广义表，第一个元素是原子， 第二个元素是子表，深度为2。

(4)D=(A,B,C)=((), (a), (a, (b,c)))---D是一个长度为3的广义表，其中三个元素均为子表，深度为3。

(5)E=(C, d)=((a, (b, c)), d) --- E是一个长度为2的广义表，第一个元素是子表，第二个元素是原子，深度为3。

(6)F=(e, F)=(e, (e, (e, ...))) ---F是一个递归的表，它的长度为2， 第一个元素是原子， 第二个元素是表自身，展开后它是一个无限的广义表，深度为∞。

2、广义表的几个重要的性质

(1) 广义表的元素可以是子表，而子表有可以含有子表，因此广义表是一个多层次结构的表，它可以用图来形象地表示。

(2)广义表具有递归和共享的性质，例如，表F就是一个递归的广义表，D表是共享的表，在表D中可以不必列出子表的值，而是通过子表的名字来引用。

二、广义表的基本运算

广义表是对线性表和树的推广，广义表的大部分运算与这些数据结构上的运算类似。在此，只讨论广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。任何一个非空的广义表其表头可能是原子，也可能是子表，而其表尾一定是子表。

【例】 已知有下列的广义表，试求出下面广义表的表对head()、表尾tail(), 表长length()和深度depth()。

(1) A=(a, (b, c,d), e, (f, g)); (2) B=((a)); (3) C=(y, (z, w), (x, (z,w), a)) (4) D=(x, ((y), B), D )。

【解答】

(1) head(A)=a, tail(A)=((b, c, d), e (f, g)), length(A) = 4, depth(A) = 2;

(2) head(B)=(a), tail(B)=(), length(B)=1, depth(B)=2;

(3) head(C) = y， tail(C)=((z, w), (x, (z, w), a)), length(C)=3, depth(C)=3;

(4) head(D)=x, tail(D)=(((y), B), D), length(D)=3, depth(D)= ∞。

【例】 取出广义表A=((x, y, z), (a, b, c, d))中原子b的函数是 。

【解析】 要从广义表A中取出原子b， 需要先对A取尾运算:tail(A)=((a, b, c, d)), 然后再对tail(A)结果进行取表头运算head(tail(A))=(a, b, c, d), 然后再结果进行取表尾运算tail(head(tail(A)))=(b, c, d), 最后再进行取表头运算

head(tail(head(tail(A)))) = b。

【答案】 head(tail(head(tail(A))))

【例】1、已知广义表如下: A=(B, y) B=(x, L) L=(a, b) 要求：(1) 写出下列操作的结棍

tail(A)= (y) head(B)=(x)

2、请画出广义表A对应的图形表示。

2、已知广义表C=(a, (b, c), d), 则： tail(head(tail(C)))=(c)。

三、广义表的存储结构

1、结点结构

说明： (1) tag标志位， tag=1, 该结点是子表， 第二个域为slink, 用以存放子表的地址; 当tag=0时, 该结点是原子结点，第二个域为data, 用以存放元素值。

(2) link域是用来存放与本元素同一层的下一个元素对应结点的地址，当该元素是所在层的最后一个元素时，link的值为NULL。

【例】

第五章 树和二叉树

第一节 树的基本概念和术语

一、引言

树形结构是一类重要的非线性数据结构，树中结点之间具有明确的层次关系，并且结点之间有分支，非常类似于真正的树。树形结构在客观世界中大量存在，如行政组织机构和人类社会的家谱等都可用树形结构形象地表示。

二、树的定义

1、树(Tree)是n(n>=0)个结点的有限集T, n=0时称为空树，任意非空树(1)有且仅有一个特定的称为根(Root)的结点:

(2) n>1时，除根结点外的其余结点可分为m(m>=0)个互不相交的子集T1, T2, ...,Tm, 其中每个子集本身有是一棵树，并称其为根的子树（Subtree)。

2、从逻辑上看，树形结构具有以下特点:

(1) 任何非空树中有且仅有一个结点没有前驱结点，这个结点就是树的根结点。

(2)除根结点之外，其余所有结点有且仅有一个直接前驱结点。

(3)包括根结点之外，每个结点可以有多个直接后继结点。

(4)树形结构是一种具有递归特征的数据结构。

(5)树形结构中的数据元素之间存在的关系通常是一对多，或者多对一的关系。

三、树的表示法

1、树结构

2、嵌套集合

3、凹形表示法

4、广义表表示法

(A (B (E, (F (J, K))), C (G), D (H, I)))

四、树结构的基本术语

(1) 结点的度： 结点所拥有的子树的个数。如A的度为3, E的度为2。

(2)树的度：树中结点度的最大最。

(3)叶子(终端结点)：度为0的结点。

(4) 分支结点(非终端结点): 度不为0的结点。除根结点之外的分支结点统称为内部结点。根结点又称为开始结点为。

(5)孩子：结点的直接后继(即结点的子树的根)。如B是A的孩子，N是I的孩子

(6)双亲: 结点的直接前趋。如B的双亲是A， N的双亲是I。

(7)兄弟:同一双亲的孩子互为兄弟。如B、C、D互为兄弟， M,N互为兄弟。

(8)子孙：一棵树上的任何结点(不包括根结点)称为根的子孙。如图中其它结点都是根结点A的子孙。

(9)祖先：从根结点开始到该 结点连线上的所有结点(除该结点)都是该结点的祖先。如N的祖先是I,C,A。

(10)路径：若树中存在一个结点序列k1, k2, ..., ki,使得ki是ki+1的双亲(i<=i<j),则称该结点序列是从k1到kj的一条路径或道路。路径的长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1.

注意：若一个结点序列是路径，则在树的树形图表示中，该结点序列"自上而下"地通过路径上的每条边。

从树的根结点到树中其余结点均存在一条唯一的路径。

(11) 结点的层: 设根结点的层数为1， 其余结点的层数等于双亲结点的层数加1。如B的层数是，N的数是4。

(12) 树的高度(或深度)： 树中所胡结点层数的最大值。图所示的树的高度为4。

(13)有序树和无序树：将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树; 否则称为无序树。

(14)森林： 是m(m>=0)棵互不相交的树的集合。树和森林的概念相近，删去一棵树的根，就得到一个森林; 反之，加上一个结点作树根，森林就变为一棵树。

五、树的性质

性质一： 非空树中的结点总数等于树中所胡结点的度之和加1.

证明：根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个双新结点，即每个结点与指向它的一个分支结点--对应，因而除了树的根结点之外的结点数等于树中所有结点的分支数(度数)，由此可得知树中的结点总数应为所胡结点的度之和加1.

性质二: 度为k的非空树的第i层最多有ki-1个结点(i>=1)。

性质三：深度为h的k叉树最多有( ) 个结点

证明：显然，只有当深度为h的k叉树上的每一层都达到该层最大结点总数时，该数的结点总数将达到最大，因此，有

第二节 二叉树

一、二叉树的定义和性质

1、二叉树的定义

二叉树(Binary Tree)是n(n>=0)个结点的有限集，它或者是空集(n=0), 或者由一个根结点及及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。这是一个递归定义。

2.二叉树的五种基本形态

二叉树可以是空集；根可以有空的左子树或右子树; 或者左、右子树皆为空。二叉树的五种基本形态如下图所示。

3.二叉树与树的关系

(1) 二叉树与无序树不同

二叉树中，每个结点最多只能有两棵子树，并且有左右之分。二叉树并非是树的特殊情形，它们是两种不同的数据结构。

(2)二叉树并非是度数为2的有序树不同

在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。

图(a), 它是一棵度为2的有序树，由于根结点的子树没有左右之分，所以它不是二叉树。

另外，具有三个结点的度为2的有序树有一种形态，如图(b)所示。

具有三个结点的树有两种形态，如图(b)和(c)所示，

具有三个结点的二叉树有五种形态，如图(b)、(d)、 (e)、(f)、(g)所示。

4、二叉树的性质

性质一： 二叉树第i(i>=1)层最多有  个结点

证明：用数学归纳法证明：(1)当i=1时，有  =2º=1。因为第1层上只有一个根结点，所以命题成立。

(2)假设对所有的j(1<=j<i)命题成立，即第j层上到多有

个结点。

(3)根据归纳假设， 第i-1层上至多有

个结点。由于二叉树的每个结点纛多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍，即j=i时，该层上至多有2* =  个结点，故命题成产立。

性质二: 深度为k(k>=1)的二叉树，最多有 个结点。

证明：在具胡相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：

故命题正确。

性质三: 任意非空二叉树中，若叶结点的数目为n₀ ,度为2的结点数目为n₂, 则有关系n₀=n₂+1;

证明：设度为1的结点数目为n₁,二叉树的结点总数为n,有n=n₀ + n₁+n₂;设B表示分支数，具有n个结点的二叉树的分支总数为n-1。则有B=n-1而所有这些分支不是来自于度为1的结点就是来自于度为2的结点，即每一个度为1的结点发出一个分支，每一个度为2的结点发出两个分支。于是有B=n₁+n₂， 联立上面三个等式可以得到n₀=n₂+1. 故命题正确。

满二叉树：一棵深度为k且有

个结点的二叉树称为满二叉树。

满二叉树的特点：(1)每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。满二叉树的结点总数一定是奇数。(2)满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且叶结点都在最下一层上。

【例】求具有n个结点的满二叉树叶结点数n₀与度为2的结点数n₂分别为多少?

【解答】由于满二叉树中没有度为1的结点，则有： n=n₀+n₂，

根据二叉树的性质三，有 : n₀=n₂+1; 联立上面两个等式可以得到： n₀=(n+1)/2  ;   n₂=(n-1)/2

完全二叉树： 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

完全二叉树的特点：(1)满二叉树是完全二叉树，完全二叉树不定是满二叉树。(2)在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。(3)在完全二叉树中，若某个结点没有左孩子，则它一下没有右孩子，即该结点必是叶结点。

性质4：具有n个结点的完全二叉树的深度为k=或

证明: 设所求完全二叉树的深度为k。由完全二叉树定义可得： 深度为k的完全二叉树的深度为k。由完全二叉树定义可得：深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，一共有

个结点。

由于完全二叉树深度为k, 故第k层上还有若干个结点，因此该完全二叉树的结点个数： n >

另一方面，由性质2可得: n

即： 2k-1-1<n≤2k-1

由此可推出:

,取对数后有:  ​​k-1

又因k-1和k是相邻牟两个整数，故有k=

性质五：如果将一棵有n个结点的完全二叉树按层从1开始编号,则对任一编号为i(1<=i<=n)的结点X有:

若i =1, 则结点X是根; 若 i > 1, 则X的双亲的编号为i 。

若2i > n, 则结点X无左孩子(且无右孩子); 否则， X的左孩子编号为2i。

若2i + 1 > n, 则结点X无右孩子；否则，X的右孩子的编号为2i+1.

二、二叉树的存储结构

1、顺序存储结构

(1)完全二叉树的顺序存储

性质五修改为: 如果将一棵有n个结点的完全二叉树按层从0开始编号， 则对任一编号为i(0<=i<n)的结点X有：若i=0,则结点X是根；若i>0,则X的双亲的编号为

。若2i+1<n, 则结点X的左孩子编号为2i+1，否则，结点X无左孩子(且无右孩子)。若2i+2<n，则结点X的右孩子的编号为2i+2，否则，X无右孩子。

(2)一般二叉树的顺序存储

(3)顺序存储二叉树的优点和缺点

①对完全二叉树而言，顺序存储结构既简单又节省存储空间。

②一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个 结点为的存储空间(相当于满二叉树)。

③在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。

2、链式存储结构

(1)二叉链结点结构

说明：

①数据域data，用以存放元素值。

②指针域lchild和rchild，分别指向该结点的左孩子和右孩子。没有左孩子时lchild=NULL，没有右孩子时rchild=NULL.

【例】画出下图所示的二叉树的二叉链表表示图.

【解答】该二叉树的二叉链表表示如下图所示。

当二叉树有n个结点时，其二叉树链表上共有2n个指针域，其中只有n-1个指针域用于存放其左、右孩子的指针(n个结点的二叉树一共有n-1个分支)，剩下的n+1个指针域为空。

(2) 二叉树结点类型定义

typedef struct node
{DataType data;struct node* lchild, * rchild;    //左右孩子指针
} BinTNode;                         //结点类型
typedef BinTNode * BinTree;          //BinTree为指向BinTNode类型结点的指针类型

(3) 三叉链结点结构

说明：增加的parent域指向其双亲

【例】画出图所示的二叉树的三叉链表表示图

【解答】

三叉链表结构与二叉链表结构的区别是它的结点多了一个指向双亲的指针域。当二叉树有n个结点时，其三叉链表上共有3n个指针域，其中只有n-1个指针域用于存放其左、右孩子的指针，有n-1个指向双亲，剩下的n+2个指针域为空。

第三节 二叉树的运算

一、二叉树的生成

1.按广义表表示二叉树结构生成二叉链表的算法

上图所示二叉树的广义表表示形式为: (A(B(, D(E, F)), C))。

特点：靠近左括号的结点是在左子树上，而逗号右边的结点是在右子树上。

算法中用了一个指针数组来模拟栈存储结点的双亲指针，根据读入广义表中的字符分四种不同的情况进行处理：

【算法描述】

BinTNode* CreateTree(char* str)    //按广义表表示二叉树结构生成二叉链表的算法
{                     //str为存储广义表的字符串的指针BinTNode* St[100];  //用指针数组模拟栈BinTNode* p = NULL;int top, k, j = 0;top = -1;           //置空栈char ch = str[j];BinTNode* b = NULL;while (ch != '\0')    //循环读广义表字符串中字符{switch (ch) {case '(':top++;St[top] = p;k = 1;break;case ')':top--;break;case ',':k = 2;break;default:p = (BinTNode*)malloc(sizeof(BinTNode));p->data = ch;p->lchild = p->rchild = NULL;if (b == NULL){b = p;}else{switch (k) {case 1: St[top]->lchild = p; break;case 2: St[top]->rchild = p; break;}}}j++; ch = str[j];}return b;
}

2.按完全二叉树的层次顺序依次输入结点信息建立二叉链表的算法

【算法思想】 首先对一般的二叉树添加 若干个虚结点，使其成为完全二叉树，然后依次输入结点信息，若输入的结点不是虚结点“@”，则建立一个新结点，若是第一个结点，则令其为根结点，否则将新结点作为左孩子或右孩子 链接到它的双亲结点上。如此重复下去，直到输入结束符号"#"时为止(假设结点数据域为字符型)。

BinTree CreateBinTree(BinTree bt )      //按完全二叉树的层次顺序依次输入结点信息建立二叉链表的算法
{//Q[1,,,,n]是一个BinTNode类型的指针数组, front和rear分别是队头和队尾指针BinTNode* Q[100];     //定义队列BinTNode* s;int front, rear;char ch;ch = getchar();bt = NULL;       //置空二叉树front = 1; rear = 0;    //初始化队列 while (ch != '#')            //假设结点值为单字符，#为终止符{                            s = NULL;if (ch != '@')             //先假设读入的为虚结点@ {s = (BinTNode*)malloc(sizeof(BinTNode));     //申请新结点s->data = ch;s->lchild = s->rchild = NULL;             //新结点赋值}rear++;                                       //队尾指针自增Q[rear] = s;                                  //将新结点地址或虚结点地址(NULL)入队if (rear == 1)                                //若rear为1， 则说明是根结点， 用bt指向它{bt = s;}else{if (s != NULL && Q[front] != NULL)     //当前结点及其双亲结点都不是虚结点{if (rear % 2 == 0){Q[front]->lchild = s;       //rear为偶数，新结点应作为左孩子}else{Q[front]->rchild = s;       //rear为奇数，新结点应作为右孩子}}if (rear % 2 != 0){front++;    //rear为奇数，说明front所指结点的左右儿子都处理完了，因此front加1指向下一个双亲}}ch = getchar();    //读下一个结点值}return bt;
}

二、二叉树的遍历

遍历：是指没着某条搜索路径(线)周游二叉树，依次对树中每个结点访问且仅访问一次。

遍历方案

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作:①访问根结点本身(D), ②遍历根结点的左子树(L),③遍历根结点的右子树(R).

以上三种操作操作有六种执行次序: DLR(根左右)、 LDR(左根右)、LRD(左右根)；DRL(根右左)、RDL(右根左)。

注意：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。

1、递归遍历的算法

三种遍历的递归定义：

(1)先序遍历DLR(根左右): 也叫先根遍历，若二叉树非空，则依次执行如下操作：

①访问根结点 ②遍历左子树 ③遍历右子树

(2)中序遍历LDR(左根右): 也叫中根遍历， 若二叉树非空，则依次执行如下操作>

①遍历左子树 ②访问根结点 ③遍历右子树

(3)后序遍历LRD(左右根) : 也叫后根遍历， 若二叉树非空，则依次执行如下操作：

①遍历左子树 ②遍历右子树 ③访问根结点

【例】分别写出图所示的二叉树的前序、中序、后序遍历序列。

【答案】 前序遍历序列： ABDCEF 中序遍历系列： DBAECF 后序遍历序列： DBEFCA

三种遍历的算法

(1)前序遍历递归算法

void Preorder(BinTree bt)   //前序遍历递归算法
{//采用二叉链表存储结构， 并设结点值为字符型if (bt != NULL){printf("%c", bt->data);   //访问根结点Preorder(bt->lchild);    //前序遍历左子树Preorder(bt->rchild);     //前序遍历右子树}
}

(2)中序遍历递归算法

void Inorder(BinTree bt)       //中序遍历递归算法
{if (bt != NULL){Inorder(bt->lchild);    //中序遍历左子树printf("%c", bt->data);   //访问根结点Inorder(bt->rchild);    //中序遍历右子树}
}

(3)后序遍历递归算法

void Postorder(BinTree bt)  //后序遍历递归算法
{if (bt != NULL){Postorder(bt->lchild);  //中序遍历左子树Postorder(bt->rchild);   //中序遍历右子树printf("%c", bt->data);  //访问根结点}
}

2.二叉树遍历的非递归算法

(1)利用栈的非递归中序遍历算法

#define StackSize 100      //栈空间的大小应根据实际需要来定义，这里假设为100
typedef BinTNode DataType;    //DataType的类型可根据实际情况而定，这里假设为char
typedef struct {                //顺序栈的定义DataType data[StackSize];   //数组data用来存放表结点int top;                    //表示栈顶指针
} SeqStack;void Inorderl(BinTree bt)     //利用栈的非递归中序遍历算法
{//采用二叉树链表存储结构SeqStack S;BinTNode* P;InitStack(&S);Push(&S, bt);                 //根结点入栈while (!StackEmpty(&S)){while (GetTop(&S))        //读栈顶元素，当栈顶不为空{Push(&S, GetTop(&S)->lChild);   //左孩子依次入栈，直到左子树空为止}p = Pop(&S);               //最后一个入栈的空指针退栈if (!StackEmpty(&S)){printf("%c", GetTop(&S)->data);   //访问根结点p = Pop(&S);Push(&S, p->rchild);      //右子树进栈}}
}

(2)利用指针数组模拟栈实现的非递归中序遍历算法

void Inorder2(BinTree bt)    //利用指针数组模拟栈实现的非递归中序遍历算法
{//二叉树非递归中序遍历算法BinTNode* ST[100];    //用指针数组模拟栈int top = 0;            //初始化数组ST[top] = bt;do{while (ST[top] != NULL)     //根结点及其所有的左结点地址装入数组{top = top + 1;ST[top] = ST[top - 1]->lchild;}top = top - 1;                 //最后一个入数组的空指针退"栈"if (top >= 0)   //判断数组中地址是否访问完{printf("%c", ST[top]->data);   //访问结点ST[top] = ST[top]->rchild;   //扫描右子树}} while (top != -1);
}

(3)利用栈的非递归前序遍历算法

算法思想：利用栈先将二叉树根结点指针入栈，然后执行出栈，获取栈顶元素值(即结点指针)， 若不为空值，则访问该结点，再将右、左子树的根结点指针分别入栈，依次重复出栈、入栈，直到栈空为止。

void Preorderl(BinTree bt)      //利用栈的非递归前序遍历算法
{SeqStack S;InitStack(&S);         //初始化栈Push(&S, bt);          //根结点指针进栈while (!StackEmpty(&S)){bt = Pop(&S);      //出栈if (bt != NULL){printf("%c", bt->data);   //访问结点，假设数据域为字符型Push(&S, bt->rchild);    //右子树入栈   先访问左子树， 栈先进后出Push(&S, bt->lchild);    //左子树入栈}}
}

(4)非递归的按层次遍历二叉链表树。

按层遍历二叉树，从上到下，从左到右遍历二叉树。

【例】对下图二叉树按层进行遍历

【答案】 ABCDEF

算法思想：采用一队列Q，若树不空，先将二叉树根结点输出，并将根结点指针入队，然后出队。若根结点有左子树，则将左子树的根结点输出并将其指针入队;若其有右子树，则将其右子树的根结点输出并将其指针入队，再出队，如此下去，直至队列空为止。

#define QueueSize 100
typedef char DataType;    //假设数据为字符型typedef struct
{DataType data[QueueSize];int front, rear;
} CirQueue;void TransLevel(BinTree bt)
{CirQueue Q;     //按层遍历二叉树，从上到下，从左到右InitQueue(&Q);  //初始化队列为空队列if (bt == NULL){return;}else{printf("%c", bt->data);    //输出根结点，假设其数据域为字符型EnQueueEmpty(&Q, bt);      //根结点指针入队while (!QueueEmpty(&Q)){bt = DeQueue(&Q);      //出队列if (bt->lchild != NULL){printf("%c", bt -> lchild->data);  //输出左子树根结点EnQueue(&Q, bt->lchild);    //左子树入队}if (bt->rchild != NULL){printf("%c", bt->rchild->data);   //输出右子树根结点EnQueue(&Q, bt->rchild);   //右子树入队列}}}
}

3、由遍历序列恢复二叉树

(1)已知二叉树的前序遍历序列和中序遍历序列，可以唯一地恢复该二叉树。

原则是：在前序序列中确定根结点(最前面那个结点一定是根结点)，然后根据根结点在中序序列中的位置分出根结点的左、右子树(根结点前面的那些结点为根结点的左子树上的结点，根结点后面的那些结点为根结点的右子树上的结点)。恢复该二叉树的任何一棵子树的过程仍然遵循这个原则。

【例】已知一棵二叉树的前序遍历序列与中序遍历序列分别为前序遍历序列： A B C D E F G H I

中序遍历序列： B C A E D G H F I , 试恢复该二叉树。

【解答】按照上述分解原则求得整棵二叉树的过程如下所示

同理，已知二叉树的中序遍历序列和后序遍历序列，也可以唯一地恢复该二叉树，只是在后序序列中去确定根结点(最后面那个结点一定是根结点)， 而在中序序列中分出左右子树的过程与上述过程没有区别。

已知二叉树的前序遍历序列和后序遍历序列，无法唯一地恢复该二叉树，因为无法确定左右子树。

三、二叉树应用举例

【例1】已知二叉树的链式存储结构，求二叉树的深度。

【分析】若一棵二叉树为空，则它的深度为0，否则它的深度等于其左右子树中的最大深度加1。设depl和depr分别表示左右子树的深度，则二叉树的深度为： max(depl, depr) + 1

【算法描述】

int BinTreeDepth(BinTree bt)    //二叉树的深度为： max(depl, depr) + 1
{//求由bt指向的二叉树的深度int depl, depr;if (bt == NULL){return 0;    //对于空树，返回0值，结束递归}else{depl = BinTreeDepth(bt->lchild);   //计算左子树的深度depr = BinTreeDepth(bt->rchild);   //计算右子树的深度if (depl > depr){return depl + 1;}else{return depr + 1;}}
}

【例2】以二叉链表为存储结构，试编写在二叉树中查找值为x的结点的位置。

【分析】该算法是比较简单的，无论是利用三种遍历算法的哪一种，都很容易实现，不妨用前序遍历算法。

【算法描述】

//在二叉树中查找值为x的结点的位置
int found = 0;
BinTNode* p;           //用found来作为是否查找到的标志
void FindBT(BinTree bt, DataType x)
{BinTNode* P = NULL;if ((bt != NULL) && (!found)){if (bt->data == x){p = bt;found = 1;}else{FindBT(bt->lchild, x);   //遍历查找左子树FindBT(bt->rchild, x);   //遍历查找右子树}}
}

【例3】以二叉链表为存储结构，试编写p所指结点在树中层数的算法。

【分析】设h为返回p所指结点的所在层数，初值为0;树为空时返回0。lh指示二叉树bt的层数(即高度), 调用时置初值为1。

【算法描述】

int Level(BinTree bt, BinTNode* p, int lh)
{//求一结点在二叉树中的层次static int h = 0;     //h设置为静态遍历if (bt == NULL){h = 0;}else{if (bt == p){h = lh;}else{Level(bt->lchild, p, lh + 1);       //左子树中查找pif (h == 0)                          //表示左子树已查完{Level(bt->rchild, p, lh + 1);   //右子树中查找p}}}return h;
}

第四节 线索二叉树

一、线索二叉树的概念

1、定义：n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为“线索”)。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为称为线索二叉树。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

2、线索链表的结点结构

其中： 

【例】 如图(a)所示的二叉树所对应的中序线索二叉树如图(b)所示，图(c)所示为二叉线索链表树。

3、线索链表的结点类型定义

typedef struct node   //线索链表
{DataType data;int ltag, rtag;struct node* lchild, * rchild;
} BinThrNode;        //线索链表结点类型
typedef BinThrNode* BinThrTree;    //定义线索链表类型

二、二叉树线索化算法

1.算法思想

按某种次序遍历二叉树，在遍历过程中用线索取代空指针即可。

(1)如果根结点的左孩子指针域为空，则将左线索标志域置1，同时给根结点加左线索。

(2)如果根结点的右孩子指针域为空，则将右线索标志域置1，同时给根结点加右线索。

(3)将根结点指针赋给存放前趋结点指针的变量，以便当访问下一个结点时，此根结点作为前趋结点。

2.二叉链表加中序线索的算法

算法与中序遍历算法类似，只是将遍历算法中访问根结点*bt的操作改为在*bt和中序前趋*pre之间建立线索。

void InorderThread(BinThrTree bt)     //二叉链表加中序线索的算法
{//定义指向前趋结点的指针pre(静态变量), 保存刚访问过的结点static BinThrNode* pre = NULL;if (bt != NULL){InorderThread(bt->lchild);   //左子树线索化if (bt->lchild == NULL){bt->ltag = 1;}else{bt->ltag = 0;}if (bt->rchild == NULL){bt->rtag = 1;}else{bt->rtag = 0;}if (pre){if (pre->rtag==1){pre->rchild = bt;    //给前趋结点加后继线索}if (bt->ltag == 1){bt->lchild = pre;    //给当前结点加前趋线索	}}pre = bt;    //将刚访问过的当前结点置为前趋结点InorderThread(bt->rchild);   //右子树线索化}
}

三、二叉线索链表上的运算

1、在中序线索二叉树上查找某结点*p的后继结点

【分析】分两种情况：

(1)若结点*p的rtag域值为1，则表明p->rchild为右线索，它直接指向结点。

(2)若结点*p的rtag域值为0，则表明p->rchild指向右孩子结点，结点*p的中序后继结点必是其右子树第一个中序遍历到的结点，因此从结点*p的右孩子开始，沿左指针链向下查找，直到找到一个没有左孩子(即ltag为1)的结点为止，该结点是结点*p的右子树中"最左下"的结点，它就是结点*p的中序后继结点。

【算法描述】

BinThrNode* InorderNext(BinThrNode* p)
{//在中序线索二叉树上求结点*p的中序后继结点if (p->rtag == 1)           //rchild域为右线索{return p->rchild;    //返回中序后继结点白指针}else{p = p->rchild;while (p->ltag == 0){p = p->lchild;     //沿左指针链向下查找}return p;}
}

2、线索二叉树的中序遍历算法

【基本思想】首先从根结点起沿左指针链向下查找，直到找到一个左线索标志为1的结点止，该结点的左指针域为空，它就是整个中序序列中的第一个结点。访问该结点，然后就可以依次找结点的后继，直至中序后继为空时为止。

【算法描述】

void TinorderThrTree(BinThrTree bt)  //线索二叉树的中序遍历算法
{BinThrNode* p;if (bt != NULL)    //二叉树不空{p = bt;      //使p指向根结点while (p->ltag == 0)    //查找出中序遍历的第一个结点{p = p->lchild;}do {printf("%c", p->data);   //输出访问结点值p = InorderNext(p);        //查找结点\*p的中序后继} while (p != NULL);           //当p为空时算法结束}
}

第五节 森林和树

一、树的存储结构

1、双亲表示法

在双亲表示法中，每个存储结点由两个域组成：数据域--存储树上结点的数据元素; 双亲域--存储双亲结点在结点数组中的下标值。在这种表示法下，求指定结点的祖先很方便，但求指定结点的子孙则不方便。

2、孩子链表表示法

孩子链表表示的基本思想是：为树上的每个结点X建立一个“孩子链表”，存储X中的数据元素和指向X的所有孩子的指针。一个孩子链表是一个带头结点的单链表，单链表的头结点含两个域：数据域和指针域。其中，数据域用于存储结点X中的数据元素；指针域用于存放指向该单链表中第一个表结点(首结点)的指针。

为了检索方便，所有头结点组成一个数组，称为表头数组。对每个结点X的孩子链表来说，其中的所胡表结点也含两个域，孩子域(即数据域)和指针域。第i个表结点的孩子域存储X的第i个孩子在头结点数组中的下标值。

为了便于查找双亲，可在各个头结点中增加一个双亲域以存储双亲结点在头结点数组中的下标值，称其为带双亲的孩子链表表示法。

3、孩子兄弟表示法 孩子兄弟表示法又称二叉链表表示法，孩子兄弟表示法中所有存储结点的形式相同，均含三个域：数据域--存储树上结点的数据元素;孩子域--存放指向本结点第一个孩子的指针;兄弟域--存放指向本结点下一个兄弟的指针。

二、树、森林与二叉树的转换

1、树、森林转换为二叉树

(1)树转换为二叉树

将一棵树转换为二叉树可以按以下步骤进行：

①在所有相邻兄弟结点之间分别加一条连线。

②对每个分支结点，除了其最左孩子外，删去该结点与其他孩子结点的连线。

③ 以根结点为轴心，顺时针旋转45°。

注意：由树转换的二叉树的根结点的右孩子始终为空，原因是树的根结点不存在兄弟结点。下图给出的例子显示了这一转换过程。

(2)森林转换为二叉树

将森林转换为二叉树的步骤可以归纳如下：①分别将树林中的每棵树转换为二叉树。②从最后那棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，直到所有二叉树全部连接，这样得到的二叉树的根结点就是树林中第一棵树的根结点。

(3)二叉树转换为树

将一棵二叉树转换为树可以按下列步骤进行:

①若某结点是其双亲结点的左孩子，则将该结点的右孩子以及当且仅当连续地沿着此右孩子的右子树方向不断的搜索到的所有右孩子，都分别与该结点的双亲结点用虚线连接起来。

②删去原二叉树中所有双亲结点与其右孩子的连线。

③将图形规整化，使各结点按层次排列，并且将虚线改成实现。

(4)二叉树转换为森林

将一棵二叉树转换为森林可以按下列步骤进行：

①去掉二叉树的右子树，将去掉右子树后剩下的二叉树转换为一棵树。

②将在第①步中被云掉的右子树再执行第①步。

③重复前两步，直到转换完成。

【例】已知二叉树如下：

请画出该二叉树对应的森林。

【解析】

【答案】

三、树和森林的遍历

1、树的遍历

(1) 树的前序遍历定义

①访问根结点; ②依次前序遍历根的各子树

(2)树的后序遍历定义

① 依次后序遍历根的各子树; ② 访问根结点R。

【例】写出如图所示树的前序遍历和后序遍历的序列和该树对应二叉树的前序遍历、中序遍历和后序遍历的序列

树的前序遍历序列: A B E F G C H D I J

二叉树的前序遍历序列： A B E F G C H D I J

树的后序遍历序列： E F G B H C I J D A

二叉树的中序遍历序列： E F G B H C I J D A

二叉树的后序遍历序列： G F E H J I D C B A

注意：① 前序遍历一棵树恰好等价于前序遍历该树对应的二叉树 ②后序遍历一棵树恰好等价于中序遍历该树对应的二叉树.

2、森林的遍历

(1) 前序遍历森林

若森林非空，则：

① 访问森林中第一棵树的根结点 ；

② 前序遍历第一棵树中根结点的各子树所构成的森林

③ 前序遍历除第一棵树外其它树构成的森林。

(2) 后序遍历森林

若森林非空，则：

①后序遍历森林中第一棵树的根结点的各子树所构成的森林

②访问第一棵树的根结点

③后序遍历除第一棵树外其它树构成的森林。

【例】写出如图所示森林的前序遍历和后序遍历的序列和该树对应二叉前序遍历、中序遍历和后序遍历的序列

树的前序遍历序列: A B C D E F G H J K

二叉树的前序遍历序列： A B C D E F G H J K

树的后序遍历序列： B C D A F E J H G K

二叉树的中序遍历序列： B C D A F E J H G K

二叉树的后序遍历序列：D C B F J H K G E A

注意：①前序遍历森林等同于前序遍历该森林对应的二叉树 ② 后序遍历森林等同于中序遍历该森林对应的二叉树。

第六节 哈夫曼树及其应用

一、最优二叉树(哈夫曼树)

1.树的路径长度

树的路径长度是从树根到树中每一结点的路径长度之各。在结点数目相同的二叉树中，完全二叉树的路径长度最短。

2.树的带权路径长度(WPL)

结点的权：在一些应用中，赋予树中结点的一个某种意义的实数。

结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。

树的带权路径长度(WPL):定义为树中所有叶结点的带权路径长度之和。

3.最优二叉树或哈夫曼树

带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树。

【例】给定4个叶子 结点a, b, c和d, 分别带树8, 5, 4和2.构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为: (a): WPL=8×3+5×3+2×1+4×2=49 (b) WPL=8×3+5×2+2×3+4×1=44 (c): WPL=8×1+5×2+2×3+4×3=36

其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

二、哈夫曼算法

1、构造哈夫曼树的方法:

①将给定的权值按照从小到大排列成(W1, W2, ... ， Wm),并且构造出树林F={T1, T2，..., Tm}。此时，其中的每棵树Ti(1<=i<=m)为左、右子树均为空的二叉树，二叉树的根结点的权值为Wi。

②把F中树根结点的权值最小的两棵二叉树T1和T2合并为一棵新的二叉树T(T的左子树为T1, 右子树为T2), 并令T的根结点的权值为T1和T2的根结点的权值之和，然后将T按其根结点的权值大小依次加入树林F中。同时，从F中删去T1和T2这两棵二叉树。

③重复步骤②，直到构造成一棵哈夫曼树。

【例】用6个权值分别不6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径他要( ).

【解析】 用6个权值构造的过程如下图

构造的哈夫曼树的带权路径长度=(16+18+30)×2 + 13 ×3 +(6+7)×4=219

2、哈夫曼树的特点：

① 在哈夫曼树中，权值越大的叶子离根结点越近。

② 若有n0个权值，需要进行n0-1次合并，构造成为哈夫曼树。

③ 哈夫曼树没有度为1的结点。

④ 由n0个权值构成的哈夫曼树，叶结点数为n0, 度为2的结点数为n0-1,结点总数为n0+n2=n0+n0-1=2n0-1。

⑤给定一组权值，构造出的哈夫曼树的形态可能不唯一，但它们的带权路径长度都一样。

三、哈夫曼编码

1、编码的概念

(1)编码和解码

数据压缩过程称为编码。即将文件中的每个字符均转换为一个唯一的二进制位串。

数据解压过程称为解码。即将二进制位串转换为对应的字符。

(2)前缀码方案

对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码。

【例】下述编码中不是前缀码的是( )

A。 (00, 01, 10, 11) B (0， 1， 00， 11) C (0, 10, 110, 111) D (1, 01, 000, 001)

【答案】 B 【解析】 四个选项中除选项B外，其它三个选项的编码满足任一字符的编码都不是其它字符的编码的前缀。

2、哈夫曼编码

设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作为权构造一棵哈夫曼树，由哈夫曼树求得的编码就是哈夫曼编码

【例】假设通信电文使用的字符集为{a, b, c, d, e, f, g, h}, 各字符在电文中出现的频度分别为: 7, 26, 2, 28, 13, 10, 3, 11, 试为这8个字符设计 哈夫曼编码。要求：

(1) 画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值);

(2) 按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。

【解析】先按照权值构造哈夫曼树，注意要满足题目的要求： 树中左孩子结点的权值不大于右孩子结点的权值。构造过程如下图：

答案：(1)

(2)各字符的编码： a(0101), b(10), c(01000), d(11), e(011) f(000) g(01001) h(001)

注意：每个字符的编码都不是另外一个编码的前缀。

第六章 图

第一节 图的基本定义和术语

一、图的定义

图是由顶点的非空有穷集合(用V表示该集合)与项点之间的关系(边或孤)的集合(用E表示该集合)构成的结构。可以形式化表示为G=(V, E)其中，V为项点的非空有穷集合，E为关系的有穷集合。

对于图中任意一条边(Vi, Vj), 若(Vi, Vj)是顶点的无序偶对，这样的图称为无向图。若(Vi, Vj)是顶点的有序偶对，记作<Vi, Vj>, 这样的图称为有向图。直观地判断，无向图中的所有边都不带有箭头，而有向图中的所有边(习惯称之为弧)都带有箭头。边上有权利的图称为带权图，带权的连通图称为网络。

二、图的有关名词术语

(1)顶点的度: 所谓某个项点V的度是依附于顶点的边或弧的数量， 记为D(V)。对于无向图而言，仅此而已。而对于有向图，要区分顶点的出度与入度的概念。所谓一个顶点V的出席是指以该顶点为出发点的弧的数量，记为0D(V)。所谓一个顶点V的入度是指以该顶点为终止点的弧的数量，记为ID(V)。D(V)=0D(V) + ID(V)。

结论： ① 所有顶点的度之和等于边或弧的条数2倍。

②具有n个项点的无向图中边的数目最多为n(n-1)/2, 具有n个项点的有向图中边(弧)的数目最多为n(n-1).

(2)路径： 顶点Vx与Vy之间有路径是指存在着顶点序列Vx, Vi1,Vi2, ..., Vy, 并且序列中相邻两个元素构成的顶点偶对分别表示图中的一条边或弧。这里， 称Vx为出发点，Vy为终止点，出发点与终止点相同的路径称为环或回路。序列中顶点不重复出现的路径称为简单路径。

对于不带权的图，两个项点之间的路径长度是指该路径上所经过的边的数目。对于带权的图，两个项点之间的路径长度是指该路径上所经过的边上的权值之和。

(3)子图：对于图 G=(V, E) 与 G'=(V', E'), 若有V'V, E'E, 则称G‘是G的一个子图。一个图是其自身的子图.

(4) 图的连通

无向图的连通：若项点Vx与Vy之间有路径，就称Vx与Vy是连通的。若图中任意两个顶点之间都有路径，就称该无向图是连通 的。

有向图的连通：若项点Vx与Vy之间有路径，并且顶点Vy与Vx之间也有路径，就称 Vx与Vy是连通的。若图中任意两个项点之间都有连通，就称该有向图是强连通的。

连通分量：无向图中的极大连通子图。任何一个连通图的连通分量只有一个，是它本身。

强连通分量： 有向图中的极大连通子图。

第二节 图的存储结构

对于具有n个项点的图，最常采用的存储方法有邻接矩阵存储方法与邻接表存储方法。

一、邻接矩阵表示法

1、邻接矩阵

设 G=(V, E)是具有n个项点的图，则G的邻接矩阵是具有如下定义的n阶方阵:

【例】

2、采用邻接矩阵存储方法具有以下特点：

①无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上(或者下)三角形阵的元素即可。②不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵(特别是对于稀疏图)， 于是可可以采用三元组表的方法存储邻接矩阵。③对于无向图， 邻接矩阵的第i行(或者第i列)非零元素(或者非∞元素)的个数正好是第i个项点的度D(Vi)。④对于有向图，邻接矩阵的第i行(或者第i列)非零元素(或者非∞元素)的个数正好是第i个项点的出度OD(Vi)(或者入度ID(Vi))。⑤对于无向图，邻接矩阵的所有非零元素(或者非∞元素)的个数正好是边数的2倍。 ⑥对于有向图，邻接矩阵的所有非零元素(或者非∞元素)的个数正好等于弧数。 ⑦一个图的邻接矩阵表示是唯一的。 

3、邻接矩阵表示的存储结构定义

#define MaxVertexNum 50        //最大顶点数
typedef char VertexType;
typedef int Adjmstrix;
typedef struct {               //邻接矩阵表示的存储结构定义VertexType vexs[MaxVertexNum];        //顶点数组，类型假定为char型Adjmstrix arcs[MaxVertexNum][MaxVertexNum];    //邻接矩阵，假定为int型
} MGraph;

4、建立一个无向网的算法

【算法描述】

void CreateGrahp(MGraph* G, int n, int e)
{//采用邻接矩阵表示法构造无向网G，n, e表示图的当前顶点数和边数int i, j, k, w;scanf("%d, %d", &n, &e);   //读入顶点数和边数for (i = 0; i < n; i++)       //输入顶点信息{scanf("%c", &G->vexs[i]);}for (i = 0; i < n; i++){for (j = 0; j < n; j++){G->arcs[i][i] = INT_MAX;                   //初始化邻接矩阵元素为无穷大，一般填32767}for (k = 0; k < e; k++)                        //读入e条边，建立邻接矩阵{scanf("%d, %d", &i, &j, &w);               //读入一条边的两端顶点序号i, j 及边上的权WG->arcs[i][j] = w;G->arcs[j][i] = w;                         //置矩阵对称元素权值}}
}

算法的时间复杂度O(n^2)

二、邻接表表示法

1、邻接表

对于具有n个顶点的图建立n个线性链表。每一个链表最前面都分别设置一个称之为顶点表结点，n个项点构成一个数组结构。第i个链表中的每一个链结点称之为边表结点。

【例】

2、采用邻接表存储方法具有以下特点：

① 一个图的邻接表表示法不唯一，这是因为邻接表中各结点的链接次序取决于建立邻接表的算法(前插法还是后插法建链表)及边的输入次序、

② 对于无向图，若它有n个顶点，e条边，则其邻接表中需要2e+n个结点。其中有2e个边表结点，n个顶点表结点。边表结点。边表结点的个数一 定是偶数，为边数的2倍。

③ 对于有向图，若它有n个项点，e条边，则其邻接表中需要e+n个结点。其中有e个边表结点，n个顶点表结点。

④ 对于无向图，第i个链表中的边表结点的数目是第i个项点的度。

⑤ 对于有向图，第i个链表中的边表结点的数目是第i个顶点的出度。在其逆邻接表中，第i个链表中的边表结点的数目是第i个顶点的入度。

3、图的邻接表存储结构定义

#define MaxVertexNum 20
typedef char VertexType;
typedef struct node //边表结点类型
{int adjvexj;                  //顶点的序号struct node* next;            //指向下一条边的指针
} EdgeNode;
typedef struct vnode     //顶点表结点
{VertexType vertex;              //顶点域EdgeNode* link;                 //边表头指针
}VNode, Adjlist[MaxVertexNum];      //邻接表
typedef Adjlist ALGraph;           //定义为图类型

4、无向图邻接表的建表算法：

void CreateGraph(ALGraph GL, int n, int e)
{//n为项点数， e为l图的边数int i, j, k;EdgeNode* p;for (i = 0; i < n; i++){GL[i].vertex = getchar();      //建立顶点表GL[i].link = NULL;             //边表头指针置空}for (k = 0; k < e; k++)             //采用头插法建立每个顶点的邻接表。{scanf("%d, %d", &i, &j);    //读入边(vi, vj)的顶点序号p = (EdgeNode*)malloc(sizeof(EdgeNode));  //生成新的边表结点p->adjvexj = j;  //将邻接点序号j赋给新结点的邻接点域p->next = GL[i].link;GL[i].link = p;   //将新结点插入到顶点Vi的边表头部p = (EdgeNode*)malloc(sizeof(EdgeNode));   //生成新的边表结点p->adjvexj = i;    //将邻接点序号i赋给新结点的邻接点域p->next = GL[j].link;GL[j].link = p;   //将新结点插入到顶点vj的边表头部}
}

算法的时间复杂度0(n+e)建立有向图的邻接表更加简单，每当读入一个顶点对<i, j>时，仅需要生成一个邻接点序号为j的边表结点，将其插入到Vi的出边表头即可。

第三节 图的遍历

图的遍历：从某个顶点出发，沿着某条搜索路径对图中每个顶点做且仅做一次访问。图的遍历最常用的是深度优先搜索遍历和广度优先搜索遍历两种方法。

一、深度优先搜索遍历

1、深度优先搜索遍历思想：

深度优先搜索(Depth First Search, DFS)遍历类似于树的前序(先根)遍历。假设初始状态是图中所有顶点都未曾访问过，则可以从图G中任选一顶点V为初始出发点，首先访问出发点V, 并将其标记为已访问过；然后依次从V出发搜索V的每个邻接点W,若W未曾访问过，则以W做为新的出发点出发，继续进行深度优先遍历，直到图中所有和V有路径相通的顶点都被访问到;若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述过程，直到图中所有顶点都被访问到为止。

【例】

从V0开始的深度优先搜索序列： V0, V1, V2, V5, V4, V6, V3, V7, V8.

从V8开始的深度优先搜索序开：V8, V4, V0, V1,V2, V5, V3, V6, V7.

2、以邻接矩阵为存储结构的深度优先搜索遍历算法

//以邻接矩阵为存储结构的深度优先搜索遍历算法
int visited[20];
void DFS(MGraph G, int i, int n)
{//从顶点Vi出发，深度优先搜索遍历图G(邻接矩阵结构)int j;printf("V%d->", i);    //假定访问项点vi以输出该顶点的序号代之visited[i] = 1;        //标记vi已访问过for (j = 0; j < n; j++)     //依次搜索vi的每个邻接点{if (G.arcs[i][j] == 1 && !visited[j]){DFS(G, j, n);      //若(vi, Vj)∈(G), 且Vj未被访问过，则从开始递归调用}}
}

该算法的时间复杂度为O(n^2)

3、以邻接表为存储结构的深度优先搜索遍历算法

//以邻接表为存储结构的深度优先搜索遍历算法
int visited[20];       //全局量数组， 用以标记某个顶点是否被访问过
void DFSI(ALGraph G, int i)
{//从顶点Vi出发， 深度优先搜索遍历图G(邻接表结构)EdgeNode* p;int j;printf("V%d->", i);          //假定访问顶点Vi以输出该顶点的序号代之visited[i] = 1;      //标记vi已访问过p = G[i].link;       //取Vi邻接表的表头指针while (p != NULL){j = p->adjvexj;   //j为vi的一个邻接点序号if (!visited[j]){DFSI(G, j);    //若(vi, Vj)∈(G), 且Vj未被访问过，则从开始递归调用	}p = p->next;         //使p指向vi的下一个邻接点}
}

该算法的时间复杂度为O(n+e)。

二、广度优先搜索遍历

1.广度优先搜索遍历思想

广度优先搜索(BFS)遍历类拟于树的按层次遍历。其基本思想是: 首先访问出发点Vi,接着依次访问Vi的所有未被访问过的邻接点Vi1， Vi2， ...， Vit， 并均标记为已访问过，然后再按照Vi1, Vi2, ..., Vit的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依次类推，直到图中所有和初始出发点Vi有路径想通的顶点都被访问过为止。

【例】

从V0开始的广度优先搜索序列: V0, V1, V3, V4，V2, V6, V8, V5, V7。

从V8开始的广度优先搜索序列：V8, V4, V0, V1, V6, V3， V2, V7, V5。

2、以邻接矩阵为存储结构的广度优先搜索遍历算法

//以邻接矩阵为存储结构的广度优先搜索遍历算法
int visited[20];
void VBFS(MGraph G, int i, int n)
{//从顶点Vi出发， 广度优先搜索遍历图G(邻接矩阵结构)CirQueue Q;       //定义一个队列int k, j;InitQueue(&Q);      //初始化队列printf("v%d->", i);    //假定访问顶点Vi用输出该顶点的序号代之visited[i] = 1;        //标记Vi已访问过EnQueue(&Q, i);        //将已访问的顶点序号i入队while (!QueueEmpty(&Q))      //当队列非空时，循环处理Vi的每个邻接点{k = DeQueue(&Q);        //删除头元素for (j = 0; j < n; j++)    //依次搜索Vk的每一个可能的{if (G.arcs[k][j] == 1 && !visited[j]){printf("V%d->", j);     //访问未曾访问过的顶点vjvisited[j] = 1;         //标记Vi已访问过EnQueue(&Q, j);         //顶点序号j入队}}}
}

该算法的时间复杂度为O(n^2)。

3、以邻接表为存储结构的广度优先搜索遍历算法

//以邻接表为存储结构的广度优先搜索遍历算法
void BFSI(ALGraph G, int i, int n)
{//从顶点出发，广度优先搜索遍历图GCirQueue Q;     //定义一个队列指针 int j, k;InitQueue(&Q);  //初始化队列EdgeNode* p;int visited[20];printf("V%d->", i);  //假定访问顶点vi以输出该顶点的序号代之visited[i] = 1;        //标记Vi已访问过EnQueue(&Q, i);      //将已访问的顶点序号i入队while (!QueueEmpty(&Q))    //循环处理Vi的每个邻接点{k = DeQueue(&Q);       //删除头元素p = G[k].link;         //取Vk邻接表的表头指针while (p != NULL)       //依次搜索Vk的每一个可能的邻接点{j = p->adjvexj;       //Vj为Vk的每一个可能的邻接点if (!visited[j])    //若Vj未被访问过{printf("V%d->", j);  //访问未曾访问过的顶点Vjvisited[j] = 1;      //标记Vj已访问过EnQueue(&Q, j);      //顶点序号j入队}p = p->next;   //使p指向Vk邻接表的下一个邻接点}}
}

该算法的时间复杂度O(n+e)。

注意：由于图G=(V, E)中项点集合V与边的集合E中元素的排列是任意的，在采用邻接表存储以后，如果存放顶点结点的先后顺序不同，或者边结点的链接次序不同，在按照某种方式遍历图时，将会影响到顶点被访问的先后顺序，即经过遍历得到的遍历序列有可能不同。 即使存储结构确定，如果指定的出发顶点不同，遍历结果也会不同。当然，对于某种已经确定的存储结构与指定的出发顶点，按照某种遍历方法得到的遍历结果应该是唯一的。

第四节 图的生成树和最小生成树

一、图的生成树

1、生成树的概念 对于具有n个顶点的连通图，包含了该图的全部n个顶点，仅包含它的n-1条边的一个极小连通子图被称为生成树。一个图的生成树为一个无回路的连通图。也就是说，若在图中任意添加一条边，就会出现回路；若在图中去掉任何一条边，都会使之成为非连通图。一个连通图的生成树不一定是唯一的。

【例】下图中的(b)和(c)是图(a)的生成树。

由深度优先搜索所得的生成树称为深度优先生成树，简称为DFS生成树，而由广度优先搜索所得的生成树称之为广度优先生成树，简称为BFS生成树。

【例】下图中图(b)是图(a)从V0开始的深度优先搜索所得的生成树，图(c)是图(a)从V0开始的广度优先搜索的生成树。从V0开即时的深度优先搜索序列：

从V0开始的深度优先搜索序列： V0, V1, V2, V5, V4, V6, V3, V7, V8。

从V0开始的广度优先搜索序列：V0, V1, V3, V4, V2, V6, V8, V5, V7。 

二、最小生成树

1、最小生成树的概念

对于连通的带权图(网)G，其生成树也是带权的。把生成树各边的权值总和称为该树的权，把权值最小的生成树称为图的最小生成树(Mininum Spanning Tree, MST)。

【例】图(b)、(c)、(d)是图(a)的三棵生成树。

2、普里姆(Prim)算法

(1) 算法思想

用自然语言描述的Prim算法：设G=(V, GE)为具有n个顶点的带权连通图， T=(U, TE)为G的一个子图，初始时，有TE=空， U={VI}, VI∈V。Prim算法描述为： 从G中选择一个顶点仅在V中，而另一个顶点在U中，并且权值最小的边加入集合TE中，同时将该边仅在V中的那个顶点加入集合U中。重复上述过程n-1次，直到U=V，此时T为G的最小生成树。

【例】试用Prim算法构造(a)图的最小生成树，要求分步给出构造过程

【分析】算法一开始取u={1}, 然后到V-U中找一条代价最小且依附于顶点1的边，(uo, vo)=(1, 3), 将vo=3加入集合U中，修改辅助数组中的值。使minedge[3].lowcost=0,以表示顶点3已并入U,由于边(3,6)上的权值是一条最小且依附于顶点集U中顶点的边，因此修改minedge[6]的值，依此类推，直到U=V，其过程如表所示。

(2)算法描述

附设一个辅助数组minedge[vtxptr], 记录从U到V-U具有最小代价的边。对每个顶点v∈V-U，在辅助数组中存在一个分量minedge[v], 它包括两个域，其中lowcost存储该边上的权值，ver域存储该边的依附在U中的顶点。Minedge[v]=min{cost(u,v), u∈U}, (cost(u, v)表示该边的权)。

​缺算法

普里姆算法的时间复杂度是o(n^2)

【例】试用Prim算法构造下图的最小生成树，画出所有可能的情况。

【解析】根据Prim算法构造，本题的最小生成树有图有两种。

【答案】最小生成树图有两种，如下图所示

3、克鲁斯卡尔(krtskal)算法

(1)算法思想： 假设G=(V, E)是一个具有n个顶点的连通网，T=(U, TE)是G的最小生成树，U的初值等于V， 即包含有G中的全部顶点。T的初始状态是只含有n个顶点而无边的森林T=(V, ∅)。该算法的思想是： 将图中G的边按权值从小到大的顺序依次选取E中的边(u, v),若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树T形成回路，则将其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T即为最小生成树。

【例】试用克鲁斯卡尔(Krtskal)算法构造(a)图的最小生成树，要求分步给出构造过程

(2)算法描述

​​缺算法

克鲁斯卡尔算法的时间复杂度为O(eloge)。

注意：一个网中，若有权值相同的边，则其最小生成树不一定唯一；若所有边的权值均不相同，则其最小生成树是唯五的。

第五节 最短路径

1.最短路径的问题

最短路径问题的提法很多，在这里仅讨论单源最短路径问题：从某个源点S∈V到G中其余各顶点的最短路径。对于求多源点的最短路径问题，可以用每个顶点作为源点调用一次单源最短路径问题算法予以解决。

【例】下图所示带权有向图，假定以v1为源点，则v1到其他各顶点的最短路径下表所示。

2、迪杰斯特拉(Dijkstra)算法

该算法是典型的最短路径路由算法，用于计算一个顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。

【算法思想】创建三个数组，数组S记录了当前从源点到该顶点存在最短路径的顶点集合；数组dist(简称)记录当前状态源点到图中其余各顶点之间的最短路径长度；数组path(简称P)是最短路径的路径数组，其中path[j]表示从源点到顶点j的最短路径上顶点的前驱顶点。每一次循环都是从数组D中选择未被加入到数组S中的顶点到源点路径最短的顶点加入到数组S中，然后对数组D和数组P进行修改，直到所有顶点都加到了数组S中为止。

【例】已知有向图如图所示，根据迪杰斯特拉算法画出求源点v1开始的单源最短路径的过程示意图，以及算法的动态执行过程。

迪杰斯特拉算法的动态执行情况

第六节 拓扑排序

1、拓扑排序的概念

对一有向图，如果从Vi到Vj存在一条路径，且在由图中所有顶点构成的线性序列中，Vi总是在Vj之前，那么这样的线性序列就被称为拓扑列。构造一个有向图的拓扑序列的过程称为拓扑排序。一个有向图必须满足两个条件存在拓扑序列：

①初始时有向图中必须至少有一个入度为0的顶点。

②有向图中不存在回路。

满足以上两条的有向图称为AOV网。

2、拓扑排序过程是：

①从有向图中选择一个入度为0的顶点;

②从有向图中将该顶点以及由该顶点发出的所有弧全部删除;

③重复上述过程，直到剩余的网中不再存在入度为0的顶点。

【例】

拓扑排序的结果为： C1，C4，C2，C7，C9，C3，C6，C5，C8

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

第七章 排序

第一节 基本概念

1、排序(sort)的概念

所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。

2、排序的稳定性

在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

注意：

排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

3、排序方法的分类

(1) 按是否涉及数据的内、外存交换分

在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序); 反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。

注意： ①内排序适用于记录个数不很多的小文件 ②外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。

(2)按策略划分内部排序方法

内部排序可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。

4.排序算法性能评价

(1)评价排序算法好坏的标准

① 执行算法需要的时间

② 算法所需的辅助空间

③ 算法本身的复杂程度

(2)排序算法的时间开销

一般情况下，用算法执行中关键字之间的比较次数和记录的移动次数来衡量。

(3)排序算法的空间复杂度

若排序算法所需的辅助空间并不依赖于问题的规模n, 空间复杂度是O(1)， 则称这样的排序为就地排序。非就地排序的空间复杂度是一般为O(n)。

5、待排序记录的数据类型定义

#define MAXSIZE 100       //假设的文件长度，即待排序的记录数目
typedef int KeyType;     //假设的关键字类型
typedef char InfoType;
typedef struct     //记录类型
{KeyType key;       //关键字项InfoType otherinfo;  //其它数据项，类型InfoType 依赖于具体应用而定义
} RecType;
typedef RecType SeqList[MAXSIZE + 1];    //SeqList为顺序表类型， 表中第0个单元一般用作哨兵

第二节 插入排序

插入排序(Insertion Sort)的基本思想是： 每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。插入排序主要包括：直接插入排序和希尔排序。

一、直接插入排序

1、排序思想

假设待排序的记录存放在数组R[1..n]中，初始时，R[1]自成1个有序区，无序区为R[2..n].从i=2起直到i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

2、实例分析

【例】给定一组关键字(46, 39, 17, 23, 28, 55, 18, 46),要求按直接插入排序算法给出每一趟排序结果。

3、算法描述

#define ListSize 100   //表的大小根据实际需要定义， 这里假设为100
typedef int DataType;   //DataType的数据类型根据实际情况而定，这里定义为int
typedef struct {DataType key;                //数组data用来存放表结点
} SeqList[ListSize], RecType;;             //顺序表的数据类型名void InsertSort(SeqList R, int n)
{//对顺序表R做直接插入排序int i, j;for (i = 2; i <= n; i++){if (R[i].key < R[i - 1].key)         //若R[i].key  < R[i - 1].key , 移动{R[0].key = R[i].key;      //当前记录复制为哨兵for (j = i - 1; R[0].key < R[j].key; j--)   //找插入位置{R[j + 1].key == R[j].key;    //记录后移}R[j + 1].key = R[0].key;    //R[i]插入到正确的位置}}
}

4、算法分析

(1)哨兵的作用

算法中引进的附加记录R[0]称为哨兵(Sentinel), 哨兵有两个作用：

① 进入查找(插入位置)循环之前，它保存了R[i]的副本，不致于因记录后移而丢失R[i]的内容;

② 它的主要作用是:在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0), 因为R[0].key 和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1"), 使得测试查找循环条件的时间大约减少了一半。

(2) 算法的时间性能分析 、

对于具有n个记录的文件，要进行n-1趟排序

各种状态下的时间复杂度：

(3)算法的空间复杂度分析

算法所需的辅助空间是一个监视哨，辅助空间复杂度S(n)=O(1).是一个就地排序。

(4)直接插入排序是稳定的排序方法。

二、希尔排序

1、排序思想

先取一个小于n的整数d1作为第一个增量，把文伯的全部记录分成d1个组。所有距离为d1的位数的记录放在同一组中。先在各组内进行直接插入排序; 然后，取第二个增量d2 < d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-1<...<d2<d1),即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

2、实例分析

初始关键字序列为(36, 25, 48, 27, 65, 25, 43, 58, 76, 32)。

其增量序列的取值依次为5, 3, 1, 排序过程如图所示。

3、算法描述

void ShellInsert(SeqList R, int dk, int n)
{ //希尔排序中的一趟插入排序，dk为当前增量int i, j;for (i = dk + 1; i <= n; i++)       //将R[dk + 1 ... n]分田中插入有序区{if (R[i].key < R[i - dk].key){R[0].key = R[i].key;   //暂存在R[0]中;j = i - dk;while (j > 0 && R[0].key < R[j].key){R[j + dk] = R[j];        //记录后移，查找插入位置j = j - dk;}R[j + dk] = R[0];            //插入R[i]到正确的位置}}
}void ShellSort(SeqList R, int d[], int t, int n)
{  //按增量序列d[0...t-1]对顺序表R作希尔排序int k;for (k = 0; k < t; k++){ShellInsert(R, d[k], n);}
}

4、算法分析

(1) 增量序列的选择

① 最后一个增量必须为1；

② 应该尽量避免序列中的值(尤其是相邻的值)互为位数的情况。

(2)Shell排序的时间性能优于直接插入排序，实验表明，当n较大时，比较和移动的次数约在n1.25到136n1.25之间。

(3)算法的空间复杂分析

算法空间复杂度为O(1)。是一个就地排序。

(4)稳定性

希尔排序是不稳定的。

第三节 交换排序

交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有： 冒泡排序和快速排序。

一、冒泡排序

1.排序思想 通过相邻元素之间的比较和交换，使关键字较小的元素逐渐从底部移向顶部，关键字较大的元素逐渐下移(后移)，小的上浮，大的下沉，所以冒泡排序有被称为"起泡"排序。

第一趟扫描： 依次比较(R[n], R[n-1]), (R[n-1], R[n-2]), ..., (R[2], R[1]); 对于每对气泡(R[j+1]， R[j]), 若R[j+1].key < R[j].key, 则交换R[j+1]和R[j]的内容。第一趟扫描完毕时，“最轻”的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上，然后再对R[n]-R[2]的记录进行第二趟排序，使次小关键字的元素被上浮到R[2]中，重复进行，n-1趟后，整个冒泡排序结束。

2、实例分析

【例】有8个记录的关键字序列为(36, 28, 45, 13, 67, 36, 18, 56)，如下图所示为该序列起泡排序的全过程。

3、算法描述

void BubbleSort(SeqList R, int n)
{ //采用自底向上扫描数组R[1, ... n] 做冒泡排序int i, j, flag;for (i = 1; i < n; i++)   //最多做n-1趟排序{flag = 0;        //flag表示每一趟是否有交换，先置0for (j = n; j >= i + 1; j--)   //进行第i趟排序{if (R[j].key < R[j - 1].key){R[0].key = R[j - 1].key;       //R.data[0]作为交换时的暂存单元R[j - 1].key = R[j].key;       //相邻两个元素完成交换R[j].key = R[0].key;flag = 1;                          //有交换，flag置1}}if (flag == 0){return;}}
}

4、算法分析

(1) 算法的最好时间复杂度： 若待排序记录为有序(最好情况), 则一趟扫描完成，关键比较次数为n-1次且没有移动，比较的时间复杂度为O(n)。

(2) 算法的最坏时间复杂度： 若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1<=i<=n-1),且每次比较都必须移动记录三次来达到交换记录位置。总的比较次数为(n-1)+(n-2)+...+1=n(n-1)/2; 总的移动次数为3n(n-1)/2。在平均情况 下，比较和移动记录的总次数大约为最坏情况下的一半，所以，冒泡排序算法的时间复杂度为O(n²)。

(3) 算法的空间复杂度： 冒泡排序的空间复杂度为O(1), 是就地排序。

(4) 算法稳定性; 冒泡排序是稳定的.

【例】设计一个修改冒泡排序算法以实现双向冒泡排序的算法。

双向冒泡排序则是交替改变扫描方向，即一趟从下向上通过两个相邻关键字的比较，将关键字最小的记录换至最上面的位置 ，再一趟则是从第二个记录开始向下通过两个相邻记录关键字的比较，将关键字最大的记录换至最下面的位置;然后再从倒数第二个记录开始向上两两比较至顺数第二个记录，将其中关键字较小的记录换至第二个记录位置，再从第三个记录向下至倒数第二个记录两两比较，将其中较大关键字的记录换至倒数第二个位置，依此类推，直到全部有序为止。

void DbubbleSort(SeqList R, int n)
{//自底向上，自顶向下交替进行双向扫描冒泡排序int i = 1, j;RecType recType;int NoSwap;            //表示一趟扫描是否有交换，为假无交换NoSwap = 1;            //首先假设有交换，表无序.while (NoSwap)          //当有交换时做循环{NoSwap = 0;         //置成无交换for (j = n - i + 1; j >= i + 1; j--)   //自底向上扫描{if (R[j].key < R[j - 1].key)   //若反序(后面的小于前一个), 即交换{recType = R[j];R[j].key = R[j - 1].key;R[j - 1] = recType;NoSwap = 1;                   //说明有交换}}for (j = i + 1; j <= n - i; j++)       //自项向下扫描{if (R[j].key > R[j + 1].key)   //若反序(前面的大于后一个)， 即交换{recType = R[j];R[j].key = R[j + 1].key;R[j + 1] = recType;NoSwap = 1;                    //说明有交换}}i = i + 1;}	
}

二、快速排序

1、排序思想： 快速排序的基本思想是：首先在当前无序区R[low ... high]中任取一个记录作为排序比较的基准(不妨设为x), 用此基准将当前无序区划分为两个较小的无序区R[low...i-1]和R[i+1...high]，并使左边的无序区中所有记录的关键字均小于等于基准的关键字，而基准记录x则位于最终排序的位置i上，这个过程称为一趟快速排序(或一次划分).当R[low...i-1]和R[i+1...high]均非空时，分别对它们进行上述划分，直到所有的无序区中的记录均已排好序为止。一趟快速排序的具体操作是：设两个指针i和j, 它们的初值分别为low和high,基准记录x=R[i],首先从j所指位置起向前搜索找到第一个关键字小于基准x.key的记录存入当前i所指向的位置上，i自增1,然后再从i所指位置起向后搜索，找到第一个关键字大于x.key的记录存入当前j所指向的位置上,j自减1,重复这两步，直至i等于j为止。

2、实例分析

依次可得各趟排序结果如下:

3、算法描述

int Partition(SeqList R, int i, int j)
{ //对R[i]...R[j]区间内的记录进行一次划分排序RecType x = R[i];     //用区间的第一个记录为基准while(i < j){while (i < j && R[j].key >= x.key){j--;      //从j所指位置起向前(左)搜索}if (i < j){R[i] = R[j];    //后面有的数往前移动i++;}while (i < j && R[i].key <= x.key){i++;                      //从i所指位置起向后(右)搜索}if (i < j){R[j] = R[i];              //前面小的数往前移动   j--;}}R[i] = x;              //基准记录x位于最终排序的位置return i;
}void QuickSort(SeqList R, int low, int high)
{  //对顺序表R中的子区间进行快速排序int p;if (low < high)     //长度大于1{p = Partition(R, low, high);QuickSort(R, low, p - 1);QuickSort(R, p + 1, high);}}

4、算法分析

(1) 算法时间复杂度 快速排序的时间复杂度为O(n㏒₂n)。快速排序方法被认为是排序时间效率非常高的一种方法，但是，当参加排序的原始序列已经是一个按值或基本有序的序列时，快速排序方法的时间效率将降到最低，这种情况下其时间复杂度为O(n²)

(2) 算法空间复杂度 快速排序的空间复杂度为O（log₂n）。

(3) 算法的稳定性 快速排序方法是一种不稳定的排序方法。

第四节 选择排序

选择排序(Selection Sort)的基本思想是：每一趟从特排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。

一、直接选择排序

1、排序思想

直接选择排序(Straight Select Soft)是一种简单的排序方法。它的基本思想是：每次从待排序的无序区中选择出关键字值最小的记录，将该记录与该区中的第一个记录交换位置。初始时，R[1...n]为无序区，有序区为空。第一趟排序是在无序区R[1...n]中选出最小的记录，将它与R[1]交换R[1]为有序区；第二趟排序是在无序区R[2...n]中选出最小的记录与R[2]交换，此时R[1...2]为有序区;依此类推，做n-1趟排序后，区间R[1...n]中记录递增有序。

2、实例分析

【例】 一组关键字(38, 33, 65, 82, 76, 38, 24, 11)，直接选择排序过程。

3、算法描述

void SelectSort(SeqList R, int n)
{  //对R作直接选择排序int i, j, k;for (i = 1; i < n; i++)     //做n-1趟排序{k = i;                  //设k为第i趟排序中关键字最小的记录位置for (j = i + 1; j <= n; j++)    //在[i...n]选择关键字最小的记录{if (R[j].key < R[k].key){k = j;                  //若有比R[k].key小的记录，记住该位置}}if (k != i)                    //与第i个记录交换{R[0] = R[i];R[i] = R[k];R[k] = R[0];}}
}

4、算法分析

(1)时间复杂度

无论文件初始状态如何，在第i趟排序中选出最小关键字的记录需要做n-i次比较，总比较次数为(n-1)+(n-2)+...+1=n(n-1)/2; 当初始文件为正序时，移动次数为0; 文件初态为反序时，每趟排序均要执行交换操作，每次交换需要移动3次，总的移动次数取最大值3(n-1).

直接选择排序的平均时间复杂度为O(n²)。

(3) 空间复杂度 直接选择排序的空间复杂度是O(1)，是一个就地排序。

(4) 稳定性 直接选择排序是秒稳定的。

【例】 假设采用不带头结点的单链表作为存储结构，试缩写一个直接发选择排序(升序)的算法。

设单链表结点类型和链表类型的定义如下：

typedef int DataType;typedef struct node {                      //结点类型定义DataType data;                        //结点数据域struct node* next;                    //结点指针域
} ListNode;typedef ListNode* LinkList;

(1)按直接选择排序算法思想，交换结点的数据域和关键字域值的算法。

void LSelectsort1(LinkList head)
{ //先找最小的和第一个结点交换，再找次小的和第二个结点交换, ... ，以此类推ListNode* p, * r, * s;ListNode q;p = head;while (p != NULL)      //假设链表不带头结点{s = p;             //s为保存当前关键字最小结点地址指针r = p->next;while (r != NULL)      //向后比较，找关键字值最小结点{if (r->data < s->data)      //若r指向结点的关键字值小，使s指向它{s = r;}r = r->next;             //比较下一个}if (s != p)            //说明有关键字值比s的关键字值小的结点，需交换{q = (*p);          //整个结点记录赋值p->data = s->data;s->data = q.data;}p = p->next;     //指向下一个结点}
}

(2) 按直接选择排序算法思想， 每次选择到最小的结点后，将其脱链并加入到一新链表中，这样可避免结点域值交换，最后将新链表的头指针返回。

LinkList LSelectSort2(LinkList head)
{//找最小的为新表的第一个结点， 找次小的作为第二个结点，...，依次类推ListNode* p, * q, * r, * s, * t, * t1;t = NULL;               //置空表，采用尾插法建立新链表while (head != NULL){s = head;          //先假设s指向关键字最小值的结点p = head; q = NULL;   //q指向这的前趋结点r = NULL;while (p != NULL){if (p->data < s->data)        //使s指向当前关键字值小的结点{s = p;                    //使r指向s的前一个结点r = q;       }q = p; p = p->next;           //指向后续结点}if (s == head)                    //没发现更小的{head = head->next;            //删除第一个结点}else{r->next = s->next;           //删除最小结点    }if (t == NULL){t = s;t1 = t;                     //t1指向新表的当前结点}else{t1->next = s;               //插入新结点t1 = s;}}t1->next = NULL;return t;                           //返回新表头指针
}

二、堆排序

1、堆排序定义

n个关键字序列K1, K2, ..., Kn称为堆，当且仅当该序列满足如下关系：

(1) Ki <= K2i且ki<=K2i+1 或 (2) Ki>=K2i且Ki>=K2i+1(1<=i<=n)

前者称为小根堆，后者称为大根堆。

【列】 关键字序列(76, 38, 59, 27, 15, 44)就是一个大根堆，还可以将此调整为小根堆(15, 27, 44, 76, 38, 59), 它们对应的完全二叉树如图:

2、堆排序的思想

从小到大排序的步骤

第一步：将参加排序的原始序列转换为第一个大根堆(建初始堆)。

第二步：把堆的第一个元素(最大值元素)与堆的最后那个元素交换位置。

第三步： 将在第二步中“去掉”最大值元素后剩下的元素组成的序列重新调整为一个新的堆。

第四步：重复第二步与第第三步n-1次，直到排序结束。

3、实例分析

【例】已知关键字序列为(47, 33, 11, 56,72,61, 25, 47), 采用堆序方法对该序列进行堆排序，画出建初始堆的过程和每一趟排序结果。

第一步： 将参加排序的原始序列转换为第一个大根堆(建初始堆)

第二步： 将根结点(最大值)与最后一个结点调换如下图(a)所示，完成第一趟排序，第一趟排序的结果为： 47 56 61 47 33 11 25 [72]

第三步：将第一趟排序的结果除最后一个元素外的其余结点组成的序列调整为堆，如图(b)所示，然后将根结点与倒数第2个结点调换如下图(c)所示，完成第二趟排序，第二趟排序的结果为：25 56 47 47 33 11 25 [61 72]

第四步：将第二趟排序的结果除最后2个元素外的其余结点组成的序列调整为堆，如图(d)所示，然后将根结点与倒数第3个结点调换如下图(e)所示，完成第三趟排序，第三趟排序的结果为: 11 47 47 25 33 [56 61 72]

第五步： 将第三趟排序的结果 除最后3个元素外的其余结点组成的序列调整为堆，如图(f)所示，然后将根结点与倒数第4个结点调换如图(g)所示，完成第四趟排序，第四趟排序的结果为: 11 33 47 25 [47 56 61 72]

第六步：将第四趟排序的结果除最后4个元素外的其余结点组成的序列调整为堆，如图(h)所示，然后将根结点与倒数第5个结点调换如图(i)所示，完成第五趟排序，第五趟排序的结果为: 25 33 11 [47 47 56 61 72]

第七步：将第五趟排序的结果除最后5个元素外的其余结点组成的序列调整为堆,如图(j)所示，然后将根结点与倒数第6个结点调换如图(k)所示，完成第六趟排序，第六趟排序的结果为:11 25 [33 47 47 56 61 72]。排序结束(8个元素七趟排序)。

第八步：将第六趟排序的结果除最后6个元素外的其余结点组成的序列调整为堆,如图(m)所示，然后将根结点与倒数第7个结点调换如图(n)所示，完成第七趟排序，第七趟排序的结果为:11 [25 33 47 47 56 61 72]。排序结束(8个元素七趟排序)。

4、算法分析

堆排序方法是一种不稳定的排序方法，具有n个数据元素的序列,堆排序方法的排序趟数为n-1,其时间复杂度为O(log₂n),空间复杂度为o(1)。

第五节 归并排序

1、二路归并排序的思想

初始时将特排序序列R[1...n]看成是n个长度为1的有序序列，通过第一趟两两归并后，得到个长度为2的有序序列，然后再两两归并，得到⌈n/4⌉个长度为4的有序序列，如此重复，直到得到一个长度为n的有序序列。

2、实例分析

【例】已知序列(72, 18, 53, 36, 48, 31, 36)，请写出对该序列采用二路归并排序方法进行升序排序时各趟的结果。

【解答】

3、算法描述

4、算法分析

二路归并排序法需要进行趟，其时间复杂度为O(log₂n)，空间复杂度为O(n).是一种稳定的排序方法。

第六节 分配排序

分配排序的基本思想：排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。常用的分配排序有箱排序和基数排序。

一、箱排序

1、箱排序的基本思想：箱排序也称桶排序，其基本思想是：设置若干个箱子，依次扫描待排序的的记录R[0], R[1], ..., R[n-1], 把关键等于k的记录全部装入到第k个箱子里(分配)，然后按序号依次将各非空的牌子首尾连接起来(收集)。

【例】要将一一副混洗的52张扑克牌按点数A<2<...<J<Q<K排序，需设置13个“箱子”，排序时褒奖将每张牌按点数放入相应的箱子里，然后依次将这些箱子首尾相撞，就得到了按点数递增排列的一副牌。

2、算法简析

箱排序的时间复杂度为O(n)。箱排序是稳定排序，箱排序只适用于关键字取值范围较小的情况，否则所需要箱子的数目太多，会导致存储空间的浪费和计算时间的增长。

二、基数排序

基数排序(Radix Sort)是对臬排序的改进和推广。

1、基数排序的思想

基数排序的基本思想是：从低位到高们依次对Kj(j=d-1,d-2,..., 0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd,这就是“基数排序”名称的由来。

2、实例分析

【例】已知关键字序列[278, 109, 063, 930, 589, 184, 505, 269, 008, 083],写出基数排序(升序)的排序过程。

3、算法分析

基数排序的时间复杂度是O(d*(rd+n)。其中rd是基数，d是关键字的位数，n是元素个数。基数排序所需的辅助存储空间为O(n+rd)。基数排序是稳定的。

第七节 内部排序方法的分析比较

1、时间复杂度

(1) 直接插入、直接选择、冒泡排序算法的时间复杂度为O(n²)

(2) 快速、归并、堆排序算法的时间复杂度为O(nlog₂n)。

(3) 希尔排序算法的时间复杂度很难计算，有几种较接近的答案： O(nlog₂n)或O(n1.25)。

(4) 基数排序算法的时间复杂度为O(d*(rd+n))，其中rd是基数，d是关键字的位数， n是元素个数。

2、稳定性

(1) 直接插入、冒泡、归并和基数排序算法是稳定的;

(2)直接选择、希尔、快速和堆排序算法是不稳定的。

3、辅助空间(空间复杂度)

(1)直接插入、直接选择、冒泡、希尔和堆排序算法需要辅助空间为O(1)。

(2)快速排序算法需要辅助空间为O(log₂n);

(3) 归并排序算法需要辅助空间为O(n);

(4) 基数排序算法需要辅助空间为O(n+rd)。

4、选取排序方法时需要考虑的主要因素

(1) 特排序的记录个数。

(2)记录本身的大小和存储结构

(3)关键字的分布情况

(4)对排序稳定性的要求

(5)时间和空间复杂度等

5、排序方法的选取

(1) 若待排序的一组记录数目较小(如 n <=50)时，可采用插入排序或选择排序。

(2) 若n较大时，则应采用快速排序、堆排序或归并排序。

(3) 若待排序记录按关键之际基本有序时，则适宜选用直接插入排序或冒泡排序。

(4) 当n很大，而且关键字位数较少时，采用链式基数排序较好。

(5) 关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。

6、排序方法对记录存储方式的要求

一般的排序方法都可以在顺序结构(一维数组)上实现。当记录本身信息量较大时，为了避免移动记录耗费大量的时间，可以采用链式存储结构。例如插入排序、归并排序、基数排序易于在链表上实现，使之减少记录的移动次数，但有的排序方法，如快速排序、堆排序在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。

第八章 查找

第一节 基本概念

1、查找

查找的定义是： 给定一个值K, 在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。

2、查找表的数据结构表示

(1) 动态查找表和静态查找表

若在查找的同时对表做修改操作(如插入和删除)，则相应的表称之为动态查找表。否则称之为静态查找表。

(2) 内查找和外查找

若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。

(3)平均查找长度ASL

查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。

平均查找长度ASL(Average Search Length)定义为：ASL=

其中：

① n是结点的个数;

③ Ci是找到第i个结点所需进行的比较次数。

③ Pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相乘， 即p1=p2..=pn=1/n, 这时ASL=

第二节 顺序表的查找

顺序表是指线性表的顺序存储结构，具体数据类型定义：

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 100
typedef int KeyType;     //假设的关键字类型
typedef char InfoType;
typedef struct
{KeyType key;InfoType data;
} NodeType;typedef NodeType SeqList[MAXSIZE + 1];    //0号单元用作哨兵

一、顺序查找

1、一般顺序表的查找算法

(1)算法描述

int SeqSearch(SeqList R, KeyType k, int n)
{  //R[0]作为哨兵， 用R[0].key == k作为循环下界的终结条件R[0].key = k;     //设置哨兵int i = n;            //从后向前扫描while (R[i].key != k){i--;}return i;        //返回其下标， 若找不到，返回0
}

(2)算法分析

①查找成功的情况： 最好的情况比较1次，最坏的情况比较n次; 查找成功时的平均查找长度=(1+2+3+...+n)/n=(n+1)/2

②查找失败时的查找长度=(n+1)

③如果查找成功和不成功机会相等，顺序查找的平均查找长度为((n+1)/2 + (n+1))/2 = 3(n+1)/4

2、在递增有序的顺序表的查找算法

(1) 算法描述

//有序表的顺序查找算法
int SeqSearch1(SeqList R, KeyType k, int n)
{int i = n;       //从后向前扫描，表按递增排序while (R[i].key > k){i--;     //循环结束时，要么R[i].key = k, 要么R[i].key < k}if (R[i].key == k){return i;      //找到,返回其下标}return 0;          //没找到，返回0;
}

(2) 算法分析

查找成功的平均查找长度 =

查找失败的平均查找长度 =

如果查找成功和不成功机会相等，该算法的平均查找长度为   ​​​​​​ ​​​​​ (   + ) =

二、二分查找法

对有序表可以用查找效率较高的二分查找方法来实现查找运算。

1、二分查找法的思想

二分查找的思想： 首先将待查的k值和有序表R[1...n]的中间位置mid上的记录的关键字进行比较，若相等，则查找成功，返回该记录的下标mid,否则，若R[mid].key》中，则k在左子表R[1...min-1]中，接着再左子表中进行二分查找即可; 否则，若R[mid].key < k, 则说明待查记录在右子表R[min+1...n]中，接着只要在右子表中进行二分查找即可。这样，经过一次关键字的比较，就可缩小一半的查找空间，如此进行下去，直到找到关键字为k的记录或者当前查找区间为空时(即查找失败)为止。二分查找的过程是递归的。

2、实例分析

【例】对有序表(13, 25, 36, 42, 48, 56, 64, 69, 78, 85, 92)用二分查找法查找42和80，所需的比较次数依次为( )

A。1次和2次， B。 2次和3次 C. 3次和2次 D . 3次和3 次

【答案】 D 【解析】 按二分查找的基本思想给出查找42的过程如下:

查找k=42需要比较3次查找成功。

按二分查找的基本思想给出查找80的过程如下：

3、算法描述

(1) 二分查找递归算法

int BinSearch(SeqList R, KeyType k, int low, int high)
{//在区间R[low...high]内进行二分递归，查找关键字值等于k的记录//low的初始值为1， high的初始值为nint mid;if (low <= high){mid = (low + high) / 2;if (R[mid].key == k){return mid;                 //查找成功，返回其下标}if (R[mid].key > k){return BinSearch(R, k, low, mid - 1);    //在左子表中继续查找}else{return BinSearch(R, k, mid + 1, high);     //在右子表中继续查找}}else{return 0;}
}

(2) 二分查找非递归算法

int BinSearch(SeqList R, KeyType k, int n)      //初始化上下界
{  //二分查找非递归算法int low = 1, mid, high = n;while (low <= high){mid = (low + high) / 2;if (R[mid].key == k){return mid;}if (R[mid].key > k){high = mid - 1;             //修改上界}else{low = mid + 1;               //修改下界}return 0;                       //查找失败，返回0值}
}

4、算法分析

二分查找方法可以用一棵判定树描述，查找任一元素的过程对应该 树中从根结点到相应结点的一条路径。最短的查找长度为1，最长的查找长度为对应判定树的深度

， 平均查找长度为

。 二分查找方法效率高是有代价的，因为有序表是通过排序而得到的，而排序操作又是比较费时的。二分查找只适用于顺序结构上的有序表，对链式结构无法进行二分查找。

5、应用实例

【例】试写一算法，利用二分查找算法在有序表R中插入一个元素x, 并保持表的有序性。

void BinInsert(SeqList R, KeyType x, InfoType y, int n)
{int low = 1, high = n, mid, inspace, i;int find = 0;     //find是作为是否找到与x相等的关键字，先假设未发现while (low < -high && !find){mid = (low + high) / 2;if (x < R[mid].key){high = mid - 1;}else if(x > R[mid].key){low = mid + 1;}else{find = 1;}}if (find == 1){inspace = mid;       //找到关键字与x相等，mid为x的插入位置}else{inspace = low;      //所指向的结点关键字正好大于x,此时low即为插入位置}for (i = n; i >= inspace; i--){R[i + 1] = R[i];     //后移结点，留出插入的空位             }R[inspace].key = x;      //插入结点，x是该结点的关键字，y是其他数据R[inspace].data = y;     //插入结点，x是该结点的关键字，y是其他数据
}

三、索引顺序查找

索引顺序查找又称分块查找。这是一种性能介于顺序查找和二分查找之间的查找方法。

1、索引查找表的存储结构

(1) "分块有序"的线性表

表R[1...n]均分为b块，前b-1块中结点个数为 , 第b块的结点数小于等于s; 每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是"分块有序"的。

(2) 索引表

抽取各块中的最大关键字及其起始位置构成一个索引表ID[1...b], 即ID[i](1<=i<=b)中存放第i块的最大关键字及该块在表R中的起始位置，由于表R是分块有序的，所以索引表是一个递增有序表。

【例】下图就是满足上述要求的存储结构，其中R中有18个结点，被分成3块，每块中有6个结点，第一块中最大关键字21小于第二块中最小关键字23，第二块中最大关键字45小于第三块中最小关键字48。

2、索引查找的基本思想

(1) 首先查找索引表: 索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。(2)然后在已确定的块中进行顺序查找: 由于块内无序，只能用顺序查找.

3、索引查找的平均查找长度

(1) 查找索引表采用二分查找时的平均查找长度 ASLblk=

(2) 查找索引表采用顺序查找时的平均查找长度ASLblk=(b+1)/2 + (s+1)/2 = (b+s)/2 + 1 = (n/s +s) /2 +1=(块数+块长)/2 +1

当s取

(即s=b)时，ASLblk达到最小值+1, 即当采用顺序查找确定块时，应将各块中的结点数选定为

1、顺序查找

优点：算法简单，对表的存储结构无任何要求.

缺点: 查找效率低，查找成功的平均查找长度为(n+1)/2, 查找失败的查找长度为(n+1)。

2、二分查找

优点：二分查找的速度快，效率高，查找成功的平均查找长度约为log2(n+1)-1。

缺点：要求表以顺序存储表示并且是按关键字有序，使用高效率的排序方法也要花费O(nlog2n)的时间。另外，当对表结点进行插入或删除时，需要移动大量的元素，所以二分查找适用于表不易变动且又经常查找的情况。

3、分块查找

优点：在表中插入或删除一个记录时，只要找到该记录所属的块，就可以在该块内进行插入或删除运算。因为块内记录是无序的，所以插入或删除比较容易，无需移动大量记录。

缺点：是需要增加一个辅助数组的存储空间和将初始表块排序的运算，它也不适宜链式存储结构。

此处，顺序查找、二分查找和分块查找三种查找算法的时间复杂度分别为O(n)、O(log2n)和o()。分块查找算法的效率介于顺序查找和二分查找之间。

第三节 树表的查找

一、二叉排序树

1、二叉排序树的概念

(1) 二叉排序树的定义：二叉排序树(Binary Sort Tree, BST)又称二叉查找，是一种特殊的二叉树，二叉排序树或者是空树，或者是满足如下性质的二叉树： ①若它的左子树非空，则左子树上所有结点的值均小于根结点的值; ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值; ③左、右子树本身又各是一棵二叉排序树。

【例】下图的就是一棵二叉排序树

中序遍历序列: 15， 16， 18， 19， 20， 22， 30， 35， 42

(2) 二叉排序树的重要性质

中根遍历一棵二叉排序树所得的结点访问序列是按键值的递增序列。

(3) 二叉排序树的数据类型定义

typedef int DataType;
typedef struct node
{KeyType key;                //关键字DataType other;             //其他数据域struct node* lchild, * rchild;    //左右子树指针
} BSTNode;                      //结点类型
typedef BSTNode* BSTree;

2、二叉排序树的插入

(1) 算法思想：在二叉排序树中插入新结点，要保证插入后仍满足BST性质。其插入过程是：

① 若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；

② 若二叉 排序树T不为空，则将Key和根的关键字比较：

若二者相等，则说明树中已有此关键字key,无须插入。

若key<T->key,,则将key插入根的左子树，

若key>T->key,则将它插入根的右子树中。

子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将Key作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。

(2) 算法描述

BSTree InsertBST(BSTree T, BSTNode* S)
{BSTNode* f, * p = T;while (p)        //找插入位置{f = p;       //f记录p的双亲，为将来插入结点if (S->key < p->key){p = p->lchild;}else{p = p->rchild;}}if (T == NULL){T = S;            //T为空树， 新结点作为根结点}else if (S->key < f->key){f->lchild = S;      //作为双亲的左孩子插入     }else{f->rchild = S;     //作业双亲的右孩子插入}return T;
}

3、二叉排序树的生成

(1) 算法思想： 从空的二叉树开始，每输入一个结点数据 ，生成一新结点，就调用一次插入算法将它插入到当前生成的二叉排序树中

(2) 算法描述

BSTree CreateBST(void)
{   //从空树开始，建立一棵二叉排序树BSTree T = NULL;     //初始化T为空树KeyType key;BSTNode* S;scanf_f("%d", &key);       //输入第一个关键字while (key)                //假设key=0是输入结束{S = (BSTNode*)malloc(sizeof(BSTNode));S->key = key;                  //生成新结点S->lchild = S->rchild = NULL;  T = InsertBST(T, S);           //将新结点*S插入二叉排序树Tscan_f("%d", &key);            //输入下一个关键字}return T;                          //返回建立的二叉排序树
}

4、二叉排序树上的查找

(1) 算法思想： 若二叉排序树为空，则表明查找失败，应返回空指针。否则，若给定值key等于根结点的关键字，则表明查找成功，返回当前根结点指针; 若给定值key小于根结点的关键字，则继续在根结点的左子树中查找，若给定值key大于根结点的关键字，则继续在根结点的右子树中查找，显然，这是一个递归的查找过程

(2) 算法描述

BSTNode* SearchBST(BSTree T, KeyType x)
{  //在二叉排序树上查找关键字值为x的结点if (T == NULL || T->key == x){return T;}if (x < T->key){return SearchBST(T->lchild, x);}else{return SearchBST(T->lchild, x);}
}

(3) 算法分析： 二叉排序树上的查找长度与二叉排序树的形态有关，若二叉排序树是一棵理想的平衡树(是指树中任一结点的左右子树的高度差不能大于1)， 则进行查找的时间复杂度为O(log2N);若退化为一棵单支树，则其查找的时间复杂度为O(n)。对于一般情况，其时间复杂度应为O(log2n).

5、二叉排序树上的删除

从BST树上删除一个结点，仍然要保证删除后满足BST的性质。设被删除结点为P,其父结点为f, 如图(a) 所示的BST树，具体删除情况分析如下：

(1) 若p是叶子结点： 直接删除p, 如图(b)所示

(2) 若p只有一棵子树(左子树或右子树)，直接用p的左子树(或右子树)取代p的位置而成为f的一棵子树。即原来p是f左子树，则p的子树成为f的左子树; 原来p是f的右子树，则p的子树成为f的右子树，如图(c)所示。

(3) 若p既有左子树又有右子树，处理方法有以下两种，可以任选其中一种。①用p的直接前驱结点(中序遍历)代替p,即从p的左子树中选择值最大的结点s放在p的位置(用结点s的内容替换结点p内容)， 然后删除结点s。s是p的左子树中最右边的结点为且没有右子树，如图(d)所示。② 用p的直接后继结点(中序遍历)代替p，即从p的右子树中选择值最小的结点s放在p的位置(用结点s的内容替换结点p的内容)， 然后删除结点s。s是p的右子树中的最左边的结点且没有左子树。例如,对图(a)所示的二叉排序树，删除结点8后所得的结果如图(e)所示。

二、B树

1、B树的概念

(1) B树的定义

一棵m(m>=3)阶的B树，或为空树，或为满足下列性质的m叉树；

①每个结点至少包含下列信息域： (n, p0, k1, p1, k2, ..., kn, pn)其中， n为关键字的个数；ki(1<=i<=n)为关键字，且ki<ki+1(1<=i<=n-1); pi(0<=i<=n)为指向子树根结点的指针， 且pi所指向子树中所有结点的关键字均小于ki+1, pn所指子树中所有结点关键字均大于kn。

② 树中每个结点至多有m棵子树。

③若树为非空，则根结点至少有1个关键字，至多有m-1个关键字。因此，若根结点不是叶子，则它至少有两棵子树。

④所有的叶结点都在同一层上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向它们的指针均为空)，叶子的层数为树的高度h。

⑤每个非根结点中所包含的关键字个数满足：⌈m/2⌉-1<=n<=m-1。因为每个内部结点的度数正好是关键字总数加1， 所以，除根结点之外的所有非终端结点(非叶子结点的最下层的结点称为终端结点)至少有⌈m/2⌉棵子树，至多有m棵子树。

(2) 实例 下图是一棵4阶的B树

(3) B树的结点类型定义

#define m  10    //m为B树的阶，结点中关键字最多可有m-1个
typedef struct node
{int keynum;             //结点中关键字个数，即结点的大小KeyType key[m];         //关键字向量，key[0]不用struct node * parent;         //指向双亲结点struct node* ptr[m];    //子树指针向量
} BTNode;typedef BTNode* BTree;

2、B 树上的插入 在B树上插入一个结点的过程： 先在最低层的某个非终端结点中添加一个关键字。若该结点中关键字的个数不超过m-1, 则插入完成，否则要产生结点"分裂"。“分裂”结点时把结点分成两个，将中间的一个关键字拿出来插入到该结点的双亲结点上，如果双亲结点中已有m-1个关键字，则插入后将引起双亲结点的分裂，这一过程可能波及B树的根结点，引起根结点的分裂，从而使B树长高一层。

【例】 试画出将关键字序列： 24，45，53，90，3，50，30，61，12，70，100依次插入一棵初始为空的4阶B树中的过程。

3、B树上的删除

(1) 若需删除关键字所在的结点中的关键字数目不小于，则只需要该结点中关键字和相应的指针删除。

【例】 画出删除图(a)中所示3阶B树上的关键字3后的B树.

【解析】在3阶B树中，要删除的关键字所在的结点有2个关键字，直接删除该关键字和相应的指针即可。

【答案】删除关键字3后的B树如图(b)所示

(2) 若需删除关键字所在结点中的关键字数目等于-1, 即关键字数目已是最小值，直接删除该关键字会破坏B树的性质。删除这样关键字分两种情况处理:

①若所删除结点的左(或右)邻兄弟结点中的关键字数目不小于，则将其兄弟结点中的最大(或最小)的关键字上移至双亲结点中，而将双亲结点中相应的关键字移至删除关键字所在结点中。

【例】 画出删除上面(b)图中的关键字12后的B树。

【解析】直接删除12及其指针， 关键字24所在结点就变成 1叉树， 不满足B树的性质，可以将关键字12结点的兄弟结点中的最小值30移双亲结点中，而将双亲结点中的关键字24移至删除关键字12所在的结点中。

【答案】删除关键字12后的B树如图(c)所示。

②若需删除关键字所在结点及其相邻的左，右兄弟(或只有一个兄弟)结点中关键字数目均等于-1, 则按上述情况①的移动操作就不能实现。此时，就需要将被删结点与其左兄弟或右兄弟结点进行“合并”。

【例】画出删除上面(c)图中的关键字50后的B树。

【解析】删除50, 需要将63和70合并，90单独作为双亲结点。

【答案】删除(c)图中的关键字50后的B树如图(d)所示。

上述情况②如果因“合并”操作引起对父结点中关键字的删除，又可能要合并结点，这一过程可能波及根，引起对根结点中关键字的删除，从而可能使B树的高度降低一层。

【例】画出删除上面(d)图中的关键字24后的B树。

【解析】删除24后，30需要37进行合并，这样需要45和90合并才能满足B树的性质，使B树的高度降低一层。

【答案】删除【d】图中的关键字24后的B树如图(e)所示。

4、B树上的查找

(1) 查找算法思想

在B树中查找一个关键字等于给定值K的具体过程：若B树为非空， 则首先取出树根结点。将给定值K依次与关键字向量从高下标端(key[keynum])开始的每个关键字进行比较，直到K>=Ki(0<=i<=n=keynum,用key[0]作为中止标志，存放给定的查找值K)为止，此时，若K=Ki且i>0, 则表明查找成功，返回具有该关键字的结点的存储位置及K在key[1...keynum]中的位置；否则，其值为K的关键字只可能落在当前结点的pi所指向的子树上，接着只要在该子树上继续进行查找即可。这样，每取出一个结点比较后就下移一层，直到查找成功，或被查找的子树为空(即查找失败)为止。

(2) 算法描述

BTNode* SearchBTree(BTree T, KeyType K, int* pos)
{   //从树根指针为T的B树上查找关键字为K的对应结点的存储地址及K在其中的//位置*pos,查找失败返回NULL， *pos无定义int i;BTNode* p = T;while (p != NULL)      //从根结点开始起依次向下一层查找{i = p->keynum;    //把结点中关键字个数赋给ip->key[0] = K;    //设置哨兵，顺序查找key[0...keynum]while (K < p->key[i])      //从后向前查找第1个小于等于K的关键字{i--;}if (K == p->key[i] && i > 0){*pos = i; return p;}else{p = p->ptr[i];}}return NULL;
}

(3) 实例分析

【例】分析下图所示B树，查找18的过程

先和根结点a比较：把K=18赋给k0.K-18小于k1的值48， 再同a结点中k0比较， k0=K, 因为i=0, 所以接着取出a结点的p0指向的结点b, 用K与b结点中的k2=32进行比较， k=18<k2=32, 而K=18>k1=16, 所以再取出b结点的p1所指向的结点e, 因为k=k1, 因此查找成功，返回e结点的存储地址以及k1的位置pos=1。

三、B+树

B+树是一种常用于文件组织的B树的变形树。一棵m阶的B+树和m阶的B树的差异在于:

(1) 有k个孩子的结点必含有k个关键字。

(2) 所有的叶结点中包含了关键字的信息及指向相应结点的指针，且叶子结点本身依照关键字的大小从小到大顺序链接。

(3) 所有非终端结点可看成是索引部分，结点中仅含有其子树(根结点)中最大的关键字(或最小)关键字。

下图所示是一棵3阶的B+树。通常在B+树上有两个头指针root和sqt， 前者指向根结点，后者指向关键字最小的叶子结点。因此，可以对B+树进行两种查找运算：一种是从最小关键字起进行顺序查找， 另一种是从根结点开始进行随机查找。

第四节 散列表查找

一、散列表的概念

1、散列的概念： "散列"即是一种存储方式，又是一种查找方法。这种查找方法称为散列查找。散列的基本思想是通过由散列函数决定的键值与散列地址之间的对应关系来实现的存储组织和查找运算。

2、实例分析【例】有个线性表A=(31, 62, 74, 36, 49, 77),散列函数为H(key)=key%m即用元素的关键字key整除m, 取其余数作为存储该元素的散列地址，m一般取小于或等于散列表长的最大素数，在这里取m=11,表长也为11，因此可得到每个元素的散列地址: H(31)=31%11=9; H(62)=62%11=7; H(74)=74%11=8; H(36)=36%11=3; H(49)=49%11=5; H(77)=77%11=0; 散列表

若在上面散列表中插入元素88、7等会出现冲突。采用散列技术时需要考虑的两个主要问题是 ①如何构造(选择)”均匀的“散列函数？ ② 用什么方法解决冲突？

二、散列函数的构造方法

1、直接地址法

直接地址法是以关键字key本身或关键字加上某个常量C作为散列地址的方法。对应的散列函数H(key)=key+C

特点：方法计算简单，并且没有冲突。适合于关键字的分布基本连续的情况，若关键字分布不连续，空号较多，将会造成较大的空间浪费。

2、数字分析法

数字分析法是假设有一组关键字，每个关键字由n位数字组成，数字分析法是从中提取数字分布比较均匀的若干位作为散列地址。

3、除余数法

除余数法是一种最简单也最常用的一种散列函数构造方法。散列函数: H(k)=k%p; 其中，p最好选取小于或等于表长m的最大素数。

4、平方取中法

平方取中法是取关键字平方的中间几位作为散列地址的方法

5、折叠法

折叠法是首先把关键字分割成位数相同的几段(最后一段的位数可少一些)， 段的位数取决于散列地址的位数，由实际情况而定，然后将它们的叠加和(舍去最高进位)作为散列地址的方法。

【例】关键字k=98 123 658, 散列地址为3位，则将关键字从左到右每三位一段进行划分，得到的三个段981、236和58，叠加后值为1275, 取低3位275作为关键字98 123 658的元素的散列地址。

三、处理冲突的方法

1、开放定址法

开放定址法的思想：使用某种方法在散列表中形成的一个探查序列，沿着此序列逐个单元进行查找，直到找到一个空闲的单元时将新结点存入其中。

开放定址法又分为线性探插法、二次探查法和双重散列法。

(1) 纯性探插法

探查序列可以由下述公式得到: di=(d+i) % m

其中：di表示第i次探查的地址，m表示散列表的长度。

【例】设散列函数为h(key)=key%11; 散列地址表空间为0~10, 对关键字序列{27, 13 55 18 49 24 38 43}, 利用线性探测法解决冲突，构造散列表。并计算查找成功时的平均查找长度。

【解答】 首先根据散列函数计算散列地址

h(27)=5; h(13)=2; h(55)=0; h(32)=10; h(18)=7; h(49)=5; h(24)=2; h(38)=5; h(43)=10; 散列表

查找成功时的平均查找长度ASL=(1 * 5 + 2 * 2 + 3 * 1+4*1)/9 ≈ 1.78

(2) 二次探查法

二次探查法的探查序列为：

d0=H(k),

d1=(d0+1²)%m，

d2=(d0-1²)%m,

d3=(d0+2²)%m，

d4=(d0-2²)%m, ........

(3) 双重散列法

双重散列法是几种方法中最好的方法，它的探查序列为： hi=(H(key) + i * H1(key)) % m (0<=i<=,-1)

即探查序列为： d=H(k), (d+1 * H1(key)) %m, (d+2 * H1(key)) %m, ... 等。

2、拉链法(链地址法)

用拉链法处理冲突的办法是：把具有相同散列地址的关键字(同义词)放在同一单链表中，称为同义词链表。

【例】 设散列函数为h(key)=key % 11; 对关键字序列(27, 13, 55, 32, 18, 49, 24, 38, 43), 用拉链法构造散列表，并计算查找成功时的平均查找长度。

【解答】首先根据散列函数计算散列地址 h(27)=5; h(13)=2; h(55)=0; h(32)=10; h(18)=7; h(49)=5; h(24)=2; h(38)=5; h(43)=10;

查找成功时的平均查找长度=(1 * 5 + 2 * 3 + 3 * 1)/9=1.55

四、散列表的查找

1、线性探查法解决冲突的查找和插入算法

采用开放定值法构造散列表的类型定义

#define M 997         //M定义为表长，一般M为一个素数
typedef struct        //定义散列表结点类型
{KeyType key;DataType data;
} NodeType;
typedef NodeType HashTable[M];      //散列表类型

(1) 采用线性探查法的散列表查找算法

int HashSearch(HashTable HT, KeyType K, int n)
{   //在长度为n的散列表HT中查找关键字值为K的元素位置int d, temp;d = K % n;                 //计算散列地址temp = d;                  //temp作为哨卡，防止进入重复循环while (HT[d].key != -32768)    //当散列地址中的key域不为空，则循环{if (HT[d].key == K){return d;          //查找成功返回其下标}else{d = (d + 1) % n;    //计算下一个地址}if (d == temp){return -1;          //查找一周仍无空位置，返回-1表示失败}}return d;                   //遇到空单元，查找失败
}

(2) 在散列表上插入一个结点的算法

int HashInsert1(HashTable HT, NodeType s, int n)
{//在HT表上插入一个新结点sint d;d = HashSearch(HT, s.key, n);       //查找插入位置if (d == -1){return -1;}else{if (HT[d].key == s.key){return 0;                   //表中已有该结点     }else                            //找到一个开放的地址{HT[d] = s;                  //插入新结点Sreturn 1;                   //插入成功}}
}

2、拉链法建立散列表上的查找和插入运算

采用拉链法的散列表类定义:

typedef struct node 
{  //定义结点类型KeyType key;DataType data;struct node* next;
} HTNode;
typedef HTNode* HT[M];   //定义散列表类型

(1) 查找算法

HTNode* HashSearch2(HT T, KeyType K, int n)
{  //在长度为n的散列表T中查找关键字值为K的元素位置HTNode* p = T[K % m];    //取K所在链表的头指针while (p != NULL && p->key != K){p = p->next;     //顺链查找}return p;            //查找成功p指向K结点的位置，不成功返回NULL
}

(2) 插入算法

int HashInsert2(HT T, HTNode* s, int n)
{ //采用头插法在T表上插入一个新结点int d;HTNode* p = HashSearch2(T, s->key, n);      //查找表中有无待插结点if (p != NULL){return 0;                               //说明表中已有该结点}else                                       //将*s插入在相应链表的表头上{d = s->key % n;s->next = T[d];T[d] = s;return 1;                         //说明插入成功}
}

3、几种处理冲突方法的散列表的平均查找长度比较

【例】 设散列函数h(k)=k%13, 散列表地址空间为0`12, 对给定的关键字序列(19，14，01，68，20，84，27，26，50，36)分别以拉链法和线性探查法解决冲突构造散列表，画出所构造的散列表，指出在这两个散列表中查找每一个关键字时进行比较的次数，并分析在等概率情况下查找成功和不成功时的平均查找长度以及当结点数n=10时的顺序查找和二分查找成功与不成功的情况。

【解答】 首先根据散列函数计算散列地址

h(19)=6; h(14)=1; h(01)=1; h(68)=3; h(20)=7;

h(84)=6; h(27)=1; h(26)=0; h(50)=11; h(36)=10;

(1) 线性探查法解决冲突构造散列表:

查找成功的平均查找长度=(1 * 7 + 2 * 1 + 3 * 1 + 4 * 1) / 10 =1.6

查找不成功的平均查找长度=()6 + g +4 +3 +2 +1+4+3+2+1+3+2+1)/13=2.85

(2) 拉链法解决冲突 构造散列表

查找成功的平均查找长度=(1 * 7 + 2 * 2 + 3 * 1) /10 = 1.4

查找不成功的平均查找长度(不包括空指针的比较)=(1+3+0+1+0+0+2+1+0+0+1+1+0)/13=0.7

当n=10时，顺序查找成功的平均查找长度=(10+1)/2=5.5 顺序查找不成功的平均查找长度=10 + 1 =11

n=10的有序表的判定树：

当n=10时， 二分查找成功的平均查找长度=（1 * 1 + 2 * 2 + 3 * 3 + 4 * 3 ) / 10 = 3

二分查找不成功的平均查找长度= (3 * 2 + 3 * 1 + 4 * 2 + 3 * 1 + 4 * 23 * 1 + 4 + 2 )/ 11 = 3.2

注意：结点个数n, 散列表长度为m，散列表的平均查找长度不是n的函数， 而是装填因子的函数 ，采用四种不同方法处理冲突时得出的散列表的平均查找长度：

开放地址要求散列表的装填因子a<=1, 实用中一般取0.65~0.9之间的某个值为宜。在拉链法中，其装填因子a可以大于1， 但一般均取a <=1。