數據結構第9章 查找

第九章查找

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

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

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

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

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

（3）在查找表中插入一個數據元素；

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

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

int

Search_Bin(SSTableST,KeyType

kval)

{

//在有序表ST中折半查找其關鍵字等于kval的數據元素，

//若找到，則函數值為該元素在表中的位置，否則為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ù)在前半區(qū)間內進行查找

elselow=mid+1;

//繼續(xù)在后半區(qū)間內進行查找

}//while

return0;

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

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

線性表中的記錄按關鍵字“分段有序”稱它為"分塊有序表")，同時，另建一個"索引"，由"分塊有序表"和相應的"索引"構成一個"索引順序表"，

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

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

一、二叉查找樹的定義

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

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

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

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

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

二叉鏈表作為二叉查找樹的存儲結構typedef

struct

BiTNode

{

//結點結構

ElemTypedata;

//數據元素

struct

BiTNode

*lchild,*rchild;

//左右孩子指針

}

BiTNode,*BSTree;

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

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

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

1）若給定值等于根結點的關鍵字，則查找成功；

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

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

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

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

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

分三種情況討論：

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

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

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

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

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

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

9.3.1何謂哈希表

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

根據設定的哈希函數

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

9.3.2構造哈希函數的方法

若對于關鍵字集合中的任意一個關鍵字，經哈希函數映象到地址集合中任何一個地址的概率相等，則稱此類哈希函數為均勻的哈希函數

構造均勻的哈希函數的方法有如下幾種：

一、直接定址法

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

（a和b均為常數）

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

二、數字分析法

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

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

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

例如，key=110108780428895

，(哈希表的表長為1000)

895

824780

801+）1103410

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

六、隨機數法

當關鍵字不等長時，可取關鍵字的某個偽隨機函數值作為哈希地址。

Hash(key)=random(key)

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

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

一、開放定址法

二、鏈地址法

一、開放定址

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

若也已被占用，則再H2

=(Hash(key)+d2)MODm，

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

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

22,

-22,…,

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

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

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

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

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

則表