数据结构与算法课件12静态查找

8.2静态查找静态查找是指在静态查找表上进行的查找操作，查找满足条件的数据元素的存储位置或各种属性。顺序查找折半查找分块检索一、顺序查找基本思想查找表的存储结构是线性表（顺序表或链表）查找过程是依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。顺序表的类型定义#defineMAX_NUM100//用于定义表的长度typedefstructelemtype{ keytypekey; ……}RecordType[MaxSize]；数据元素个数为n(n<MAX_NUM)分别存放在数组的下标变量a[1]~a[n]中下面我们给出顺序查找的完整算法 intSeqSearch(RecordTyper,intn,KeyTypek){

/*返回关键字值等于k的数据元素在表r中的位置，n为表中元素的个数*/

i=n；

r[0].key=k；

/*监视哨*/

while(r[i].key!=k)

i--；

if(i>0)

return（i）；

/*查找成功*/

else

return（-1）；

/*查找失败*/ } /*SeqSearch*/二、折半查找折半查找只适用于对有序顺序表进行查找。折半查找的基本思想是每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复直到查找成功或查找范围缩小为空即查找失败为止。例如，假设给定有序表中关键字为（3，6，12，23，30，43，56，64，78，85，98）

，查找23图8.1折半查找初始示意图图8.2折半查找中low、mid、high的变动情况折半查找算法描述如下：intBinSearch(RecordTyper,intn,KeyTypek){/*在有序表r中折半查找关键字值等于k的数据元素*/intlow,high,mid;low=1；high=n；//置初始查找范围的低、高端指针

while(low<=high){mid=(low+high)/2；/*取表的中间位置*/if(k==r[mid].key)return（mid）；/*查找成功*/elseif(k<r[mid].key)high=mid-1；/*在左子表中查找*/elselow=mid+1；/*在右子表中查找*/}return（-1）；/*查找失败*/}/*BinSearch*/小结二分查找算法平均查找长度为log2n，比较次数少，查找速度快。只能应用于有序的顺序表。二分查找适用于那种一经建立就很少改动，而又经常需要查找的顺序表。

分块检索

分块查找(BlockingSearch)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。1、查找表存储结构查找表由“分块有序”的线性表和“有序的”索引表组成（1）“分块有序”的线性表

线性表R被均分为若干块，每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是"分块有序"的。（2）“有序的”索引表

抽取各块中的最大关键字及其起始位置和长度构成一个索引表ID中，即：

2、分块查找的基本思想

（1）首先查找索引表

索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。

（2）然后在已确定的块中进行顺序查找8146910223418193140385466467178688085140034516610285153keylink下标索引表012345678910111213141516171819key其它域位置主表

索引表中的数据元素由两个域构成，key域为被索引的若干个数据元素中关键字的最大值，link域为被索引的若干个数据元素中第一个数据元素