數(shù)據(jù)結(jié)構(gòu)中常見的基本結(jié)構(gòu)

1、整理課件 數(shù)據(jù)結(jié)構(gòu)中常見的基本結(jié)構(gòu) 線性線性結(jié)構(gòu) 樹形樹形結(jié)構(gòu) 圖狀圖狀結(jié)構(gòu) 集合集合結(jié)構(gòu) 線性表線性表 棧棧 隊列隊列 串串 樹和二叉樹樹和二叉樹 圖圖 第第9 9章章 查找表查找表 整理課件 什么是查找？什么是查找？ 如何進行查找？如何進行查找？ 隨機查閱有關(guān)的班級課程檔案！隨機查閱有關(guān)的班級課程檔案！ 2006.12.032006.12.03是什么日子？是什么日子？評估專家進校評估專家進校 對班級課程檔案進行的最為常見的對班級課程檔案進行的最為常見的“操作操作”是什么？是什么？ 對同學(xué)而言： 查看、核實 現(xiàn)場試驗 查找與現(xiàn)實生活的密切關(guān)系如何？查找與現(xiàn)實生活的密切關(guān)系如何？ 整理課件 請

2、查閱號18號同學(xué)的成績 整理課件 整理課件 請查閱 “周麗”同學(xué)的成 績 整理課件 整理課件 結(jié)論： 1.按照學(xué)號查找相對容易、省時 2.按照姓名查找相對費時 同樣：日常生活中的查字典也是如此！ 數(shù)據(jù)存放的方式?jīng)Q定數(shù)據(jù)查找的方法 原因：一個有序、一個無序 整理課件 第第9章章 查找表查找表 9.1 基礎(chǔ)知識簡介基礎(chǔ)知識簡介 9.2 靜態(tài)查找表靜態(tài)查找表 9.3 動態(tài)查找表動態(tài)查找表 9.4 哈希表哈希表 整理課件 1.1.基本概念基本概念 若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄 否則，稱查找不成功（也應(yīng)輸出失敗標志或失敗位置）否則，稱查找不成功

3、（也應(yīng)輸出失敗標志或失敗位置） 1)查找表 查找表 2)查找 查找 3)查找成功 查找成功 4)查找不成功 查找不成功 5)靜態(tài)查找 靜態(tài)查找 6)動態(tài)查找 動態(tài)查找 7)關(guān)鍵字 關(guān)鍵字 8)主關(guān)鍵字 主關(guān)鍵字 9)次關(guān)鍵字 次關(guān)鍵字 由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合 查詢查詢(Searching)特定元素特定元素是否在表中是否在表中 只查找，不改變集合內(nèi)的數(shù)據(jù)元素。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。 既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素 記錄中某個數(shù)據(jù)項的值，可用來識別一個記錄記錄中某個數(shù)據(jù)項的值，可用來識

4、別一個記錄 ( 預(yù)先確定的記錄的某種標志預(yù)先確定的記錄的某種標志 ) 可以可以唯一唯一標識一個記錄的關(guān)鍵字標識一個記錄的關(guān)鍵字 例如例如“學(xué)號學(xué)號” 例如例如“女女” 是一種數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu) 識別若干記錄的關(guān)鍵字識別若干記錄的關(guān)鍵字 9.1 基礎(chǔ)知識基礎(chǔ)知識 整理課件 2.2.對查找表經(jīng)常進行的對查找表經(jīng)常進行的操作操作 1）查詢查詢某個“特定的”數(shù)據(jù)元素是 否在查找表中； 2）檢索檢索某個“特定的”數(shù)據(jù)元素的 各種屬性； 3）在查找表中插入插入一個數(shù)據(jù)元素； 4）從查找表中刪去刪去某個數(shù)據(jù)元素。 整理課件 僅作查詢和檢索操作的查找表。 靜態(tài)查找表靜態(tài)查找表 有時在查詢之后，還需要將“查

5、詢”結(jié) 果為“不在查找表中”的數(shù)據(jù)元素插入 到查找表中；或者從查找表中刪除其 “查詢”結(jié)果為“在查找表中”的數(shù)據(jù) 元素。 動態(tài)查找表動態(tài)查找表 3.3.查找表的分類查找表的分類 整理課件 9.2 靜靜 態(tài)態(tài) 查查 找找 表表 整理課件 數(shù)據(jù)對象數(shù)據(jù)對象D： 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： D是具有相同特性的數(shù) 據(jù)元素的集合。 數(shù)據(jù)元素同屬一個集合。 ADT StaticSearchTable 1.抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型的定義 D是具有相同特性的數(shù) 據(jù)元素的集合。每個數(shù)每個數(shù) 據(jù)元素含有類型相同的據(jù)元素含有類型相同的 關(guān)鍵字關(guān)鍵字，可唯一標識數(shù) 據(jù)元素。 整理課件 Create( Destroy(

6、 Search(ST, key); Traverse(ST, Visit(); 基本操作基本操作 P： ADT StaticSearchTable 整理課件 typedef struct / 數(shù)據(jù)元素存儲空間基址，建表時 / 按實際長度分配，0號單元留空 int length; / 表的長度 SSTable; 2.靜態(tài)查找表靜態(tài)查找表的順序存儲結(jié)構(gòu)存儲結(jié)構(gòu) ElemType *elem; elem 0 1 2 3 4 5 6 7 8 9 10 11 typedef struct keyType key; / 關(guān)鍵字域 / 其它屬性域 ElemType ; 整理課件 3.靜態(tài)查找表的查找算法靜態(tài)

7、查找表的查找算法 1)順序查找順序查找 即用逐一比較的辦法順序查找關(guān)鍵字，即用逐一比較的辦法順序查找關(guān)鍵字， 技巧：技巧： 把待查關(guān)鍵字把待查關(guān)鍵字key存入表頭或表尾存入表頭或表尾 （俗稱（俗稱“哨兵哨兵”），）， 即用即用逐一比較逐一比較的辦法順序查找關(guān)鍵字，的辦法順序查找關(guān)鍵字， 這顯然是最直接的辦法。這顯然是最直接的辦法。 技巧：技巧： 把待查關(guān)鍵字把待查關(guān)鍵字key存入表頭或表尾存入表頭或表尾 （俗稱（俗稱“哨兵哨兵”），這樣可以加快執(zhí)），這樣可以加快執(zhí) 行速度。行速度。 Flash動畫演示 整理課件 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3

8、4 5 6 7 8 9 10 11 ST.Length ST.elem i 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length ST.elem i 60 i key=64 key=60 i 64 示例：已知靜態(tài)查找表ST如下： 整理課件 int Search_Seq(SSTable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為0。 ST.elem0.key = key; / “哨兵” for (i=ST.le

9、ngth; ST.elemi.key!=key; -i); / 從后往前找 return i; / 找不到時，i為0 / Search_Seq 整理課件 int Search_Seq(SSTable ST, KeyType key) pd=0; / 判斷標記 for (i=1;i=ST.length; i+) if (ST.elemi.key=key) pd=i; / 判斷標記記錄具體位置 break; return pd; / Search_Seq 實踐：在上題的基礎(chǔ)上寫出從前往后找的算法 整理課件 上述順序查找算法簡單，但平均查找長 度較大，特別不適用于表長較大的查找表。 2)折半查找折半

10、查找 為此引入折半查找算法 先給數(shù)據(jù)排序（例如按升序排好），形 成有序表，然后再將key與中間元素相比，若 key小，則縮小至左半部內(nèi)查找； 為此引入折半查找算法 先給數(shù)據(jù)排序（例如按升序排好），形 成有序表，然后再將key與中間元素相比，若 key小，則縮小至左半部內(nèi)查找；若key大， 則縮小至右半部內(nèi)查找； 為此引入折半查找算法 先給數(shù)據(jù)排序（例如按升序排好），形 成有序表，然后再將key與中間元素相比，若 key小，則縮小至左半部內(nèi)查找；若key大， 則縮小至右半部內(nèi)查找；再取其中值比較， 每次縮小1/2的范圍，直到查找成功或失敗為 止。 整理課件 05 13 19 21 37 56 6

11、4 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elem ST.length 例如例如: key=64 的查找過程如下： lowhigh mid low mid high mid low 指示查找區(qū)間的下界 high 指示查找區(qū)間的上界 mid = (low+high)/2 整理課件 int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值 while (low = high) mid = (low + high) / 2; if （EQ (key , ST.

12、elemmid.key) ) / return mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) / data.key=key) return(T); else if (T-data.keykey) return(SearchBST (T-lchild, key) ); else return(SearchBST (T-rchild, key) ); / SearchBST 整理課件 根據(jù)動態(tài)查找表的定義，“插入插入” 操作在操作在查找不成功查找不成功時才進行時才進行； 4二叉排序樹的插入算法二叉排序樹的插入算法 若二叉排序樹為空樹空樹，則

13、新插入的 結(jié)點為新的根結(jié)點新的根結(jié)點；否則，新插入 的結(jié)點必為一個新的葉子結(jié)點新的葉子結(jié)點，其 插入位置插入位置由查找過程得到。 這樣算法需要改進！ 整理課件 二叉排序樹查找算法的改進：二叉排序樹查找算法的改進： Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree / SearchBST 否則表明否則表明查找不成功查找不成功，返回，返回 / 指針指針 p 指向查找路徑上訪問的最后一個結(jié)點，指向查找路徑上訪問的最后一個結(jié)點， / 并返回函數(shù)值為并返回函數(shù)值為FALSE, 指針指針 f 指向當前訪問指向當前訪問 / 的結(jié)點的雙親，其初

14、始調(diào)用值為的結(jié)點的雙親，其初始調(diào)用值為NULL 整理課件 if (!T) else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找不成功 p = T; return TRUE; / 查找成功 SearchBST (T-lchild, key, T, p ); / 在左子樹中繼續(xù)查找 SearchBST (T-rchild, key, T, p ); / 在右子樹中繼續(xù)查找 整理課件 30 20 10 40 3525 23 f T 設(shè) key = 48 f T f

15、T 22 p f T f T T T T f f f p 整理課件 Status Insert BST(BiTree 否則，不進行插入并返回否則，不進行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST 二叉排序樹的插入算法：二叉排序樹的插入算法： 整理課件 s = (BiTree) malloc (sizeof (BiTNode); / 為新結(jié)點分配空間 s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 為新

16、的根結(jié)點 else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 為 *p 的左孩子 else p-rchild = s; / 插入 *s 為 *p 的右孩子 return TRUE; / 插入成功 二叉樹生成二叉樹生成Flash 整理課件 （1）被刪除的結(jié)點是葉子； 5二叉排序樹的刪除算法二叉排序樹的刪除算法 可分三種情況討論： 和插入相反，刪除在查找成功查找成功之后進行，并 且要求在刪除二叉排序樹上某個結(jié)點之后，仍仍 然保持二叉排序樹的特性然保持二叉排序樹的特性。 （1）被刪除的結(jié)點是葉子； （2）被刪除的結(jié)點只有左子樹或者只有 右子

17、樹； （1）被刪除的結(jié)點是葉子； （2）被刪除的結(jié)點只有左子樹或者只有 右子樹； （3）被刪除的結(jié)點既有左子樹，也有右 子樹。 整理課件 50 3080 2090 85 40 35 8832 （1）被刪除的結(jié)點是葉子結(jié)點葉子結(jié)點 例如例如: 被刪關(guān)鍵字被刪關(guān)鍵字 = 2088 其雙親結(jié)點中相應(yīng)指針域的值改為其雙親結(jié)點中相應(yīng)指針域的值改為“空空” 整理課件 50 3080 2090 85 40 35 8832 （2）被刪除的結(jié)點只有左子樹只有左子樹 或者只有右子樹只有右子樹 其雙親結(jié)點的相應(yīng)指針域的值改為其雙親結(jié)點的相應(yīng)指針域的值改為 “指向被刪除結(jié)點的左子樹或右子樹指向被刪除結(jié)點的左子樹或右子

18、樹”。 被刪關(guān)鍵字被刪關(guān)鍵字 = 4080 整理課件 50 3080 2090 85 40 35 8832 （3）被刪除的結(jié)點既有左子樹，也有右子樹既有左子樹，也有右子樹 40 40 以其前驅(qū)替代之，然以其前驅(qū)替代之，然 后再刪除該前驅(qū)結(jié)點后再刪除該前驅(qū)結(jié)點 被刪結(jié)點前驅(qū)結(jié)點 （中序遍歷） 被刪關(guān)鍵字被刪關(guān)鍵字 = 50 整理課件 50 30 80 20 90 85 40 35 88 32 （3）被刪除的結(jié)點既有左子樹，也有右子樹既有左子樹，也有右子樹 40 被刪關(guān)鍵字被刪關(guān)鍵字 = 50 直接觀察看有沒有其他方法？ 整理課件 50 30 80 20 90 85 40 35 88 32 （3）

19、被刪除的結(jié)點既有左子樹，也有右子樹既有左子樹，也有右子樹 40 被刪關(guān)鍵字被刪關(guān)鍵字 = 50 整理課件 二、平衡二叉樹二、平衡二叉樹 樹中每個結(jié)點的樹中每個結(jié)點的左、右子樹深度左、右子樹深度 之差的絕對值不大于之差的絕對值不大于1 。 例如例如: 5 48 2 5 48 2 1 是平衡樹是平衡樹不是平衡樹不是平衡樹 平衡 因子 1 RL hh 又稱又稱AVL樹，是具有如下性質(zhì)的二叉樹：樹，是具有如下性質(zhì)的二叉樹： 整理課件 如何構(gòu)建一棵平衡二叉樹？平衡二叉樹？ 平衡二叉樹的構(gòu)建過程類似于二平衡二叉樹的構(gòu)建過程類似于二 叉排序樹的建立過程，即在二叉排序叉排序樹的建立過程，即在二叉排序 樹的建立

20、過程每當插入一個結(jié)點后，樹的建立過程每當插入一個結(jié)點后， 立刻檢查該樹是否平衡，如果平衡：立刻檢查該樹是否平衡，如果平衡： 繼續(xù)；繼續(xù)； 平衡二叉樹的構(gòu)建過程類似于二平衡二叉樹的構(gòu)建過程類似于二 叉排序樹的建立過程，即在二叉排序叉排序樹的建立過程，即在二叉排序 樹的建立過程每當插入一個結(jié)點后，樹的建立過程每當插入一個結(jié)點后， 立刻檢查該樹是否平衡，如果平衡：立刻檢查該樹是否平衡，如果平衡： 繼續(xù)；繼續(xù)；否則：進行相應(yīng)的調(diào)整！否則：進行相應(yīng)的調(diào)整！ 整理課件 構(gòu)造平衡二叉樹的方法： 插入、判斷、平衡旋轉(zhuǎn)插入、判斷、平衡旋轉(zhuǎn) 若在若在A的的左子樹的左子樹上插入左子樹的左子樹上插入 結(jié)點，使結(jié)點，使

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

22、(以插入的結(jié)點以插入的結(jié)點C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 若在若在A的的左左子樹的子樹的右右子樹上插入子樹上插入 結(jié)點，使結(jié)點，使A的平衡因子從的平衡因子從1增加至增加至 2，需要，需要先進行先進行逆逆時針旋轉(zhuǎn)，再時針旋轉(zhuǎn)，再 順順時針旋轉(zhuǎn)。時針旋轉(zhuǎn)。 (以插入的結(jié)點以插入的結(jié)點C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 整理課件 構(gòu)造平衡二叉樹的方法： 插入、判斷、平衡旋轉(zhuǎn)插入、判斷、平衡旋轉(zhuǎn) 平衡旋轉(zhuǎn)的具體操作可以演繹為左右手原則！平衡旋轉(zhuǎn)的具體操作可以演繹為左右手原則！ A B C A B CC A BB C A A B CB C A LL型RR型RL型LR型 C B AA C B 整理課件 0 0 1313 0

23、0 3737 0 0 2424 例例1 1：請將下面序列構(gòu)成一棵請將下面序列構(gòu)成一棵平衡二叉排序樹平衡二叉排序樹： （ 13，24，37，90，53） 0 0 1313 0 0 3737 -1-1 1313 0 0 2424 -1-1 2424 1313 需要需要RR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn) (繞繞B逆轉(zhuǎn)逆轉(zhuǎn),B為根）為根） 0 0 9090 -1-1 2424 -1-1 3737 0 0 5353 1 1 9090 3737 需要需要RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn) (繞繞C先順后逆）先順后逆） 0 0 3737 0 0 9090 0 0 5353 0 0 3737 0 0 9090 0 0 5353 整理課件

24、 例2: 依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 9 5 4 2 4 25 8 6 6 58 4 2 向右旋轉(zhuǎn) 一次 先向右旋轉(zhuǎn) 再向左旋轉(zhuǎn) 整理課件 4 26 58 9 6 4 2 8 9 5 向左旋轉(zhuǎn)一次 繼續(xù)插入關(guān)鍵字 9 依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 9 整理課件 一、一、哈希表是什么？哈希表是什么？ 二、哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法 三、處理沖突的方法處理沖突的方法 四、哈希表的查找哈希表的查找 9.4 哈希表哈希表 整理課件 一、哈希表是什么？哈希表是什么？ 前面介紹的所有查找都是基于待查前面介紹的所有查找都是基于待查 關(guān)鍵字與表中元素進行比較而實

25、現(xiàn)的查關(guān)鍵字與表中元素進行比較而實現(xiàn)的查 找方法，查找的效率依賴于查找過程中找方法，查找的效率依賴于查找過程中 所進行的比較次數(shù)。理想的情況是希望所進行的比較次數(shù)。理想的情況是希望 不經(jīng)過任何比較，一次便能得到所查記不經(jīng)過任何比較，一次便能得到所查記 錄。錄。 哈希表哈希表 它既是一種查找方法，它既是一種查找方法， 又是一種存貯方法又是一種存貯方法 整理課件 哈希表：哈希表：即散列存儲結(jié)構(gòu)。即散列存儲結(jié)構(gòu)。 散列法存儲的基本思想：散列法存儲的基本思想：建立關(guān)鍵碼字與其存儲位置的建立關(guān)鍵碼字與其存儲位置的對應(yīng)對應(yīng) 關(guān)系，關(guān)系，或者說，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址?；蛘哒f，由關(guān)鍵碼的值決定數(shù)據(jù)的

26、存儲地址。 優(yōu)點：優(yōu)點：查找速度極快（查找速度極快（O(1)O(1)）, ,查找效率與元素個數(shù)查找效率與元素個數(shù)n n無關(guān)！無關(guān)！ 例如：例如：有數(shù)據(jù)元素序列有數(shù)據(jù)元素序列(14(14，2323，3939，9 9，2525，11)11)，若規(guī)定每，若規(guī)定每 個元素個元素k k的存儲地址的存儲地址H H（k k）k k，請畫出存儲結(jié)構(gòu)圖。，請畫出存儲結(jié)構(gòu)圖。 （注：（注：H H（k k）k k稱為散列函數(shù)）稱為散列函數(shù)） 解：解：根據(jù)散列函數(shù)根據(jù)散列函數(shù)H H（k k）k k ，可知元素，可知元素1414應(yīng)當存入地址為應(yīng)當存入地址為 1414的單元，元素的單元，元素2323應(yīng)當存入地址為應(yīng)當存入

27、地址為2323的單元，的單元， 對應(yīng)散列存儲表（哈希表）如下：對應(yīng)散列存儲表（哈希表）如下： 地址地址 9 11 14 23 24 25 39 內(nèi)容內(nèi)容整理課件 選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置， 并按此存放；并按此存放；查找時，由同一個函數(shù)查找時，由同一個函數(shù)對給定值對給定值k k計算地址，計算地址， 將將k k與地址單元中元素關(guān)鍵碼進行比較，確定查找是否成與地址單元中元素關(guān)鍵碼進行比較，確定查找是否成 功。功。 通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)

28、 過哈希函數(shù)變換后，過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同可能將不同的關(guān)鍵碼映射到同 一個哈希地址上一個哈希地址上，這種現(xiàn)象稱為，這種現(xiàn)象稱為沖突沖突。 2.若干術(shù)語若干術(shù)語 哈希方法哈希方法 ( (雜湊法雜湊法) ) 哈希函數(shù)哈希函數(shù) ( (雜湊函數(shù)雜湊函數(shù)) ) 哈希表哈希表 ( (雜湊表雜湊表) ) 沖沖 突突 哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)哈希函數(shù)( (雜雜 湊函數(shù)湊函數(shù)) ) 按上述思想構(gòu)造的表稱為按上述思想構(gòu)造的表稱為哈希表哈希表( (雜湊表雜湊表) ) 整理課件 有有6個元素的關(guān)鍵碼分別為：（個元素的關(guān)鍵碼分別為：（14，23，39，9，2

29、5，11）。）。 選取關(guān)鍵碼與元素位置間的函數(shù)為選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k mod 7 通過哈希函數(shù)對通過哈希函數(shù)對6 6個元素建立哈希表：個元素建立哈希表： 25 3923 9 14 6個元素用個元素用7個個 地址應(yīng)該足夠地址應(yīng)該足夠! H(14)=14%7=011 H(25)=25%7=4 H(11)=11%7=4 0 1 2 3 4 5 6 整理課件 二、構(gòu)造哈希函數(shù)的方法構(gòu)造哈希函數(shù)的方法 對數(shù)字數(shù)字的關(guān)鍵字可有下列構(gòu)造方法： 若是非數(shù)字關(guān)鍵字非數(shù)字關(guān)鍵字，則需先需先對其進行進行 數(shù)字化處理數(shù)字化處理。 1. 直接定址法直接定址法 3. 平方取中法平方取中法 5. 除留

30、余數(shù)法除留余數(shù)法 4. 折疊法折疊法 6. 隨機數(shù)法隨機數(shù)法 2. 數(shù)字分析法數(shù)字分析法 整理課件 哈希函數(shù)為關(guān)鍵字的線性函數(shù) H(key) = key 或者 H(key) = a key + b 1. 直接定址法直接定址法 此法僅適合于：此法僅適合于： 地址集合的大小地址集合的大小 = = 關(guān)鍵字集合的大小關(guān)鍵字集合的大小 整理課件 此方法僅適合于：此方法僅適合于： 能預(yù)先估計出預(yù)先估計出全體關(guān)鍵字的每一位上每一位上 各種數(shù)字出現(xiàn)的頻度數(shù)字出現(xiàn)的頻度。 2. 數(shù)字分析法數(shù)字分析法 假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是 由 s 位數(shù)字組成 (u1, u2, , us)，分析關(guān) 鍵字集中的全體， 并

31、從中提取分布均勻 的若干位或它們的組合作為地址。 整理課件 以關(guān)鍵字的平方值的中間幾位作為存 儲地址。求“關(guān)鍵字的平方值” 的目的 是“擴大差別” ，同時平方值的中間各 位又能受到整個關(guān)鍵字中各位的影響。 3. 平方取中法平方取中法 此方法適合于此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重復(fù) 出現(xiàn)頻度很高的現(xiàn)象。 整理課件 將關(guān)鍵字分割成若干部分，然后取它 們的疊加和為哈希地址。有兩種疊加處 理的方法：移位疊加移位疊加和間界疊加間界疊加。 4. 折疊法折疊法 此方法適合于此方法適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多。 整理課件 5. 除留余數(shù)法除留余數(shù)法 設(shè)定哈希函數(shù)為設(shè)定哈希函數(shù)為: H(key

32、) = key MOD p 其中其中， pm ( (表長表長) ) 并且并且 p 應(yīng)為不大于應(yīng)為不大于 m 的素數(shù)的素數(shù) 或是或是 不含不含 20 以下的質(zhì)因子以下的質(zhì)因子 整理課件 6.隨機數(shù)法隨機數(shù)法 設(shè)定哈希函數(shù)為設(shè)定哈希函數(shù)為: H(key) = Random(key) 其中，其中，Random 為偽隨機函數(shù)為偽隨機函數(shù) 通常，此方法用于對長度不等的關(guān)鍵 字構(gòu)造哈希函數(shù)。 注意：實際造表時總的原則是使產(chǎn)生沖突總的原則是使產(chǎn)生沖突 的可能性降到盡可能地小的可能性降到盡可能地小。 整理課件 三、處理沖突的方法處理沖突的方法 “處理沖突處理沖突” 的實際含義是： 為產(chǎn)生沖突的地址尋找下一個尋

33、找下一個哈希地址。 1. 開放定址法開放定址法 2. 鏈地址法鏈地址法 整理課件 為產(chǎn)生沖突的地址為產(chǎn)生沖突的地址 H(key) H(key) 求得一個地址序列：求得一個地址序列： H H0 0, H, H1 1, H, H2 2, , H, , Hs s 1 sm-11 sm-1 其中：其中：H H0 0 = H(key) H = H(key) Hi i = ( H(key) + = ( H(key) + d di i ) MOD m ) MOD m i=1, 2, , s i=1, 2, , s 1. 開放定址法開放定址法 其中：對增量其中：對增量 d di i 有三種取法 有三種取法 1

34、) 1) 線性探測再散列線性探測再散列 d di i = c = c i i 最簡單的情況最簡單的情況 c=1c=1 2) 2) 二次探測再散列二次探測再散列 d di i = 1 = 12 2, -1, -12 2, 2, 22 2, -2, -22 2, , , 3) 3) 隨機探測再散列隨機探測再散列 d di i 是一組偽隨機數(shù)列是一組偽隨機數(shù)列 或者或者 d di i=i=iH H2 2(key) (key) ( (又稱雙散列函數(shù)探測又稱雙散列函數(shù)探測) ) 整理課件 例如例如: 關(guān)鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 設(shè)定設(shè)定哈希函數(shù) H(

35、key) = key MOD 11 ( 表長=11 ) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 190123 145568 190123 1468 2+4 若采用線性探測再散列線性探測再散列處理沖突 若采用二次探測再散列二次探測再散列處理沖突 11 8236 55 11 (0-1)mod 11 8236 1 1 2 1 3 6 2 5 1 Flash演示演示 整理課件 將所有哈希地址相同的記錄 都鏈接在同一鏈表中。 2. 鏈地址法鏈地址法 0 1 2 3 4 5 6 14 0136 1982 23 11 68 55 ASL=(61+22+3)

36、/9=13/9 例如:同前例的關(guān)鍵 字，哈希函數(shù)為 H(key)=key MOD 7 Flash演示演示 整理課件 查找過程和造表過程一致。假設(shè)采用 開放定址處理沖突，則查找過程查找過程為： 四、哈希表的查找哈希表的查找 對于給定值 K， 計算哈希地址 i = H(K) 若若 ri = NULL 則查找不成功 若若 ri.key = K 則查找成功 否則否則 “求下一地址 Hi” ，直至 rHi = NULL (查找不成功) 或 rHi.key = K (查找成功) 為止。 整理課件 1. 順序表順序表和有序表有序表的查找方法。 3. 熟練掌握哈希表的構(gòu)造方法。 2.熟練掌握二叉排序樹、二叉排序樹、平衡二叉樹二叉樹 的構(gòu)造和查找方法