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

第九章查找

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

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

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

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

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

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

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

折半查找(BinarySearch)又稱二分查找折半查找的過(guò)程為：給定值首先和處于待查區(qū)間“中間位置”的關(guān)鍵字進(jìn)行比較，若相等，則查找成功，否則將查找區(qū)間縮小到“前半個(gè)區(qū)間”或“后半個(gè)區(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)鍵字“分段有序”稱它為"分塊有序表")，同時(shí)，另建一個(gè)"索引"，由"分塊有序表"和相應(yīng)的"索引"構(gòu)成一個(gè)"索引順序表"，

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

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

一、二叉查找樹(shù)的定義

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

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

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

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

例如，下圖所示是一棵二叉查找樹(shù)

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

struct

BiTNode

{

//結(jié)點(diǎn)結(jié)構(gòu)

ElemTypedata;

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

struct

BiTNode

*lchild,*rchild;

//左右孩子指針

}

BiTNode,*BSTree;

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

二、二叉查找樹(shù)的查找算法

若二叉查找樹(shù)為空，則查找不成功；否則

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

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

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

三、二叉查找樹(shù)的插入算法

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

四、二叉查找樹(shù)的刪除算法

分三種情況討論：

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

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

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

（d）fFSCPRCLQQLSLcpq方法2*p的直接前驅(qū)或直接后繼代替*p，然后再?gòu)亩媾判驑?shù)中刪除它的直接前驅(qū)或直接后繼。（b）fFPCPRCLQQLSLScpqs參見(jiàn)教材p230算法9.7算法9.89.2.3平衡二叉(查找)樹(shù)

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

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

9.3.1何謂哈希表

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

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

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

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

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

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

一、直接定址法

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

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

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

二、數(shù)字分析法

如果可能出現(xiàn)的關(guān)鍵字的數(shù)位相同，且取值事先知道，則可對(duì)關(guān)鍵字進(jìn)行分析，取其中“分布均勻”的若干位或它們的組合作為哈希表的地址。①②③④⑤⑥⑦⑧02146532021722420228742702201367022288170223298202354152023685350231932702395715例如已知80個(gè)記錄的關(guān)鍵字為8位十進(jìn)制數(shù)（右圖列出其中部分），假設(shè)哈希表的表長(zhǎng)為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

，(哈希表的表長(zhǎng)為1000)

895

824780

801+）1103410

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

六、隨機(jī)數(shù)法

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

Hash(key)=random(key)

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

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

一、開(kāi)放定址法

二、鏈地址法

一、開(kāi)放定址

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

若也已被占用，則再H2

=(Hash(key)+d2)MODm，

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

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

22,

-22,…,

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

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

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

9.4.4開(kāi)放定址的哈希表的查找和插入

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

則表