數(shù)據(jù)結(jié)構(gòu)與算法-檢索

10檢索主要內(nèi)容基本概念10.1線性表的檢索10.2集合的檢索10.3散列表的檢索小結(jié)檢索(10.1-10.2)2/423基本概念檢索查找檢索的效率非常重要尤其對(duì)于大數(shù)據(jù)量需要對(duì)數(shù)據(jù)進(jìn)行特殊的存儲(chǔ)處理在一組記錄集合中找到關(guān)鍵碼值等于給定值的某個(gè)記錄，或者找到關(guān)鍵碼值符合特定條件的某些記錄的過(guò)程檢索(10.1-10.2)3/424提高檢索效率的方法預(yù)排序建立索引散列技術(shù)當(dāng)散列方法不適合于基于磁盤(pán)的應(yīng)用程序時(shí)，我們可以選擇B樹(shù)方法檢索時(shí)充分利用輔助索引信息犧牲一定的空間從而提高檢索效率把數(shù)據(jù)組織到一個(gè)表中根排序算法本身比較費(fèi)時(shí)只是預(yù)處理（在檢索之前已經(jīng)完成）據(jù)關(guān)鍵碼的值確定表中記錄的位置缺點(diǎn)：不適合進(jìn)行范圍查詢一般也不允許出現(xiàn)重復(fù)關(guān)鍵碼檢索(10.1-10.2)4/42檢索(10.1-10.2)基本概念（續(xù)1）查找:查詢某個(gè)關(guān)鍵字是否在(數(shù)據(jù)元素集合）表中的過(guò)程。也稱(chēng)作檢索。主關(guān)鍵字:能夠惟一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字次關(guān)鍵字:通常不能惟一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字查找成功:在數(shù)據(jù)元素集合中找到了要查找的數(shù)據(jù)元素查找不成功:在數(shù)據(jù)元素集合中沒(méi)有找到要查找的數(shù)據(jù)元素靜態(tài)查找:只查找，不改變數(shù)據(jù)元素集合內(nèi)的數(shù)據(jù)元素動(dòng)態(tài)查找:既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素靜態(tài)查找表:靜態(tài)查找時(shí)構(gòu)造的存儲(chǔ)結(jié)構(gòu)動(dòng)態(tài)查找表:動(dòng)態(tài)查找時(shí)構(gòu)造的存儲(chǔ)結(jié)構(gòu)5/426平均檢索長(zhǎng)度（ASL）關(guān)鍵碼的比較：檢索運(yùn)算的主要操作平均檢索長(zhǎng)度(AverageSearchLength)檢索過(guò)程中對(duì)關(guān)鍵碼的平均比較次數(shù)衡量檢索算法優(yōu)劣的時(shí)間標(biāo)準(zhǔn)ASL是存儲(chǔ)結(jié)構(gòu)中對(duì)象總數(shù)n的函數(shù)Pi

為檢索第i個(gè)元素的概率Ci

為找到第

i

個(gè)元素所需的關(guān)鍵碼值與給定值的比較次數(shù)檢索(10.1-10.2)6/427平均檢索長(zhǎng)度的例子假設(shè)線性表為（a,b,c）檢索a、b、c的概率分別為0.4、0.1、0.5順序檢索算法的平均檢索長(zhǎng)度為0.4×1+0.1×2+0.5×3=2.1即平均需要2.1次給定值與表中關(guān)鍵碼值的比較才能找到待查元素檢索(10.1-10.2)7/428檢索算法評(píng)估的幾個(gè)問(wèn)題衡量一個(gè)檢索算法還需要考慮算法所需的存儲(chǔ)量算法的復(fù)雜性...檢索(10.1-10.2)8/4210.1基于線性表的檢索10.1.1順序檢索10.1.2二分檢索10.1.3分塊檢索檢索(10.1-10.2)9/4210.1.1順序檢索針對(duì)線性表里的所有記錄，逐個(gè)進(jìn)行關(guān)鍵碼和給定值的比較。若某個(gè)記錄的關(guān)鍵碼和給定值比較相等，則檢索成功；否則檢索失敗(找遍了仍找不到)。存儲(chǔ)：可以順序、鏈接排序要求：無(wú)檢索(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;//關(guān)鍵碼域

//…//其它域 public: Item(Typevalue):key(value){}TypegetKey(){returnkey;}//取關(guān)鍵碼值voidsetKey(Typek){key=k;}//置關(guān)鍵碼};vector<Item<Type>*>dataList;檢索(10.1-10.2)12/42“監(jiān)視哨”順序檢索算法檢索成功返回元素位置，檢索失敗統(tǒng)一返回0;template<classType>intSeqSearch(vector<Item<Type>*>&dataList,intlength,Typek){inti=length;//將第0個(gè)元素設(shè)為待檢索值

dataList[0]->setKey(k);//設(shè)監(jiān)視哨

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

假設(shè)檢索每個(gè)關(guān)鍵碼是等概率的：Pi=1/n檢索失敗

假設(shè)檢索失敗時(shí)都需要比較n+1次（設(shè)置了一個(gè)監(jiān)視哨）檢索(10.1-10.2)14/42順序檢索平均檢索長(zhǎng)度假設(shè)檢索成功的概率為p，檢索失敗的概率為q=(1-p)（n+1)/2<ASL<(n+1)檢索(10.1-10.2)15/42順序檢索優(yōu)缺點(diǎn)優(yōu)點(diǎn)：插入元素可以直接加在表尾Θ(1)缺點(diǎn)：檢索時(shí)間太長(zhǎng)Θ(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]后縮小進(jìn)一步檢索的區(qū)間檢索(10.1-10.2)17/42檢索(10.1-10.2)二分檢索法有序表：線性表中所有數(shù)據(jù)元素按關(guān)鍵碼值遞增（或遞減）的次序排列在有序表的存儲(chǔ)表示下，檢索可以用效率更高的二分檢索法實(shí)現(xiàn)。算法的基本思想：先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至前半部?jī)?nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。反之，如果key大，則縮小至后半部?jī)?nèi)查找。18/42檢索(10.1-10.2)表中數(shù)據(jù)元素按照主關(guān)鍵字順序排列。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;//右縮檢索區(qū)間

elseif(k>dataList[mid]->getKey())low=mid+1;//左縮檢索區(qū)間

elsereturnmid;//成功返回位置

}return0;//檢索失敗，返回0}檢索(10.1-10.2)22/42關(guān)鍵碼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二分法檢索性能分析最大檢索長(zhǎng)度失敗的檢索長(zhǎng)度是

或

在算法復(fù)雜性分析中l(wèi)ogn是以2為底的對(duì)數(shù)其他底，算法量級(jí)不變151822517892134886093351756檢索(10.1-10.2)24/42二分法檢索性能分析（續(xù)）成功的平均檢索長(zhǎng)度為：

(n>50)優(yōu)缺點(diǎn)優(yōu)點(diǎn)：平均與最大檢索長(zhǎng)度相近，檢索速度快缺點(diǎn)：要排序、順序存儲(chǔ)，不易更新(插/刪)檢索(10.1-10.2)25/4210.1.3分塊檢索順序與二分法的折衷既有較快的檢索又有較靈活的更改檢索(10.1-10.2)26/42分塊檢索思想“按塊有序”設(shè)線性表中共有n個(gè)數(shù)據(jù)元素，將表分成b塊不需要均勻每一塊可能不滿每一塊中的關(guān)鍵碼不一定有序但前一塊中的最大關(guān)鍵碼必須小于后一塊中的最小關(guān)鍵碼檢索(10.1-10.2)27/42檢索(10.1-10.2)分塊檢索思想索引表各塊中的最大關(guān)鍵碼及各塊起始位置可能還需要塊中元素個(gè)數(shù)（每一塊可能不滿）索引表是一個(gè)遞增有序表由于表是分塊有序的8146910223418193140385466467178688085140034516610285153keylink下標(biāo)索引表012345678910111213141516171819key其它域位置主表28/42索引表索引表各塊中的最大關(guān)鍵碼及各塊起始位置可能還需要塊中元素個(gè)數(shù)（每一塊可能不滿）索引表是一個(gè)遞增有序表由于表是分塊有序的檢索(10.1-10.2)29/42分塊檢索——索引順序結(jié)構(gòu)link:Key:01234567891011121314151617

2213983342442448608074498653

00612-

2248860556塊內(nèi)最大關(guān)鍵碼塊起始位置塊內(nèi)有效元素個(gè)數(shù)count:檢索(10.1-10.2)30/42typedefstruct{ intmaxkey,firstloc,count;}Index;typedefstruct{ int*elem,length,blknum;//塊的數(shù)目 Indexidx[MAXBLOCK];//塊起始位置

//和最大元素，其中idx[0]不利用}IdxSqList; //索引順序表類(lèi)型檢索(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; //設(shè)置監(jiān)視哨 for(k=j;L.elem[k]!=key;k--) ; //順序查找 L.elem[i-1]=temp; //放回左鄰元素 if(k<i) returnERROR; //未找到 returnk;}檢索(10.1-10.2)33/42分塊檢索性能分析分塊檢索為兩級(jí)檢索先在索引表中確定待查元素所在的塊；設(shè)在索引表中確定塊號(hào)的時(shí)間開(kāi)銷(xiāo)是ASLb然后在塊內(nèi)檢索待查的元素。在塊中查找記錄的時(shí)間開(kāi)銷(xiāo)為ASLwASL(n)=ASLb+ASLw檢索(10.1-10.2)34/42分塊檢索性能分析(續(xù)2)假設(shè)在索引表中用順序檢索，在塊內(nèi)也用順序檢索當(dāng)s=時(shí)，ASL取最小值，

ASL=+1≈

檢索(10.1-10.2)35/42分塊檢索性能分析(續(xù)3)當(dāng)n=10,000時(shí)順序檢索5,000次二分法檢索14次分塊檢索100次如果數(shù)據(jù)塊（子表）存放在外存時(shí)，還會(huì)受到頁(yè)塊大小的制約此時(shí)往往以外存一個(gè)Ｉ/Ｏ讀取的數(shù)據(jù)（一頁(yè)）作為一塊檢索(10.1-10.2)36/42分塊檢索性能分析(續(xù)4)若采用二分法檢索確定記錄所在的子表，則檢索成功時(shí)的平均檢索長(zhǎng)度為ASL=ASLb

+ASLw

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

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