【软件技术基础】查找与排序技术.ppt

第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，满足以下条件：, 1in。 对于任意的元素关键字k1k2，恒存在i(k1)i(k2)。 则称此表为直接查找表。 其中函数i = i(k)称为关键字k的映象函数。,对直接查找表的操作主要有以下两种 （1）直接查找表的填入 （2）直接查找表的取出,2Hash表 Hash表技术是直接查找技术的推广，其主要目标是提高查找效率。 如果按照直接查找表的填入方法，填入结果如表3.1所示。,设表的长度为n。 如果存在一个函数i = i(k)，对于表中的任意一个元素的关键字k，满足1in，则称此表为Hash表。 其中函数i = i(k)称为关键字k的Hash码。,Hash表技术的关键是要处理好表中元素的冲突问题，它主要包括以下两方面的工作： （1）构造合适的Hash码，以便尽量减少表中元素冲突的次数。 即Hash码的均匀性要比较好。 （2）当表中元素发生冲突时，要进行适当的处理。,3Hash码的构造 在实际设计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)（其中lowmidhigh）已经有序，现要将这两个有序子表归并成一个有序子表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树时，为了使处理方便，一般在每一个结点中还增加两个域：一个用于记录本结点中实际的关键字个数；另一个用于指向父结点。 1B树的查找 由B树的定义可知，在B树中进行查找的过程与二叉排序树的查找很类似。 B树查找的效率取决于B树的深度以及结点中的元素数目。,2B树的插入 在2m + 1阶的B树中插入一个新元素x，首先要进行查找，以便找到元素x在叶子结点中应插入的位置。 如果在查找过程中发现B树中已经存在元素x，则表示出错，这是因为在B树一般不允许存在两个相等的元素；否则根据找到的插入位置（参看B树的查找），将元素x插入，并保持有序排列。,图3.17给出了在B树中进行插入的示意图。,3B树的删除 要在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+树。,1B+树的查找 B+树的查找分随机查找与顺序查找两种。 2B+树的插入 B+树的插入与B树的插入过程也基本相同。 3B+树的删除 在B+树中删除一个元素要比B树简单，这也是B+树的优点之一。,3.5 拓扑分类,拓扑分类是指对一个序列按需要的顺序进行重新排列。 拓扑分类也称拓扑排序。,