查找算法匯總

第1章查找表1.0基礎知識簡介1.1靜態(tài)查找表1.2動態(tài)查找表1.3哈希表1.基本概念——若表中存在特定元素，稱查找成功，應輸出該記錄——否則，稱查找不成功（也應輸出失敗標志或失敗位置）1)查找表2)查找3)查找成功4)查找不成功5)靜態(tài)查找6)動態(tài)查找7)關(guān)鍵字8)主關(guān)鍵字9)次關(guān)鍵字——由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合——查詢(Searching)特定元素是否在表中——只查找，不改變集合內(nèi)的數(shù)據(jù)元素?！炔檎?，又改變（增減）集合內(nèi)的數(shù)據(jù)元素——元素中某個數(shù)據(jù)項的值，可用來識別一個元素

(預先確定的數(shù)據(jù)元素的某種標志)

——可以唯一標識一個元素的關(guān)鍵字例如“學號”例如“姓名”是一種數(shù)據(jù)結(jié)構(gòu)——識別若干元素的關(guān)鍵字1.0基礎知識2.對查找表經(jīng)常進行的操作1）查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個數(shù)據(jù)元素；4）從查找表中刪去某個數(shù)據(jù)元素。僅作查詢和檢索操作的查找表。靜態(tài)查找表有時在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。動態(tài)查找表3.查找表的分類1.1靜態(tài)查找表1、順序表的查找2、有序表的查找3、索引順序表的查找1、順序表的查找L復習順序表的查找運算線性表有兩種基本的查找運算。按序號查找GetData(L,i):要求查找線性表L中第i個數(shù)據(jù)元素，其結(jié)果是L.elem[i-1]按內(nèi)容查找Locate（L,e）:要求查找線性表L中與給定值e相等的數(shù)據(jù)元素，其結(jié)果是：若在表L中找到與e相等的元素，則返回該元素在表中的序號；若找不到，則返回一個“空序號”，如-1。復習順序表的按內(nèi)容查找算法分析：查找運算可采用順序查找法實現(xiàn)，即從第一個元素開始，依次將表中元素與e相比較，若相等，則查找成功，返回該元素在表中的序號；若e與表中的所有元素都不相等，則查找失敗，返回“-1”。復習算法實現(xiàn)：int

Locate(SeqListL，ElemTypee){

i=0;

//i為計數(shù)器,從第一個元素開始比較

while((i<=L.length-1)&&(L.elem[i]!=e))

/*順序掃描表,直到找到值為e的元素,或掃描到表尾而沒找到*/i++;

if

(i<=L.length-1)

return(i+1);

/*若找到值為e的元素，則返回其序號*/

else

return(-1);

/*若沒找到，則返回空序號*/}typedefstruct{

//數(shù)據(jù)元素存儲空間基址，建表時按實際長度分配，0號單元留空

int

length;//表的長度}SSTable;ElemType

*elem;i例01234567891011513192137566475808892找6464監(jiān)視哨iiii比較次數(shù)=5技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。ST.elemiST.elemi60ikey=64key=60i64示例：已知靜態(tài)查找表ST如下：intSearch_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;

//找不到時，i為0}//Search_Seq2、有序表的查找lowhighmidlowmid54上述順序查找算法實現(xiàn)簡單，但不適用于表長較大的查找表。折半查找為此引入折半查找算法先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與中間元素相比，若key小，則縮小至前半部內(nèi)查找；若key大，則縮小至后半部內(nèi)查找；intSearch_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ū)間進行查找

else

low=mid+1;

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

}return0;//順序表中不存在待查元素}//Search_Bin算法描述lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid查找過程：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查元素所在塊，再在塊內(nèi)查找適用條件：分塊有序表算法實現(xiàn)用數(shù)組存放待查元素,每個數(shù)據(jù)元素至少含有關(guān)鍵字域建立索引表，每個索引表結(jié)點含有最大關(guān)鍵字域和指向本塊第一個結(jié)點的指針3.索引查找12345678910111213141516171822121389203342443824486058745786532248861713索引表查38查找過程：（1）先確定待查元素所在的塊（子表）（2）然后在塊中順序查找ASL最大最小兩者之間表結(jié)構(gòu)有序表無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表查找方法比較順序查找折半查找索引查找1.2動態(tài)查找表一、二叉排序樹二、平衡二叉樹（1）若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；1．定義：二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（3）它的左、右子樹也都分別是二叉排序樹。（2）若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；一、二叉排序樹503080209010854035252388例如:是二叉排序樹。66不思考：二叉排序樹的中序遍歷序列有什么特點？二叉排序樹的中序遍歷序列是一個有序序列（升序）2．二叉排序樹的查找算法1）若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；3）若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。否則，若二叉排序樹為空，則查找不成功；50308020908540358832例如:二叉排序樹查找關(guān)鍵字==50,505035,503040355090,50809095從上述查找過程可見：在查找過程中，生成了一條查找路徑：

從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點;或者

從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。

——查找成功

——查找不成功根據(jù)動態(tài)查找表的定義，“插入”操作在查找不成功時才進行；3．二叉排序樹的插入算法若二叉排序樹為空樹，則新插入的結(jié)點為新的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子結(jié)點，其插入位置由查找過程得到。30201040352523設key=222245241253903027{45,24,53,12,30,27,90}（1）被刪除的結(jié)點是葉子；4．二叉排序樹的刪除算法可分三種情況討論：和插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結(jié)點之后，仍然保持二叉排序樹的特性。（1）被刪除的結(jié)點是葉子；（2）被刪除的結(jié)點只有左子樹或者只有右子樹；（1）被刪除的結(jié)點是葉子；（2）被刪除的結(jié)點只有左子樹或者只有右子樹；（3）被刪除的結(jié)點既有左子樹，也有右子樹。50308020908540358832（1）被刪除的結(jié)點是葉子結(jié)點例如:被刪關(guān)鍵字=2088其雙親結(jié)點中相應指針域的值改為“空”50308020908540358832（2）被刪除的結(jié)點只有左子樹或者只有右子樹其雙親結(jié)點的相應指針域的值改為“指向被刪除結(jié)點的左子樹或右子樹”。被刪關(guān)鍵字=408050308020908540358832（3）被刪除的結(jié)點既有左子樹，也有右子樹4040以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點被刪結(jié)點前驅(qū)結(jié)點（中序遍歷）被刪關(guān)鍵字=505030802090854035883240被刪關(guān)鍵字=50908588二、平衡二叉樹樹中每個結(jié)點的左、右子樹深度之差的絕對值不大于1。例如:548254821是平衡樹不是平衡樹平衡因子又稱AVL樹，是具有如下性質(zhì)的二叉樹：如何構(gòu)建一棵平衡二叉排序樹？構(gòu)建過程類似于二叉排序樹的建立過程，即在二叉排序樹的建立過程每當插入一個結(jié)點后，立刻檢查該樹是否平衡，如果平衡：繼續(xù)；否則：進行相應的調(diào)整！構(gòu)造平衡二叉樹的方法：

插入、判斷、平衡旋轉(zhuǎn)若在A的左子樹的左子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要進行一次順時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC若在A的右子樹的右子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要進行一次逆時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC1）LL平衡旋轉(zhuǎn)：構(gòu)造平衡二叉樹的方法：

插入、判斷、平衡旋轉(zhuǎn)若在A的右子樹的左子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要先進行順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)。(以插入的結(jié)點C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC若在A的左子樹的右子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要先進行逆時針旋轉(zhuǎn)，再順時針旋轉(zhuǎn)。(以插入的結(jié)點C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：構(gòu)造平衡二叉樹的方法：

插入、判斷、平衡旋轉(zhuǎn)ABCABCCABBCAABCBCALL型RR型RL型LR型CBAACB013037024例1：請將下面序列構(gòu)成一棵平衡二叉排序樹：

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋轉(zhuǎn)(繞B逆轉(zhuǎn),B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞C先順后逆）037090053037090053

例2:依次插入的關(guān)鍵字為5,4,2,8,6,95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字9依次插入的關(guān)鍵字為5,4,2,8,6,9

一、哈希表是什么？二、哈希函數(shù)的構(gòu)造方法

三、處理沖突的方法

四、哈希表的查找1.3哈希表一、哈希表是什么？前面介紹的所有查找都是基于待查關(guān)鍵字與表中元素進行比較而實現(xiàn)的查找方法，查找的效率依賴于查找過程中所進行的比較次數(shù)。理想的情況是希望不經(jīng)過任何比較，一次便能得到所查記錄。哈希表它既是一種查找方法，又是一種存貯方法哈希表：即散列存儲結(jié)構(gòu)。

散列法存儲的基本思想：建立關(guān)鍵碼字與其存儲位置的對應關(guān)系，或者說，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址。優(yōu)點：查找速度極快（O(1)）,查找效率與元素個數(shù)n無關(guān)！1.哈希表的概念例如：有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個元素k的存儲地址H（k）＝k，請畫出存儲結(jié)構(gòu)圖。（注：H（k）＝k稱為散列函數(shù)）解：根據(jù)散列函數(shù)H（k）＝k，可知元素14應當存入地址為14的單元，元素23應當存入地址為23的單元，……，對應散列存儲表（哈希表）如下取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，并按此存放；查找時，由同一個函數(shù)對給定值k計算地址，將k與地址單元中元素關(guān)鍵碼進行比較，確定查找是否成功。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個哈希地址上，這種現(xiàn)象稱為沖突。2.若干術(shù)語哈希方法(雜湊法)哈希函數(shù)(雜湊函數(shù))哈希表(雜湊表)沖突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))按上述思想構(gòu)造的表稱為哈希表(雜湊表)

有6個元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=kmod7通過哈希函數(shù)對6個元素建立哈希表：253923914沖突現(xiàn)象舉例：6個元素用7個地址應該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！0123456二、構(gòu)造哈希函數(shù)的方法對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法：若是非數(shù)字關(guān)鍵字，則需先對其進行數(shù)字化處理。1.

直接定址法3.平方取中法5.除留余數(shù)法4.折疊法6.隨機數(shù)法2.數(shù)字分析法哈希函數(shù)為關(guān)鍵字的線性函數(shù)H(key)=key或者

H(key)=akey+b1.

直接定址法此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小此方法僅適合于：

能預先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。2.

數(shù)字分析法假設關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。

以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。3.平方取中法

此方法適合于:

關(guān)鍵字中的每一位都有某些數(shù)字重復出現(xiàn)頻度很高的現(xiàn)象。

將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。4.折疊法此方法適合于:

關(guān)鍵字的數(shù)字位數(shù)特別多。5.除留余數(shù)法設定哈希函數(shù)為:

H(key)=keyMODp

其中，

p≤m(表長)

并且p應為不大于m的素數(shù)或是不含20以下的質(zhì)因子6.隨機數(shù)法設定哈希函數(shù)為:H(key)=Random(key)其中，Random為偽隨機函數(shù)

通常，此方法用于對長度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。注意：實際造表時總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。三、處理沖突的方法

“處理沖突”的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。1.開放定址法2.鏈地址法為產(chǎn)生沖突的地址H(key)求得一個地址序列：H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di

)MODmi=1,2,…,s1.開放定址法其中：對增量di

有三種取法1)線性探測再散列

di=ci最簡單的情況c=12)二次探測再散列

di=12,-12,22,-22,…,3)隨機探測再散列

di

是一組偽隨機數(shù)列或者

di=i×H2(key)(又稱雙散列函數(shù)探測)例如:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}設定哈希函數(shù)H(key)=keyMOD11(表長=11)19012314556819012314682+4若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突1182365511(0-1)mod118236112136251Flash演示將所有哈希地址相同的記錄都鏈接在同一鏈表中。

2.鏈地址法0123456140136198223116855ASL=(6×1+2×2+3)/9=13/9例如:同前例的關(guān)鍵字，哈希函數(shù)為H(key)=keyMOD7查找過程和造表過程一致。假設采用開放定址處理沖突，則查找過程為：四、哈希表的查找

對于給定值K，計算哈希地址i=H(K)