第8章查找第1講第6章樹與二叉樹1第8章查找查找是對數(shù)據(jù)進行處理時常用操作，是各種數(shù)據(jù)結(jié)構(gòu)中最常用的算法之一。不論在線性表中還是在樹或圖中都會涉及查找問題。例如：在一個電話通信表中，查找某個員工的電話；在計算機的某個操作系統(tǒng)環(huán)境下，查找某個文件；在互聯(lián)網(wǎng)上，通過搜索引擎查找所需要的某類信息。這些都是典型的查找問題。查找算法的優(yōu)劣對系統(tǒng)運行效率的影響極大。本章討論有關(guān)查找的若干算法，并通過對它們的分析來比較各種查找方法的優(yōu)劣。

2第8章查找本章重點介紹基于內(nèi)存中的數(shù)據(jù)集合的典型查找方法。同時簡單介紹涉及外部存儲的查找方法，如：B?樹、B+樹等。主要內(nèi)容： 查找的基本概念 靜態(tài)查找 動態(tài)查找 哈希表及其查找3本章分為（3～4）講第1講

8.1

查找的基本概念

8.2

靜態(tài)查找表第3講

8.4哈希表及其查找第2講

8.4動態(tài)查找表

供教師參考48.1查找的基本概念查找（Search）也稱檢索，就是確定一個已給的數(shù)據(jù)是否出現(xiàn)在某個數(shù)據(jù)元素集合中。

查找表（SearchTable）是由一組類型相同的數(shù)據(jù)元素（記錄）構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素間存在著松散的關(guān)系。因此，查找表是一種靈便的數(shù)據(jù)結(jié)構(gòu)?？谑觯?/p>

例如，學(xué)生高考成績表存放著全體考生的記錄，每個記錄看作一個數(shù)據(jù)元素，包含有考生的準考證號、姓名以及語文、數(shù)學(xué)等各科成績和總成績。當(dāng)按照準考證號或姓名進行成績查詢時，就是數(shù)據(jù)查找問題。將高考成績表視為查找表。5查找表、記錄和關(guān)鍵字表通常是指文件，文件是由記錄組成的集合。本章討論的是用于查找的內(nèi)存中若干記錄的集合，稱查找表。每個記錄（Record）表示數(shù)據(jù)元素，由若干個數(shù)據(jù)項組成。每個數(shù)據(jù)項，稱為域（Field）或字段（Segment）。是數(shù)據(jù)表示的基本單位。每個記錄（數(shù)據(jù)元素）中總存在一個或一組數(shù)據(jù)項，它們的值能夠標識（識別）一個數(shù)據(jù)元素，這個數(shù)據(jù)項稱為關(guān)鍵字（Key）。6主關(guān)鍵字和次關(guān)鍵字能夠唯一地標識一個記錄的關(guān)鍵字叫主關(guān)鍵字（PrimaryKey）。不能唯一確定一個記錄的關(guān)鍵字，稱為次關(guān)鍵字（SecondaryKey）或?qū)傩杂?。例如：高考成績表準考證號為主關(guān)鍵字。語文、數(shù)學(xué)成績是次關(guān)鍵字或?qū)傩杂颉?查找（Searching）一般提法是：設(shè)查找表有n個具有相同類型的記錄r0，r1，r2，…，rn?1，每個記錄由一個稱為主關(guān)鍵字的數(shù)據(jù)項和若干相關(guān)數(shù)據(jù)項的值組成，對給定值K，查找是否存在關(guān)鍵字值等于K的某個記錄。查找的結(jié)果有兩種：

1.查找成功，可給出整個記錄的信息，或該記錄的位置；

2.查找失敗，可給出查找不成功的信息，或一個“空”記錄或“空”指針。8查找方法的分類按查找表的結(jié)構(gòu)可將查找表分為靜態(tài)查找表（StaticSearchTable）和動態(tài)查找表（DynamicSearchTable）兩類。

靜態(tài)查找表是指在查找過程中其結(jié)構(gòu)始終不發(fā)生變化的查找表；動態(tài)查找表是指其結(jié)構(gòu)在查找過程中可能發(fā)生插入/刪除變化的查找表。靜態(tài)查找表主要采用順序存儲結(jié)構(gòu)。而動態(tài)查找表一般都采用鏈表存儲結(jié)。后面的哈希表及查找，有時采用順序結(jié)構(gòu)，有時采用鏈表結(jié)構(gòu)。9分析算法的主要因素：常以算法的效率和存儲開銷來衡量查找算法的優(yōu)劣。效率和存儲開銷常常是相互制約很難兼顧，效率只是相對的。衡量查找算法效率的主要因素是，已知的K值與記錄中關(guān)鍵字的比較。通常把對關(guān)鍵字的最多比較次數(shù)和平均比較次數(shù)作為兩個基本的技術(shù)指標。對查找表進行查找，對關(guān)鍵字比較的最多次數(shù)叫做最大查找長度（MaximumSearchLength，MSL）。10平均查找長度：對查找表進行查找，對關(guān)鍵字的平均比較次數(shù)叫做平均查找長度（AverageSearchLength，ASL）。對n個對象記錄進行查找時，平均查找長度：

Ci

為查找第i個記錄所需的比較次數(shù)，

Pi為查找第i個記錄的查找概率（可能性）。簡單情況下認為是等概率的，Pi均等于1/n。118.2靜態(tài)查找表靜態(tài)查找表是指在查找過程中其結(jié)構(gòu)始終不發(fā)生變化的查找表。靜態(tài)查找表主要采用順序存儲結(jié)構(gòu)。數(shù)據(jù)元素（記錄）結(jié)構(gòu)如下：constintMAXSIZE=100;//表的最大長度typedef

int

KeyType; //關(guān)鍵字的類型struct

datanode //記錄結(jié)構(gòu)

{KeyTypekey;

//關(guān)鍵字域

charch; //其他屬性域

};12順序表類：

classSqtable{private:datanode

r[MAXSIZE];//查找表

intn;//數(shù)據(jù)元素個數(shù)，表長

public:Sqtable();voidcreat();voidoutput();voidsq_search(KeyTypeK);//順序查找

voidbinary_search(KeyTypeK);//折半查找

//………};138.2.1

順序表的查找已知表r、關(guān)鍵數(shù)據(jù)K、表長n，算法8.1

voidSqtable::sq_search(KeyTypeK){r[n].key=K;//設(shè)置監(jiān)視哨

inti=0;while(r[i].key!=K))i++;

if(i<n)

cout<<"\n查找成功，記錄下標為："<<i<<endl;elsecout<<"\n查找失敗!\n"<<endl;}14算法分析：（1）在最壞的情況下，順序查找需要比較n次，即MSL=n。（2）假定各記錄的查找機會均等，即Pi=1/n。由于查找第i個記錄需要比較i次，即Ci=i，于是有：

這樣，最大查找長度和平均查找長度的數(shù)量級，即算法的時間復(fù)雜度為O(n)。15假設(shè)有n=8個記錄的查找表：8個關(guān)鍵字為：8131104434757312分析：如果K=12需要比較8次，成功。如果K=60也需要比較8次，不成功。因此可以說最大比較長度為MSL=n=8。查找成功的平均比較長度：ASL=(1+2+…+8)/8=4.5。常將ASL看成查找算法的時間復(fù)雜度。 16

實際的數(shù)據(jù)查詢系統(tǒng)中，記錄被查找的頻率或機會并不相同。

在高考成績記錄中，單科成績優(yōu)秀者、總成績排在前10名者常被查詢，而單科成績和總成績一般的人則很少問津，若把常查找的記錄盡量放前，則可降低ASL。如，根據(jù)對10個記錄做100次查詢得到的統(tǒng)計資料，其中一個被查找37次，兩個各被查找25次，三個各被查找3次，其余各被查找1次。按查找次數(shù)遞減的順序進行排列（見下頁表），則對這些記錄進行順序查找時，其平均查找長度為2.41。這比一般平均查找長度5.5效率提高了1.28倍?？刹シ胖v解,可只講,但不播放文字.17

10個記錄按查找次數(shù)遞減順序排列情況記錄查找次數(shù)統(tǒng)計概率記錄查找次數(shù)統(tǒng)計概率

r1370.37r630.03r2250.25r710.01r3250.25r810.01r430.03r910.01r530.03r1010.01可播放講解,可只講,但不播放文字.188.2.2

有序表的折半查找對于以數(shù)組方式存儲的記錄，如果數(shù)組中各個記錄的次序是按其關(guān)鍵字值的大小順序排列的，則稱為有序表。對順序分配的有序表可以采用折半查找（BinarySearch），又稱二分查找。折半查找不像順序查找那樣，從第1個記錄開始逐個順序搜索，而是每次把要找的給定值K，與在中間位置的記錄的關(guān)鍵字值進行比較。19有序表的折半查找設(shè)數(shù)組r有n個記錄。每個記錄的關(guān)鍵字值按升序排列為：

r0.key，r1.key，r2.key，…，

rn-1.key

當(dāng)i＜j時，有ri.key≤rj.key。開始，中間位置記錄的序號為m=

將給定值K與rm.key比較，有3種可能的結(jié)果：（1）K=rm.key。查找成功，結(jié)束查找。（2）K<rm.key。則對左半部分繼續(xù)用折半查找進行搜索。（3）K>rm.key。則對右半部分繼續(xù)用折半查找進行搜索。20

這樣，在查找過程中搜索區(qū)間不斷對分并成指數(shù)地縮小，因而查找速度明顯地快于順序查找。當(dāng)最后只剩下一個記錄，而且此記錄不是要找的記錄，則宣告查找失敗。假有一組記錄的關(guān)鍵字值（ri.key）為：

5123143477381104

用low,m,high

分別指向第一個、中間一個和最后一個記錄的下標。

low=0，high=7，m=3。21例如：K=73假設(shè)要查找K=73的記錄，則折半查找過程如下：

5123143477381104

↑

↑↑lowmhigh因K＞43(rm.key)，下一步查找區(qū)間必定在右半部：

5123143477381104↑↑↑

lowmhigh此時，low=4，high=7，m=5。由于K=73，查找成功，所找到的記錄序號為5。22再如：k=15假若查找K=15的記錄，則折半查找過程如下：

5123143477381104

↑↑

↑lowmhigh

因low=0、high=7、m=3，有K＜43。下一步查找區(qū)間必定在下標為3的記錄的左半部分:

5123143477381104

↑

↑

↑low

mhigh23

5123143477381104

↑

↑

↑low

mhigh

因low=0、high=2、m=1，K＞12，下一步查找區(qū)間必定轉(zhuǎn)到下標為1的記錄的右半部分:

5123143477381104

↗↑↖

lowmhigh此時low、high、m均指31，K≠31，查找失敗。24折半查找算法-算法8.2voidSqtable::Sqtable

binary_search(KeyTypeK){int

m,low,high,find;low=0;high=n-1;find=0;do{m=(low+high)/2;

if(K==r[m].key){cout<<"\n查找成功，記錄下標："<<m<<endl;find=1;}elseif(K<r[m].key)high=m–1;elselow=m+1;}while(find==0&&low<=high);

if(find==0)cout<<"查找失??！\n";}25折半查找分析-折半查找的二叉判定樹

可用二叉樹來說明，分析前例中的8個記錄：數(shù)據(jù)：5123143477381104

下標：01234567樹根結(jié)點是第一次中指針m值(下標)，左子樹的根值是左半表的m值，……。該樹是二叉排序樹，由m取值組成。26查找成功的情況：

在判定樹中可直觀看出查找關(guān)鍵字的比較次數(shù)。若K=43，記錄下標是3，比較1次找到。又如K=81，記錄下標6在第三層，比較3次找到。再如K=104，記錄下標7在第四層，比較4次找到。查找成功時的平均查找長度：ASL

=

(1*1+2*2+4*3+1*4)/8

=

21/8=2.62527查找不成功的情況：

若K=1，它比0號記錄的關(guān)鍵字5還要小，該記錄不存在，從樹中可以看出比較3次未找到。又如K=8，它比0號記錄的關(guān)鍵字5大，但它比1號記錄的關(guān)鍵字12小，該記錄也不存在，可以看出比較3次未找到。再如K=110，它比7號記錄的關(guān)鍵字104還要大，該記錄不存在，可以看出比較4次未找到。那么K=100呢？它仍是比較4次未找到。，

28折半查找算法時間復(fù)雜度：從圖可知，折半查找的過程是從二叉樹的根結(jié)點開始，到該序號的記錄結(jié)點被查找的過程。因此，最大比較的次數(shù)不超過二叉樹的深度：

，

粗略估算，折半查找的平均查找長度數(shù)量級，即算法時間復(fù)雜度亦為O(log2n)。

可見，折半查找的優(yōu)點是比較的次數(shù)少，查找速度快。但，以預(yù)先對記錄按關(guān)鍵字大小排序為代價。另外，由于存儲結(jié)構(gòu)必須是向量，所以對經(jīng)常要進行插入和刪除操作的表，不宜采用這種方法。298.2.3靜態(tài)索引結(jié)構(gòu)

靜態(tài)索引結(jié)構(gòu)就是索引順序表的查找。在靜態(tài)查找表中數(shù)據(jù)對象的個數(shù)很多時，查找效率非常低，這時可以采用索引方法來實現(xiàn)查找，進行分塊查找。

分塊查找又稱索引順序查找，是順序查找的一種改進。除表本身以外，需建立一個“索引表”。30靜態(tài)索引結(jié)構(gòu)除表本身以外，需建立一個“索引表”。如圖所示為一個順序表及其索引表。共含有18個紀錄，分成3個子表：

(r0，r1，r2，…，r5)、

(r6，r7，r8，…，r11)、

(r12，r13，…，r17)。對每個子表（或稱塊）建立一個索引項，每項其中包括兩內(nèi)容：塊的最大關(guān)鍵字和塊的首地址。31索引表必須按關(guān)鍵字有序。而查找表或者有序，或者分塊有序。所謂“分塊有序”是指第i個子表中所有紀錄的關(guān)鍵字均大于第i-1個子表中的最大關(guān)鍵字。分塊查找過程分兩步:先確定待查記錄所在的塊（子表），然后在塊中順序查找。