《软件技术基础》课件第8章.ppt

第8章查找

8.1线性表查找

8.2散列技术

习题8

8.1线性表查找

8.1.1顺序查找

顺序查找(SequentialSearch)是一种最简单的查找方法，即从

表头开始查找，直到找到为止。这种方法适用于较小的顺序表或

链表。顺序查找的过程为：从表的一端开始，逐个将记录的关键

字与给定值进行比较，若某个记录的关键字与给定值相等，则查

找成功；反之，若直至最后一个记录，都没有找到与给定值相等

的关键字，则表明表中没有所查的记录，查找失败。

算法8.1是以一维数组作为存储结构的顺序查找算法，该算法可

以很容易地修改为基于链表结构的顺序查找算法。

算法8.1是以一维数组作为存储结构的顺序查找算法，该算

法可以很容易地修改为基于链表结构的顺序查找算法。

给定关键字序列(21，9，33，64，15，59，75，47)，现

要查找的关键字为9，根据算法8.1，经过7次比较得到的查找

结果为：要查的关键字在表中的下标为2。如果待查找的关键

字为3，那么查找失败，返回i=0。

在算法8.1中，监视哨R[0]的作用是为了在for循环中省去

下标i的判断条件i0。这一改进可以减少约一半的比较次数，

从而节省时间。同理，监视哨也可设在数组高端。

下面分析顺序查找的性能。查找算法的平均查找长度定义

为：查找给定值所需进行的关键字比较次数的期望值。

在等概率情况下，顺序查找成功时的平均查找长度为

n1nn1

ASLpc(ni1)

seqiin2

i1i1(8-1)

若待查找的关键字k不在表中，则必须进行n+1次比较才

能确定查找失败。顺序查找的平均查找长度应当综合考虑查找

成功时的平均查找长度和查找失败时的平均查找长度。

通常情况下，表中各记录被查找的可能性并不相等，例如

汉字中常用字、词的使用频率就比较高，而一些偏僻字则使用

极少。那么，为了减少平均查找长度，在事先知道查找概率或

它们的分布情况下，可将表中记录按查找概率的大小顺序存放。

若无法确定各记录的查找概率，则可对算法做如下修改：每当

查找成功，就将找到的记录位置提前一位或若干位。这样，查

找概率大的记录在查找过程中能不断向前移，在以后的查找过

程中就能减少比较次数。常用的汉字输入法就是基于这个原理。

顺序查找的优点非常明显，其算法简单，并且对线性表的

存储结构和关键字的有序性无任何要求，但是当n很大时，这种

方法的查找效率较低。因此，顺序查找只适用于长度较小的线

性表。

8.1.2折半查找

折半查找(BinarySearch)又称为二分查找，它是一种效率

较高的查找方法。查找的对象必须是顺序存储结构的有序表，

即表中记录按关键字有序。假设有序的记录序列为{R1,R2,…,

Rn}，其关键字值分别是k1,k2,…,kn。利用折半查找算法查找

关键字值k的过程是：每次将k先与表的中间记录相比较，如果

未找到，则判断k是在表的左半部还是右半部，以缩小查找范

围；逐步缩小查找区间，直至查找成功或查找区间不存在时结

束。

折半查找的过程如算法8.2所示。

在算法8.2中，low和high分别表示当前查找区间的下界和

上界，当前查找区间的中值设为mid= (low+high)/2。如果关

键字k与中值不相等，则将查找区间缩小为上一次的一半。那

么在第i次比较时，最多只剩下n/2i个记录，故折半查找又称

为二分查找。

下面举例说明。已知有序表中关键字序列为：9,15,21,33,

47,59,64,77,84,91，现要查找关键字为15及80的记录，其查

找过程如下：

(1)查找k=15的记录。

初始查找区间为R[1]～R[10]。

下标：12345678910

9152133475964778491

lowmid