查找算法匯總

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

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

——可以唯一標(biāo)識(shí)一個(gè)元素的關(guān)鍵字例如“學(xué)號(hào)”例如“姓名”是一種數(shù)據(jù)結(jié)構(gòu)——識(shí)別若干元素的關(guān)鍵字1.0基礎(chǔ)知識(shí)2.對(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)查找表3.查找表的分類1.1靜態(tài)查找表1、順序表的查找2、有序表的查找3、索引順序表的查找1、順序表的查找L復(fù)習(xí)順序表的查找運(yùn)算線性表有兩種基本的查找運(yùn)算。按序號(hào)查找GetData(L,i):要求查找線性表L中第i個(gè)數(shù)據(jù)元素，其結(jié)果是L.elem[i-1]按內(nèi)容查找Locate（L,e）:要求查找線性表L中與給定值e相等的數(shù)據(jù)元素，其結(jié)果是：若在表L中找到與e相等的元素，則返回該元素在表中的序號(hào)；若找不到，則返回一個(gè)“空序號(hào)”，如-1。復(fù)習(xí)順序表的按內(nèi)容查找算法分析：查找運(yùn)算可采用順序查找法實(shí)現(xiàn)，即從第一個(gè)元素開始，依次將表中元素與e相比較，若相等，則查找成功，返回該元素在表中的序號(hào)；若e與表中的所有元素都不相等，則查找失敗，返回“-1”。復(fù)習(xí)算法實(shí)現(xiàn)：int

Locate(SeqListL，ElemTypee){

i=0;

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

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

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

if

(i<=L.length-1)

return(i+1);

/*若找到值為e的元素，則返回其序號(hào)*/

else

return(-1);

/*若沒找到，則返回空序號(hào)*/}typedefstruct{

//數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按實(shí)際長(zhǎng)度分配，0號(hào)單元留空

int

length;//表的長(zhǎng)度}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;

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

else

low=mid+1;

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

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

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

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

——查找成功

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

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

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

插入、判斷、平衡旋轉(zhuǎn)ABCABCCABBCAABCBCALL型RR型RL型LR型CBAACB013037024例1：請(qǐng)將下面序列構(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)鍵字與表中元素進(jìn)行比較而實(shí)現(xiàn)的查找方法，查找的效率依賴于查找過(guò)程中所進(jìn)行的比較次數(shù)。理想的情況是希望不經(jīng)過(guò)任何比較，一次便能得到所查記錄。哈希表它既是一種查找方法，又是一種存貯方法哈希表：即散列存儲(chǔ)結(jié)構(gòu)。

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

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

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

H(key)=akey+b1.

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

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

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

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

此方法適合于:

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

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

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

H(key)=keyMODp

其中，

p≤m(表長(zhǎng))

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

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

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

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

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

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

di=ci最簡(jiǎn)單的情況c=12)二次探測(cè)再散列

di=12,-12,22,-22,…,3)隨機(jī)探測(cè)再散列

di

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

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

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

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