數(shù)據(jù)結(jié)構(gòu)第9章 查找

第九章查找

查找表（SearchTable）是由一些具有相同可辨認(rèn)特性的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。關(guān)鍵字（key）是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用它可以標(biāo)識（識別）一個數(shù)據(jù)元素。主關(guān)鍵字唯一地標(biāo)識一個元素，次關(guān)鍵字識別若干元素查找（searching）根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。定義：查找過程中先后和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值稱作查找算法的平均查找長度(AverageSearchLength)。查找表通?？煞謨深悾?/p>

1.靜態(tài)查找表

2.動態(tài)查找表如何評價查找算法的時間效率？對查找表經(jīng)常進(jìn)行的操作有：

（1）查詢某個"特定的"數(shù)據(jù)元素是否在表中；

（2）檢索某個"特定的"數(shù)據(jù)元素的各種屬性；

（3）在查找表中插入一個數(shù)據(jù)元素；

（4）從查找表中刪除某個數(shù)據(jù)元素。9.1靜態(tài)查找表9.1.1順序表的查找實現(xiàn)靜態(tài)查找表的最簡單的方法是以“順序存儲結(jié)構(gòu)的線性表-順序表”表示之。查找過程為：從第一個或最后一個數(shù)據(jù)元素起，逐個進(jìn)行“比較”直至其中某個數(shù)據(jù)元素的關(guān)鍵字等于給定值為止。缺點：其平均查找長度較大，特別是當(dāng)表中記錄數(shù)n很大時，查找效率較低。優(yōu)點：算法簡單且適應(yīng)面廣，無論表中記錄是否按關(guān)鍵字有序排列均可應(yīng)用，而且，上述討論對鏈?zhǔn)酱鎯Φ木€性表也同樣適用。9.1.2有序表的查找

折半查找(BinarySearch)又稱二分查找折半查找的過程為：給定值首先和處于待查區(qū)間“中間位置”的關(guān)鍵字進(jìn)行比較，若相等，則查找成功，否則將查找區(qū)間縮小到“前半個區(qū)間”或“后半個區(qū)間”之后繼續(xù)進(jìn)行查找。例如，在有序表(05,13,19,21,37,56,64,75,80,88,92)中查找關(guān)鍵字為21和85的數(shù)據(jù)元素。算法

int

Search_Bin(SSTableST,KeyType

kval)

{

//在有序表ST中折半查找其關(guān)鍵字等于kval的數(shù)據(jù)元素，

//若找到，則函數(shù)值為該元素在表中的位置，否則為0。

low=1;high=ST.length;

//置區(qū)間初值

while(low<=high){

mid=(low+high)/2;

if(kval==ST.elem[mid].key)

returnmid;

//找到待查元素

else

if(kval<ST.elem[mid].key)

high=mid-1;

//繼續(xù)在前半?yún)^(qū)間內(nèi)進(jìn)行查找

elselow=mid+1;

//繼續(xù)在后半?yún)^(qū)間內(nèi)進(jìn)行查找

}//while

return0;

//有序表中不存在待查元素

}//Search_Bin9.1.3索引順序表的查找

線性表中的記錄按關(guān)鍵字“分段有序”稱它為"分塊有序表")，同時，另建一個"索引"，由"分塊有序表"和相應(yīng)的"索引"構(gòu)成一個"索引順序表"，

索引表13718648225386497458604824384442332098131222最大關(guān)鍵字起始地址9.2動態(tài)查找表9.2.1動態(tài)查找表的類型定義

動態(tài)查找表的特點：在查找過程中尚需進(jìn)行"插入"或"刪除"的操作。因此，表示動態(tài)查找表的結(jié)構(gòu)應(yīng)不僅便于查找，還應(yīng)便于插入和刪除。抽象數(shù)據(jù)類型動態(tài)查找表的定義參見教材P226-2279.2.2二叉查找樹

一、二叉查找樹的定義

二叉查找樹或者是一棵空樹；或者是具有如下特性的二叉樹：

（1）若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；

（2）若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；

（3）它的左、右子樹也都分別是二叉查找樹。

例如，下圖所示是一棵二叉查找樹

二叉鏈表作為二叉查找樹的存儲結(jié)構(gòu)typedef

struct

BiTNode

{

//結(jié)點結(jié)構(gòu)

ElemTypedata;

//數(shù)據(jù)元素

struct

BiTNode

*lchild,*rchild;

//左右孩子指針

}

BiTNode,*BSTree;

例如，下圖所示是不是一棵二叉查找樹？

二、二叉查找樹的查找算法

若二叉查找樹為空，則查找不成功；否則

1）若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；

2）若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找；

3）若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。

三、二叉查找樹的插入算法

二叉查找樹結(jié)構(gòu)本身正是從空樹開始逐個插入生成的。插入的原則：若二叉查找樹為空樹，則插入的結(jié)點為新的根結(jié)點；否則，插入的結(jié)點必為一個新的葉子結(jié)點，其插入位置由查找過程確定。例如，若給定值序列為{50,30,40,80,20,36,90,40,38}

四、二叉查找樹的刪除算法

分三種情況討論：

(1)被刪結(jié)點為“葉子”，僅需修改其雙親結(jié)點的相應(yīng)指針；(2)被刪結(jié)點只有左子樹或右子樹，則只需保持該結(jié)點的子樹和其雙親之間原有的關(guān)系(3)被刪結(jié)點的左右子樹均不空。四、二叉查找樹的刪除算法

FPPLPRfp（a）（b）fFPCPRCLQQLSLScpqs四、二叉查找樹的刪除算法

FCCLfc（c）SLPRSs方法1*p的左子樹為*f的左子樹*p的右子樹為*s的右子樹（b）fFPCPRCLQQLSLScpqs四、二叉查找樹的刪除算法

（d）fFSCPRCLQQLSLcpq方法2*p的直接前驅(qū)或直接后繼代替*p，然后再從二叉排序樹中刪除它的直接前驅(qū)或直接后繼。（b）fFPCPRCLQQLSLScpqs參見教材p230算法9.7算法9.89.2.3平衡二叉(查找)樹

平衡二叉樹：它或是空樹，或具有下列特性：其左子樹和右子樹都是平衡二叉樹，且左右子樹深度之差的絕對值不大于1。平衡二叉樹非平衡二叉樹樹中結(jié)點內(nèi)的數(shù)值稱作結(jié)點的"平衡因子"，定義為左子樹的深度減去右子樹的深度。

"平衡"處理的原則是保證二叉查找樹始終處于平衡狀態(tài)。從空樹起（空樹是平衡樹），每插入一個關(guān)鍵字都需要檢查二叉查找樹是否失去平衡，如因插入新的結(jié)點引起不平衡，則需對它進(jìn)行"平衡旋轉(zhuǎn)"處理。9.3哈希表

9.3.1何謂哈希表

記錄在表中的位置為關(guān)鍵字的某個函數(shù)，通常稱這種函數(shù)為“哈希函數(shù)”。若關(guān)鍵字不同而函數(shù)值相同，則稱這兩個關(guān)鍵字（對于該哈希函數(shù)而言）為"同義詞"，并稱這種現(xiàn)象為"沖突"。

根據(jù)設(shè)定的哈希函數(shù)

H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的"象"作為相應(yīng)記錄在表中的存儲位置，這種表被稱為哈希表，這一映象的過程亦被稱為"散列"。

9.3.2構(gòu)造哈希函數(shù)的方法

若對于關(guān)鍵字集合中的任意一個關(guān)鍵字，經(jīng)哈希函數(shù)映象到地址集合中任何一個地址的概率相等，則稱此類哈希函數(shù)為均勻的哈希函數(shù)

構(gòu)造均勻的哈希函數(shù)的方法有如下幾種：

一、直接定址法

Hash(key)=key或Hash(key)=akey+b

（a和b均為常數(shù)）

直接定址所得地址集的大小和關(guān)鍵字集的大小相同，關(guān)鍵字和地址一一對應(yīng)，決不會產(chǎn)生沖突。但實際應(yīng)用中能采用直接定址的情況極少。

二、數(shù)字分析法

如果可能出現(xiàn)的關(guān)鍵字的數(shù)位相同，且取值事先知道，則可對關(guān)鍵字進(jìn)行分析，取其中“分布均勻”的若干位或它們的組合作為哈希表的地址。①②③④⑤⑥⑦⑧02146532021722420228742702201367022288170223298202354152023685350231932702395715例如已知80個記錄的關(guān)鍵字為8位十進(jìn)制數(shù)（右圖列出其中部分），假設(shè)哈希表的表長為100，即地址為00～99。三、平方取中法

如果關(guān)鍵字的所有各位分布都不均勻，則可取關(guān)鍵字的平方值的中間若干位作為哈希表的地址。例如：右表八進(jìn)制數(shù)的關(guān)鍵字及其哈希地址

關(guān)鍵字(關(guān)鍵字)2哈希地址010000100000101100121000021012001440000440116013704003702061431054131020624314704314216147347417342162474130474121634745651745四、折疊法若關(guān)鍵字的位數(shù)很多，且每一位上數(shù)字分布大致均勻，則可采用移位疊加或間界疊加，即將關(guān)鍵字分成若干部分，然后以它們的疊加和(舍去進(jìn)位)作為哈希地址。

例如，key=110108780428895

，(哈希表的表長為1000)

895

824780

801+）1103410

895428780108+）1102321間界疊加移位疊加五、除留余數(shù)法以關(guān)鍵字被某個數(shù)p除后所得余數(shù)作為哈希地址。即Hash(key)=keyMODp其中，MOD表示"取模"運算，p為不大于表長的素數(shù)或不包含小于20的質(zhì)因素的合數(shù)。

六、隨機數(shù)法

當(dāng)關(guān)鍵字不等長時，可取關(guān)鍵字的某個偽隨機函數(shù)值作為哈希地址。

Hash(key)=random(key)

對于非數(shù)值型關(guān)鍵字，則需先將它們轉(zhuǎn)化為數(shù)字。實際造表時，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。

9.3.3處理沖突的方法有兩類處理沖突的方法:

一、開放定址法

二、鏈地址法

一、開放定址

處理沖突的辦法是，設(shè)法為發(fā)生沖突的關(guān)鍵字"找到"哈希表中另一個尚未被記錄占用的位置。哈希表的表長為m（即哈希表中可用地址為：0～m-1），若關(guān)鍵字key，Hash(key)的位置已被占用，則"下一個"地址H1=(Hash(key)+d1)MODm，

若也已被占用，則再H2

=(Hash(key)+d2)MODm，

…，依次類推直至找到一個地址Hs=(Hash(key)+ds)MODm未被占用為止。即Hi是為解決沖突生成的一個地址序列，其值取決于設(shè)定"增量序列di"。對于di通?？捎腥N設(shè)定方法：

“線性探測再散列”，di=1,2,3,…,m-1，2.“平方探測再散列”，di=12,-12,

22,

-22,…,

k2(k≤m/2)，3.偽隨機探測再散列“或”雙散列函數(shù)探測再散列

為偽隨機數(shù)列或者di=i×H2(key)，（H2(key)為關(guān)鍵字的另一個哈希函數(shù)）按線性探測再散列處理沖突構(gòu)造的哈希表為：012345678910562314688270361991按平方探測再散列處理沖突構(gòu)造的哈希表為：012345678910562314708268361991按雙散列函數(shù)探測處理沖突構(gòu)造的哈希表為：012345678910235668147082911936二、鏈地址法

將所有關(guān)鍵字為"同義詞"的記錄鏈接在一個線性鏈表中例如，假設(shè)關(guān)鍵字序列為{19,56,23,14,68,82,70,36,91}，哈希表的表長為7，哈希函數(shù)為Hash(key)=key%7，則構(gòu)建的以鏈地址處理沖突的哈希表如flash9-4-2所示。

9.4.4開放定址的哈希表的查找和插入

在利用開放定址處理沖突的哈希表中進(jìn)行查找時，首先應(yīng)計算給定值的哈希函數(shù)值，若表中該位置上沒有記錄，

則表