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

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

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

Locate(SeqListL，ElemTypee){

i=0;

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

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

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

if

(i<=L.length-1)

return(i+1);

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

else

return(-1);

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

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

int

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

*elem;i例01234567891011513192137566475808892找6464監視哨iiii比較次數=5技巧：把待查關鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執行速度。ST.elemiST.elemi60ikey=64key=60i64示例：已知靜態查找表ST如下：intSearch_Seq(SSTableST,KeyTypekey){

//在順序表ST中順序查找其關鍵字等于//key的數據元素。若找到，則函數值為//該元素在表中的位置，否則為0。

ST.elem[0].key=key;

//“哨兵”

for(i=ST.length;ST.elem[i].key!=key;--i);

//從后往前找

returni;

//找不到時，i為0}//Search_Seq2、有序表的查找lowhighmidlowmid54上述順序查找算法實現簡單，但不適用于表長較大的查找表。折半查找為此引入折半查找算法先給數據排序（例如按升序排好），形成有序表，然后再將key與中間元素相比，若key小，則縮小至前半部內查找；若key大，則縮小至后半部內查找；intSearch_Bin(SSTableST,KeyTypekey){

low=1;

high=ST.length;

//置區間初值

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;//繼續在前半區間進行查找

else

low=mid+1;

//繼續在后半區間進行查找

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

從根結點出發，沿著左分支或右分支逐層向下直至關鍵字等于給定值的結點;或者

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

——查找成功

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

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

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

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

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

例2:依次插入的關鍵字為5,4,2,8,6,95424258665842向右旋轉一次先向右旋轉再向左旋轉426589642895向左旋轉一次繼續插入關鍵字9依次插入的關鍵字為5,4,2,8,6,9

一、哈希表是什么？二、哈希函數的構造方法

三、處理沖突的方法

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

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

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

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

H(key)=akey+b1.

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

能預先估計出全體關鍵字的每一位上各種數字出現的頻度。2.

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

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

此方法適合于:

關鍵字中的每一位都有某些數字重復出現頻度很高的現象。

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

關鍵字的數字位數特別多。5.除留余數法設定哈希函數為:

H(key)=keyMODp

其中，

p≤m(表長)

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

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

“處理沖突”的實際含義是：為產生沖突的地址尋找下一個哈希地址。1.開放定址法2.鏈地址法為產生沖突的地址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

是一組偽隨機數列或者

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

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

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