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

第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表及表外结点