第 3章 查找与排序技术
3.1 线性表的查找技术
3.2 Hash表技术
3.3 线性表的排序技术
3.4 索引查找
3.5 拓扑分类
在数据处理领域中，最常见的运算是
在给定的数据结构中查找所需要处理的数
据元素。
另一常见的运算是对给定的数据结构
进行重新分类，或按数据元素的大小重新
进行排序，以方便对数据元素的处理。
查找与排序是数据处理的基本技术。
本章主要介绍线性表查找与排序的基本方
法，以及索引存储结构下的查找技术。
3.1 线性表的查找技术
3.1.1 顺序查找
顺序查找的基本方法是，从线性表的第一
个元素开始，依次将线性表中的元素与被查元素
进行比较，若遇到线性表中某位置上的元素与被
查元素相等，则表示找到（即查找成功）；若线
性表中所有的元素与被查元素进行比较都不相等，
则表示线性表中不存在需要找的元素（即查找失
败）。
对于大的线性表来说，顺序查找的效
率是很低的。
3.1.2 有序表的对分查找
虽然顺序查找的效率不高，但在下列
两种情况下也只能采用顺序查找。
① 线性表为无序表（即表中元素的排
列是无序的）
②采用链式存储结构的有序线性表
先将线性表中的元素按值非递减进行
重新排列。
这样的线性表称为有序表 。
设有序线性表的长度为 n，被查元素
为 x，则对分查找的方法如下。
将 x与线性表的中间项进行比较：
若被查元素 x与该线性表的中间项的
值相等，则说明查到，查找结束；
若被查元素 x小于该线性表的中间项
的值，则取线性表的前半部分作为子表
（即取中间项以前的部分，而不再考虑线
性表后半部分的元素）以相同的方法进行
查找；
若被查元素 x大于该线性表的中间项
的值，则取线性表的后半部分作为子表
（即取中间项以后的部分，而不再考虑线
性表前半部分的元素）以相同的方法进行
查找。
这个过程一直进行到查找成功或子表
长度为 0（说明线性表中没有这个元素）
为止。
当有序线性表为顺序存储时才能采用
对分查找，并且，对分查找的效率要比顺
序查找高得多。
3.2 Hash表技术
3.2.1 Hash表的基本概念
1．直接查找技术
设表的长度为 n。
如果存在一个函数 i = i(k)，对于
表中的任意一个元素的关键字 k，满足
以下条件：
① 1≤i≤n。
② 对于任意的元素关键字 k1≠k2，
恒存在 i(k1)≠i(k2)。
则称此表为直接查找表。
其中函数 i = i(k)称为关键字 k的映
象函数。
对直接查找表的操作主要有以下两种
（ 1）直接查找表的填入
（ 2）直接查找表的取出
2,Hash表
Hash表技术是直接查找技术的推广，
其主要目标是提高查找效率。
如果按照直接查找表的填入方法，填
入结果如表 3.1所示。
设表的长度为 n。
如果存在一个函数 i = i(k)，对于
表中的任意一个元素的关键字 k，满
足 1≤i≤n，则称此表为 Hash表。
其中函数 i = i(k)称为关键字 k的
Hash码。
Hash表技术的关键是要处理好表中元
素的冲突问题，它主要包括以下两方面的
工作：
（ 1）构造合适的 Hash码，以便尽量
减少表中元素冲突的次数。
即 Hash码的均匀性要比较好。
（ 2）当表中元素发生冲突时，要进
行适当的处理。
3,Hash码的构造
在实际设计 Hash码时，要考虑以下两
方面的因素：
① 使各关键字尽可能均匀地分布在
Hash表中 。
② Hash码的计算要尽量简单。
比较简单的 Hash码的构造方法。
（ 1）截段法
（ 2）分段叠加法
（ 3）除法
（ 4）乘法
3.2.2 几种常用的 Hash表
1．线性 Hash表
设线性 Hash表的长度为 n，对线性
Hash表的查找过程如下。
（ 1）线性 Hash表的填入
（ 2）线性 Hash表的取出
线性 Hash表的优点是简单，但它有以
下两个主要缺点。
当 Hash码的冲突较多时，在线性 Hash
表中会存在“堆聚”现象，即许多关键字
被连续登记在一起，从而会降低查找效率。
2．随机 Hash表
当 Hash表的长度 n设计成 n = 2k时，还
可以定义另外一种 Hash表 ——随机 Hash
表。
随机 Hash表的填入与取出的过程。
（ 1）随机 Hash表的填入
（ 2）随机 Hash表的取出
3．溢出 Hash表
前面所介绍的线性 Hash表与随机 Hash
表均存在两个致命的缺点：一是在 Hash表
填入过程中不顾后效，从而在填入过程中
其冲突的机会在不断增多；二是当 Hash表
填满时，不能正常地进行查找。
如果将冲突的元素安排在另外的
空间内，不占用 Hash表本身的空间，
就不会产生新的冲突。
这就是溢出 Hash表。
溢出 Hash表包括 Hash表和溢出
表两部分。
溢出 Hash表的填入与取出的过程。
（ 1）溢出 Hash表的填入
（ 2）溢出 Hash表的取出
4．拉链 Hash表
拉链 Hash表又分为外链 Hash表与内链
Hash表。
外链 Hash表由 Hash表及表外结点组成。
Hash表的第 i项登记着 Hash码为 i的所
有关键字的表外结点。
在初始状态下,Hash表中的所有指针
为空。
外链 Hash表的填入与取出过程如下。
（ 1）外链 Hash表的填入
填入后的外链 Hash表如图 3.1所示。
（ 2）外链 Hash表的取出
5．指标 Hash表
指标 Hash表包括指标表与内
容表两部分。
3.3 线性表的排序技术
排序是指将一个无序序列整理成按
值非递减顺序排列的有序序列。
排序的方法有很多，根据待排序序
列的规模、存储结构以及对数据处理的
要求，可以采用不同的排序方法。
本节主要介绍针对顺序表的常用排
序法。
3.3.1 互换排序
互换排序是指借助数据元素之间的互
相交换进行排序的一种方法。
1．冒泡排序
冒泡排序是通过相邻数据元素的交换
逐步将线性表变成有序。
冒泡排序的基本方法如下。
首先，从表头开始往后扫描线性表，
在扫描过程中逐次比较相邻两个元素的
大小。
然后，从后到前扫描剩下的线性表，
同样，在扫描过程中逐次比较相邻两个
元素的大小。
在上述排序过程中，对线性表的每一
次来回扫描，都将其中的最大者沉到了表
的底部，最小者像气泡一样冒到表的前头，
冒泡排序由此而得名。
冒泡排序又称下沉排序。
图 3.2是冒泡排序的示意图。
2．快速排序
快速排序的关键是对线性表的分割，
以及对各分割出的子表再进行分割，这
个过程如图 3.3所示。
快速排序在最坏情况下需要 n(n–
1)/2次比较，但实际的排序效率要比冒
泡排序高得多。
3.3.2 插入排序
插入排序是指将无序序列中的各元素依次
插入到已经有序的线性表中。
1．简单插入排序
首先将第 j个元素放到一个变量 T中。然后
从有序子表的最后一个元素（即线性表中第 j– 1
个元素）开始，往前逐个与 T进行比较，将大于
T的元素均依次向后移动一个位置，直到发现一
个元素不大于 T为止，此时就将 T（即原线性表
中的第 j个元素）插入到刚移出的空位置上，有
序子表的长度就变为 j了。
图 3.4给出了插入排序的示意图。
图中画有方框的元素表示刚被插入到
有序子表中。
2．希尔排序
将整个无序序列分割成若干小的子序
列分别进行插入排序。
但这种分割不是逐段分割，而是将相
隔某个增量 h的元素构成一个子序列。
在排序过程中，逐次减小这个增量，
最后当 h减到 1时，进行一次插入排序，排
序就完成。
图 3.5为希尔排序的示意图。
3.3.3 选择排序
1．简单选择排序
简单选择排序的基本方法是：扫描整
个线性表，从中选出最小的元素，将它交
换到表的最前面（这是它应有的位置）；
然后对剩下的子表采用同样的方法，直到
子表空为止。
2．堆排序
堆的定义如下：
具有 n个元素的序列 (h1,h2,…, hn)，
当且仅当满足
i = 1,2,…, n/2时称之为堆。
调整建堆的问题。
在调整建堆的过程中，总是将根结点
值与左、右子树的根结点值进行比较，若
不满足堆的条件，则将左、右子树根结点
值中的大者与根结点值进行交换。
这个调整过程一直做到所有子树均为
堆为止。
堆排序的方法如下：
① 首先将一个无序序列建成堆。
② 然后将堆顶元素（序列中的最大项）
与堆中最后一个元素交换（最大项应该在
序列的最后）。
3.3.4 其他排序方法简介
1．归并排序
归并 (Merging)是将两个或两个以上的
有序表合并成一个新的有序表。
设线性表 L(1,n)中的某段 L(low：
high)已经部分有序，即它的两个子表
L(low,mid)与 L(mid + 1,high)（其中
low≤mid≤high）已经有序，现要将这两个
有序子表归并成一个有序子表 L(low：
high)。
两个子表的归并基本做法。
① 开辟一个与线性表 L同样大小的表
空间 A。
② 设置三个指针 i,j,k，其初始状
态分别指向两个有序子表的首部及表空
间 A中与 L中需要进行排序段相对应空间
的首部。
即 i = low,j = mid + 1,k = low。
③ 沿两个有序子表扫描：
④ 将未取空的子表中的剩余元素依次
放入表空间 A中。
⑤ 将 A中的对应段复制到 L中。
图 3.9所示的为归并排序的示意图。
归并排序的算法有递归和非递归两种
形式。
2．基数排序
基数排序（ Radix Sort）又称为吊桶
排序，它属于分配类的排序方法。
设线性表中各元素的关键字具有 k位
有效数字，则基数排序的基本思想是从有
效数字的最低位开始直到最高位，对每一
位有效数字在线性表中进行重新排列，其
调整的原则为：
① 将线性表依当前位的有效数字为序
排列。
② 当前位的有效数字相同时，按原次
序排列。
这种基数排序法称为最低位优先法
（ Least Significant Digit first,LSD）。
图 3.10是基数排序的示意图。
3.4 索引查找
3.4.1 分块查找
从整体来看，线性表不是有序表，如
果将线性表分成若干个子表，虽然每一子
表也不是有序的，但各个子表之间却是有
序的，这样的线性表称为分块有序表。
分块有序表的结构可以分为两部分。
① 线性表本身采用顺序存储结构。
② 再建立一个索引表。
图 3.11是将一个长度 n = 19的线性表分
成 m = 3个子表的分块有序表示意图。
分块查找又称索引顺序查找，用于在
分块有序表中进行查找。
分块查找的过程可以分两步进行：
（ 1）查找索引表，以便确定被查元
素所在子表的位置。
（ 2）在相应的子表中用顺序查找法
进行具体的查找。
3.4.2 二叉排序树查找
1．二叉排序树及其构造
二叉排序树是指满足下列条件的二叉
树：
① 左子树上的所有结点值均小于根结
点值；
② 右子树上的所有结点值均不小于根
结点值；
③ 左、右子树也满足上述两个条件。
根据二叉排序树的定义，构造二叉排
序树的过程如下：
依次读入给定序列中的每一个元素，
然后进行如下处理：
① 若当前的二叉排序树为空，则读入
的元素为根结点；
② 若读入的元素值小于根结点值，则
将元素插入到左子树中；
③ 若读入的元素值不小于根结点值，
则将元素插入到右子树中。
例如，如果依次读入元素序列
（ 80,82,85,75,82,68,71，
77,88）中的元素，则构造二叉排
序树的过程如图 3.13所示
例如，如果将读入上述元素序列的顺
序改为（ 75,82,68,71,77,88,80，
82,85），则构造出的二叉排序树如图
3.14所示。
二叉排序树有一个重要特性：中序遍
历二叉排序树可以得到有序序列。
2．二叉排序树查找
从二叉排序树的根结点开始与被查值
进行比较：
① 若被查值等于根结点值，则查找成
功，查找过程结束。
② 若被查值小于根结点值，则到左子
树中去查找。
③ 若被查值大于根结点值，则到右子
树中去查找。
对于经常需要动态增长且经常需
要查找的大线性表来说，采用二叉排
序树这种结构是很方便的，它既有利
于插入元素，也有利于查找。
3.4.3 B–树
二叉排序树实际上就是一种多层索引
树。
一般来说，多层索引树中的每个结点
包含 2m个关键字域和 2m + 1个指针域。
多层索引树中的结点结构如图 3.15所
示。
B–树的定义如下。
一棵 2m + 1阶的 B–树，或为
空，或为满足下列特性的度为
2m + 1的树。
在实际存储 B–树时，为了使处理方便，
一般在每一个结点中还增加两个域：一个
用于记录本结点中实际的关键字个数；另
一个用于指向父结点。
1,B–树的查找
由 B–树的定义可知，在 B–树中进行查
找的过程与二叉排序树的查找很类似。
B–树查找的效率取决于 B–树的深度以
及结点中的元素数目。
2,B–树的插入
在 2m + 1阶的 B–树中插入一个新元素
x，首先要进行查找，以便找到元素 x在叶
子结点中应插入的位置。
如果在查找过程中发现 B–树中已经存
在元素 x，则表示出错，这是因为在 B–树
一般不允许存在两个相等的元素；否则根
据找到的插入位置（参看 B–树的查找），
将元素 x插入，并保持有序排列。
图 3.17给出了在 B–树中进行插入
的示意图。
3,B–树的删除
要在 B–树中删除一个指定的元素
x，首先也要进行查找，找到元素 x在
B–树中的位置。
如果要删除的元素 x在 B–树的叶子结
点上，则进行删除；如果要删除的元素 x
不在叶子结点上，则要用一个比 x大、而
又最接近 x的元素 y代替 x（即删除了元素
x），显然，这个 y就是 x右边指针所指的
路径上最左边叶子结点上的第一个元素，
然后在叶子结点中删除 y。
由此可以看出,B–树的删除都归结为
在叶子结点上删除一个元素。
3.4.4 B+树
在 B+树中，所有的元素均按递增顺
序从左到右被安排在叶子结点上，各叶
子结点之间从左到右用指针（利用叶子
结点中的最后一个指针域）链接起来。
图 3.18是一个 B+树的模型。
图 3.19所示的是一棵 5阶（ m = 2）的
B+树。
1,B+树的查找
B+树的查找分随机查找与顺序查找
两种。
2,B+树的插入
B+树的插入与 B–树的插入过程也
基本相同。
3,B+树的删除
在 B+树中删除一个元素要比 B–树
简单，这也是 B+树的优点之一。
3.5 拓扑分类
拓扑分类是指对一个序列按需要
的顺序进行重新排列。
拓扑分类也称拓扑排序。
3.1 线性表的查找技术
3.2 Hash表技术
3.3 线性表的排序技术
3.4 索引查找
3.5 拓扑分类
在数据处理领域中，最常见的运算是
在给定的数据结构中查找所需要处理的数
据元素。
另一常见的运算是对给定的数据结构
进行重新分类，或按数据元素的大小重新
进行排序，以方便对数据元素的处理。
查找与排序是数据处理的基本技术。
本章主要介绍线性表查找与排序的基本方
法，以及索引存储结构下的查找技术。
3.1 线性表的查找技术
3.1.1 顺序查找
顺序查找的基本方法是，从线性表的第一
个元素开始，依次将线性表中的元素与被查元素
进行比较，若遇到线性表中某位置上的元素与被
查元素相等，则表示找到（即查找成功）；若线
性表中所有的元素与被查元素进行比较都不相等，
则表示线性表中不存在需要找的元素（即查找失
败）。
对于大的线性表来说，顺序查找的效
率是很低的。
3.1.2 有序表的对分查找
虽然顺序查找的效率不高，但在下列
两种情况下也只能采用顺序查找。
① 线性表为无序表（即表中元素的排
列是无序的）
②采用链式存储结构的有序线性表
先将线性表中的元素按值非递减进行
重新排列。
这样的线性表称为有序表 。
设有序线性表的长度为 n，被查元素
为 x，则对分查找的方法如下。
将 x与线性表的中间项进行比较：
若被查元素 x与该线性表的中间项的
值相等，则说明查到，查找结束；
若被查元素 x小于该线性表的中间项
的值，则取线性表的前半部分作为子表
（即取中间项以前的部分，而不再考虑线
性表后半部分的元素）以相同的方法进行
查找；
若被查元素 x大于该线性表的中间项
的值，则取线性表的后半部分作为子表
（即取中间项以后的部分，而不再考虑线
性表前半部分的元素）以相同的方法进行
查找。
这个过程一直进行到查找成功或子表
长度为 0（说明线性表中没有这个元素）
为止。
当有序线性表为顺序存储时才能采用
对分查找，并且，对分查找的效率要比顺
序查找高得多。
3.2 Hash表技术
3.2.1 Hash表的基本概念
1．直接查找技术
设表的长度为 n。
如果存在一个函数 i = i(k)，对于
表中的任意一个元素的关键字 k，满足
以下条件：
① 1≤i≤n。
② 对于任意的元素关键字 k1≠k2，
恒存在 i(k1)≠i(k2)。
则称此表为直接查找表。
其中函数 i = i(k)称为关键字 k的映
象函数。
对直接查找表的操作主要有以下两种
（ 1）直接查找表的填入
（ 2）直接查找表的取出
2,Hash表
Hash表技术是直接查找技术的推广，
其主要目标是提高查找效率。
如果按照直接查找表的填入方法，填
入结果如表 3.1所示。
设表的长度为 n。
如果存在一个函数 i = i(k)，对于
表中的任意一个元素的关键字 k，满
足 1≤i≤n，则称此表为 Hash表。
其中函数 i = i(k)称为关键字 k的
Hash码。
Hash表技术的关键是要处理好表中元
素的冲突问题，它主要包括以下两方面的
工作：
（ 1）构造合适的 Hash码，以便尽量
减少表中元素冲突的次数。
即 Hash码的均匀性要比较好。
（ 2）当表中元素发生冲突时，要进
行适当的处理。
3,Hash码的构造
在实际设计 Hash码时，要考虑以下两
方面的因素：
① 使各关键字尽可能均匀地分布在
Hash表中 。
② Hash码的计算要尽量简单。
比较简单的 Hash码的构造方法。
（ 1）截段法
（ 2）分段叠加法
（ 3）除法
（ 4）乘法
3.2.2 几种常用的 Hash表
1．线性 Hash表
设线性 Hash表的长度为 n，对线性
Hash表的查找过程如下。
（ 1）线性 Hash表的填入
（ 2）线性 Hash表的取出
线性 Hash表的优点是简单，但它有以
下两个主要缺点。
当 Hash码的冲突较多时，在线性 Hash
表中会存在“堆聚”现象，即许多关键字
被连续登记在一起，从而会降低查找效率。
2．随机 Hash表
当 Hash表的长度 n设计成 n = 2k时，还
可以定义另外一种 Hash表 ——随机 Hash
表。
随机 Hash表的填入与取出的过程。
（ 1）随机 Hash表的填入
（ 2）随机 Hash表的取出
3．溢出 Hash表
前面所介绍的线性 Hash表与随机 Hash
表均存在两个致命的缺点：一是在 Hash表
填入过程中不顾后效，从而在填入过程中
其冲突的机会在不断增多；二是当 Hash表
填满时，不能正常地进行查找。
如果将冲突的元素安排在另外的
空间内，不占用 Hash表本身的空间，
就不会产生新的冲突。
这就是溢出 Hash表。
溢出 Hash表包括 Hash表和溢出
表两部分。
溢出 Hash表的填入与取出的过程。
（ 1）溢出 Hash表的填入
（ 2）溢出 Hash表的取出
4．拉链 Hash表
拉链 Hash表又分为外链 Hash表与内链
Hash表。
外链 Hash表由 Hash表及表外结点组成。
Hash表的第 i项登记着 Hash码为 i的所
有关键字的表外结点。
在初始状态下,Hash表中的所有指针
为空。
外链 Hash表的填入与取出过程如下。
（ 1）外链 Hash表的填入
填入后的外链 Hash表如图 3.1所示。
（ 2）外链 Hash表的取出
5．指标 Hash表
指标 Hash表包括指标表与内
容表两部分。
3.3 线性表的排序技术
排序是指将一个无序序列整理成按
值非递减顺序排列的有序序列。
排序的方法有很多，根据待排序序
列的规模、存储结构以及对数据处理的
要求，可以采用不同的排序方法。
本节主要介绍针对顺序表的常用排
序法。
3.3.1 互换排序
互换排序是指借助数据元素之间的互
相交换进行排序的一种方法。
1．冒泡排序
冒泡排序是通过相邻数据元素的交换
逐步将线性表变成有序。
冒泡排序的基本方法如下。
首先，从表头开始往后扫描线性表，
在扫描过程中逐次比较相邻两个元素的
大小。
然后，从后到前扫描剩下的线性表，
同样，在扫描过程中逐次比较相邻两个
元素的大小。
在上述排序过程中，对线性表的每一
次来回扫描，都将其中的最大者沉到了表
的底部，最小者像气泡一样冒到表的前头，
冒泡排序由此而得名。
冒泡排序又称下沉排序。
图 3.2是冒泡排序的示意图。
2．快速排序
快速排序的关键是对线性表的分割，
以及对各分割出的子表再进行分割，这
个过程如图 3.3所示。
快速排序在最坏情况下需要 n(n–
1)/2次比较，但实际的排序效率要比冒
泡排序高得多。
3.3.2 插入排序
插入排序是指将无序序列中的各元素依次
插入到已经有序的线性表中。
1．简单插入排序
首先将第 j个元素放到一个变量 T中。然后
从有序子表的最后一个元素（即线性表中第 j– 1
个元素）开始，往前逐个与 T进行比较，将大于
T的元素均依次向后移动一个位置，直到发现一
个元素不大于 T为止，此时就将 T（即原线性表
中的第 j个元素）插入到刚移出的空位置上，有
序子表的长度就变为 j了。
图 3.4给出了插入排序的示意图。
图中画有方框的元素表示刚被插入到
有序子表中。
2．希尔排序
将整个无序序列分割成若干小的子序
列分别进行插入排序。
但这种分割不是逐段分割，而是将相
隔某个增量 h的元素构成一个子序列。
在排序过程中，逐次减小这个增量，
最后当 h减到 1时，进行一次插入排序，排
序就完成。
图 3.5为希尔排序的示意图。
3.3.3 选择排序
1．简单选择排序
简单选择排序的基本方法是：扫描整
个线性表，从中选出最小的元素，将它交
换到表的最前面（这是它应有的位置）；
然后对剩下的子表采用同样的方法，直到
子表空为止。
2．堆排序
堆的定义如下：
具有 n个元素的序列 (h1,h2,…, hn)，
当且仅当满足
i = 1,2,…, n/2时称之为堆。
调整建堆的问题。
在调整建堆的过程中，总是将根结点
值与左、右子树的根结点值进行比较，若
不满足堆的条件，则将左、右子树根结点
值中的大者与根结点值进行交换。
这个调整过程一直做到所有子树均为
堆为止。
堆排序的方法如下：
① 首先将一个无序序列建成堆。
② 然后将堆顶元素（序列中的最大项）
与堆中最后一个元素交换（最大项应该在
序列的最后）。
3.3.4 其他排序方法简介
1．归并排序
归并 (Merging)是将两个或两个以上的
有序表合并成一个新的有序表。
设线性表 L(1,n)中的某段 L(low：
high)已经部分有序，即它的两个子表
L(low,mid)与 L(mid + 1,high)（其中
low≤mid≤high）已经有序，现要将这两个
有序子表归并成一个有序子表 L(low：
high)。
两个子表的归并基本做法。
① 开辟一个与线性表 L同样大小的表
空间 A。
② 设置三个指针 i,j,k，其初始状
态分别指向两个有序子表的首部及表空
间 A中与 L中需要进行排序段相对应空间
的首部。
即 i = low,j = mid + 1,k = low。
③ 沿两个有序子表扫描：
④ 将未取空的子表中的剩余元素依次
放入表空间 A中。
⑤ 将 A中的对应段复制到 L中。
图 3.9所示的为归并排序的示意图。
归并排序的算法有递归和非递归两种
形式。
2．基数排序
基数排序（ Radix Sort）又称为吊桶
排序，它属于分配类的排序方法。
设线性表中各元素的关键字具有 k位
有效数字，则基数排序的基本思想是从有
效数字的最低位开始直到最高位，对每一
位有效数字在线性表中进行重新排列，其
调整的原则为：
① 将线性表依当前位的有效数字为序
排列。
② 当前位的有效数字相同时，按原次
序排列。
这种基数排序法称为最低位优先法
（ Least Significant Digit first,LSD）。
图 3.10是基数排序的示意图。
3.4 索引查找
3.4.1 分块查找
从整体来看，线性表不是有序表，如
果将线性表分成若干个子表，虽然每一子
表也不是有序的，但各个子表之间却是有
序的，这样的线性表称为分块有序表。
分块有序表的结构可以分为两部分。
① 线性表本身采用顺序存储结构。
② 再建立一个索引表。
图 3.11是将一个长度 n = 19的线性表分
成 m = 3个子表的分块有序表示意图。
分块查找又称索引顺序查找，用于在
分块有序表中进行查找。
分块查找的过程可以分两步进行：
（ 1）查找索引表，以便确定被查元
素所在子表的位置。
（ 2）在相应的子表中用顺序查找法
进行具体的查找。
3.4.2 二叉排序树查找
1．二叉排序树及其构造
二叉排序树是指满足下列条件的二叉
树：
① 左子树上的所有结点值均小于根结
点值；
② 右子树上的所有结点值均不小于根
结点值；
③ 左、右子树也满足上述两个条件。
根据二叉排序树的定义，构造二叉排
序树的过程如下：
依次读入给定序列中的每一个元素，
然后进行如下处理：
① 若当前的二叉排序树为空，则读入
的元素为根结点；
② 若读入的元素值小于根结点值，则
将元素插入到左子树中；
③ 若读入的元素值不小于根结点值，
则将元素插入到右子树中。
例如，如果依次读入元素序列
（ 80,82,85,75,82,68,71，
77,88）中的元素，则构造二叉排
序树的过程如图 3.13所示
例如，如果将读入上述元素序列的顺
序改为（ 75,82,68,71,77,88,80，
82,85），则构造出的二叉排序树如图
3.14所示。
二叉排序树有一个重要特性：中序遍
历二叉排序树可以得到有序序列。
2．二叉排序树查找
从二叉排序树的根结点开始与被查值
进行比较：
① 若被查值等于根结点值，则查找成
功，查找过程结束。
② 若被查值小于根结点值，则到左子
树中去查找。
③ 若被查值大于根结点值，则到右子
树中去查找。
对于经常需要动态增长且经常需
要查找的大线性表来说，采用二叉排
序树这种结构是很方便的，它既有利
于插入元素，也有利于查找。
3.4.3 B–树
二叉排序树实际上就是一种多层索引
树。
一般来说，多层索引树中的每个结点
包含 2m个关键字域和 2m + 1个指针域。
多层索引树中的结点结构如图 3.15所
示。
B–树的定义如下。
一棵 2m + 1阶的 B–树，或为
空，或为满足下列特性的度为
2m + 1的树。
在实际存储 B–树时，为了使处理方便，
一般在每一个结点中还增加两个域：一个
用于记录本结点中实际的关键字个数；另
一个用于指向父结点。
1,B–树的查找
由 B–树的定义可知，在 B–树中进行查
找的过程与二叉排序树的查找很类似。
B–树查找的效率取决于 B–树的深度以
及结点中的元素数目。
2,B–树的插入
在 2m + 1阶的 B–树中插入一个新元素
x，首先要进行查找，以便找到元素 x在叶
子结点中应插入的位置。
如果在查找过程中发现 B–树中已经存
在元素 x，则表示出错，这是因为在 B–树
一般不允许存在两个相等的元素；否则根
据找到的插入位置（参看 B–树的查找），
将元素 x插入，并保持有序排列。
图 3.17给出了在 B–树中进行插入
的示意图。
3,B–树的删除
要在 B–树中删除一个指定的元素
x，首先也要进行查找，找到元素 x在
B–树中的位置。
如果要删除的元素 x在 B–树的叶子结
点上，则进行删除；如果要删除的元素 x
不在叶子结点上，则要用一个比 x大、而
又最接近 x的元素 y代替 x（即删除了元素
x），显然，这个 y就是 x右边指针所指的
路径上最左边叶子结点上的第一个元素，
然后在叶子结点中删除 y。
由此可以看出,B–树的删除都归结为
在叶子结点上删除一个元素。
3.4.4 B+树
在 B+树中，所有的元素均按递增顺
序从左到右被安排在叶子结点上，各叶
子结点之间从左到右用指针（利用叶子
结点中的最后一个指针域）链接起来。
图 3.18是一个 B+树的模型。
图 3.19所示的是一棵 5阶（ m = 2）的
B+树。
1,B+树的查找
B+树的查找分随机查找与顺序查找
两种。
2,B+树的插入
B+树的插入与 B–树的插入过程也
基本相同。
3,B+树的删除
在 B+树中删除一个元素要比 B–树
简单，这也是 B+树的优点之一。
3.5 拓扑分类
拓扑分类是指对一个序列按需要
的顺序进行重新排列。
拓扑分类也称拓扑排序。
