大學數(shù)據(jù)結構課件--第9章查找

1、1 基本概念基本概念 靜態(tài)查找表靜態(tài)查找表 動態(tài)查找表動態(tài)查找表 哈希表哈希表第第9章章 查找查找2基本概念基本概念若表中存在特定元素，稱查找成功，應輸出該記錄或位置；若表中存在特定元素，稱查找成功，應輸出該記錄或位置；否則，稱查找不成功（也應輸出失敗標志或失敗位置）否則，稱查找不成功（也應輸出失敗標志或失敗位置）查找表 查 找查找成功查找不成功靜態(tài)查找動態(tài)查找關鍵字主關鍵字次關鍵字由同一類型的數(shù)據(jù)元素（或記錄）構成的集合。由同一類型的數(shù)據(jù)元素（或記錄）構成的集合。查詢查詢(Searching)特定元素特定元素是否在表中。是否在表中。只查找，不改變集合內的數(shù)據(jù)元素。只查找，不改變集合內的數(shù)據(jù)元

2、素。既查找，又改變（增減）集合內的數(shù)據(jù)元素。既查找，又改變（增減）集合內的數(shù)據(jù)元素。記錄中某個數(shù)據(jù)項的值，可用來識別一個記錄記錄中某個數(shù)據(jù)項的值，可用來識別一個記錄可以可以唯一唯一標識一個記錄的關鍵字標識一個記錄的關鍵字識別若干記錄的關鍵字識別若干記錄的關鍵字3明確：明確：查找的過程就是將給定的查找的過程就是將給定的K K值與文件中各記錄的關鍵字項進行比值與文件中各記錄的關鍵字項進行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為平均查找平均查找長度長度（ASLASL：average search lengthaverage sea

3、rch length）。）。其中：其中： n n是記錄個數(shù)；是記錄個數(shù)； P Pi i是查找第是查找第i i個記錄的查找概率（通常取等概率個記錄的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ; C Ci i是找到第是找到第i i個記錄時所經歷的比較次數(shù)。個記錄時所經歷的比較次數(shù)。物理意義：物理意義：假設每一元素被查找的概率相同，則查找每一元素所需假設每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為的比較次數(shù)之總和再取平均，即為ASLASL。顯然，顯然，ASLASL值越小，時間效率越高。值越小，時間效率越高。 如何評估查找方法的優(yōu)劣？1iini

4、ASLPC基本概念基本概念4針對靜態(tài)查找表的查找算法主要有：針對靜態(tài)查找表的查找算法主要有： 一、順序查找（線性查找）一、順序查找（線性查找）二、折半查找（二分或對分查找）二、折半查找（二分或對分查找）三、靜態(tài)樹表的查找三、靜態(tài)樹表的查找四、分塊查找（索引順序查找）四、分塊查找（索引順序查找）9.1 靜態(tài)查找表靜態(tài)查找表5（1）順序表的機內存儲結構：順序表的機內存儲結構：typedef struct ElemType *elem; /表基址，表基址，0 0號單元留空。表容量為全部元素號單元留空。表容量為全部元素 int length; /表長，即表中數(shù)據(jù)元素個數(shù)表長，即表中數(shù)據(jù)元素個數(shù)SSTa

5、ble;Linear search，又稱線性查找，又稱線性查找，即用逐一比較的辦法順即用逐一比較的辦法順序查找關鍵字，這顯然是最直接的辦法。序查找關鍵字，這顯然是最直接的辦法。 9.1.1 順序查找順序查找6（2）算法的實現(xiàn)：算法的實現(xiàn)：技巧：技巧：把待查關鍵字把待查關鍵字keykey存入表頭或表尾（俗稱存入表頭或表尾（俗稱“哨兵哨兵”），）， 若將待查找的特定值若將待查找的特定值keykey存入存入順序表的順序表的首部首部（如（如0 0號單元），則號單元），則順序查找的實現(xiàn)方案為：順序查找的實現(xiàn)方案為：從后向前從后向前逐個比較！逐個比較！int Search_Seq( SSTable ST

6、, KeyType key ) ST.elem0.key =key; /設立哨兵，可免去查找過程中每一步都要檢設立哨兵，可免去查找過程中每一步都要檢測是否查找完畢。當測是否查找完畢。當n1000n1000時，查找時間將減少一半。時，查找時間將減少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /從后往前找從后往前找 return i; /若到達若到達0 0號單元才結束循環(huán)，說明不成功，返回號單元才結束循環(huán)，說明不成功，返回0 0值值(i=0)(i=0)。成功。成功時則返回找到的元素位置時則返回找到的元素位置i i。 / Search_Se

7、q/不要用不要用for(i=n; i0; - -i) for(i=n; i0; - -i) 或或 for(i=1; i=n; i+)for(i=1; i=n; i+)9.1.1 順序查找順序查找7說明說明 查找效率怎樣計算？查找效率怎樣計算？用平均查找長度用平均查找長度ASL衡量。衡量。說明說明 如何計算如何計算ASL？查找第查找第1個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為1；查找第查找第2個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為2；查找第查找第n個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為n；總計全部比較次數(shù)為：總計全部比較次數(shù)為：12n = (1+n)n/2這是查找成功的情況這是查

8、找成功的情況若求某一個元素的平均查找次數(shù)，還應當除以若求某一個元素的平均查找次數(shù)，還應當除以n，即：即： ASL（1n）/2 ，時間效率為，時間效率為 O(n)優(yōu)點：優(yōu)點：算法簡單，且對順序結構或鏈表結構均適用。算法簡單，且對順序結構或鏈表結構均適用。缺點：缺點： ASL 太長，時間效率太低。太長，時間效率太低。說明說明 順序查找的特點：順序查找的特點：8先給數(shù)據(jù)排序先給數(shù)據(jù)排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再將，然后再將keykey與與正中元素相比，若比正中元素相比，若比keykey小，則縮小至右半部內查找；再取其中值小，則縮小至右半部內查找；再取其中值比

9、較，每次縮小比較，每次縮小1/21/2的范圍，直到查找成功或失敗為止。的范圍，直到查找成功或失敗為止。折半查找舉例：折半查找舉例：LowLow指向待查元素指向待查元素所在區(qū)間的下界所在區(qū)間的下界highhigh指向待查元素所指向待查元素所在區(qū)間的上界在區(qū)間的上界midmid指向待查元素所在指向待查元素所在區(qū)間的中間位置區(qū)間的中間位置 已知如下已知如下11個元素的個元素的有序表有序表：（05 13 19 21 37 56 64 75 80 88 92）, 請查找關鍵字為請查找關鍵字為21和和85的數(shù)據(jù)元素。的數(shù)據(jù)元素。9.1.2 折半查找折半查找（又稱二分查找或對分查找又稱二分查找或對分查找）9

10、 運算步驟運算步驟： （1） low =1,high =11 ,mid =6 ，待查范圍是，待查范圍是 1,11； （2）若）若 ST.elemmid.key key，說明，說明key low ,mid-1， 則令：則令：high =mid1;重算重算 mid ； （4）若）若 ST.elem mid .key = key，說明查找成功，元素序號，說明查找成功，元素序號=mid; 結束條件：結束條件： （1）查找成功）查找成功 ： ST.elemmid.key = key （2）查找不成功）查找不成功 ： highlow （意即區(qū)間長度小于（意即區(qū)間長度小于0）解：解： 先設定先設定3個輔助標

11、志個輔助標志: low,high,midlow,high,mid，顯然有：顯然有：mid= (low+high)/2 9.1.2 折半查找折半查找（又稱二分查找或對分查找又稱二分查找或對分查找）10查找查找21:（05 13 19 21 37 56 64 75 80 88 92）lowhighmidlowhighmidlowhighmid 查找結果：查找成功，查找結果：查找成功，21所在位置是所在位置是49.1.2 折半查找折半查找（又稱二分查找或對分查找又稱二分查找或對分查找）11查找查找85:（05 13 19 21 37 56 64 75 80 88 92）lowhighmidlowhi

12、ghlow highmidlowhighmid查找結果：查找失敗查找結果：查找失敗9.1.2 折半查找折半查找（又稱二分查找或對分查找）（又稱二分查找或對分查找）12折半查找算法折半查找算法int Search_Bin(SSTable ST,KeyType key) low=1; high=ST.length; while(lowlchild=NULLf-lchild=NULL或或 f-rchild=NULLf-rchild=NULL20SQPLP中序遍歷：Q S PL PSQPL中序遍歷：Q S PL(2)SPPLQ中序遍歷：PL P S QSPLQ中序遍歷：PL S Q(1)刪除18634

13、218158634215821中序遍歷：P PR S QSPRQ中序遍歷：PR S Q(3)SPPRQ中序遍歷：Q S P PRSQPR中序遍歷：Q S PR(4)SQPRP刪除12634218121513634218151322F FC CCLS SSLQLPPRQPRF FC CCLS SSLQLPPRQ法法2: 2: S的左子樹成為的左子樹成為S的雙親的雙親Q的右子樹，的右子樹， 用用S取代取代p；若若C無右子樹，用無右子樹，用C取代取代p F FC CCLS SSLQLPPRQ法法1: 1: P的左子樹成為的左子樹成為f的左子樹，的左子樹， P的右子樹成為的右子樹成為S的右子樹的右子樹

14、例：請從下面的二叉排序樹中刪除結點例：請從下面的二叉排序樹中刪除結點P P。S SSL231036241812156342181215刪除104362181215問題：問題：如何提高二叉排序樹的查找效率？如何提高二叉排序樹的查找效率？盡量讓二叉樹的形狀均衡盡量讓二叉樹的形狀均衡口訣：用左子樹最大的結點代替P； 或 用右子樹最小的結點代替P24平衡二叉樹又稱平衡二叉樹又稱AVL樹，它是具有如下性質的二叉樹：樹，它是具有如下性質的二叉樹：為了方便起見，給每個結點附加一個為了方便起見，給每個結點附加一個數(shù)字數(shù)字，給出，給出該結點左該結點左子樹與右子樹的高度差子樹與右子樹的高度差。這個數(shù)字稱為結點的。

15、這個數(shù)字稱為結點的平衡因子平衡因子balance。這樣，可以得到這樣，可以得到AVL樹的其它性質：樹的其它性質：左、右子樹是平衡二叉樹；左、右子樹是平衡二叉樹；所有結點的左、右子樹深度之差的絕對值所有結點的左、右子樹深度之差的絕對值 1 1v任一結點的平衡因子只能取：任一結點的平衡因子只能取：-1-1、0 0 或或 1 1；如果樹中任；如果樹中任意一個結點的平衡因子的絕對值大于意一個結點的平衡因子的絕對值大于1 1，則這棵二叉樹，則這棵二叉樹就失去平衡，不再是就失去平衡，不再是AVLAVL樹；樹；三、平衡二叉樹三、平衡二叉樹25(a) (a) 平衡樹平衡樹 (b) (b) 不是平衡樹不是平衡樹

16、例：例：判斷下列二叉樹是否判斷下列二叉樹是否AVL樹？樹？0001 11 1-1-10001-1三、平衡二叉樹三、平衡二叉樹26如果在一棵如果在一棵AVL樹中插入一個新結點，就有可能造成失衡，樹中插入一個新結點，就有可能造成失衡，此時必須此時必須重新調整樹的結構重新調整樹的結構，使之恢復平衡。我們稱調整，使之恢復平衡。我們稱調整平衡過程為平衡過程為平衡旋轉平衡旋轉。平衡旋轉可以歸納為四類：平衡旋轉可以歸納為四類：v RR平衡旋轉平衡旋轉v LL平衡旋轉平衡旋轉v LR平衡旋轉平衡旋轉v RL平衡旋轉平衡旋轉三、平衡二叉樹三、平衡二叉樹27若在A的左子樹的左子樹上插入結點，使A的平衡因子從1增加

17、至2，需要進行一次順時針旋轉。(以B為旋轉軸）若在A的右子樹的右子樹上插入結點，使A的平衡因子從-1增加至-2，需進行一次逆時針旋轉。(以B為旋轉軸）（2）LL平衡旋轉（1）RR平衡旋轉三、平衡二叉樹三、平衡二叉樹28若在A的右子樹的左子樹上插入結點，使A的平衡因子從-1增加至-2，需要先進行順時針旋轉，再逆時針旋轉。(以插入的結點C為旋轉軸）（4）RL平衡旋轉若在A的左子樹的右子樹上插入結點，使A的平衡因子從1增加至2，需要先進行逆時針旋轉，再順時針旋轉。(以插入的結點C為旋轉軸）（3）LR平衡旋轉這種調整規(guī)則可以保證二叉排序樹的次序不變三、平衡二叉樹三、平衡二叉樹290 013130 03

18、7370 02424例：例：請將下面序列構成一棵平衡二叉排序樹：請將下面序列構成一棵平衡二叉排序樹： （ 1313，2424，3737，9090，5353）0 013130 03737-1-113130 02424-1-124241313需要需要RR平衡旋轉平衡旋轉(繞繞B逆轉逆轉,B為根）為根）0 09090-1-12424-1-137370 053531 190903737需要需要RL平衡旋轉平衡旋轉(繞繞C先順后逆）先順后逆）0 037370 090900 053530 037370 090900 05353三、平衡二叉樹三、平衡二叉樹30B-樹是一種 平衡平衡 的 多路多路 查找查找

19、樹： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96一棵4階B-樹1781501152718432026432382566228996FFFFFFFFFFFFFFF四、四、B-B-樹和樹和B+B+樹樹31平衡樹的特性平衡樹的特性樹中每個結點最多含有樹中每個結點最多含有 m 棵子樹棵子樹; ;根結點或為葉子結點，或至少含有兩棵子樹根結點或為葉子結點，或至少含有兩棵子樹;其余所有非葉子結點均至少含有其余所有非葉子結點均至少含有 m/2 棵棵子樹；子樹；樹中所有葉子結點均不帶信息，且在樹中的同一層次上樹中所有葉子結點均不帶信息，且在樹中的同一層次上;每個非終

20、端結點可能含有：每個非終端結點可能含有： n 個個關鍵字關鍵字 Ki（1 in） nm n 個個指向記錄的指針指向記錄的指針 Di（1in） n+1 個個指向子樹的指針指向子樹的指針 Ai（0in）;多叉樹的特性多叉樹的特性非葉結點中的非葉結點中的多個關鍵字多個關鍵字均均自小至大自小至大有序排列，即：有序排列，即：K1 K2 Kn;且且 Ai-1 所指子樹上所有關鍵字均所指子樹上所有關鍵字均小于小于Ki;Ai 所指子樹上所有關鍵字均所指子樹上所有關鍵字均大于大于Ki; ;查找樹的特性查找樹的特性 一棵m階的B-樹,或為空樹,或為滿足下列特性的m叉樹:（n,A0,K1,A1,K2Kn,An）32

21、從根結點出發(fā)，沿指針搜索結點搜索結點和在結點內進行在結點內進行順序（或折半）查找查找 兩個過程交叉進行。若查找不成功查找不成功，則需要插入關鍵值需要插入關鍵值。在B-樹中插入一個關鍵值k，不是在樹中添加一個葉子結點，而是首先在最低層的某個非終端結點中添加一個關鍵值。并且要使插入的結點中的關鍵值個數(shù)m1，否則將涉及到結點的分裂問題。3 3、B-B-樹的插入樹的插入2 2、B-B-樹的查找樹的查找331）插入后，該結點的關鍵字個數(shù)插入后，該結點的關鍵字個數(shù)nm，不修改指針不修改指針; ; 2）插入后，該結點的關鍵字個數(shù)插入后，該結點的關鍵字個數(shù) n=m，則，則需進行需進行“結點分結點分裂裂”，令，

22、令 s = m/2 ， 在原結點中保留在原結點中保留A0，K1， Ks-1，As-1）；）； 建新結點建新結點（As，Ks+1， ，Kn，An）；）； 將（將（Ks，p）插入雙親結點）插入雙親結點；-分裂后提升3）若雙親為空，則若雙親為空，則建新的根結點建新的根結點。3 3、B-B-樹的插入樹的插入34例如例如:下列為下列為 3 階階B-樹，分別插入樹，分別插入60、90、30。5020 408060 80 60 80 90906050 8020906030 50 804080 30 503 3、B-B-樹的插入樹的插入35 和插入的考慮相反，首先必須找到待刪關鍵字所在結點，并且要求刪除之后，

23、結點中關鍵字的個數(shù)不能小于m/2-1，否則，要從其左(或右)兄弟結點借調關鍵字，若其左和右兄弟結點均無關鍵字可借(結點中只有最少量的關鍵字)，則必須進行結點的合并 。4 4、B-B-樹的刪除樹的刪除36例：請在下面的3階B-樹上依次刪除關鍵字12、50（或100）、37 。53 9053 90454524243 123 123737505010010061 7061 7053 9053 90454524243 33737505010010061 7061 7061 9061 90454524243 3373753531001007070刪除12刪除5053 7053 70454524243 3

24、3737505090906161刪除100從鄰近兄弟結點中取一個放到雙親中，從雙親中取一個下移到被刪除結點中。3770 9070 90454524243 33737616110010061 9061 90454524243 3373753531001007070刪除539090454524243 3373710010061 7061 70從雙親結點中取一個與其鄰近兄弟合并389090454524243 3373710010061 7061 70909045453 243 2410010061 7061 7045 9045 903 243 2410010061 7061 70刪除3739前面介紹

25、的所有查找都是基于待查關鍵字與表中元素進行比較而實現(xiàn)的查找方法，查找的效率依賴于查找過程中所進行的比較次數(shù)。理想的情況是希望不經過任何比較，一次便能得到所查記錄。哈希表哈希表它既是一種查找方法，它既是一種查找方法，又是一種存儲方法又是一種存儲方法40一、哈希表的概念一、哈希表的概念二、哈希函數(shù)的構造方法二、哈希函數(shù)的構造方法三、沖突處理方法三、沖突處理方法四、哈希表的查找及分析四、哈希表的查找及分析9.4 哈希查找表哈希查找表41哈希表：哈希表：即散列即散列(Hash)存儲結構。存儲結構。 散列法存儲的基本思想：散列法存儲的基本思想：建立關鍵字與其存儲位置的建立關鍵字與其存儲位置的對應關系，對

26、應關系， 或者說，由關鍵字的值決定數(shù)據(jù)的存儲地址?；蛘哒f，由關鍵字的值決定數(shù)據(jù)的存儲地址。 例例1 1：若將學生信息按如下方式存入計算機，如：若將學生信息按如下方式存入計算機，如：將將20010118102200101181020101的所有信息存入的所有信息存入V01V01單元；單元；將將20010118102200101181020202的所有信息存入的所有信息存入V02V02單元；單元；將將20010118102200101181023131的所有信息存入的所有信息存入V31V31單元。單元。欲查找學號為欲查找學號為20010118102200101181021616的信息，便可直接訪問

27、的信息，便可直接訪問V16V16單元單元優(yōu)點：優(yōu)點：查找速度極快（查找速度極快（ (1)(1)）, ,查找效率與元素個數(shù)查找效率與元素個數(shù)n n無關！無關！9.4 哈希查找表哈希查找表42解：解：根據(jù)散列函數(shù)根據(jù)散列函數(shù)H H（k k）k k ，可知元素，可知元素1414應當存入地址為應當存入地址為 1414的單元，元素的單元，元素2323應當存入地址為應當存入地址為2323的單元，的單元， 對應散列存儲表（哈希表）如下：對應散列存儲表（哈希表）如下：地址地址9111423242539內容內：有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個元素k的存儲地

28、址H（k）k，請畫出存儲結構圖。 注：H（k）k稱為散列函數(shù)）9.4 哈希查找表哈希查找表43討論：如何進行散列查找？ 根據(jù)存儲時用到的散列函數(shù)根據(jù)存儲時用到的散列函數(shù)H(k)H(k)表達式，即可查到結果！表達式，即可查到結果！ 例如，查找例如，查找key=9,key=9,則訪問則訪問H(9)=9H(9)=9號地址，若內容為號地址，若內容為9 9則成則成 功；若查不到，應當設法返回一個特殊值，例如空指針或功；若查不到，應當設法返回一個特殊值，例如空指針或 空記錄。空記錄。 缺點：空間效率低！9.4 哈希查找表哈希查找表44選取某個函數(shù)，該函數(shù)按關鍵字計算元素的存儲選取某個函數(shù)，該函數(shù)按關鍵字計

29、算元素的存儲位置，并按此存放；位置，并按此存放；查找時，由同一個函數(shù)查找時，由同一個函數(shù)對給對給定值定值k k計算地址，將計算地址，將k k與地址單元中元素關鍵字進與地址單元中元素關鍵字進行比較，確定查找是否成功。行比較，確定查找是否成功。通常關鍵字的集合比哈希地址集合大得多，因而通常關鍵字的集合比哈希地址集合大得多，因而經過哈希函數(shù)變換后，經過哈希函數(shù)變換后，可能將不同的關鍵字映射可能將不同的關鍵字映射到同一個哈希地址上到同一個哈希地址上，這種現(xiàn)象稱為，這種現(xiàn)象稱為沖突沖突。哈希方法哈希方法哈希函數(shù)哈希函數(shù) 哈希表哈希表 沖沖 突突哈希方法中使用的轉換函數(shù)稱為哈希方法中使用的轉換函數(shù)稱為哈希

30、函數(shù)哈希函數(shù)按上述思想構造的表稱為按上述思想構造的表稱為哈希表哈希表哈希表的若干術語哈希表的若干術語45有有6個元素的關鍵碼分別為：（個元素的關鍵碼分別為：（14，23，39，9，25，11）。）。選取關鍵碼與元素位置間的函數(shù)為選取關鍵碼與元素位置間的函數(shù)為H(k)=k mod 7，地址編地址編號從號從0-6。通過哈希函數(shù)對6個元素建立哈希表：253923914H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4 0 1 2 3 4 5 6沖突現(xiàn)象舉例沖突現(xiàn)象舉例46所以，所以，哈希方法必須解決以下兩個問題哈希方法必須解決以下兩個問題：1）構造好的哈希函數(shù) （a a）所

31、選函數(shù)盡可能簡單，以便提高轉換速度；）所選函數(shù)盡可能簡單，以便提高轉換速度； （b b）所選函數(shù)對關鍵碼計算出的地址，應在哈希地址集）所選函數(shù)對關鍵碼計算出的地址，應在哈希地址集 中致均勻分布，以減少空間浪費。中致均勻分布，以減少空間浪費。2）制定一個好的解決沖突的方案 查找時，如果從哈希函數(shù)計算出的地址中查不到關鍵查找時，如果從哈希函數(shù)計算出的地址中查不到關鍵 碼，則應當依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相碼，則應當依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相 關單元。關單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。47常用的哈

32、希函數(shù)構造方法有：常用的哈希函數(shù)構造方法有：1.1. 直接定址法直接定址法 2.2. 除留余數(shù)法除留余數(shù)法 3.3. 乘余取整法乘余取整法4.4. 數(shù)字分析法數(shù)字分析法 5.5. 平方取中法平方取中法 6.6. 折疊法折疊法 7.7. 隨機數(shù)法隨機數(shù)法 要求一：要求一：n n個數(shù)據(jù)原僅占用個數(shù)據(jù)原僅占用n n個地址，個地址，雖然散列查找是以空間換時間，但仍雖然散列查找是以空間換時間，但仍希望散列的地址空間盡量小。希望散列的地址空間盡量小。要求二：要求二：無論用什么方法存儲，目無論用什么方法存儲，目的都是盡量均勻地存放元素，以避免的都是盡量均勻地存放元素，以避免沖突。沖突。二、哈希函數(shù)的構造方法

33、哈希函數(shù)的構造方法48Hash(key) = akey + b ( (a、b為常數(shù)為常數(shù)) )優(yōu)點：優(yōu)點：以關鍵碼以關鍵碼keykey的某個線性函數(shù)值為哈希地址，的某個線性函數(shù)值為哈希地址，不會產生沖突不會產生沖突. .缺點：缺點：要占用連續(xù)地址空間，空間效率低。要占用連續(xù)地址空間，空間效率低。 例：例：關鍵碼集合為關鍵碼集合為100，300，500，700，800，900， 選取哈希函數(shù)為選取哈希函數(shù)為Hash(key)=key/100， 則存儲結構（哈希表）如下：則存儲結構（哈希表）如下：0 1 2 3 4 5 6 7 8 99008007005003001001 1、直接定址法、直接定址

34、法49Hash(key)=key mod p (p (p是一個整數(shù)是一個整數(shù)) )特點：特點：以關鍵碼除以以關鍵碼除以p的余數(shù)作為哈希地址。的余數(shù)作為哈希地址。關鍵：關鍵：如何選取合適的如何選取合適的p？技巧：技巧：若設計的哈希表長為若設計的哈希表長為m，則一般取，則一般取pm且為且為質數(shù)質數(shù) 2、除留余數(shù)法50Hash(key)= B*( A*key mod 1 ) ( (A、B均為常數(shù)，且均為常數(shù)，且0A 724+518+69 = 724+518+69 =13111311法法1 1：移位法移位法 將各部分的最后一位對齊相加。將各部分的最后一位對齊相加。法法2 2：間界疊加法間界疊加法從一端

35、向另一端沿分割界來回折疊后，從一端向另一端沿分割界來回折疊后， 最后一位對齊相加。最后一位對齊相加。 6、折疊法54Hash(key) = random ( key ) (random (random為偽隨機函數(shù)為偽隨機函數(shù)) )適用于：適用于：關鍵字長度不等的情況。造表和查找都很方便。關鍵字長度不等的情況。造表和查找都很方便。 執(zhí)行速度（即計算哈希函數(shù)所需時間）；執(zhí)行速度（即計算哈希函數(shù)所需時間）； 關鍵字的長度；關鍵字的長度； 哈希表的大??；哈希表的大??； 關鍵字的分布情況；關鍵字的分布情況； 查找頻率。查找頻率。小結：構造哈希函數(shù)的原則：7、隨機數(shù)法55三、沖突處理方法沖突處理方法56設

36、計思路：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。 具體實現(xiàn)：Hi=(Hash(key)+di) mod m ( 1i m )其中： Hash(key)為哈希函數(shù) m為哈希表長度 di 為增量序列 1，2，m-1，且di=i 1.線性探測法1 1、開放定址法（開地址法）、開放定址法（開地址法）57例：關鍵碼集為關鍵碼集為 47，7，29，11，16，92，22，8，3，哈希表表，哈希表表長為長為m=m=11；哈希函數(shù)為；哈希函數(shù)為Hash(key)=key mod 11；擬用；擬用處處理沖突。建哈希表如下：理沖突。建哈希表如下：解釋：解釋：

37、47、7均是由哈希函數(shù)得到的沒有沖突的哈希地址；均是由哈希函數(shù)得到的沒有沖突的哈希地址；0 1 2 3 4 5 6 7 8 9 10 Hash(29)=7，哈希地址有沖突，需尋找下一個空的哈希地址：，哈希地址有沖突，需尋找下一個空的哈希地址：由由H1=(Hash(29)+1) mod 11=8，哈希地址哈希地址8為空，因此將為空，因此將29存入。存入。另外，另外，22、8、3同樣在哈希地址上有沖突，也是由同樣在哈希地址上有沖突，也是由H1找到空找到空 的哈希地址的。的哈希地址的。 平均查找長度ASL=(1+2 +1 +1 +1 +4 +1 +2 +2)/9=1.6747729111692228

38、3 11、16、92均是由哈希函數(shù)得到的沒有沖突的哈希地址；均是由哈希函數(shù)得到的沒有沖突的哈希地址；58基本思想：基本思想：將具有相同哈希地址的記錄鏈成一個單鏈表，將具有相同哈希地址的記錄鏈成一個單鏈表，m個個 哈希地址就設哈希地址就設m個單鏈表個單鏈表，然后用一個數(shù)組將，然后用一個數(shù)組將m個個 單鏈表的表頭指針存儲起來，形成一個動態(tài)的結構。單鏈表的表頭指針存儲起來，形成一個動態(tài)的結構。 設設 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 的哈希函數(shù)為：的哈希函數(shù)為：Hash(key)=key mod 11，用用處理沖突，則建表如處理沖突，則建表如右圖

39、所示。右圖所示。 例：例：注：注：有沖突的元素可以插有沖突的元素可以插在表尾在表尾, ,也可以插在表頭也可以插在表頭平均查找長度ASL=(1*8 +2 *4)/12=1.334730 1 2 3 4 5 6 7 8 9107291116922285037892 2、鏈地址法、鏈地址法( (拉鏈法）拉鏈法）591 1、采用順序查找方法查找長度為、采用順序查找方法查找長度為n n的線性表時的線性表時, ,每個元素的平均每個元素的平均 查找長度為查找長度為 。 （A A）n n （B B）n/2n/2（C C）(n+1)/2(n+1)/2（D D）(n-1)/2(n-1)/22 2、對線性表進行二分

40、查找時、對線性表進行二分查找時, ,要求線性表必須要求線性表必須 。 （A A）以順序方式存儲）以順序方式存儲 （B B）以鏈接方式存儲）以鏈接方式存儲 （C C）以順序方式存儲）以順序方式存儲, ,且結點按關鍵字有序排序且結點按關鍵字有序排序 （D D）以鏈接方式存儲）以鏈接方式存儲, ,且結點按關鍵字有序排序且結點按關鍵字有序排序 3 3、己知一個有序表為、己知一個有序表為(12,18,20,25,29,32,40,62,83,90,95,98),(12,18,20,25,29,32,40,62,83,90,95,98),當二分查找值為當二分查找值為2929和和9090的元素時的元素時,

41、,分別需要分別需要( )( )次和次和( )( )次比較才次比較才能查找成功；若采用順序查找時能查找成功；若采用順序查找時, ,分別需要分別需要( )( )次和次和( )( )次比較次比較才能查找成功。才能查找成功。 練 習604 4、折半查找有序表（、折半查找有序表（4 4，6 6，1212，2020，2828，3838，5050，7070，8888，100100），若查找表中元素），若查找表中元素2020，它將依次與表中元素，它將依次與表中元素 比較大小。比較大小。 5 5、有一個長度為、有一個長度為1212的有序表，按二分查找法對其查找，在表內各的有序表，按二分查找法對其查找，在表內各元

42、素等概率情況下，查找成功的平均比較次數(shù)為（元素等概率情況下，查找成功的平均比較次數(shù)為（ ）。）。（A A）35/12 35/12 （B B）37/12 37/12 （C C）39/12 39/12 （D D）43/1243/12 6 6、對下列數(shù)據(jù)進行分塊查找。、對下列數(shù)據(jù)進行分塊查找。最大關鍵字起始地址72189276 1 610207694172172104189150201276211271練 習617、已知序列50，72，43，85，75，20，35，45，65，30，請構造二叉排序樹，并依次給出插入結點58和刪除結點20、72之后的二叉排序樹。 插入插入58：437220456585

43、5035307558436545588550353075刪除刪除72：4375456585503530或者或者5843724565855035307558刪除刪除20：練 習628 8、請將下面序列構成一棵平衡二叉排序樹：請將下面序列構成一棵平衡二叉排序樹： （ 3939，5858，2727，1212，6464，8888，4747，9696）39395858272712126464888858586464888847479696練 習639、請在下面的3階B_樹上依次插入關鍵字22、66、88，80；再依次刪除 89，88。37 7337 7317 2917 29575779 8979 8937 7337 7317 17 2222 29 29575779 8979