數(shù)據(jù)結(jié)構(gòu)課件考研輔導(dǎo)查找

1、查查 找找 主講：魯法明主講：魯法明 fm_ 上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束大大 綱綱l查找的基本概念查找的基本概念l順序查找法順序查找法l折半查找法折半查找法l補：二叉排序樹與平衡二叉樹補：二叉排序樹與平衡二叉樹lB-B-樹及其基本操作、樹及其基本操作、B+B+樹的基本概念樹的基本概念l散列散列(Hash)(Hash)表表l查找算法的分析及應(yīng)用查找算法的分析及應(yīng)用 靜態(tài)查找表靜態(tài)查找表 順序表上的操作順序表上的操作動態(tài)查找表動態(tài)查找表 樹表上的操作樹表上的操作哈希查找哈希查找哈希表上的操作哈希表上的操作上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束查找的基本概念查找的基本概念n查找表：用于查

2、找的同一類型的數(shù)據(jù)元素或記錄構(gòu)成的查找表：用于查找的同一類型的數(shù)據(jù)元素或記錄構(gòu)成的集合集合. Typedef structKeyType key;ElemType;. Typedef structKeyType key;ElemType;n查找：根據(jù)給定的值在查找表中確定一個關(guān)鍵字等于給查找：根據(jù)給定的值在查找表中確定一個關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素定值的記錄或數(shù)據(jù)元素. .n關(guān)鍵字：數(shù)據(jù)元素或記錄中某個數(shù)據(jù)項的值關(guān)鍵字：數(shù)據(jù)元素或記錄中某個數(shù)據(jù)項的值, ,用它可以用它可以標(biāo)識數(shù)據(jù)元素或記錄標(biāo)識數(shù)據(jù)元素或記錄. .若關(guān)鍵字能唯一標(biāo)識一個元素或若關(guān)鍵字能唯一標(biāo)識一個元素或記錄則稱其為主關(guān)鍵字

3、記錄則稱其為主關(guān)鍵字, ,否則稱其為次關(guān)鍵字。本章查否則稱其為次關(guān)鍵字。本章查找通常按主關(guān)鍵字查找，或查找不成功，或找到一個找通常按主關(guān)鍵字查找，或查找不成功，或找到一個n平均查找長度平均查找長度: :查找過程中關(guān)鍵字的平均比較次數(shù)查找過程中關(guān)鍵字的平均比較次數(shù). .如在如在長度為長度為n n的查找表上的查找表上, ,假設(shè)查找肯定成功則假設(shè)查找肯定成功則ASLASL成功成功=PiCi=PiCin靜態(tài)查找表與動態(tài)查找：創(chuàng)建后僅查找或檢索、不允許靜態(tài)查找表與動態(tài)查找：創(chuàng)建后僅查找或檢索、不允許插入或刪除的查找表稱為靜態(tài)查找表；允許則稱為動態(tài)插入或刪除的查找表稱為靜態(tài)查找表；允許則稱為動態(tài)查找表查找

4、表. .上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束1 1 靜態(tài)查找表靜態(tài)查找表l靜態(tài)查找表的存儲結(jié)構(gòu)選擇及其定義靜態(tài)查找表的存儲結(jié)構(gòu)選擇及其定義l普通表上的順序查找普通表上的順序查找(帶帶/不帶監(jiān)視哨不帶監(jiān)視哨)l有序表上的順序查找有序表上的順序查找l有序表上的折半查找有序表上的折半查找l其它其它上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束1.1 1.1 靜態(tài)查找表的存儲結(jié)構(gòu)靜態(tài)查找表的存儲結(jié)構(gòu)-靜態(tài)查找表的順序存儲結(jié)構(gòu)靜態(tài)查找表的順序存儲結(jié)構(gòu) 順序表順序表 -typedef * KeyType;/關(guān)鍵字類型關(guān)鍵字類型Typedef structKeyType key;ElemType; /元素類型元素

5、類型 typedef struct ElemType *elem; /空間基址空間基址, 0號留空它用號留空它用 int length; /表長表長SSTable /思考如何定義表、訪問記錄和記錄關(guān)鍵字思考如何定義表、訪問記錄和記錄關(guān)鍵字-線性表的順序存儲結(jié)構(gòu)定義線性表的順序存儲結(jié)構(gòu)定義-typedef * ElemType; typedef struct ElemType *elem; /空間基址空間基址 int length; /表長表長 int listsize; /容量容量 Sqlist上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束1.2 1.2 普通順序表上的順序查找普通順序表上的順序查找-

6、靜態(tài)查找表的順序存儲結(jié)構(gòu)靜態(tài)查找表的順序存儲結(jié)構(gòu)-typedef * KeyType;/關(guān)鍵字類型關(guān)鍵字類型Typedef structKeyType key;ElemType; /元素類型元素類型 typedef struct ElemType *elem; /空間基址空間基址, 0號留空它用號留空它用 int length; /表長表長SSTable /思考如何定義表和訪問記錄及記錄關(guān)鍵字思考如何定義表和訪問記錄及記錄關(guān)鍵字int Search_Seq(SSTable ST, KeyType key) /存在返下標(biāo),否返0 int i; for(i=1;iST.length)return

7、0; else return i; /每次循環(huán)都要判斷i=ST.length和是否EQ,能否合并為一個操作 ST.elem0.key=key; /監(jiān)視哨，哨兵，位置也可在最后監(jiān)視哨，哨兵，位置也可在最后 for(i=ST.length ;!EQ(ST.elemi.key, key);-i); return i;/算法復(fù)雜度均為算法復(fù)雜度均為O(n),但平均查找時間幾乎減少一半但平均查找時間幾乎減少一半上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束帶監(jiān)視哨的順序查找性能分析：帶監(jiān)視哨的順序查找性能分析：int Search_Seq(SSTable ST, KeyType key int i; ST.el

8、em0.key=key; /監(jiān)視哨，哨兵 for(i=ST.length ;!EQ(ST.elemi.key, key);-i); return i;設(shè)查找第設(shè)查找第i個元素概率為個元素概率為Pi, 找不到概率找不到概率P0,則平均查找長則平均查找長度度ASLSS=n*P1+(n-1)*P2+.+Pi*(n-i+1)+.+1*Pn +(n+1)*P0通常查找不成功的概率認(rèn)為很小，可認(rèn)為通常查找不成功的概率認(rèn)為很小，可認(rèn)為P0=0若查找保證成功且各元素幾率同若查找保證成功且各元素幾率同(1/n)則則ASLSS=(n+1)/2若成功與否各若成功與否各50%，且各元素被找到概率同，且各元素被找到概率

9、同(1/2n)則則ASLSS=(n+1)/4 + (n+1)/2= 3*(n+1)/4 概率越大越靠后放則概率越大越靠后放則ASL越小越小,事先不知概率可動態(tài)調(diào)事先不知概率可動態(tài)調(diào)整整上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束1.3 1.3 有序順序表上的順序查找有序順序表上的順序查找typedef struct ElemType *elem; /元素由小到大排列元素由小到大排列 int length;SSTableint Search_Seq(SSTable ST, KeyType key) int i; for(i=1;i=ST.length;i+) /零單元留空它用 if(EQ(ST.ele

10、mi.key, key)return i; else if(GT(ST.elemi.key, key) return -1; return -1;若查找保證成功且各元素幾率同若查找保證成功且各元素幾率同(1/n)則則ASLSS=(n+1)/2若查找可能不成功則需借助判定樹描述查找過程若查找可能不成功則需借助判定樹描述查找過程設(shè)設(shè)n條記錄條記錄,則失敗結(jié)點則失敗結(jié)點n+1個個,記錄結(jié)點記錄結(jié)點n個，假設(shè)到達(dá)個，假設(shè)到達(dá)各結(jié)點的概率相同各結(jié)點的概率相同1/(2n+1)則則ASL= (1+2+n)+(1+2+n+n)/(2*n+1)20103040(-,10)(10,20)(20,30)30,40)

11、(40,+)上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束1.4 1.4 折半查找折半查找l算法思想算法思想l存儲結(jié)構(gòu)選擇存儲結(jié)構(gòu)選擇l算法實現(xiàn)算法實現(xiàn)l性能分析性能分析上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束l算法思想算法思想針對有序表而言，又稱二分查找，思路如下：針對有序表而言，又稱二分查找，思路如下： low low指向最低端記錄指向最低端記錄,high,high指向最高端記錄指向最高端記錄; ;只要區(qū)間內(nèi)只要區(qū)間內(nèi)還有元素則定位還有元素則定位midmid到中間元素，比較待查元素與中間元到中間元素，比較待查元素與中間元素素, ,若比中間元素小則查找區(qū)間縮小為左半部分若比中間元素小則查找區(qū)間縮小為左

12、半部分, ,重新查找重新查找; ;若比中間元素大則查找區(qū)間縮小為右半部分若比中間元素大則查找區(qū)間縮小為右半部分, ,重新查找；重新查找；若相等則找到并返回位置若相等則找到并返回位置midmid。 區(qū)間內(nèi)無元素時返回區(qū)間內(nèi)無元素時返回0 0如找如找6464和和100100lowhighmidlowmidhighmid上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束l存儲結(jié)構(gòu)選擇存儲結(jié)構(gòu)選擇typedef struct ElemType *elem; /空間基址空間基址,0號留空它用，數(shù)組元素有序號留空它用，數(shù)組元素有序 int length; /表長表長SSTablelowlow指向最低端記錄：指向最低端

13、記錄：low=1low=1highhigh指向最高端記錄指向最高端記錄;high=ST.length;high=ST.length只要區(qū)間內(nèi)還有元素只要區(qū)間內(nèi)還有元素: while(low=high): while(low=high) 則定位到中間元素則定位到中間元素:mid=(low+high)/2:mid=(low+high)/2 若待查元素比中間元素小則查找區(qū)間縮小為左半部分若待查元素比中間元素小則查找區(qū)間縮小為左半部分 if(LT(key,ST.elemmid.key)high=mid-if(LT(key,ST.elemmid.key)high=mid-1 1 若比中間元素大則查找區(qū)間

14、縮小為右半部分：若比中間元素大則查找區(qū)間縮小為右半部分： if(GT(key,ST.elemmid.key)low=mid+1if(GT(key,ST.elemmid.key)low=mid+1 若相等則找到并返回位置若相等則找到并返回位置midmid if(EQ(key,ST.elemmid.key)return mid;if(EQ(key,ST.elemmid.key)return mid;區(qū)間內(nèi)無元素時返回區(qū)間內(nèi)無元素時返回-1: -1: 循環(huán)退出時循環(huán)退出時return 0return 0上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束l折半查找實現(xiàn)：折半查找實現(xiàn)：int Search_Bin

15、( SSTable ST, KeyType key ) /low=1,high=n,只要只要low=high則比較中間元素則比較中間元素,后改后改low或或high low = 1; high = ST.length; while (low ST.elemmid.key) return biSearch(ST,mid+1,high,key); 遞歸遞歸:參考專題課件參考專題課件遞歸邊界：區(qū)間長度遞歸邊界：區(qū)間長度為為1即即 low=high遞歸關(guān)系：遞歸關(guān)系：lowhigh時先與待查找區(qū)間中時先與待查找區(qū)間中間元素比較，相等則間元素比較，相等則找到，比中間元素小找到，比中間元素小則到左半?yún)^(qū)間則

16、到左半?yún)^(qū)間(降階降階)遞歸查找，比中間元遞歸查找，比中間元素大則到右半?yún)^(qū)間素大則到右半?yún)^(qū)間(降降階階)查找。查找。上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束性能分析性能分析折半查找的判定樹折半查找的判定樹639142578101111 元素值元素值 查找長度查找長度折半查找的判定樹折半查找的判定樹:比較時生成根比較時生成根,到左側(cè)區(qū)間比較時生成左孩子到左側(cè)區(qū)間比較時生成左孩子,右側(cè)比右側(cè)比較生成右孩子，如此遞歸較生成右孩子，如此遞歸折半查找判定樹特點：右子樹中各結(jié)點值比根大折半查找判定樹特點：右子樹中各結(jié)點值比根大,左子樹中各結(jié)點值比根左子樹中各結(jié)點值比根小小,子樹也如此子樹也如此.根據(jù)判定樹可如

17、下完成查找：從根結(jié)點開始根據(jù)判定樹可如下完成查找：從根結(jié)點開始,比當(dāng)前元素大比當(dāng)前元素大就向右、小則向左就向右、小則向左,或者找到或者找到,或者到空或者到空折半查找判定樹葉子結(jié)點所在層次之差最多為折半查找判定樹葉子結(jié)點所在層次之差最多為1,可證此類樹深度為可證此類樹深度為log2n+1,籍此可證查找成功時最壞查找長度為籍此可證查找成功時最壞查找長度為log2n+1,借助方形外部結(jié)借助方形外部結(jié)點可證不成功時的最大查找長度也如此。平均長度點可證不成功時的最大查找長度也如此。平均長度log2n+1-1,12233334444上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束性能分析性能分析平均查找長度平均查找

18、長度最壞查找長度為最壞查找長度為log2n+1,復(fù)雜度復(fù)雜度O(log2n)當(dāng)判定樹為滿二叉樹時當(dāng)判定樹為滿二叉樹時(n=2h-1),若查找成功且各元素幾率同若查找成功且各元素幾率同(1/n)則則ASLbs=(1*20+2*21+3*22+h*2h-1)/nlog2(n+1)-1對具體例子要會求查找成功和不成功的平均查找長度對具體例子要會求查找成功和不成功的平均查找長度5個關(guān)鍵字，如個關(guān)鍵字，如A B C D ECADBEDBACFEG7個關(guān)鍵字，如個關(guān)鍵字，如A B C D E F G上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束1.51.5其它：靜態(tài)查找表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及操作其它：靜態(tài)查找表的鏈?zhǔn)?/p>

19、存儲結(jié)構(gòu)及操作typedef * KeyType;/關(guān)鍵字類型關(guān)鍵字類型Typedef structKeyType key;ElemType; /元素類型元素類型typedef struct LNode ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 struct LNode * next; /指針域指針域LNode,*LinkList;Typedef LinkList SSTable;int Search_Seq(SSTable ST, KeyType key) LNode *p=ST-next; while(p!=NULL&!EQ(p-data.key, key) /注意技巧注意技巧

20、 p=p-next; /不可寫成不可寫成p+ return P;說明說明:平均比較次數(shù)與順序存儲結(jié)構(gòu)上的相應(yīng)算法同，折半不適用平均比較次數(shù)與順序存儲結(jié)構(gòu)上的相應(yīng)算法同，折半不適用上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束題目說明：題目說明：l計算普通順序表上順序查找、有序順序表上計算普通順序表上順序查找、有序順序表上順序查找和折半查找的平均查找長度。順序查找和折半查找的平均查找長度。l前兩個理解過程，最后一個在給定表長時會前兩個理解過程，最后一個在給定表長時會求，未給定時理解最壞查找長度、復(fù)雜度，求，未給定時理解最壞查找長度、復(fù)雜度，記住平均查找長度?？山Y(jié)合實例驗證記住平均查找長度?？山Y(jié)合實例驗證

21、l算法設(shè)計算法設(shè)計l設(shè)計高效查找算法，如設(shè)計高效查找算法，如0909年考題年考題l遞歸關(guān)鍵找邊界條件和遞歸關(guān)系，遞歸關(guān)系遞歸關(guān)鍵找邊界條件和遞歸關(guān)系，遞歸關(guān)系不明顯可考慮降階、分治、回溯不明顯可考慮降階、分治、回溯上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束2 2 動態(tài)查找表動態(tài)查找表l存儲結(jié)構(gòu)設(shè)計存儲結(jié)構(gòu)設(shè)計l二叉排序樹二叉排序樹l平衡二叉樹平衡二叉樹lB B樹與基本操作樹與基本操作lB+B+樹的基本概念樹的基本概念上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束2.1 2.1 存儲結(jié)構(gòu)設(shè)計存儲結(jié)構(gòu)設(shè)計l為方便增刪需用鏈?zhǔn)酱鎯?，但單鏈表查找效為方便增刪需用鏈?zhǔn)酱鎯?，但單鏈表查找效率太低，希望類似折半查找的?/p>

22、定樹，左子率太低，希望類似折半查找的判定樹，左子樹均比根小，右子樹均比根大，子樹內(nèi)部也樹均比根小，右子樹均比根大，子樹內(nèi)部也滿足這一規(guī)律，如此比較一次即可將查找范滿足這一規(guī)律，如此比較一次即可將查找范圍縮小到一個子樹上圍縮小到一個子樹上-二叉排序樹二叉排序樹l二叉排序樹整體越矮則查找效率越高，類似二叉排序樹整體越矮則查找效率越高，類似折半查找的判定樹，同樣結(jié)點個數(shù)的二叉樹折半查找的判定樹，同樣結(jié)點個數(shù)的二叉樹何時最矮何時最矮-二叉平衡樹二叉平衡樹(類滿二叉樹類滿二叉樹)l若能將二叉排序樹推廣為三叉、四叉則整體若能將二叉排序樹推廣為三叉、四叉則整體高度會更矮，查找效果更好高度會更矮，查找效果更好

23、上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束（1）若左子樹不空，則左子樹所有結(jié)點的）若左子樹不空，則左子樹所有結(jié)點的值均嚴(yán)格小于根結(jié)點的值；值均嚴(yán)格小于根結(jié)點的值； 二叉排序樹或者是一棵空樹；或者是具二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：有如下特性的二叉樹：（3）左、右子樹也都分別是二叉排序樹。）左、右子樹也都分別是二叉排序樹。（2）若右子樹不空，則右子樹上）若右子樹不空，則右子樹上 所有結(jié)點所有結(jié)點的值均嚴(yán)格大于根結(jié)點的值；的值均嚴(yán)格大于根結(jié)點的值；2.2 2.2 二叉排序樹（二叉查找樹）二叉排序樹（二叉查找樹）折半查找的判定樹是二叉排序樹，特殊的二叉排序樹折半查找的判定樹是二叉排

24、序樹，特殊的二叉排序樹上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束503080209010854035252388例如例如:是二叉排序樹。是二叉排序樹。66不不上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束 1）若根結(jié)點的關(guān)鍵字等于給定值則查找成功）若根結(jié)點的關(guān)鍵字等于給定值則查找成功,返根返根 2）若給定值小于根結(jié)點關(guān)鍵字則遞歸找左子樹并返回）若給定值小于根結(jié)點關(guān)鍵字則遞歸找左子樹并返回查找結(jié)果查找結(jié)果 3）若給定值大于根結(jié)點關(guān)鍵字則遞歸找右子樹并返回）若給定值大于根結(jié)點關(guān)鍵字則遞歸找右子樹并返回查找結(jié)果查找結(jié)果 若二叉排序樹為空，則查找不成功；否則若二叉排序樹為空，則查找不成功；否則:2.2.12.2.

25、1二叉排序樹（二叉查找樹）的查找二叉排序樹（二叉查找樹）的查找BiTree SearchBST(BiTree T,KeyType key) if(!T) return NULL; else if(EQ(key,T-data.key)return T; else if(LT(key,T-data.key)return(SearchBST(T-lchild,key); else return(SearchBST(T-rchild,key);上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束50308020908540358832查找關(guān)鍵字查找關(guān)鍵字= 50 ,505035 ,503040355090 ,508

26、09095l非遞歸思路：非遞歸思路：p最初指向根結(jié)點，只要最初指向根結(jié)點，只要p不空且不空且p所指結(jié)點不是所求則根據(jù)比較結(jié)果令所指結(jié)點不是所求則根據(jù)比較結(jié)果令p變?yōu)楫?dāng)前結(jié)變?yōu)楫?dāng)前結(jié)點的左孩子或右孩子。如此重復(fù)則最終點的左孩子或右孩子。如此重復(fù)則最終p空或者找空或者找到到上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束二叉排序樹查找的非遞歸實現(xiàn)二叉排序樹查找的非遞歸實現(xiàn)l思路：思路：p最初指向根結(jié)點，只要最初指向根結(jié)點，只要p不空且不空且p所指結(jié)所指結(jié)點不是所求則根據(jù)比較結(jié)果令點不是所求則根據(jù)比較結(jié)果令p變?yōu)楫?dāng)前結(jié)點的左變?yōu)楫?dāng)前結(jié)點的左孩子或右孩子。如此重復(fù)則最終孩子或右孩子。如此重復(fù)則最終p空或者找到空

27、或者找到BiTNode *Search(BiTree T, KeyType key) BiTNode *p=T; while(p!=null&!EQ(key,p-data.key) if(LT(key,p-data.key)p=p-lchild; elsep=p-rchild; return p;上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束2.2.2 2.2.2 二叉排序樹結(jié)點的插入二叉排序樹結(jié)點的插入2010252320102325上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束查找定位子函數(shù)查找定位子函數(shù)非遞歸非遞歸l思路思路:p最初指向根結(jié)點最初指向根結(jié)點,只要只要p不空且不空且p所指結(jié)點非所所

28、指結(jié)點非所求則根據(jù)比較結(jié)果令求則根據(jù)比較結(jié)果令p變?yōu)楫?dāng)前結(jié)點的左孩子或右孩變?yōu)楫?dāng)前結(jié)點的左孩子或右孩子。如此重復(fù)則最終子。如此重復(fù)則最終p空或者找到。找到返回空或者找到。找到返回TRUE，否則返回否則返回FALSE。同時設(shè)引用型參數(shù)。同時設(shè)引用型參數(shù)f帶回帶回“父節(jié)點父節(jié)點”BiTNode *SearchBST(BiTree T, KeyType key,BiTNode * &f) BiTNode *p=T; f=NULL; while(p!=null&!EQ(key,p-data.key) f=p; if(LT(key,p-data.key)p=p-lchild; elsep

29、=p-rchild; return p;上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束插入算法：插入算法：Status InsertBST(BiTree &T,ElemType e ) BiTNode *p,*f,*s; p=SearchBST( T, e.key, f ); if (p!=NULL) return FALSE; else s=(BiTree)malloc(sizeof(BiTNode); if(s=NULL) return FALSE; s-data=e;s-lchild=NULL;s-rchild=NULL; if(f=NULL) T=s; /原樹為空原樹為空 else i

30、f( LT(e.key,p-data.key) )p-lchild=s; else p-rchild=s; return TRUE; /插入成功插入成功 上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束20102523查找定位查找定位-遞歸函數(shù)遞歸函數(shù)上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束if (!T)else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) )elsereturn SearchBST (T-lchild, key, T, p ); / 在左子樹中繼續(xù)查找在左子樹中繼續(xù)查找return SearchBST (T-rchil

31、d, key, T, p ); / 在右子樹中繼續(xù)查找在右子樹中繼續(xù)查找上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束30201040352523fTfTfT22pfTfTTTTfffp48上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束插入算法插入算法基于遞歸查找定位基于遞歸查找定位Status Insert BST(BiTree &T,ElemType e ) if (!SearchBST ( T, e.key, NULL, p ) s=(BiTree)malloc(sizeof(BiTNode); s-data=e;s-lchild=NULL;s-rchild=NULL; if(!p) T=s;

32、/未找到插入位置未找到插入位置,意味著原樹空意味著原樹空 else if( LT(e.key,p-data.key) )p-lchild=s; else p-rchild=s; return TRUE; /插入成功插入成功 else return FALSE;/原樹中存在元素關(guān)鍵字與原樹中存在元素關(guān)鍵字與e等等上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束說明：說明：l看書做題及時鞏固所講知識點看書做題及時鞏固所講知識點l不明白的問題或題目發(fā)不明白的問題或題目發(fā)fm_，屆時統(tǒng)一，屆時統(tǒng)一講解講解l如何有效查找單鏈表中倒數(shù)第如何有效查找單鏈表中倒數(shù)第k個結(jié)點個結(jié)點上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束回

33、顧：回顧：l查找的基本概念查找的基本概念l靜態(tài)查找表靜態(tài)查找表l順序查找法（哨順序查找法（哨 有序表）有序表）l折半查找法（有序順序表折半查找法（有序順序表 判定樹）判定樹）l動態(tài)查找表動態(tài)查找表l存儲結(jié)構(gòu)設(shè)計存儲結(jié)構(gòu)設(shè)計l二叉排序樹：定義二叉排序樹：定義+ +查找查找+ +插入插入+ +刪除刪除l平衡二叉樹平衡二叉樹lB B樹與基本操作樹與基本操作lB+B+樹的基本概念樹的基本概念l哈希查找哈希查找上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束2.2.3 2.2.3 二叉排序樹結(jié)點的刪除二叉排序樹結(jié)點的刪除Status DeleteBST(BiTree &T,KeyType key) /找到

34、關(guān)鍵字為找到關(guān)鍵字為key元素則刪除并返回刪除結(jié)果元素則刪除并返回刪除結(jié)果,否則返回否則返回FALSE if(!T)return FALSE; else if( EQ(key,T-data.key) return( delete(T) ); else if(LT(key,T-data.key) return DeleteBST(T-lchild, key); else return( DeleteBST(T-rchild,key) ); 如刪除如刪除23,由由T為引用型知最后執(zhí)行實為為引用型知最后執(zhí)行實為delete(T-rchild-lchild)最終執(zhí)行最終執(zhí)行Delete(T)時時T是是

35、T-rchild-lchild的別名的別名,即雙親左指針即雙親左指針,刪刪除函數(shù)設(shè)計為除函數(shù)設(shè)計為delete(BiTree &p)，則，則p也是也是T-rchild-lchild，通過，通過p即可操作雙親指針即可操作雙親指針, 對于上例只需令對于上例只需令p=NULL即可。但若即可。但若p左右子樹左右子樹不空需認(rèn)真考慮以保證刪除后仍然是二叉排序樹不空需認(rèn)真考慮以保證刪除后仍然是二叉排序樹20102523上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束50308020908540358832被刪關(guān)鍵字被刪關(guān)鍵字 = 2088其雙親結(jié)點中相應(yīng)指針域的值改為其雙親結(jié)點中相應(yīng)指針域的值改為“空空”if

36、(!p-lchild&!p-rchild)p=NULL;p是是T-rchild-rchild-lchild-rchild的的別名別名,是是88雙親的右指針雙親的右指針,隱含雙親信息隱含雙親信息,不必再定位雙親不必再定位雙親上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束50308020908540358832雙親結(jié)點的相應(yīng)指針域指向被刪結(jié)點的唯一子樹雙親結(jié)點的相應(yīng)指針域指向被刪結(jié)點的唯一子樹被刪關(guān)鍵字被刪關(guān)鍵字 = 4080if(!p-lchild)BiTree q=p;p=p-rchild;free(q);/刪除刪除80時時p是是T-rchild的別名的別名,相當(dāng)雙親的孩子指針相當(dāng)雙親的孩子指

37、針, 而而q則是另一個則是另一個普通指針變量普通指針變量,雖然也指向雖然也指向80,但但q改變不影響改變不影響80的雙親指針的雙親指針上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束5030802090854035883245設(shè)設(shè)p指向刪除結(jié)點指向刪除結(jié)點,找找p左子樹中最大結(jié)點左子樹中最大結(jié)點s”取代取代”p，分兩種情況：，分兩種情況：(1)p的左孩子存在右子樹的左孩子存在右子樹,此時最大結(jié)點此時最大結(jié)點s必位于該右子樹必位于該右子樹,且且s必為右必為右上方第一個右孩子為空的結(jié)點。設(shè)置輔助指針上方第一個右孩子為空的結(jié)點。設(shè)置輔助指針q指向指向s的雙親，則的雙親，則s=p-lchild-rchild;

38、q=p-lchild;while(s-rchild) q=s; s=s-rchild; p-data=s-data; q-rchild=s-lchild; (2) p的左孩子不存在右子樹的左孩子不存在右子樹,此時此時p-lchild最大最大,故故 s=p-lchild; p-data=s-data; p-lchild=s-lchild; free(s);被刪關(guān)鍵字被刪關(guān)鍵字 = 504542上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束Status Delete(&p)/從二叉排序樹中刪除結(jié)點從二叉排序樹中刪除結(jié)點p,并重接其左右子樹并重接其左右子樹.p含雙親信息含雙親信息if(!p-rchi

39、ld) /包含包含p為葉子結(jié)點的情況為葉子結(jié)點的情況 q=p; p=p-lchild; free(q); /刪除刪除p結(jié)點，注意結(jié)點，注意p與與q不同不同 else if(!p-lchild) q=p; p=p-rchild; free(q);/q為普通指針為普通指針,p是雙親指針別是雙親指針別名名else/結(jié)點結(jié)點p左右子樹均不空左右子樹均不空,書中是下述兩種情況合并書中是下述兩種情況合并,會分析會分析 if(!p-lchild-rchild)/p的左孩子無右子樹時的左孩子無右子樹時,p左孩子最大左孩子最大 s=p-lchild; p-data=s-data; /用用s取代取代p p-lch

40、ild=s-lchild; free(s);s=NULL; else /p的左孩子有右子樹的左孩子有右子樹,最大元素是該右子樹中第一個無最大元素是該右子樹中第一個無/右孩子的結(jié)點右孩子的結(jié)點 s=p-lchild-rchild; q=p-lchild; while(s-rchild) q=s; s=s-rchild; p-data=s-data; q-rchild=s-lchild;free(s);s=NULL; /此算法是按前面思路得到，教材在此基礎(chǔ)上進(jìn)行了此算法是按前面思路得到，教材在此基礎(chǔ)上進(jìn)行了“整理整理”上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束關(guān)鍵字輸入序列關(guān)鍵字輸入序列 3，1，2，

41、5，4：關(guān)鍵字輸入序列：關(guān)鍵字輸入序列： 1，2，3，4，5：21345354122.2.42.2.4二叉排序樹查找性能分析二叉排序樹查找性能分析( (假設(shè)查找成假設(shè)查找成功功) )平均：1ASL2log=O(log )nnCnn 二叉排序樹中序遍歷序列必嚴(yán)格遞增二叉排序樹中序遍歷序列必嚴(yán)格遞增;若中序遞增則必二叉排序樹若中序遞增則必二叉排序樹總體深度越小越好，最好情況下類似折半查找的判定樹，任意結(jié)總體深度越小越好，最好情況下類似折半查找的判定樹，任意結(jié)點的左右子樹深度之差絕對值不超過點的左右子樹深度之差絕對值不超過1.平衡二叉樹平衡二叉樹:任意結(jié)點左右子樹深度差任意結(jié)點左右子樹深度差(平衡因

42、子平衡因子)絕對值不超過絕對值不超過1上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束2.3 2.3 平衡二叉樹平衡二叉樹(BBT(BBT或或AVLAVL樹或樹或Height Height Balanced Tree)Balanced Tree) 樹中每個結(jié)點的左、右子樹深度之差樹中每個結(jié)點的左、右子樹深度之差(平平衡因子衡因子)為為0 1 或或-1 。1RLhh52815281-1是二叉平衡樹，是二叉平衡樹，同時是二叉排序樹同時是二叉排序樹 是二叉排序樹是二叉排序樹不是平衡二叉樹不是平衡二叉樹“最小不平衡二叉樹最小不平衡二叉樹”440上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束u平衡的二叉排序樹的構(gòu)造平衡的

43、二叉排序樹的構(gòu)造l思路：按二叉排序樹進(jìn)行構(gòu)造，每插入思路：按二叉排序樹進(jìn)行構(gòu)造，每插入一個結(jié)點，檢查該結(jié)點是否導(dǎo)致不平衡。一個結(jié)點，檢查該結(jié)點是否導(dǎo)致不平衡。若導(dǎo)致不平衡則找若導(dǎo)致不平衡則找“最小不平衡樹最小不平衡樹”，通過旋轉(zhuǎn)使該最小的不平衡樹平衡即可。通過旋轉(zhuǎn)使該最小的不平衡樹平衡即可。l旋轉(zhuǎn)原則：第一保證平衡性；第二保證旋轉(zhuǎn)原則：第一保證平衡性；第二保證是二叉排序樹是二叉排序樹l例：例：13 24 37 90 53 95 10 5 40 上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束RR型：在最小不平衡二叉樹根結(jié)點的右孩子的右子樹中插型：在最小不平衡二叉樹根結(jié)點的右孩子的右子樹中插入新結(jié)點導(dǎo)致失

44、衡。入新結(jié)點導(dǎo)致失衡。abBCAhabBCAh例：例：13 24 37 90 53 95 10 5 40上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束RL型：在最小不平衡二叉樹根結(jié)點的右孩子的左子樹上插入新結(jié)點導(dǎo)致失衡。型：在最小不平衡二叉樹根結(jié)點的右孩子的左子樹上插入新結(jié)點導(dǎo)致失衡。abCDABhcabCDABhcacDCbAB例：例：13 24 37 90 53 95 10 5 40上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束RR型：在最小不平衡二叉樹根結(jié)點的右孩子的右子樹中插入新結(jié)點導(dǎo)致失衡。型：在最小不平衡二叉樹根結(jié)點的右孩子的右子樹中插入新結(jié)點導(dǎo)致失衡。abBCAhabBCAh例：例：13 24

45、37 90 53 95 10 5 40上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束LL型：在最小不平衡二叉樹根節(jié)點的左孩子的左子樹上插入新結(jié)點導(dǎo)致失衡。型：在最小不平衡二叉樹根節(jié)點的左孩子的左子樹上插入新結(jié)點導(dǎo)致失衡。abBCAhabBCAh例：例：13 24 37 90 53 95 10 5 40上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束LR型：在最小不平衡二叉樹根結(jié)點的左孩子的右子樹上插入新結(jié)點導(dǎo)致失衡。型：在最小不平衡二叉樹根結(jié)點的左孩子的右子樹上插入新結(jié)點導(dǎo)致失衡。abCDABhcabCDABhc例：例：13 24 37 90 53 95 10 5 40上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束作業(yè)

46、作業(yè)1：45, 32, 16, 77, 94, 38, 44, 21, 39, 68, 33, 87454532453216453216453216779445321677944532167794384532167794384532167794384445321677943844214532167794384421394532167794384421394532167794384421396845321677943844213968334532167794384421396833453216779438442139683387453216779438442139683387上頁上頁 下頁下頁節(jié)

47、節(jié)末頁末頁結(jié)束結(jié)束2.4 B-2.4 B-樹及其基本操作樹及其基本操作l概念：可看作平衡二叉排序樹的推廣，是一概念：可看作平衡二叉排序樹的推廣，是一種種“平衡平衡”的的“多路多路”“”“查找查找”樹，如下例樹，如下例是一個是一個4階階B-樹樹(階數(shù)由結(jié)點的最大子樹個數(shù)階數(shù)由結(jié)點的最大子樹個數(shù)決定決定) root 50 15 71 84 3 8 20 26 43 56 62 78 89 96FFFF FFFFFFFFFF F上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束2.4.1 B-2.4.1 B-樹形式化定義樹形式化定義l一顆一顆m階的階的B樹是空樹，或是滿足下列特性的樹是空樹，或是滿足下列特性的m

48、叉樹：叉樹：l(1)樹中每個結(jié)點至多有樹中每個結(jié)點至多有m棵子樹棵子樹(m-1個關(guān)鍵字個關(guān)鍵字)l(2)若根結(jié)點不是葉子結(jié)點則至少有兩棵子樹若根結(jié)點不是葉子結(jié)點則至少有兩棵子樹l(3)根之外所有非終端結(jié)點至少有根之外所有非終端結(jié)點至少有ceil(m/2)棵子樹棵子樹l(4) 非終端結(jié)點包含信息非終端結(jié)點包含信息(n, A0,K1,A1,K1,A2,.,Kn ,An)lKi為關(guān)鍵字為關(guān)鍵字,有序有序; Ai為指向子樹根結(jié)點的指針為指向子樹根結(jié)點的指針,且且Ai所指所指子樹中所有結(jié)點關(guān)鍵字均介于子樹中所有結(jié)點關(guān)鍵字均介于Ki-1和和Ki之間之間.l(5)葉子結(jié)點都出現(xiàn)在同一層次上葉子結(jié)點都出現(xiàn)在同

49、一層次上,不帶信息，相當(dāng)于查不帶信息，相當(dāng)于查找失敗結(jié)點找失敗結(jié)點 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96FFFF FFFFFFFFFF F上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束2.4.2 B-2.4.2 B-樹上的查找樹上的查找l類似二叉排序樹的查找，是一個順指針查找結(jié)點和類似二叉排序樹的查找，是一個順指針查找結(jié)點和在結(jié)點的關(guān)鍵字中進(jìn)行查找交叉進(jìn)行的過程在結(jié)點的關(guān)鍵字中進(jìn)行查找交叉進(jìn)行的過程l查找操作包括在查找操作包括在B樹中找結(jié)點和在結(jié)點中找關(guān)鍵字，樹中找結(jié)點和在結(jié)點中找關(guān)鍵字，前者在磁盤上進(jìn)行前者在磁盤上進(jìn)行,后者在內(nèi)存中進(jìn)行后者在內(nèi)存中

50、進(jìn)行, 在磁盤上進(jìn)在磁盤上進(jìn)行查找的次數(shù)或者說待查關(guān)鍵字所在結(jié)點在行查找的次數(shù)或者說待查關(guān)鍵字所在結(jié)點在B-樹上樹上的層次是決定查找效率的首要因素的層次是決定查找效率的首要因素,故提高路數(shù)可改故提高路數(shù)可改善查找效率。設(shè)含善查找效率。設(shè)含N個關(guān)鍵字則讀盤次數(shù)不超過個關(guān)鍵字則讀盤次數(shù)不超過1+log（m/2,(n+1)/2），詳見），詳見P240 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96FFFF FFFFFFFFFF F上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束2.4.3 B-2.4.3 B-樹結(jié)點的插入樹結(jié)點的插入l類似二叉排序樹的插入，首先查找，若

51、查找成功則類似二叉排序樹的插入，首先查找，若查找成功則不能插入，否則應(yīng)試圖插入到查找路徑中最后一個不能插入，否則應(yīng)試圖插入到查找路徑中最后一個內(nèi)部結(jié)點上。但每個內(nèi)部結(jié)點關(guān)鍵字個數(shù)必須在內(nèi)部結(jié)點上。但每個內(nèi)部結(jié)點關(guān)鍵字個數(shù)必須在Ceil(m/2-1)和和m-1之間，若插入后超出上界之間，若插入后超出上界m-1則需則需要進(jìn)行要進(jìn)行“分裂分裂”l分裂分裂:選中間關(guān)鍵字上移選中間關(guān)鍵字上移,當(dāng)前結(jié)點分成兩個當(dāng)前結(jié)點分成兩個,下層相下層相應(yīng)分；若上移導(dǎo)致雙親關(guān)鍵字個數(shù)超界則繼續(xù)上應(yīng)分；若上移導(dǎo)致雙親關(guān)鍵字個數(shù)超界則繼續(xù)上移移.P242圖圖9.16 root 50 15 71 84 3 8 20 26 4

52、3 56 62 78 89 96FFFF FFFFFFFFFF F上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束2.4.4 B-2.4.4 B-樹結(jié)點的刪除樹結(jié)點的刪除l先找到關(guān)鍵字所在結(jié)點，若結(jié)點不是最下層的非終端結(jié)點，設(shè)先找到關(guān)鍵字所在結(jié)點，若結(jié)點不是最下層的非終端結(jié)點，設(shè)關(guān)鍵字為關(guān)鍵字為Ki,則應(yīng)用則應(yīng)用Ai所指向子樹中的最小關(guān)鍵字所指向子樹中的最小關(guān)鍵字x代替代替Ki,然后然后在在x所在結(jié)點所在結(jié)點(必為最下層非終端結(jié)點必為最下層非終端結(jié)點)上刪除上刪除x。問題歸結(jié)為在。問題歸結(jié)為在最下層的非終端結(jié)點上刪除關(guān)鍵字最下層的非終端結(jié)點上刪除關(guān)鍵字l(1)若刪除后最下層非終端結(jié)點的關(guān)鍵字個數(shù)仍然不超

53、出下界若刪除后最下層非終端結(jié)點的關(guān)鍵字個數(shù)仍然不超出下界Ceil(m/2)-1則直接刪除則直接刪除l(2)若刪除前關(guān)鍵字個數(shù)為若刪除前關(guān)鍵字個數(shù)為Ceil(m/2)-1，且該結(jié)點左，且該結(jié)點左/右兄弟關(guān)鍵右兄弟關(guān)鍵字個數(shù)未達(dá)下界，則將雙親左字個數(shù)未達(dá)下界，則將雙親左/右側(cè)關(guān)鍵字下移、左右側(cè)關(guān)鍵字下移、左/右兄弟右右兄弟右/左端關(guān)鍵字上移即可左端關(guān)鍵字上移即可l(3)若所在結(jié)點及其左右兄弟結(jié)點關(guān)鍵字?jǐn)?shù)均達(dá)下界則雙親左若所在結(jié)點及其左右兄弟結(jié)點關(guān)鍵字?jǐn)?shù)均達(dá)下界則雙親左/右右側(cè)關(guān)鍵字下移并與左側(cè)關(guān)鍵字下移并與左/右兄弟合并；若下移后雙親結(jié)點不滿足要右兄弟合并；若下移后雙親結(jié)點不滿足要求則上層重復(fù)該過

54、程。如動畫或求則上層重復(fù)該過程。如動畫或P245-F9.17 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96FFFF FFFFFFFFFF F上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束2.5 B+2.5 B+樹的基本概念樹的基本概念 50 96 15 5062 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sqm階階B+樹：可看作多層索引表。關(guān)鍵字及記錄的位置信息全部包樹：可看作多層索引表。關(guān)鍵字及記錄的位置信息全部包含在葉結(jié)點中，每個結(jié)點至多包含含在葉結(jié)點中，每個結(jié)點至多包含m個子樹，葉結(jié)點內(nèi)與葉結(jié)點個子樹，葉結(jié)點

55、內(nèi)與葉結(jié)點間關(guān)鍵字均有序，均在最下層且依關(guān)鍵字順序鏈接成一個鏈表。間關(guān)鍵字均有序，均在最下層且依關(guān)鍵字順序鏈接成一個鏈表。上層結(jié)點是對葉結(jié)點最大上層結(jié)點是對葉結(jié)點最大/小值的提取。其余同小值的提取。其余同B樹的定義樹的定義與與B-樹區(qū)別：結(jié)點關(guān)鍵字?jǐn)?shù)與子樹數(shù)同樹區(qū)別：結(jié)點關(guān)鍵字?jǐn)?shù)與子樹數(shù)同 關(guān)鍵字信息均在葉中關(guān)鍵字信息均在葉中 存在葉結(jié)點鏈表存在葉結(jié)點鏈表 上層結(jié)點關(guān)鍵字信息是冗余上層結(jié)點關(guān)鍵字信息是冗余上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束pB+B+樹的查找樹的查找l順序查找和按樹順序查找和按樹(隨機隨機)查找兩種查找兩種l順序查找類似有序順序表上的普通查找順序查找類似有序順序表上的普通查找

56、,折半不可用折半不可用l隨機查找即使在中間找到也不停止隨機查找即使在中間找到也不停止,必須走到葉結(jié)點必須走到葉結(jié)點 50 96 15 5062 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sq上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束作作 業(yè)業(yè)l作業(yè)作業(yè)1：按如下插入順序構(gòu)造平衡二叉樹：按如下插入順序構(gòu)造平衡二叉樹： 45, 32, 16, 77, 94, 38, 44, 21, 39, 68, 33, 87l作業(yè)作業(yè)2：從空樹開始，按以下次序向：從空樹開始，按以下次序向3階階B-樹中插入關(guān)鍵碼：樹中插入關(guān)鍵碼：20，30，50，52，60，68，70。先

57、畫出創(chuàng)建后形成的。先畫出創(chuàng)建后形成的B-樹，樹，之后刪除之后刪除50，68，畫出最終的，畫出最終的B-樹樹上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束 一、什么是哈希表？二、哈希函數(shù)的構(gòu)造方法二、哈希函數(shù)的構(gòu)造方法 三、處理沖突的方法 四、哈希表的查找及性能分析四、哈希表的查找及性能分析上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束前述查找表的各種存儲結(jié)構(gòu)前述查找表的各種存儲結(jié)構(gòu), ,無法根據(jù)所查找關(guān)鍵字計無法根據(jù)所查找關(guān)鍵字計算元素位置，因記錄在表中的位置和它的關(guān)鍵字取值算元素位置，因記錄在表中的位置和它的關(guān)鍵字取值無任何關(guān)系。通過比較進(jìn)行查找，至少比較無任何關(guān)系。通過比較進(jìn)行查找，至少比較1 1次次,

58、, 查找查找長度均不為零長度均不為零 對于頻繁使用的查找表希望對于頻繁使用的查找表希望ASLASL接近接近0 0，如何做到？，如何做到？上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束例如：為每年固定招收的例如：為每年固定招收的1000 名新生建名新生建立一張查找表，其關(guān)鍵字為學(xué)號，關(guān)鍵立一張查找表，其關(guān)鍵字為學(xué)號，關(guān)鍵字取值范圍為字取值范圍為2005000 2005999存儲結(jié)構(gòu)存儲結(jié)構(gòu):以下標(biāo)為以下標(biāo)為000 999 的順序表表示該查找的順序表表示該查找表表,i號元素對應(yīng)學(xué)號為號元素對應(yīng)學(xué)號為2005i的學(xué)生信息的學(xué)生信息查找方案：直接根據(jù)查找方案：直接根據(jù)key值后三位便可定位相應(yīng)元值后三位便可定

59、位相應(yīng)元素素,無需比較無需比較. Hash函數(shù)函數(shù):從關(guān)鍵字到存儲地址之間的映像函數(shù)，從關(guān)鍵字到存儲地址之間的映像函數(shù)，如上例如上例 H(key)=key-2005000或或H(key)=key MOD 1000上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束沖突沖突:不同的關(guān)鍵字可能得到統(tǒng)一哈希地址的現(xiàn)象。若可不同的關(guān)鍵字可能得到統(tǒng)一哈希地址的現(xiàn)象。若可能出現(xiàn)沖突則應(yīng)制定相應(yīng)的沖突處理方法，如將同余的記能出現(xiàn)沖突則應(yīng)制定相應(yīng)的沖突處理方法，如將同余的記錄組成一個鏈表錄組成一個鏈表Hash函數(shù)函數(shù):H(key)=key MOD100根據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法根據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法,將

60、一組關(guān)鍵字將一組關(guān)鍵字映象到一組有限的連續(xù)的存儲空間上，以關(guān)鍵字對應(yīng)的映象到一組有限的連續(xù)的存儲空間上，以關(guān)鍵字對應(yīng)的Hash函數(shù)值作存儲地址，如此所得表稱為哈希表。函數(shù)值作存儲地址，如此所得表稱為哈希表。映像過程稱為哈希造表或散列映像過程稱為哈希造表或散列,存儲地址稱為哈希地址存儲地址稱為哈希地址或散列地址?；蛏⒘械刂?。關(guān)鍵是構(gòu)造合適的關(guān)鍵是構(gòu)造合適的Hash函數(shù)和找合適的沖突處理方法函數(shù)和找合適的沖突處理方法上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束 對數(shù)值型的關(guān)鍵字常見構(gòu)造方法有：對數(shù)值型的關(guān)鍵字常見構(gòu)造方法有：若非數(shù)字關(guān)鍵字，則需先對其進(jìn)行數(shù)字化處理若非數(shù)字關(guān)鍵字，則需先對其進(jìn)行數(shù)字化處理1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余數(shù)法除留