文档介绍：第3章查找与排序技术
线性表的查找技术
Hash表技术
线性表的排序技术
索引查找
拓扑分类
在数据处理领域中,最常见的运算是在给定的数据结构中查找所需要处理的数据元素。
另一常见的运算是对给定的数据结构进行重新分类,或按数据元素的大小重新进行排序,以方便对数据元素的处理。
查找与排序是数据处理的基本技术。本章主要介绍线性表查找与排序的基本方法,以及索引存储结构下的查找技术。
线性表的查找技术
顺序查找
顺序查找的基本方法是,从线性表的第一个元素开始,依次将线性表中的元素与被查元素进行比较,若遇到线性表中某位置上的元素与被查元素相等,则表示找到(即查找成功);若线性表中所有的元素与被查元素进行比较都不相等,则表示线性表中不存在需要找的元素(即查找失败)。
对于大的线性表来说,顺序查找的效率是很低的。
有序表的对分查找
虽然顺序查找的效率不高,但在下列两种情况下也只能采用顺序查找。
①线性表为无序表(即表中元素的排列是无序的)
②采用链式存储结构的有序线性表
先将线性表中的元素按值非递减进行重新排列。
这样的线性表称为有序表。
设有序线性表的长度为n,被查元素为x,则对分查找的方法如下。
将x与线性表的中间项进行比较:
若被查元素x与该线性表的中间项的值相等,则说明查到,查找结束;
若被查元素x小于该线性表的中间项的值,则取线性表的前半部分作为子表(即取中间项以前的部分,而不再考虑线性表后半部分的元素)以相同的方法进行查找;
若被查元素x大于该线性表的中间项的值,则取线性表的后半部分作为子表(即取中间项以后的部分,而不再考虑线性表前半部分的元素)以相同的方法进行查找。
这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。
当有序线性表为顺序存储时才能采用对分查找,并且,对分查找的效率要比顺序查找高得多。
Hash表技术
Hash表的基本概念
设表的长度为n。
如果存在一个函数i = i(k),对于表中的任意一个元素的关键字k,满足以下条件:
① 1≤i≤n。
②对于任意的元素关键字k1≠k2,恒存在i(k1)≠i(k2)。
则称此表为直接查找表。
其中函数i = i(k)称为关键字k的映象函数。
对直接查找表的操作主要有以下两种
(1)直接查找表的填入
(2)直接查找表的取出