專題三數(shù)據(jù)結構與算法

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

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

3、不唯一。,第 5 頁,實施查找時有兩種不同的環(huán)境靜態(tài)環(huán)境 查找結構不需進行插入和刪除操作。 ? 靜態(tài)查找表,第 6 頁,動態(tài)環(huán)境 查找過程中可能要對查找結構執(zhí)行數(shù)據(jù)插入、刪除或修改等操作，并對查找結構進行調整，結構可能發(fā)生變化。 ? 動態(tài)查找表動態(tài)查找表的表結構是在查找過程中動態(tài)生成的。,第 7 頁,以線性結構表示靜態(tài)查找表。基本原理：將待查找記錄依次逐個與表中記錄進行比較。,1.1 順序查找（Sequ

4、ential Search),第 8 頁,SL.elem,,,順序查找過程（從前向后查找）,假設給定查找值 e=64,要求 SL.elem[k] = e, 問: k = ?,k,k,第 9 頁,SL.elem,,,i,SL.elem,,,i,60,i,key=64,key=60,i,64,順序查找過程（從后向前查找）,0單元用于存放待查找關鍵字，作為“哨兵”(guard),返回0,返回7,第 10 頁,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; // 查找成功時i為有效下標,否則i為0},順序查找算法實現(xiàn)（從后向前查找）,第 11 頁,查

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

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

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

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

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

11、取整）Low 指示查找區(qū)間的下界high 指示查找區(qū)間的上界,low,high,第 19 頁,查找成功的例子,,-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 頁,查找失敗的例子,,-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. 由于此時high<low,因此查找失敗.,第 21 頁,折半查找算法實現(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;},折半查找算法總結平均查找長度：

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

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

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

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

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

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

21、右子樹，此時只要令左子樹或右子樹的根結點直接代替被,二叉排序樹結點的刪除,刪除結點即可，也不破壞二叉排序樹的特性。3.若刪除結點的左、右子樹均不空，不能簡單處理，可有兩種情況。例：,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: 將刪除結點的右子樹,

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

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

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

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

26、為例： 在左圖所示的平衡樹中插入數(shù)據(jù)為 2 的結點。 插入之后仍應保持平衡分類二叉樹的性質不變。,,,,,,,,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,危機結點,如何用最簡單、最有效的辦法保持平衡分類二叉樹的性質不變？,,解決方案：不涉及到危機結點的父親結點，即以危機結點為

27、根的子樹的高度應保持不變（圖為 3 ）。新結點插入后，找到第一個平衡度不為 0 的結點（如左圖結點 9）即可。新插入的結點和第一個平衡度不為 0 的結點（也可能是危機結點）之間的結點，其平衡度皆為 0。在調整中，僅調整那些在平衡度變化的路徑上的結點（如：3 5 9），其它結點不予調整。仍應保持二叉排序樹的性質不變。,,,,,,,,,,,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,危機結點,關鍵：將導致出現(xiàn)危機結點的情況全部分析清楚，就可以使得平衡分類二叉樹的性質保持不變??！,,,,,,,,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,最低層失衡結點為A，在結點A的左子樹的左子樹上插入新結點S后，導致失衡，由A和B的平

29、衡因子可知，BL、BR和AR深度相同，為恢復平衡并保持二叉排序樹的特性，可將A改為B的右子，B原來的右子BR改為A的左子，這相當于以B為軸，對A做了一次順時針旋轉。,不平衡二叉排序樹的調整——LL型,不平衡二叉排序樹的調整——LL型,A->lchild=B->rchild B->rchild=A,最低層失衡結點為A，在結點A的左子樹的右子樹上插入新結點S后，導致失衡，假設在CL下插入S，由A、B、C的平衡因子可知，C

30、L與CR深度相同，BL與AR深度相同，且BL、AR的深度比CL、CR的深度大1；為恢復平衡并保持二叉排序樹的特性，可將B改為C的左子，而C原來的左子CL改為B的右子，然后將A改為C的右子，C原來的右子CR改為A的左子；這相當于以B為軸，對A做了一次順時針旋轉。,不平衡二叉排序樹的調整——LR型,不平衡二叉排序樹的調整——LR型,A,B,C,C,A,B,A->lchild=c->rchild B->rchild=c-&

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

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

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

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

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

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

37、樹。除根結點和葉子結點之外，每個結點的兒子個數(shù)至少為 m/2 = 2 個；結點的關鍵字個數(shù)至少為 1 。該 B_ 樹的深度為 4。葉子結點都在第 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、首先找到根結點,與根結

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

56、11, 19, 23, … 等）；隨機探測時的 m 和 di 沒有公因子。,84,例 表長為11的哈希表中已填有關鍵字為17，60，29的記錄， H(key)=key % 11,現(xiàn)有第4個記錄，其關鍵字為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ù)序列為9，則： H1=(5+9) % 11=3 不

58、沖突,38,線性探測,二次探測,隨機探測,將所有哈希地址相同的記錄都鏈接在同一鏈表中 例：關鍵字集合 { 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、其性能分析,查找過程：和造表過程一致，對于給定值，由哈希函數(shù)和解決沖突的方法定位記錄的存儲位置。,87,例：給出哈希表HT，哈希函數(shù) H(key)=key % 11,解決沖突方法：開放地址法中線性探測再散列Hi(key)=(H(KEY)+di)% 11 (d1=1, d2=2, d3=3,… ),試查找關鍵字19 、02,查找關鍵字19,,用哈希函數(shù)求19 對應的哈希地址：H(19)=19 % 11=8,將HT[8]與19比較相等查

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

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

62、 int &p, int &c) { // 在開放定址哈希表H中查找關鍵碼為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 有相同關鍵字的元素,else H.elem[p] = e; ++H.count; return OK; // 查找不成功時，返回

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

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

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

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