数据结构与算法-检索

10检索主要内容基本概念10.1线性表的检索10.2集合的检索10.3散列表的检索小结检索(10.1-10.2)2/423基本概念检索查找检索的效率非常重要尤其对于大数据量需要对数据进行特殊的存储处理在一组记录集合中找到关键码值等于给定值的某个记录，或者找到关键码值符合特定条件的某些记录的过程检索(10.1-10.2)3/424提高检索效率的方法预排序建立索引散列技术当散列方法不适合于基于磁盘的应用程序时，我们可以选择B树方法检索时充分利用辅助索引信息牺牲一定的空间从而提高检索效率把数据组织到一个表中根排序算法本身比较费时只是预处理（在检索之前已经完成）据关键码的值确定表中记录的位置缺点：不适合进行范围查询一般也不允许出现重复关键码检索(10.1-10.2)4/42检索(10.1-10.2)基本概念（续1）查找:查询某个关键字是否在(数据元素集合）表中的过程。也称作检索。主关键字:能够惟一区分各个不同数据元素的关键字次关键字:通常不能惟一区分各个不同数据元素的关键字查找成功:在数据元素集合中找到了要查找的数据元素查找不成功:在数据元素集合中没有找到要查找的数据元素静态查找:只查找，不改变数据元素集合内的数据元素动态查找:既查找，又改变（增减）集合内的数据元素静态查找表:静态查找时构造的存储结构动态查找表:动态查找时构造的存储结构5/426平均检索长度（ASL）关键码的比较：检索运算的主要操作平均检索长度(AverageSearchLength)检索过程中对关键码的平均比较次数衡量检索算法优劣的时间标准ASL是存储结构中对象总数n的函数Pi

为检索第i个元素的概率Ci

为找到第

i

个元素所需的关键码值与给定值的比较次数检索(10.1-10.2)6/427平均检索长度的例子假设线性表为（a,b,c）检索a、b、c的概率分别为0.4、0.1、0.5顺序检索算法的平均检索长度为0.4×1+0.1×2+0.5×3=2.1即平均需要2.1次给定值与表中关键码值的比较才能找到待查元素检索(10.1-10.2)7/428检索算法评估的几个问题衡量一个检索算法还需要考虑算法所需的存储量算法的复杂性...检索(10.1-10.2)8/4210.1基于线性表的检索10.1.1顺序检索10.1.2二分检索10.1.3分块检索检索(10.1-10.2)9/4210.1.1顺序检索针对线性表里的所有记录，逐个进行关键码和给定值的比较。若某个记录的关键码和给定值比较相等，则检索成功；否则检索失败(找遍了仍找不到)。存储：可以顺序、链接排序要求：无检索(10.1-10.2)10/42检索(10.1-10.2)12...n-2n-1nTomAnnieJohnRoseJack查找Jack比较2次查找John比较n-1次若查找不存在比较n次顺序检索11/42顺序检索算法template<classType>classItem{

private: Typekey;//关键码域

//…//其它域 public: Item(Typevalue):key(value){}TypegetKey(){returnkey;}//取关键码值voidsetKey(Typek){key=k;}//置关键码};vector<Item<Type>*>dataList;检索(10.1-10.2)12/42“监视哨”顺序检索算法检索成功返回元素位置，检索失败统一返回0;template<classType>intSeqSearch(vector<Item<Type>*>&dataList,intlength,Typek){inti=length;//将第0个元素设为待检索值

dataList[0]->setKey(k);//设监视哨

while(dataList[i]->getKey()!=k)i--;returni;//返回元素位置}检索(10.1-10.2)13/42顺序检索性能分析检索成功

假设检索每个关键码是等概率的：Pi=1/n检索失败

假设检索失败时都需要比较n+1次（设置了一个监视哨）检索(10.1-10.2)14/42顺序检索平均检索长度假设检索成功的概率为p，检索失败的概率为q=(1-p)（n+1)/2<ASL<(n+1)检索(10.1-10.2)15/42顺序检索优缺点优点：插入元素可以直接加在表尾Θ(1)缺点：检索时间太长Θ(n)检索(10.1-10.2)16/4210.1.2二分检索法将任一元素dataList[i].Key与给定值K比较三种情况：（1）Key=K，检索成功，返回dataList[i]

（2）Key>K，若有则一定排在dataList[i]]前（3）Key<K，若右则一定排在dataList[i]后缩小进一步检索的区间检索(10.1-10.2)17/42检索(10.1-10.2)二分检索法有序表：线性表中所有数据元素按关键码值递增（或递减）的次序排列在有序表的存储表示下，检索可以用效率更高的二分检索法实现。算法的基本思想：先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至前半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。反之，如果key大，则缩小至后半部内查找。18/42检索(10.1-10.2)表中数据元素按照主关键字顺序排列。5，13，19，21，37，56，64，75，80，88，92二分检索方法例19/42检索(10.1-10.2)5，13，19，21，37，56，64，75，80，88，92lowhighmid=(low+high)/2查找211234567891011midmid=6high=mid–1=5highmid=3midlow

=mid+1=4lowmid=4mid找到查找85lowhighmid=6midlow

=mid+1=7lowmid=9midlow

=mid+1=10lowmid=10midhigh=mid–1=9highhigh<low

查找不成功20/42检索(10.1-10.2)5，13，19，21，37，56，64，75，80，88，92lowhighmid=(low+high)/2查找211234567891011midmid=6high=mid–1=5highmid=3midlow

=mid+1=4lowmid=4mid找到查找85lowhighmid=6midlow

=mid+1=7lowmid=9midlow

=mid+1=10lowmid=10midhigh=mid–1=9highhigh<low

查找不成功21/42二分法检索算法template<classType>intBinSearch(vector<Item<Type>*>&dataList,intlength,Typek){intlow=1,high=length,mid;while(low<=high){mid=(low+high)/2;if(k<dataList[mid]->getKey())high=mid-1;//右缩检索区间

elseif(k>dataList[mid]->getKey())low=mid+1;//左缩检索区间

elsereturnmid;//成功返回位置

}return0;//检索失败，返回0}检索(10.1-10.2)22/42关键码18low=1

high=9

351

2

3

4

5

6

7

8

9

15

22

51

60

88

93

lowmidhigh1817第一次：l=1,h=9,

mid=5;array[5]=35>18第二次：l=1,h=4,mid=2;array[2]=17<18第三次：l=3,h=4,mid=3;array[3]=18＝18检索(10.1-10.2)23/42二分法检索性能分析最大检索长度失败的检索长度是

或

在算法复杂性分析中logn是以2为底的对数其他底，算法量级不变151822517892134886093351756检索(10.1-10.2)24/42二分法检索性能分析（续）成功的平均检索长度为：

(n>50)优缺点优点：平均与最大检索长度相近，检索速度快缺点：要排序、顺序存储，不易更新(插/删)检索(10.1-10.2)25/4210.1.3分块检索顺序与二分法的折衷既有较快的检索又有较灵活的更改检索(10.1-10.2)26/42分块检索思想“按块有序”设线性表中共有n个数据元素，将表分成b块不需要均匀每一块可能不满每一块中的关键码不一定有序但前一块中的最大关键码必须小于后一块中的最小关键码检索(10.1-10.2)27/42检索(10.1-10.2)分块检索思想索引表各块中的最大关键码及各块起始位置可能还需要块中元素个数（每一块可能不满）索引表是一个递增有序表由于表是分块有序的8146910223418193140385466467178688085140034516610285153keylink下标索引表012345678910111213141516171819key其它域位置主表28/42索引表索引表各块中的最大关键码及各块起始位置可能还需要块中元素个数（每一块可能不满）索引表是一个递增有序表由于表是分块有序的检索(10.1-10.2)29/42分块检索——索引顺序结构link:Key:01234567891011121314151617

2213983342442448608074498653

00612-

2248860556块内最大关键码块起始位置块内有效元素个数count:检索(10.1-10.2)30/42typedefstruct{ intmaxkey,firstloc,count;}Index;typedefstruct{ int*elem,length,blknum;//块的数目 Indexidx[MAXBLOCK];//块起始位置

//和最大元素，其中idx[0]不利用}IdxSqList; //索引顺序表类型检索(10.1-10.2)31/42intSearch_IdxSeq(IdxSqListL,intkey){ if(key>L.idx[L.blknum].maxkey) returnERROR; inti,j,temp,mid,low,high,found; low=1;high=L.blknum;found=false; while(low<=high&&!found){ mid=(low+high)/2 if(key<=L.idx[mid].maxkey &&key>L.idx[mid-1].maxkey) found=true; //就在第mid块中 elseif(key>L.idx[mid].maxkey) low=mid+1; //向右找 elsehigh=mid-1; //向左找 }检索(10.1-10.2)32/42

i=L.idx[mid].firstloc; //块的下界 j=i+L.idx[mid].count-1;//块的上界 temp=L.elem[i-1]; //保存左邻元素 L.elem[i-1]=key; //设置监视哨 for(k=j;L.elem[k]!=key;k--) ; //顺序查找 L.elem[i-1]=temp; //放回左邻元素 if(k<i) returnERROR; //未找到 returnk;}检索(10.1-10.2)33/42分块检索性能分析分块检索为两级检索先在索引表中确定待查元素所在的块；设在索引表中确定块号的时间开销是ASLb然后在块内检索待查的元素。在块中查找记录的时间开销为ASLwASL(n)=ASLb+ASLw检索(10.1-10.2)34/42分块检索性能分析(续2)假设在索引表中用顺序检索，在块内也用顺序检索当s=时，ASL取最小值，

ASL=+1≈

检索(10.1-10.2)35/42分块检索性能分析(续3)当n=10,000时顺序检索5,000次二分法检索14次分块检索100次如果数据块（子表）存放在外存时，还会受到页块大小的制约此时往往以外存一个Ｉ/Ｏ读取的数据（一页）作为一块检索(10.1-10.2)36/42分块检索性能分析(续4)若采用二分法检索确定记录所在的子表，则检索成功时的平均检索长度为ASL=ASLb

+ASLw

log2(b+1)-1+(s+1)/2

log2(1+n/s)+s/2检索(10.1-10.2)37