第九章查找何謂查找表？

查找表是由同一類(lèi)型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。

由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。對(duì)查找表經(jīng)常進(jìn)行的操作:1）查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個(gè)數(shù)據(jù)元素；4）從查找表中刪去某個(gè)數(shù)據(jù)元素。僅作查詢和檢索操作的查找表。靜態(tài)查找表有時(shí)在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。動(dòng)態(tài)查找表查找表可分為兩類(lèi):是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。關(guān)鍵字

若此關(guān)鍵字可以識(shí)別唯一的一個(gè)記錄，則稱之謂“主關(guān)鍵字”。

若此關(guān)鍵字能識(shí)別若干記錄，則稱之謂“次關(guān)鍵字”。

根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）。

查找

若查找表中存在這樣一個(gè)記錄，則稱“查找成功”。查找結(jié)果給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”。查找結(jié)果給出“空記錄”或“空指針”。9.1靜態(tài)查找表9.2動(dòng)態(tài)查找樹(shù)表9.3哈希表9.1靜態(tài)查找表數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系R：D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素含有類(lèi)型相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。

數(shù)據(jù)元素同屬一個(gè)集合。ADTStaticSearchTable{構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的靜態(tài)查找表ST。

Create(&ST,n);操作結(jié)果：銷(xiāo)毀表ST。Destroy(&ST);初始條件：操作結(jié)果：靜態(tài)查找表ST存在；若ST中存在其關(guān)鍵字等于

key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。

Search(ST,key);初始條件：操作結(jié)果：靜態(tài)查找表ST存在，key為和查找表中元素的關(guān)鍵字類(lèi)型相同的給定值；按某種次序?qū)T的每個(gè)元素調(diào)用函數(shù)Visit()一次且僅一次，一旦Visit()失敗，則操作失敗。Traverse(ST,Visit());初始條件：操作結(jié)果：靜態(tài)查找表ST存在，Visit是對(duì)元素操作的應(yīng)用函數(shù)；typedefstruct{

//數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)

//按實(shí)際長(zhǎng)度分配，0號(hào)單元留空

int

length;//表的長(zhǎng)度}SSTable;假設(shè)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)為ElemType

*elem;數(shù)據(jù)元素類(lèi)型的定義為:typedefstruct{

keyTypekey;//關(guān)鍵字域

……

//其它屬性域}

ElemType;,TElemType;一、順序查找表二、有序查找表三、靜態(tài)查找樹(shù)表四、索引順序表

以順序表或線性鏈表表示靜態(tài)查找表一、順序查找表ST.elem回顧順序表的查找過(guò)程：假設(shè)給定值e=64,要求ST.elem[k]=e,問(wèn):k=?kkintlocation(SqListL,ElemType&e,

Status(*compare)(ElemType,ElemType)){k=1;p=L.elem;

while(k<=L.length

&&

!(*compare)(*p++,e)))k++;if(k<=L.length)returnk;

elsereturn0;}//locationST.elemiST.elemi60ikey=64key=60i64intSearch_Seq(SSTableST,KeyTypekey){

//在順序表ST中順序查找其關(guān)鍵字等于

//key的數(shù)據(jù)元素。若找到，則函數(shù)值為

//該元素在表中的位置，否則為0。

ST.elem[0].key=key;

//“哨兵”

for(i=ST.length;ST.elem[i].key!=key;

--i);

//從后往前找

returni;

//找不到時(shí)，i為0}//Search_Seq

定義：

查找算法的平均查找長(zhǎng)度

(AverageSearchLength)

為確定記錄在查找表中的位置，需和給定值

進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值

其中:n

為表長(zhǎng)，Pi

為查找表中第i個(gè)記錄的概率，且，Ci為找到該記錄時(shí)，曾和給定 值比較過(guò)的關(guān)鍵字的個(gè)數(shù)。分析順序查找的時(shí)間性能在等概率查找的情況下，

順序表查找的平均查找長(zhǎng)度為：對(duì)順序表而言，Ci=n-i+1ASL=nP1+(n-1)P2+…+2Pn-1+Pn

若查找概率無(wú)法事先測(cè)定，則查找過(guò)程采取的改進(jìn)辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。在不等概率查找的情況下，ASLss

在

Pn≥Pn-1≥···≥P2≥P1時(shí)取極小值

上述順序查找表的查找算法簡(jiǎn)單，但平均查找長(zhǎng)度較大，特別不適用于表長(zhǎng)較大的查找表。二、有序查找表

若以有序表表示靜態(tài)查找表，則查找過(guò)程可以基于“折半”進(jìn)行。ST.elemST.length例如:key=64

的查找過(guò)程如下：lowhighmidlow

mid

high

midlow

指示查找區(qū)間的下界high

指示查找區(qū)間的上界mid=(low+high)/2intSearch_Bin(SSTableST,KeyTypekey){

low=1;high=ST.length;//置區(qū)間初值

while(low<=high){mid=(low+high)/2;

if（EQ(key,ST.elem[mid].key))

returnmid;//找到待查元素

elseif(LT(key,ST.elem[mid].key))

high=mid-1;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找

else

low=mid+1;//繼續(xù)在后半?yún)^(qū)間進(jìn)行查找

}return0;//順序表中不存在待查元素}//Search_Bin先看一個(gè)具體的情況，假設(shè)：n=11分析折半查找的平均查找長(zhǎng)度6391425781011判定樹(shù)12233334444假設(shè)n=2h-1并且查找概率相等則

在n>50時(shí)，可得近似結(jié)果

一般情況下，表長(zhǎng)為n的折半查找的判定樹(shù)的深度和含有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度相同。索引順序表的查找過(guò)程：1）由索引確定記錄所在區(qū)間；2）在順序表的某個(gè)區(qū)間內(nèi)進(jìn)行查找。注意：索引可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造?？梢?jiàn)，

索引順序查找的過(guò)程也是一個(gè)“縮小區(qū)間”的查找過(guò)程。索引順序查找的平均查找長(zhǎng)度=

查找“索引”的平均查找長(zhǎng)度

+查找“順序表”的平均查找長(zhǎng)度ADTDynamicSearchTable{抽象數(shù)據(jù)類(lèi)型動(dòng)態(tài)查找表的定義如下：數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系R：

數(shù)據(jù)元素同屬一個(gè)集合。D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素含有類(lèi)型相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。InitDSTable(&DT)基本操作P：DestroyDSTable(&DT)SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&T,key);TraverseDSTable(DT,Visit());}ADTDynamicSearchTable操作結(jié)果：構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DT。InitDSTable(&DT);銷(xiāo)毀動(dòng)態(tài)查找表DT。DestroyDSTable(&DT);初始條件：操作結(jié)果：動(dòng)態(tài)查找表DT存在；若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。SearchDSTable(DT,key);初始條件：操作結(jié)果：動(dòng)態(tài)查找表DT存在，key為和關(guān)鍵字類(lèi)型相同的給定值；動(dòng)態(tài)查找表DT存在，

e為待插入的數(shù)據(jù)元素；InsertDSTable(&DT,e);初始條件：操作結(jié)果：若DT中不存在其關(guān)鍵字等于e.key的數(shù)據(jù)元素，則插入e到DT。動(dòng)態(tài)查找表DT