專題三數(shù)據(jù)結(jié)構(gòu)與算法

1、查找與排序,專題三,數(shù)據(jù)結(jié)構(gòu)與控制算法分析,學(xué)習(xí)內(nèi)容與要求,學(xué)習(xí)和掌握順序查找和折半查找算法的原理和實(shí)現(xiàn)；學(xué)習(xí)和掌握二叉排序樹的概念及其構(gòu)造方法、二叉排序樹的查找算法原理。學(xué)習(xí)和掌握選擇排序、交換排序、插入排序、歸并排序和快速排序方法的原理。,第 2 頁(yè),1 Search(查找/搜索),第 3 頁(yè),第 4 頁(yè),所謂查找（或搜索），就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對(duì)象: 1.查找成功 即找到滿足條件的數(shù)據(jù)對(duì)象時(shí)

2、, 作為結(jié)果, 可報(bào)告該對(duì)象在結(jié)構(gòu)中的位置, 還可給出該對(duì)象中的具體信息。 2.查找不成功 或搜索失敗。作為結(jié)果, 應(yīng)報(bào)告一些信息, 如失敗標(biāo)志、位置等 。,通常稱用于查找的數(shù)據(jù)集合為查找結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的數(shù)據(jù)(或記錄)組成。每個(gè)對(duì)象有若干屬性，其中有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對(duì)象，稱為關(guān)鍵字。使用基于關(guān)鍵字的搜索，查找結(jié)果應(yīng)是唯一的。但在實(shí)際應(yīng)用時(shí)，查找條件是多方面的，可以使用基于屬性的查找方法，但查找結(jié)果可能

3、不唯一。,第 5 頁(yè),實(shí)施查找時(shí)有兩種不同的環(huán)境靜態(tài)環(huán)境 查找結(jié)構(gòu)不需進(jìn)行插入和刪除操作。 ? 靜態(tài)查找表,第 6 頁(yè),動(dòng)態(tài)環(huán)境 查找過(guò)程中可能要對(duì)查找結(jié)構(gòu)執(zhí)行數(shù)據(jù)插入、刪除或修改等操作，并對(duì)查找結(jié)構(gòu)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。 ? 動(dòng)態(tài)查找表動(dòng)態(tài)查找表的表結(jié)構(gòu)是在查找過(guò)程中動(dòng)態(tài)生成的。,第 7 頁(yè),以線性結(jié)構(gòu)表示靜態(tài)查找表?；驹恚簩⒋檎矣涗浺来沃饌€(gè)與表中記錄進(jìn)行比較。,1.1 順序查找（Sequ

4、ential Search),第 8 頁(yè),SL.elem,,,順序查找過(guò)程（從前向后查找）,假設(shè)給定查找值 e=64,要求 SL.elem[k] = e, 問(wèn): k = ?,k,k,第 9 頁(yè),SL.elem,,,i,SL.elem,,,i,60,i,key=64,key=60,i,64,順序查找過(guò)程（從后向前查找）,0單元用于存放待查找關(guān)鍵字，作為“哨兵”(guard),返回0,返回7,第 10 頁(yè),int Search_Seq(

5、TB SL, TYPE key ){ SL.elem[0].key = key; // “哨兵” for (i=SL.length; SL.elem[i].key!=key; --i); // 從后往前找 return i; // 查找成功時(shí)i為有效下標(biāo),否則i為0},順序查找算法實(shí)現(xiàn)（從后向前查找）,第 11 頁(yè),查

6、找成功:最少比較次數(shù) 最多比較次數(shù) 平均比較次數(shù) 查找失敗:最少比較次數(shù) 最多比較次數(shù) 平均比較次數(shù),查找算法的評(píng)價(jià)指標(biāo),第 12 頁(yè),查找算法的平均查找長(zhǎng)度ASL(Average Search Length) 指為了確定記錄在查找表中的位置，需要和給定值進(jìn)行關(guān)鍵字比較的次數(shù)的期望值:,其中，n為表長(zhǎng)，Pi為查找表中第

7、i個(gè)記錄的概率，且 ；Ci為查找到該記錄時(shí)，曾和給定值進(jìn)行關(guān)鍵字比較的次數(shù)。,第 13 頁(yè),在等概率情形，查找任一記錄的概率相等：pi = 1/n, i = 1, 2, ?, n,查找不成功時(shí)，,查找成功時(shí)，,以從前向后順序查找算法為例，,查找算法時(shí)間復(fù)雜度？,O(n),順序查找算法總結(jié)查找長(zhǎng)度： 查找成功:最少比較次數(shù)　 1 最多比較次數(shù)　 n　 平均比較次數(shù)

8、(n+1)/2 查找失敗:最少比較次數(shù) n 最多比較次數(shù) n 平均比較次數(shù) n優(yōu)點(diǎn)：查找結(jié)構(gòu)無(wú)特殊要求（線性結(jié)構(gòu)均適用）；算法簡(jiǎn)單；缺點(diǎn)：查找效率較低，不適于大表查找。,第 14 頁(yè),第 15 頁(yè),上述按順序查找表的查找算法簡(jiǎn)單，但平均查找長(zhǎng)度較大，不適用于表長(zhǎng)較大的查找結(jié)構(gòu)。,1.2 折半查找（二分查找）（Binary Search),若靜態(tài)查找表為有序表，則查找過(guò)程可以基于“折半

9、”進(jìn)行。,基于有序順序表的折半查找,設(shè)n個(gè)數(shù)據(jù)對(duì)象存放在一個(gè)有序順序表中，并按其關(guān)鍵字值從小到大（或從大到?。┡藕眯?。原理：折半查找時(shí), 每次都先求出位于查找區(qū)間正中的對(duì)象的下標(biāo)mid，用其關(guān)鍵字與給定值x比較，然后根據(jù)比較結(jié)果將查找區(qū)間縮小一半，直至找到被查找對(duì)象。,第 16 頁(yè),折半查找算法（設(shè)數(shù)據(jù)按關(guān)鍵字從小到大有序排列）,1.Element[mid].key==x 查找成功；2.Element[mid].key>x

10、 把查找區(qū)間縮小為表的前半部分，繼續(xù)折半查找；3.Element[mid].key<x 把查找區(qū)間縮小為表的后半部分，繼續(xù)折半查找；如果查找區(qū)間縮小到一個(gè)對(duì)象，且仍未找到想要查找的對(duì)象，則查找失敗。,第 17 頁(yè),第 18 頁(yè),SL.elem,,SL.length,例如: key=64 的查找過(guò)程如下,,,,low,high,mid,,,,,mid,,,,,,,,,mid,mid = ?(low+high)/2 ? （向下

11、取整）Low 指示查找區(qū)間的下界high 指示查找區(qū)間的上界,low,high,第 19 頁(yè),查找成功的例子,,-1 0 1 3 4 6 8 10 12,,,,,,,,,6,0 1 2 3 4 5 6 7 8,搜索,,,,low,mid,high,6,,6 8 10 12,,,,5 6

12、 7 8,,,,low,mid,high,6,6,5,low,mid,high,,,,6,(1) low=0,high=8,mid=4;由于Elem[mid]Key, 因此, high=mid-1=5;(3)mid=5, Elem[mid] =Key,因此查找成功.,第 20 頁(yè),查找失敗的例子,,-1 0 1 3 4 6 8 10 12,,,,,,,,,5,0

13、 1 2 3 4 5 6 7 8,搜索,,,,low,mid,high,5,,6 8 10 12,,,,5 6 7 8,,,,low,mid,high,6,5,5,low,mid,high,,,,5,(1) low=0,high=8,mid=4;由于Elem[mid]Key, 因此, high=mid-1=5;(3)mid=5,由于Ele

14、m[mid] >Key,因此, high=mid-1=4. 由于此時(shí)high<low,因此查找失敗.,第 21 頁(yè),折半查找算法實(shí)現(xiàn)int Search_Bin(TB SL, TYPE key) { int low = 1, high = SL.length,mid; while(lowSL.elem[mid].key)low=mid+1; } return 0;},折半查找算法總結(jié)平均查找長(zhǎng)度：

15、查找成功: 時(shí)間復(fù)雜度: O(log2n)優(yōu)點(diǎn)：查找效率高；缺點(diǎn)：查找結(jié)構(gòu)有限制；插入、刪除操作困難。適用場(chǎng)合：記錄按關(guān)鍵字值有序排列，查找結(jié)構(gòu)為順序表結(jié)構(gòu)，數(shù)據(jù)不經(jīng)常變動(dòng)（靜態(tài)查找）。,第 22 頁(yè),第 23 頁(yè),若要對(duì)動(dòng)態(tài)查找表進(jìn)行高效率的查找操作（包含可能的數(shù)據(jù)刪除或插入操作），可采用二叉排序樹作為查找表的組織形式。,1.3 二叉排序樹查找,第 24 頁(yè),（1）若它的左子樹不空，則左子樹上

16、所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；,二叉排序樹（或二叉查找樹）或者是一棵空樹；或者是具有如下特性的二叉樹：,（3）它的左、右子樹也都分別是二叉 排序樹。,（2）若它的右子樹不空，則右子樹上 所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；,二叉排序樹的概念,第 25 頁(yè),50,30,80,20,90,10,85,40,35,25,23,88,,,,,,,,,,,,是二叉排序樹,,45,第 26 頁(yè),50,30,80,2

17、0,90,10,85,40,35,25,23,88,,,,,,,,,,,,不是二叉排序樹,,66,第 27 頁(yè),50,30,80,20,90,10,85,40,42,25,23,88,,,,,,,,,,,,也 是二叉排序樹,,46,不,第 28 頁(yè),輸入數(shù)據(jù) { 53, 78, 65, 17, 87, 09, 81, 15 },根據(jù)輸入序列構(gòu)造二叉排序樹,第 29 頁(yè),注意：同樣 n個(gè)數(shù)據(jù){ 1, 2, …, n }，輸入順

18、序不同，建立的二叉排序樹形態(tài)也不同。例如，,{1,2,3},{1,3,2},{2,1,3},{3,2,1},{3,1,2},第 30 頁(yè),如果對(duì)一棵二叉排序樹進(jìn)行中序遍歷，其遍歷序列是將樹中的各結(jié)點(diǎn)關(guān)鍵字按從小到大的順序排列起來(lái)。,二叉排序樹與中序遍歷,第 31 頁(yè),1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字， 則查找成功; 2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字， 則繼續(xù)在左子樹上進(jìn)行查找;

19、 3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字， 則繼續(xù)在右子樹上進(jìn)行查找;,若二叉排序樹為空，則查找不成功;否則：,二叉排序樹的查找算法,第 32 頁(yè),在查找過(guò)程中，生成了一條查找路徑。,從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn)。,或者,從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。,——查找成功,——查找不成功,查找40查找成功,查找28查找失敗,第 33 頁(yè),50,30,8

20、0,20,90,85,40,35,88,,,,,,,,,32,,,查找關(guān)鍵字,50,50,50,,,,30,40,35,50,,,50,80,90,,,,root,二叉排序樹結(jié)點(diǎn)的刪除，相當(dāng)于刪去有序序列上的一個(gè)記錄，應(yīng)保證刪除結(jié)點(diǎn)后，二叉排序樹的特性不變。刪除結(jié)點(diǎn)可有三種情況：1.若刪除結(jié)點(diǎn)為葉子結(jié)點(diǎn)，即其左子樹和右子樹均為空樹。由于葉子結(jié)點(diǎn)的存在若不破壞整株樹的結(jié)構(gòu)，則只需修改其父結(jié)點(diǎn)的指針即可。2.若刪除結(jié)點(diǎn)只有左子樹或只有

21、右子樹，此時(shí)只要令左子樹或右子樹的根結(jié)點(diǎn)直接代替被,二叉排序樹結(jié)點(diǎn)的刪除,刪除結(jié)點(diǎn)即可，也不破壞二叉排序樹的特性。3.若刪除結(jié)點(diǎn)的左、右子樹均不空，不能簡(jiǎn)單處理，可有兩種情況。例：,F,P,,f,,,p,,,pL,pR,(a),,f,F,P,C,,p,,,,c,,CL,,Q,,,PR,,q,S,,QL,,,SL,,S,,F,C,,,c,,CL,,S,,,,,,S,f,SL,PR,,,,,(b),(c),方法1: 將刪除結(jié)點(diǎn)的右子樹,

22、作為刪除結(jié)點(diǎn)的左子樹的最右結(jié)點(diǎn)的右子樹.,f,F,S,C,,p,,,,c,,CL,,Q,,,PR,,q,,QL,,SL,,(d),方法2: 用刪除結(jié)點(diǎn)的左子樹的最右結(jié)點(diǎn)代替刪除結(jié)點(diǎn),同時(shí)用刪除結(jié)點(diǎn)的左子樹的最右結(jié)點(diǎn)的左子樹(如果有)代替該結(jié)點(diǎn).(左子樹最大結(jié)點(diǎn)取代,也可以右子樹最小結(jié)點(diǎn)取代),第 38 頁(yè),二叉排序樹查找性能分析,對(duì)于每一棵特定的二叉排序樹，均可按照平均查找長(zhǎng)度的定義來(lái)求它的 ASL 值。但是，由值相同的 n個(gè)關(guān)鍵字，

23、構(gòu)造得到的不同形態(tài)的各棵二叉排序樹的平均查找長(zhǎng)度的值可能不同，甚至可能差別很大。,由關(guān)鍵字序列{ 3，1，2，5，4}構(gòu)造而得的二叉排序樹:,由關(guān)鍵字序列 {1，2，3，4，5}構(gòu)造而得的二叉排序樹:,ASL =（1+2+3+4+5）/ 5 = 3,ASL =（1+2+3+2+3）/ 5 = 2.2,第 39 頁(yè),二叉排序樹總結(jié),就平均查找性能而言，二叉排序樹查找和折半查找相差不大； 就維護(hù)表的有序性而言，二叉排序樹更為有效（二叉排序

24、樹的結(jié)點(diǎn)插入、刪除方便，無(wú)需移動(dòng)大量結(jié)點(diǎn)）。因此，適用于動(dòng)態(tài)查找環(huán)境。,,,,D,,,,,G,,E,D,,,,A,B,C,F,E,G,B,A,,起因：提高查找速度，避免最壞情況出現(xiàn)。如右圖情況的出現(xiàn)。,C,F,平衡因子（平衡度）：結(jié)點(diǎn)的平衡度是結(jié)點(diǎn)的左子樹的高度－右子樹的高度。 平衡二叉樹：每個(gè)結(jié)點(diǎn)的平衡因子都為 ＋1、－1、0 的二叉樹?；蛘哒f(shuō)每個(gè)結(jié)點(diǎn)的左右子樹的高度最多差一的二叉樹。,平衡二叉樹,平衡二叉排序樹——AV樹,定義：

25、 一棵平衡二叉排序樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：1、左子樹與右子樹的高度之差的絕對(duì)值小于等于1；2、左子樹和右子樹也是平衡二叉排序樹。平衡二叉排序樹的平均查找長(zhǎng)度為O（log2n）。平衡因子：結(jié)點(diǎn)的左子樹深度與右子樹深度之差：-1，0，1。,是平衡樹 不是平衡樹,,,以插入

26、為例： 在左圖所示的平衡樹中插入數(shù)據(jù)為 2 的結(jié)點(diǎn)。 插入之后仍應(yīng)保持平衡分類二叉樹的性質(zhì)不變。,,,,,,,,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,,,,,,,,原平衡度為 0,危機(jī)結(jié)點(diǎn),如何用最簡(jiǎn)單、最有效的辦法保持平衡分類二叉樹的性質(zhì)不變？,,解決方案：不涉及到危機(jī)結(jié)點(diǎn)的父親結(jié)點(diǎn)，即以危機(jī)結(jié)點(diǎn)為

27、根的子樹的高度應(yīng)保持不變（圖為 3 ）。新結(jié)點(diǎn)插入后，找到第一個(gè)平衡度不為 0 的結(jié)點(diǎn)（如左圖結(jié)點(diǎn) 9）即可。新插入的結(jié)點(diǎn)和第一個(gè)平衡度不為 0 的結(jié)點(diǎn)（也可能是危機(jī)結(jié)點(diǎn)）之間的結(jié)點(diǎn)，其平衡度皆為 0。在調(diào)整中，僅調(diào)整那些在平衡度變化的路徑上的結(jié)點(diǎn)（如：3 5 9），其它結(jié)點(diǎn)不予調(diào)整。仍應(yīng)保持二叉排序樹的性質(zhì)不變。,,,,,,,,,,,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,

28、-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,,,,,,,,原平衡度為 0,危機(jī)結(jié)點(diǎn),關(guān)鍵：將導(dǎo)致出現(xiàn)危機(jī)結(jié)點(diǎn)的情況全部分析清楚，就可以使得平衡分類二叉樹的性質(zhì)保持不變！！,,,,,,,,14,9,3,2,5,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,12,0,0,最低層失衡結(jié)點(diǎn)為A，在結(jié)點(diǎn)A的左子樹的左子樹上插入新結(jié)點(diǎn)S后，導(dǎo)致失衡，由A和B的平

29、衡因子可知，BL、BR和AR深度相同，為恢復(fù)平衡并保持二叉排序樹的特性，可將A改為B的右子，B原來(lái)的右子BR改為A的左子，這相當(dāng)于以B為軸，對(duì)A做了一次順時(shí)針旋轉(zhuǎn)。,不平衡二叉排序樹的調(diào)整——LL型,不平衡二叉排序樹的調(diào)整——LL型,A->lchild=B->rchild B->rchild=A,最低層失衡結(jié)點(diǎn)為A，在結(jié)點(diǎn)A的左子樹的右子樹上插入新結(jié)點(diǎn)S后，導(dǎo)致失衡，假設(shè)在CL下插入S，由A、B、C的平衡因子可知，C

30、L與CR深度相同，BL與AR深度相同，且BL、AR的深度比CL、CR的深度大1；為恢復(fù)平衡并保持二叉排序樹的特性，可將B改為C的左子，而C原來(lái)的左子CL改為B的右子，然后將A改為C的右子，C原來(lái)的右子CR改為A的左子；這相當(dāng)于以B為軸，對(duì)A做了一次順時(shí)針旋轉(zhuǎn)。,不平衡二叉排序樹的調(diào)整——LR型,不平衡二叉排序樹的調(diào)整——LR型,A,B,C,C,A,B,A->lchild=c->rchild B->rchild=c-&

31、gt;lchildc->rchild=Ac->lchild=B,最低層失衡結(jié)點(diǎn)為A，在結(jié)點(diǎn)A的右子樹的右子樹上插入新結(jié)點(diǎn)S后，導(dǎo)致失衡，由A和B的平衡因子可知，BL、BR和AL深度相同，為恢復(fù)平衡并保持二叉排序樹的特性，可將A改為B的左子，B原來(lái)的左子BL改為A的右子，這相當(dāng)于以B為軸，對(duì)A做了一次逆時(shí)針旋轉(zhuǎn)。,不平衡二叉排序樹的調(diào)整——RR型,不平衡二叉排序樹的調(diào)整——RR型,A->rchild=B->lc

32、hild B->lchild=A,最低層失衡結(jié)點(diǎn)為A，在結(jié)點(diǎn)A的右子樹的左子樹上插入新結(jié)點(diǎn)S后，導(dǎo)致失衡，假設(shè)在CR下插入S，由A、B、C的平衡因子可知，CL與CR深度相同，AL與BR深度相同，且AL、BR的深度比CL、CR的深度大1；為恢復(fù)平衡并保持二叉排序樹的特性，可將B改為C的右子，而C原來(lái)的右子CR改為B的左子，然后將A改為C的左子，C原來(lái)的左子CL改為A的右子；這相當(dāng)于以B為軸，對(duì)A做了一次順時(shí)針旋轉(zhuǎn)。,不平衡二叉排序

33、樹的調(diào)整——RL型,不平衡二叉排序樹的調(diào)整——RL型,A,B,C,A->rchild=c->lchild B->lchild=c->rchildc->lchild=Ac->rchild=B,,,,,,,,,,,,,,,,,,,1、引入大量數(shù)據(jù)存放在外存中，通常存放在硬盤中。由于是海量數(shù)據(jù)，不可能一次調(diào)入內(nèi)存。因此，要多次訪問(wèn)外存。但硬盤的驅(qū)動(dòng)受機(jī)械運(yùn)動(dòng)的制約，速度慢。所以，主要矛盾變?yōu)闇p少訪

34、外次數(shù)。在 1970 年由 R bayer 和 E macreight 提出用B_ 樹作為索引組織文件。提高訪問(wèn)速度、減少時(shí)間。,,,,,,,,,內(nèi)存,,,用二叉樹組織文件，當(dāng)文件的記錄個(gè)數(shù)為 100，000時(shí)，要找到給定關(guān)鍵字的記錄，需訪問(wèn)外存17次（log100,000）,太長(zhǎng)了！,,,,,,,,50,25,10,75,,,15,35,60,90,,,20,,,30,,40,,55,,70,,80,,95,,,,,,,,索引

35、文件,數(shù)據(jù)文件,文件頭，可常駐內(nèi)存,,文件訪問(wèn)示意圖：索引文件、數(shù)據(jù)文件存在盤上,B_ 樹,m 階 B_ 樹的 定義,定義：一棵m階的B-樹，或者為空樹，或?yàn)闈M足下列特性的m叉樹： ⑴樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹； ⑵若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹； ⑶除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有?m/2? 棵子樹； ⑷所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù)：（n，A0，K1，A1，K2，…，Kn，An）其中：Ki（i=1,2

36、,…,n）為關(guān)鍵碼，且Ki<Ki+1，Ai為指向子樹根結(jié)點(diǎn)的指針(i=0,1,…,n)，且指針Ai-1所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均小于Ki (i=1,2,…,n)，An所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均大于Kn， ?m/2? ?1≤n≤m ?1 ，n為關(guān)鍵碼的個(gè)數(shù)。 ⑸所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。,,例如：m = 4 階 B_

37、樹。除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù)至少為 m/2 = 2 個(gè)；結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)至少為 1 。該 B_ 樹的深度為 4。葉子結(jié)點(diǎn)都在第 4 層上。,1，99,3，47，58，64,1，39,1，27,1，11,2，43，78,1，18,1，35,,,,,,,,第 1 層,第 2 層,第 3 層(L層),第 4 層(L＋1層),一棵5階的B-樹，其深度為4,B樹(續(xù)),B樹的查找 1、首先找到根結(jié)點(diǎn),與根結(jié)

38、點(diǎn)各鍵值進(jìn)行比較，如果 KxKi+1則查找Pi+1指向的結(jié)點(diǎn)；如果Ki <Kx<Ki+1則查找Pi指向的結(jié)點(diǎn)。 2、如果順著某個(gè)指針往下找時(shí)遇到樹葉，則說(shuō)明Kx不在B樹中，即查找失敗。 3、在下一個(gè)結(jié)點(diǎn)查找時(shí)，重復(fù)1,B樹(續(xù)),在往m階B樹中插入一個(gè)關(guān)鍵字（key）時(shí)，不是在樹中添加一個(gè)樹葉，而是首先在最底層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字，若插入后該結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目不超過(guò)m-1,則插入完畢；否則要

39、進(jìn)行分裂結(jié)點(diǎn)操作，并且這個(gè)分裂過(guò)程可能會(huì)一直波及到根結(jié)點(diǎn)。設(shè)某個(gè)結(jié)點(diǎn)已有m-1個(gè)關(guān)鍵字，那么，在插入一個(gè)關(guān)鍵字后，該結(jié)點(diǎn)將分裂成兩個(gè)結(jié)點(diǎn)：左邊一個(gè)結(jié)點(diǎn)包含前 個(gè)關(guān)鍵字，右邊一個(gè)結(jié)點(diǎn)包含后m-[m/2]個(gè)關(guān)鍵字，而第[m/2]個(gè)關(guān)鍵字被插入到上一級(jí)（雙親）結(jié)點(diǎn)中。,B樹的插入,階為7的B樹一般來(lái)說(shuō),要把一個(gè)新項(xiàng)目插入到階為m的B樹中處,當(dāng)所有葉都在l級(jí)上,則把新的鍵插入到l-1,如果該結(jié)點(diǎn)現(xiàn)在含有m個(gè)鍵,則把它

40、分為兩個(gè)結(jié)點(diǎn),并且把鍵K [m/2]插入到原來(lái)結(jié)點(diǎn)的父親處(于是,父親處結(jié)點(diǎn)的指針p為序列P, K [m/2],P`所替代).如果需要分裂根結(jié)點(diǎn),根結(jié)點(diǎn)是沒(méi)有父親的,則只需建立包含單個(gè)鍵K [m/2]的一個(gè)新根結(jié)點(diǎn)和兩個(gè)指針,這樣樹就長(zhǎng)高了一級(jí).,B樹(續(xù)),B樹的刪除1、如果要?jiǎng)h除的關(guān)鍵字不在最下面一層的非終端結(jié)點(diǎn)中，則可先把待刪關(guān)鍵字與它在B樹中的后繼對(duì)換位置，然后刪除關(guān)鍵字2、如果要?jiǎng)h除的關(guān)鍵字在最下面一層的非終端結(jié)點(diǎn)中，則把

41、它從所在的結(jié)點(diǎn)中刪除時(shí)，可能會(huì)導(dǎo)致此結(jié)點(diǎn)中關(guān)鍵字少于 (即它的孩子結(jié)點(diǎn)少于[m/2]個(gè))因此，需要進(jìn)行結(jié)點(diǎn)的合并操作。結(jié)點(diǎn)的合并操作可以根據(jù)以下兩種情況分別進(jìn)行。,(1)若被刪出關(guān)鍵字所在結(jié)點(diǎn)中正好有 個(gè)關(guān)鍵字而與該結(jié)點(diǎn)相鄰的左兄弟（或右兄弟）結(jié)點(diǎn)中的關(guān)鍵字多于 個(gè)則可將其兄弟結(jié)點(diǎn)中最大（或最?。┑年P(guān)鍵字移到雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中該上移關(guān)鍵字的后面一個(gè)

42、（或前面一個(gè)）關(guān)鍵字下移到被刪除關(guān)鍵字所在的結(jié)點(diǎn)中。(2)若被刪除關(guān)鍵字所在的結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字都是 個(gè)，則可將刪除了關(guān)鍵字的結(jié)點(diǎn)和它的雙親結(jié)點(diǎn)的一個(gè)關(guān)鍵字合并到它的兄弟結(jié)點(diǎn)中。如果因此使雙親結(jié)點(diǎn)中的關(guān)鍵字少于 個(gè)，則需要繼續(xù)進(jìn)行合并。,1.4 哈希表技術(shù),以上討論的表示查找表的各種結(jié)構(gòu)的共同特點(diǎn)：記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系，查找的過(guò)程為給

43、定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字進(jìn)行比較，查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。用這類方法表示的查找表，其平均查找長(zhǎng)度都不為零。,65,問(wèn)題：對(duì)于頻繁使用的查找，我們希望平均查找長(zhǎng)度ASL接近于0,預(yù)先知道所查關(guān)鍵字在表中的位置記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系,只有一個(gè)辦法,,66,例如：為每年招收的 1000 名新生建立一張查找表，其關(guān)鍵字為學(xué)號(hào)，其值的范圍為 xx000 ~ xx999 (前兩位為年份)

44、。若以下標(biāo)為000 ~ 999 的順序表表示學(xué)號(hào)查找過(guò)程可以簡(jiǎn)單進(jìn)行：取給定值（學(xué)號(hào)）的后三位，不需要經(jīng)過(guò)比較便可直接從順序表中找到待查關(guān)鍵字。,67,哈希查找的基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系；這樣，不經(jīng)過(guò)比較，一次存取就能得到所查元素的查找方法哈希函數(shù)：在記錄的關(guān)鍵字與記錄在表中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系，以 f(key) 作為關(guān)鍵字為 key 的記錄在表中的位置，通常稱這個(gè)函數(shù) f(k

45、ey) 為哈希函數(shù)。哈希地址：由哈希函數(shù)求出的記錄存儲(chǔ)位置稱為哈希地址，表示成：addr(ai)=f(ki)ai是表中的一個(gè)元素(記錄)addr(ai)是ai的存儲(chǔ)地址ki是ai的關(guān)鍵字,68,哈希表：應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫哈希表，也叫散列表。哈希查找：又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過(guò)程叫~,69,{Zhao, Qian, Sun, Li, Wu, Chen,

46、 Han, Ye, Dai},例：對(duì)于如下 9 個(gè)關(guān)鍵字,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dai,問(wèn)題: 若添加關(guān)鍵字 Zhou , 怎么辦？,能否找到另一個(gè)哈希函數(shù)？,設(shè) 哈希函數(shù) f(key) = ?(ASC(關(guān)鍵字第一個(gè)字母) -ASC('A')+1)/2?,70,哈希函數(shù)是一個(gè)映象，即 將關(guān)鍵字的集合映射到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè)地址集合的 大小不超出允許范圍

47、即可；由于哈希函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即： key1 key2，而 f(key1) = f(key2)很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。在構(gòu)造哈希表時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種處理沖突 的方法。,71,構(gòu)造哈希函數(shù)的幾種方法,對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法,若是非數(shù)字關(guān)鍵字，則

48、需先對(duì)其進(jìn)行數(shù)字化處理,1. 直接定址法,3. 平方取中法,5. 除留余數(shù)法,4. 折疊法,6. 隨機(jī)數(shù)法,2. 數(shù)字分析法,72,(1) 直接定址法,構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希函數(shù)　 　　　 H(key) = key 或者 　　H(key) = a. key + b特點(diǎn)直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會(huì)發(fā)生沖突實(shí)際中能用這種哈希函數(shù)的情況很少,73,(2) 數(shù)字分析法,構(gòu)造：對(duì)關(guān)鍵字進(jìn)行

49、分析，取關(guān)鍵字的若干位或其組合作哈希地址特點(diǎn)：適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況,74,(3) 平方取中法,構(gòu)造：以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值” 的目的是“擴(kuò)大差別” ，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。特點(diǎn)：關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。,75,(4) 折疊法,構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）

50、做哈希地址種類移位疊加：將分割后的幾部分低位對(duì)齊相加間界疊加：從一端沿分割界來(lái)回折送，然后對(duì)齊相加特點(diǎn)：適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況,76,例 關(guān)鍵字為 ：0442205864，哈希地址位數(shù)為4,77,(5) 除留余數(shù)法,構(gòu)造：取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)作哈希地址，即 H(key)=key % p p<=m 且P 一般應(yīng)為接近 m 的素?cái)?shù)或是不含20 以下的質(zhì)

51、因子特點(diǎn)簡(jiǎn)單、常用: 可與上述幾種方法結(jié)合使用p的選取很重要: p選的不好，容易產(chǎn)生同義詞,對(duì)P要加一定的限制,78,給定一組關(guān)鍵字為：12, 39, 18, 24, 33, 21 假定hash表的長(zhǎng)度為12若取 p=9, 則他們對(duì)應(yīng)的哈希函數(shù)值將為： 3, 3, 0, 6, 6, 3,例如：,為什么要對(duì) p 加限制？,若 p 中含質(zhì)因子 3， 則所有含質(zhì)因子 3 的關(guān)鍵字均映射到“3 的倍數(shù)”的地址上，從

52、而增加了“沖突”的可能。,79,(6) 隨機(jī)數(shù)法,構(gòu)造：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址　　　H(key)=random(key)適于關(guān)鍵字長(zhǎng)度不等的情況,實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。,80,例 有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù),?? ? ??? ??,,,分析： ?只取8

53、 ?只取1 ?只取3、4 ?只取2、7、5 ????數(shù)字分布近乎隨機(jī)所以：取????任意兩位或兩位 與另兩位的疊加作哈希地址,81,處理沖突的方法,處理沖突 ：為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。主要有二種方法開放定址法鏈地址法,82,思想：為產(chǎn)生沖突的關(guān)鍵字尋找一個(gè)新的地址 Hi(key)， 求得一個(gè)地址序列： H0,

54、H1, H2, …, Hs 1≤ s≤m-1 其中：H0 = H(key) H1 = (H(key) + d1 ) % m H2 = (H(key) + d2 ) % m …… Hi = ( H(key) + di ) % m i=1, 2, …, s,(1) 開放定址法,83,對(duì)

55、增量 di 有三種取法線性探測(cè)再散列：di=1,2,3,……m-1二次探測(cè)再散列：di=1²,-1²,2²,-2²,3²,…,±k²偽隨機(jī)探測(cè)再散列：di=偽隨機(jī)數(shù)序列注意：增量 di 應(yīng)具有“完備性”,即：產(chǎn)生的 Hi 均不相同，且所產(chǎn)生的 s個(gè) Hi 值能覆蓋哈希表中所有地址。要求： 平方探測(cè)時(shí)的表長(zhǎng) m 必為形如 4j+3 的素?cái)?shù)（如: 7,

56、11, 19, 23, … 等）；隨機(jī)探測(cè)時(shí)的 m 和 di 沒(méi)有公因子。,84,例 表長(zhǎng)為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄， H(key)=key % 11,現(xiàn)有第4個(gè)記錄，其關(guān)鍵字為38， 按三種處理沖突的方法，將它填入表中,(1) H(38)=38 % 11=5 沖突 H1=(5+1) % 11=6 沖突 H2=(5+2) % 11=7

57、 沖突 H3=(5+3) % 11=8 不沖突,38,(2) H(38)=38 % 11=5 沖突 H1=(5+1²) % 11=6 沖突 H2=(5-1²) % 11=4 不沖突,38,(3) H(38)=38 % 11=5 沖突 設(shè)偽隨機(jī)數(shù)序列為9，則： H1=(5+9) % 11=3 不

58、沖突,38,線性探測(cè),二次探測(cè),隨機(jī)探測(cè),將所有哈希地址相同的記錄都鏈接在同一鏈表中 例：關(guān)鍵字集合 { 19, 01, 23, 14, 55, 68,11, 82, 36 }哈希函數(shù)為：　 H(key)=key % 7,(2) 鏈地址法,,,,,,,,0123456,14,,01,,36,,,,,,19,,,,82,,,,,,,,,,,,,23,11,68,55,?,?,?,?,?,?,?,86,哈希表的查找及

59、其性能分析,查找過(guò)程：和造表過(guò)程一致，對(duì)于給定值，由哈希函數(shù)和解決沖突的方法定位記錄的存儲(chǔ)位置。,87,例：給出哈希表HT，哈希函數(shù) H(key)=key % 11,解決沖突方法：開放地址法中線性探測(cè)再散列Hi(key)=(H(KEY)+di)% 11 (d1=1, d2=2, d3=3,… ),試查找關(guān)鍵字19 、02,查找關(guān)鍵字19,,用哈希函數(shù)求19 對(duì)應(yīng)的哈希地址：H(19)=19 % 11=8,將HT[8]與19比較相等查

60、找成功,88,查找關(guān)鍵字02,用哈希函數(shù)求02 對(duì)應(yīng)的哈希地址：H(02)=02 % 11=2,將HT[2]與02比較不相等,用解決沖突方法為02求下一個(gè)“地址” （取d1=1） H1 (02)=(H(02)+ d1)% 11=3,將HT[3]與02比較相等查找成功,89,查找算法實(shí)現(xiàn)：開放定址哈希表,int hashsize[] = { 997, ... }; typedef struct { ElemType *el

61、em; int count; // 當(dāng)前數(shù)據(jù)元素個(gè)數(shù) int sizeindex; // hashsize[sizeindex]為當(dāng)前容量} HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1,90,bool SearchHash (HashTable H, KeyType K,

62、 int &p, int &c) { // 在開放定址哈希表H中查找關(guān)鍵碼為K的記錄} // SearchHash,p = Hash(K); // 求得哈希地址,while (H.elem[p].key != NULLKEY &&

63、 (K!= H.elem[p].key)) collision(p, ++c); // 求得下一探查地址 p,if (K==H.elem[p].key) return 1; // 查找成功，返回待查數(shù)據(jù)元素位置 p,else return 0; // 查找不成功,91,bool InsertHash (HashTable &H, Elemt

64、ype e){ },Int c = 0;,if ( HashSearch ( H, e.key, p, c ) == SUCCESS ) return DUPLICATE; // 表中已有與 e 有相同關(guān)鍵字的元素,else H.elem[p] = e; ++H.count; return OK; // 查找不成功時(shí)，返回

65、p為插入位置,else RecreateHashTable(H); // 重建哈希表,if ( c < hashsize[H.sizeindex]/2 ) { // 沖突次數(shù) c 未達(dá)到上限，（閥值 c 可調(diào)） },92,哈希表查找分析從查找過(guò)程得知，哈希表查找的平均查找長(zhǎng)度實(shí)際上并不等于零。,決定哈希表查找的ASL的因素：　(1) 選用的哈希函數(shù)；

66、 (2) 選用的處理沖突的方法； (3) 哈希表飽和的程度，裝載因子 α=n/m 值的大?。╪—記錄數(shù)，m—表的長(zhǎng)度）,93,一般情況下，可以認(rèn)為選用的哈希函數(shù)是“均勻”的，則在討論ASL時(shí)，可以不考慮它的因素。因此，哈希表的ASL是處理沖突方法和裝載因子的函數(shù)。例: 關(guān)鍵字集合 　{ 7, 15, 20, 31, 48, 53,64, 76, 82, 99 },線性探測(cè)處理沖突時(shí)， ASL

67、=,平方探測(cè)處理沖突時(shí)，　ASL =,鏈地址法處理沖突時(shí)， ASL =,2.4,2.0,1.7,94,線性探測(cè)再散列,鏈地址法,二次探測(cè)或隨機(jī)探測(cè)再散列,可以證明：查找成功時(shí)有下列結(jié)果：,95,從以上結(jié)果可見(jiàn)：,哈希表的平均查找長(zhǎng)度是 ? 的函數(shù)，而不是 n 的函數(shù)。,這說(shuō)明，用哈希表構(gòu)造查找表時(shí)，可以選擇一個(gè)適當(dāng)?shù)难b填因子 ? ，使得平均查找長(zhǎng)度限定在某個(gè)范圍內(nèi)。,—— 這是哈希表所特有的特點(diǎn)。,2 Sort(排序),第 9

68、6 頁(yè),第 97 頁(yè),什么是排序？,排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的記錄序列調(diào)整為“有序”的記錄序列。,例如：將下列關(guān)鍵字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,調(diào)整為,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,第 98 頁(yè),一般情況下，假設(shè)含n個(gè)記錄的序列為{ R1, R2, …， Rn }其相應(yīng)的關(guān)鍵字序列為 { K1,