數(shù)據(jù)結(jié)構(gòu)與算法分析(C++版)課件下ppt.ppt

1、,數(shù)據(jù)結(jié)構(gòu)與算法分析(C+版)課件下,第8講 查找 第9講 排序 第10講 文件 第11講 算法設(shè)計與分析,第8章 查找,所謂查找，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對象 1.查找成功 即找到滿足條件的數(shù)據(jù) 對象這時, 作為結(jié)果, 可報告該對 象在結(jié)構(gòu)中的位置, 還可給出該對 象中的具體信息 2.查找不成功 或查找失敗。作為結(jié) 果, 應(yīng)報告一些信息, 如失敗標 志、位置等,通常稱用于查找的數(shù)據(jù)集合為查找結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對象(或記錄)組成 在每個對象中有若干屬性，其中有一個屬性，其值可唯一地標識這個對象。稱為關(guān)鍵碼。使用基于關(guān)鍵碼的查找，查找結(jié)果應(yīng)是唯一的。但在實際應(yīng)用時，查找條件

2、是多方面的，可以使用基于屬性的查找方法，但查找結(jié)果可能不唯一,實施查找時有兩種不同的環(huán)境 靜態(tài)環(huán)境 查找結(jié)構(gòu)不用插入和刪除操作 靜態(tài)查找表,動態(tài)環(huán)境 為保持較高的查找效率, 查找結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動進行調(diào)整，結(jié)構(gòu)可能發(fā)生變化 動態(tài)查找表,查找算法的評價指標 查找成功:最少比較次數(shù) 最多比較次數(shù) 平均比較次數(shù) 查找失敗:最少比較次數(shù) 最多比較次數(shù) 平均比較次數(shù),以順序表或線性鏈表表示靜態(tài)查找表,順序查找,elem,順序查找過程,假設(shè)給定值 e=64, 要求 ST.elemk = e, 問: k = ?,k,k,template int SqSerach(ElemType ele

3、m, int n, KeyType key) / 操作結(jié)果: 在順序表中查找關(guān)鍵字的值等于key的記錄, /如查找成功,則返回此記錄的序號,否則返回-1 int i;/ 臨時變量 for (i = 0; i n ,上述順序查找表的查找算法簡單，但平均查找長度較大，特別不 適用于表長較大的查找表,折半查找,若以有序表表示靜態(tài)查找表， 則查找過程可以基于“折半”進行,基于有序順序表的折半查找,設(shè)n個對象存放在一個有序順序表中，并按其關(guān)鍵碼從小到大排好了序 折半查找時, 先求位于查找區(qū)間正中的對象的下標mid，用其關(guān)鍵碼與給定值x比較,1.elemmid=x 查找成功 2.elemmidx 把查找區(qū)

4、間縮小到表的前半部分，繼續(xù)折半查找 3.elemmidx 把查找區(qū)間縮小到表的后半部分，繼續(xù)折半查找 如果查找區(qū)間已縮小到?jīng)]有對象，仍未找到想要查找的對象，則查找失敗,elem,例如: key=64 的查找過程如下,low,high,mid,low,mid,high,mid,mid = (low+high)/2 Low 指示查找區(qū)間的下界 high 指示查找區(qū)間的上界,template int BinSerach(ElemType elem, int n, KeyType key) / 操作結(jié)果: 在有序表中查找其關(guān)鍵字的值等于key的記錄, /如查找成功,則返回此記錄的序號,否則返回-1 i

5、nt low = 0, high = n -1;/ 查找區(qū)間初值 while (low = high) int mid = (low + high) / 2;/ 查找區(qū)間中間位置 if (key = elemmid) return mid; / 查找成功 else if (key = elemmid) high = mid - 1; / 繼續(xù)在左半?yún)^(qū)間進行查找 else low = mid + 1;/ 繼續(xù)在右半?yún)^(qū)間進行查找 return -1;/ 查找失敗 ,二叉排序樹 （二叉查找樹）,（1）若它的左子樹不空，則左子樹上 所有結(jié)點的值均小于根結(jié)點的值,二叉排序樹或者是一棵空樹；或者 是具有如

6、下特性的二叉樹,（3）它的左、右子樹也都分別是二叉 排序樹,（2）若它的右子樹不空，則右子樹上 所有結(jié)點的值均大于根結(jié)點的值,50,30,80,20,90,10,85,40,35,25,23,88,是二叉排序樹,66,不,二叉排序樹的查找算法,1）若給定值等于根結(jié)點的關(guān)鍵字， 則查找成功 2）若給定值小于根結(jié)點的關(guān)鍵字， 則繼續(xù)在左子樹上進行查找 3）若給定值大于根結(jié)點的關(guān)鍵字， 則繼續(xù)在右子樹上進行查找,否則:,若二叉排序樹為空，則查找不成功,50,30,80,20,90,85,40,35,88,32,查找關(guān)鍵字,50,50,50,30,40,35,50,50,80,90,n 個結(jié)點的二叉查

7、找樹的數(shù)目 3 個結(jié)點的二叉查找樹,123 132 213 312 321,如果對一棵二叉查找樹進行中序遍歷，可以按從小到大的順序，將各結(jié)點關(guān)鍵碼排列起來，所以也稱二叉查找樹為二叉排序樹,在查找過程中，生成了一條查找路徑,從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點,或者,從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止,查找成功,查找不成功,30,20,10,40,35,25,23,f,T,key = 48,f,T,f,T,22,p,f,T,f,T,T,T,T,f,f,f,p,35,15,45,50,40,25,10,20,30,查找45 查找成功,查找28

8、 查找失敗,查找性能的分析,對于每一棵特定的二叉排序樹， 均可按照平均查找長度的定義來求它 的 ASL 值，顯然，由值相同的 n個關(guān) 鍵字，構(gòu)造所得的不同形態(tài)的各棵二 叉排序樹的平均查找長 度的值不同， 甚至可能差別很大,由關(guān)鍵字序列 3，1，2，5，4構(gòu)造而得的二叉排序樹,由關(guān)鍵字序列 1，2，3，4，5構(gòu)造而得的二叉排序樹,2,1,3,4,5,3,5,4,1,2,ASL =（1+2+3+4+5）/ 5 = 3,ASL =（1+2+3+2+3）/ 5 = 2.2,輸入數(shù)據(jù)，建立二叉查找樹的過程,輸入數(shù)據(jù) 53, 78, 65, 17, 87, 09, 81, 15 ,同樣 3 個數(shù)據(jù) 1,

9、2, 3 ，輸入順序不同，建立起來的二叉查找樹的形態(tài)也不同。這直接影響到二叉查找樹的查找性能 如果輸入序列選得不好，會建立起一棵單支樹，使得二叉查找樹的高度達到最大,1,2,3 1,3,2 2,1,3 3,1,2 3,2,1,二叉平衡樹 （AVL樹）,一棵AVL樹或者是空樹，或者是具有下列性質(zhì)的二叉查找樹：它的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對值不超過1,不平衡 平衡,A,B,C,A,B,C,D,E,D,E,結(jié)點的平衡因子(balance factor),每個結(jié)點附加一個數(shù)字, 給出該結(jié)點左子樹的高度減去右子樹的高度所得的高度差, 這個數(shù)字即為結(jié)點的平衡因子 AVL樹

10、任一結(jié)點平衡因子只能取 -1, 0, 1,如果一個結(jié)點的平衡因子的絕對值大于1, 則這棵二叉查找樹就失去了平衡, 不再是AVL樹 如果一棵二叉查找樹是平衡的, 且有 n個結(jié)點，其高度可保持在 O(log2n),平均查找長度也可保持在O(log2n),5,4,8,2,5,4,8,2,1,是平衡樹,不是平衡樹,平衡化旋轉(zhuǎn),如果在一棵平衡的二叉查找樹中插入一個新結(jié)點，造成了不平衡。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化 平衡化旋轉(zhuǎn)有兩類： 單旋轉(zhuǎn) (左旋和右旋) 雙旋轉(zhuǎn) (左旋加右旋和右旋加左旋),右單旋轉(zhuǎn) LL型,左單旋轉(zhuǎn) RR型,左右雙旋轉(zhuǎn) LR型,右左雙旋轉(zhuǎn) RL型,構(gòu)造二叉平衡（查找）樹的方法 在

11、插入過程中，采用平衡旋轉(zhuǎn)技術(shù),依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋轉(zhuǎn) 一次,先向右旋轉(zhuǎn) 再向左旋轉(zhuǎn),4,2,6,5,8,9,6,4,2,8,9,5,向左旋轉(zhuǎn)一次,繼續(xù)插入關(guān)鍵字 9,B - 樹,B-樹是一種 平衡 的 多路 查找 樹,在 m 階的B-樹上，每個非終端結(jié)點可能含有： n 個關(guān)鍵字 Ki（1 in） nm n 個指向記錄的指針 Di（1in） n+1 個指向子樹的指針 Ai（0in）,多叉樹的特性,非葉結(jié)點中的多個關(guān)鍵字均自小至大有序排列，即：K1 K2 Kn Ai-1 所指子樹上所有關(guān)鍵字均小于Ki Ai

12、所指子樹上所有關(guān)鍵字均大于Ki,查找樹的特性,平衡樹的特性,樹中所有葉子結(jié)點均不帶信息，且在樹中的同一層次上 根結(jié)點或為葉子結(jié)點，或至少含有兩棵子樹 其余所有非葉結(jié)點均至少含有m/2棵子樹，至多含有 m 棵子樹,從根結(jié)點出發(fā)，沿指針查找結(jié)點和在結(jié)點內(nèi)進行順序（或折半）查找 兩個過程交叉進行,查找過程,若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點的指針和關(guān)鍵字在結(jié)點中的位置,若查找不成功，則返回插入位置,是B-樹的一種變型,B+樹, 每個葉子結(jié)點中含有 n 個關(guān)鍵字和 n 個指向記錄的指針；并且，所有葉子結(jié)點彼此相鏈接構(gòu)成一個有序鏈表，其頭指針指向含最小關(guān)鍵字的結(jié)點, 每個非葉結(jié)點中的關(guān)鍵字 Ki

13、即為其相應(yīng)指針 Ai 所指子樹中關(guān)鍵字的最大值, 所有葉子結(jié)點都處在同一層次上，每個葉子結(jié)點中關(guān)鍵字的個數(shù)均介于 m/2和 m 之間,查找過程, 在 B+ 樹上，既可以進行縮小范圍的查找，也可以進行順序查找, 在進行縮小范圍的查找時，不管成功與否，都必須查到葉子結(jié)點才能結(jié)束,若在結(jié)點內(nèi)查找時， Ki-1 給定值Ki，則應(yīng)繼續(xù)在 Ai 所指子樹中進行查找,50 96,15 50,62 78 96,71 78,84 89 96,56 62,20 26 43 50,3 8 15,sq,root,哈 希 查 找 (Hash),以上討論的表示查找表的各種結(jié)構(gòu)的共同特點：記錄在表中的位置和它的關(guān)鍵字之間不

14、存在一個確定的關(guān)系,查找的過程為給定值依次和關(guān) 鍵字集合中各個關(guān)鍵字進行比較,查找的效率取決于和給定值進行比較的關(guān)鍵字個數(shù),用這類方法表示的查找表，其平均查找長度都不為零,不同的表示方法，其差別僅在于： 關(guān)鍵字和給定值進行比較的順序不同,只有一個辦法：預(yù)先知道所查關(guān)鍵字在表中的位置,對于頻繁使用的查找表，希望 ASL = 0,即，要求：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系,在一般情況下，需在關(guān)鍵字與記錄在表中的存儲位置之間建立一個函數(shù)關(guān)系，以 H(key) 作為關(guān)鍵字為 key 的記錄在表中的位置，通常稱這個函數(shù) H(key) 為哈希函數(shù),哈希函數(shù)是一個映象，即：將關(guān)鍵 字的集合映射

15、到某個地址集合上，它 的設(shè)置很靈活，只要這個地址集合的 大小不超出允許范圍即可,由于哈希函數(shù)是一個壓縮映象，因 此，在一般情況下，很容易產(chǎn)生 “ 沖 突 ” 現(xiàn)象，即： key1 key2，而 H(key1) = H(key2),很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生,因此，在構(gòu)造這種特殊的“查 找表”時，除了需要選擇一個好” ( 盡可能少產(chǎn)生沖突 )的哈希函數(shù) 之外；還需要找到一種“處理沖突” 的方法,哈希表的定義,根據(jù)設(shè)定的哈希函數(shù) H( key ) 和所選處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集 ( 區(qū)間) 上，并

16、以關(guān)鍵字在地址集中的“映象”作為相應(yīng)記錄在表中的存儲位置，如此構(gòu)造所得的查找表稱為“哈希表”,構(gòu)造哈希函數(shù)的方法,對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法,若是非數(shù)字關(guān)鍵字，則需先對其進行數(shù)字化處理,直接定址法,平方取中法,除留余數(shù)法,折疊法,隨機數(shù)法,數(shù)字分析法,數(shù)字分析法,此方法適合于： 能預(yù)先估計出全體關(guān)鍵字的每一位 上各種數(shù)字出現(xiàn)的頻度,假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, , us)，分析關(guān)鍵字集中的全體， 并從中提取分布均勻的若干位或它們的組合作為地址,平方取中法,以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值” 的目的是“擴大差別” ，同時平方值

17、的中間各位又能受到整個關(guān)鍵字中各位的影響,此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重 復(fù)出現(xiàn)頻度很高的現(xiàn)象,折疊法,將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加,此方法適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多,直接定址法,哈希函數(shù)為關(guān)鍵字的線性函數(shù) H(key) = key 或者 H(key) = a key + b,此法適合于： 地址集合的大小 = = 關(guān)鍵字集合的大小,除留余數(shù)法,設(shè)定哈希函數(shù)為: H(key) = key MOD p 其中， pm (表長) 并且 p 應(yīng)為不大于 m 的素數(shù) 或是 不含 20 以下的質(zhì)因子,隨機數(shù)法,設(shè)定哈希函

18、數(shù)為: H(key) = Random(key) 其中，Random 為偽隨機函數(shù),通常，此方法用于對長度不等 的關(guān)鍵字構(gòu)造哈希函數(shù),實際造表時，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小,處理沖突的方法,“處理沖突” 的實際含義是 為產(chǎn)生沖突的地址尋找下一個哈希地址,1. 開放定址法,2. 鏈地址法,為產(chǎn)生沖突的地址 H(key) 求得一個地址序列： H0, H1, H2, , Hs 1 sm-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s,開放定

19、址法(閉域法),增量 di 的三種取法,1)線性探測再散列 di = c i 最簡單的情況 c=1 2) 平方探測再散列 di = 12, -12, 22, -22, , 3) 隨機探測再散列 di 是一組偽隨機數(shù)列 或者 di=iH2(key) (又稱雙散列函數(shù)探測), 19, 01, 23, 14, 55, 68, 11, 82, 36 ,H(key) = key MOD 11,19,01,23,14,55,68,采用線性探測再散列處理沖突,11,82,36,1 1 2 1 3 6 2 5 1,將所有哈希地址相同的記錄都鏈接在同一鏈表中,鏈地址法(開域法),0 1 2 3 4 5 6,14

20、,01,36,19,82,23,11,68,55, 19, 01, 23, 14, 55, 68, 11, 82, 36 ,H(key) = key MOD 7,第9章 排序,什么是排序？,排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(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,一般情況下， 假設(shè)含n個記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn ,這些關(guān)鍵字相互之

21、間可以進行比較，即在 它們之間存在著這樣一個關(guān)系 ： Kp1Kp2Kpn,按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作排序。,內(nèi)部排序和外部排序,若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序；,反之，若參加排序的記錄數(shù)量很大， 整個序列的排序過程不可能在內(nèi)存中 完成，則稱此類排序問題為外部排序。,三、內(nèi)部排序的方法,內(nèi)部排序的過程是一個逐步擴大 記錄的有序序列長度的過程。,經(jīng)過一趟排序,有序序列區(qū),無 序 序 列 區(qū),有序序列區(qū),無 序 序 列 區(qū),基于不同的“擴大” 有序序列長度的方法，內(nèi)部排序方法大致可分下列幾種類型：,插入類,交換類,

22、選擇類,歸并類,其它方法,1. 插入類,將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。,2. 交換類,通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。,3. 選擇類,從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。,4. 歸并類,通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。,5. 其它方法,插 入 排 序,有序序列elem1.i-1,elemi,無序序列 elemi.n,一趟直接插入排序

23、的基本思想：,有序序列elem1.i,無序序列elemi+1.n,實現(xiàn)“一趟插入排序”可分三步進行：,3將elemi 插入(復(fù)制)到elemj+1的位置上。,2將elemj+1.i-1中的所有記錄均后移 一個位置；,1在elem1.i-1中查找elemi的插入位置， elem1.j elemi elemj+1.i-1 ；,直接插入排序（基于順序查找）,不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述,希爾排序（基于逐趟縮小增量）,一、直接插入排序,利用 “順序查找”實現(xiàn) “在elem0.i-1中查找elemi的插入位置”,算法的實現(xiàn)要點：,從elemi-1起向前進行順序查找,循環(huán)結(jié)束表明elemi的插入位

24、置為 j +1,j,elemi,for (j=i-1; j = 0 / 從后往前找,j=i-1,插入位置,對于在查找過程中找到的那些關(guān)鍵字大于elemi(=e)的記錄，并在查找的同時實現(xiàn)記錄向后移動；,for (j=i-1; e elemj; -j); elemj+1 = elemj,j,elemi,j= i-1,上述循環(huán)結(jié)束后可以直接進行“插入”,插入位置,令 i = 1，3，, n, 實現(xiàn)整個序列的排序。,for ( i=1; in; +i ) if (elemi elemi-1) 在 elem0.i-1中查找elemi的插入位置; 插入elemi ; ,template void Str

25、aightInsertSort(ElemType elem, int n) / 操作結(jié)果:對數(shù)組elem作直接插入排序序 for ( int i = 1; i = 0 / j+1為插入位置 ,二、希爾排序（又稱縮小增量排序）,基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。,所謂“宏觀”調(diào)整，指的是，“跳躍式” 的插入排序。 具體做法為：,將記錄序列分成若干子序列，分別對每個子序列進行插入排序。,其中，d 稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為 1。,例如：將 n 個記錄分成 d 個子序列： elem0，elem0+d，elem0+2d， elem0+k

26、d elem1，elem1+d，elem1+2d， elem1+kd elemd-1, elem2d-1, elem3d-1, , elem(k+1)d-1,例如：,16 25 12 30 47 11 23 36 9 18 31,第一趟希爾排序，設(shè)增量 d =5,11 23 12 9 18 16 25 36 30 47 31,第二趟希爾排序，設(shè)增量 d = 3,9 18 12 11 23 16 25 31 30 47 36,第三趟希爾排序，設(shè)增量 d = 1,9 11 12 16 18 23 25 30 31 36 47,template void ShellInsert(ElemType e

27、lem, int n, int incr) / 操作結(jié)果: 對數(shù)組elem作一趟增量為incr的Shell排序,對 /插入排序作出的修改是子序列中前后相鄰記錄的增 /量為incr,而不是1 for ( int i = incr ; i = 0 / j+incr為插入位置 ,template void ShellSort(ElemType elem, int n, int inc, int t) / 操作結(jié)果: 按增量序列inc0 . t -1 對數(shù)組elem作Shell排 /序 for ( int k = 0 ; k t; k+) / 第k趟Shell排序 ShellInsert(elem,

28、n, inck); ,歸并排序,歸 并 排 序,歸并排序的過程基于下列基本思想進行： 將兩個或兩個以上的有序子序列 “歸并” 為一個有序序列。,在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列,歸并為一個記錄的有序序列。,有 序 序 列 Rl.n,有序子序列 Rl.m,有序子序列 Rm+1.n,這個操作對順序表而言，是輕而易舉的。,歸并排序的算法,如果記錄無序序列 Rs.t 的兩部分 Rs.(s+t)/2 和 R(s+t)/2+1.t 分別按關(guān)鍵字有序， 則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。,由此，應(yīng)該先分別對這兩部分進行 2-路歸并排序

29、。,例如：,52, 23, 80, 36, 68, 14 (s=1, t=6), 52, 23, 80 36, 68, 14, 52, 2380, 52, 23, 52, 23, 52, 80,36, 6814,3668,36, 68,14, 36, 68, 14, 23, 36, 52, 68, 80 ,23,快速排序,一、起泡排序,假設(shè)在排序過程中，記錄序列R0.n-1的狀態(tài)為：,第 i 趟起泡排序,無序序列R0.n-i,有序序列 Rn-i+1.n-1,n-i,無序序列R0.n-i-1,有序序列 Rn-i.n-1,比較相鄰記錄，將關(guān)鍵字最大的記錄交換到 n-i 的位置上,template

30、void BubbleSort(ElemType elem, int n) / 操作結(jié)果:在數(shù)組elem中用起泡排序進行排序 for (int i = n - 1; i 0; i-) / 第i趟起泡排序 for (int j = 0; j elemj + 1) / 如出現(xiàn)逆序,則交換elemj和 / elemj + 1 Swap(elemj, elemj + 1); ,二、一趟快速排序（一次劃分）,目標：找一個記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動至該記錄之后。,致使一趟排序之后，記錄的無序序列Rs.t將分割成兩部分：Rs

31、.i-1和Ri+1.t，且 Rj Ri Rk (sji-1) 樞軸 (i+1kt)。,s,t,low,high,設(shè) Rs=52 為樞軸,將 Rhigh.key 和 樞軸的關(guān)鍵字進行比較，要求Rhigh.key 樞軸的關(guān)鍵字,將 Rlow.key 和 樞軸的關(guān)鍵字進行比較，要求Rlow.key 樞軸的關(guān)鍵字,high,23,low,80,high,14,low,52,例如,R0,52,low,high,high,high,low,可見，經(jīng)過“一次劃分” ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為: 23, 49, 14, 36, (52)

32、 58, 61, 97, 80, 75,在調(diào)整過程中，設(shè)立了兩個指針： low 和high，它們的初值分別為： s 和 t，,之后逐漸減小 high，增加 low，并保證 Rhigh52，和 Rlow52,否則進行記錄的“交換”。,快速排序,首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。,無 序 的 記 錄 序 列,無序記錄子序列(1),無序子序列(2),樞軸,一次劃分,分別進行快速排序,堆排序,一、簡單選擇排序,假設(shè)排序過程中，待排記錄序列的狀態(tài)為：,有序序列R1.i-1,無序序列 Ri.n,第 i 趟 簡單選擇排序,從中選出 關(guān)鍵字最小的記錄,有序

33、序列R1.i,無序序列 Ri+1.n,template void SimpleSelectionSort(ElemType elem, int n) / 操作結(jié)果:對數(shù)組elem作簡單選擇排序 for ( int i = 0; i n - 1; i+) / 第i趟簡單選擇排序 int lowIndex = i;/elemi.n-1中最小元素小標 for (int j = i + 1; j n; j+) if (elemj elemlowIndex) / lowIndexd當(dāng)前的最小元素小標 lowIndex = j; Swap(elemi, elemlowIndex);/ 交換 ,二、堆排序,

34、堆是滿足下列性質(zhì)的數(shù)列r0, r1, ，rn-1：,或,堆的定義:,(小頂堆),(大頂堆),ri,R2i+1,r2i+2,若將該數(shù)列視作完全二叉樹， 則 r2i+1 是 ri 的左孩子； r2i+2 是 ri 的右孩子。,12,36,27,65,49,81,73,55,40,34,98,例如:,是堆,14,不,堆排序即是利用堆的特性對記錄序列進行排序的一種排序方法。,例如：,建大頂堆, 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 , 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 ,交換 98 和 12,重新調(diào)整為大頂堆, 81,

35、 73, 49, 64, 36, 27, 40, 55, 12, 98 , 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 ,經(jīng)過篩選,如何“建堆”？,兩個問題:,如何“篩選”？,所謂“篩選”指的是，對一棵左/右子樹 均為堆的完全二叉樹，“調(diào)整”根結(jié)點 使整個二叉樹也成為一個堆。,堆,堆,篩選,98,81,49,73,55,64,12,36,27,40,例如:,是大頂堆,12,但在 98 和 12 進行互換之后，它就不是堆了，,因此，需要對它進行“篩選”。,98,12,81,73,64,12,98,比較,比較,建堆是一個從下往上進行“篩選”的過程。,40,55,4

36、9,73,81,64,36,12,27,98,例如: 排序之前的關(guān)鍵字序列為,12,36,81,73,49,98,81,73,55,現(xiàn)在，左/右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點，使整個二叉樹是個“堆”即可。,98,49,40,64,36,12,27,基 數(shù) 排 序,基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來實現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。,多關(guān)鍵字的排序,鏈式基數(shù)排序,多關(guān)鍵字的排序,n 個記錄的序列 R1, R2, ，Rn 對關(guān)鍵字 (Ki0, Ki1,Kid-1) 有序是指：,其中: K0 被稱為 “最主”位關(guān)鍵字,Kd-1 被稱為 “最次”位關(guān)鍵字,對于序列中任意兩個記錄 Ri

37、 和 Rj (1ijn) 都滿足下列(詞典)有序關(guān)系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1),實現(xiàn)多關(guān)鍵字排序 通常有兩種作法:,最低位優(yōu)先LSD法,最高位優(yōu)先MSD法,最高位優(yōu)先MSD法 先對K0進行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對 K1 進行排序，.， 依次類推，直至最后對最次位關(guān)鍵字排序完成為止。,最低位優(yōu)先LSD法 先對 Kd-1 進行排序，然后對 Kd-2 進行排序，依次類推，直至對最主位關(guān)鍵字 K0 排序完成為止。,例如:學(xué)生記錄含三個關(guān)鍵字: 系別、班號和班內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。,無序序列,對K2

38、排序,對K1排序,對K0排序,3,2,30,1,2,15,3,1,20,2,3,18,2,1,20,1,2,15,2,3,18,3,1,20,2,1,20,3,2,30,3,1,20,2,1,20,1,2,15,3,2,30,2,3,18,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,LSD的排序過程如下:,鏈式基數(shù)排序,假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范圍相同，則按LSD法進行排序時，可以采用“分配-收集”的方法，其好處是不需要進行關(guān)鍵字間的比較。,對于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用這種“分配-收集”的辦

39、法進行排序，稱作基數(shù)排序法。,例如：對下列這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 ,首先按其 “個位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)?它們 “收集” 在一起；,然后按其 “十位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈?“收集” 在一起；,最后按其“百位數(shù)”重復(fù)一遍上述操作。,在計算機上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈式基數(shù)排序，具體作法為：,待排序記錄以指針相鏈，構(gòu)成一個鏈表；,“分配

40、” 時，按當(dāng)前“關(guān)鍵字位”所取值，將記錄分配到不同的 “鏈隊列” 中，每個隊列中記錄的 “關(guān)鍵字位” 相同；,“收集”時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;,對每個關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。,例如：,p369367167239237138230139,進行第一次分配,進行第一次收集,f0 r0,f7 r7,f8 r8,f9 r9,p230,230,367 ,167,237,367167237,138,368239139,369 ,239,139,138,進行第二次分配,p230237138239139,p230367167237138368239139,f3 r

41、3,f6 r6,230 ,237,138,239,139,367 ,167,368,367167368,進行第二次收集,進行第三次收集之后便得到記錄的有序序列,f1 r1,p230237138239139367167368,進行第三次分配,f2 r2,f3 r3,138 ,139,167,230 ,237,239,367 ,368,p138139167,230237239,367368,基數(shù)排序的時間復(fù)雜度為O(d(n+rd),其中：分配為O(n) 收集為O(rd)(rd為“基”) d為“分配-收集”的趟數(shù),各種排序方法的綜合比較,一、時間性能,1. 平均的時間性能,基數(shù)排序,時間復(fù)雜度為 O

42、(nlogn)：,快速排序、堆排序和歸并排序,時間復(fù)雜度為 O(n2)：,直接插入排序、起泡排序和 簡單選擇排序,時間復(fù)雜度為 O(n):,2. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時,3. 簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。,直接插入排序和起泡排序能達到O(n)的時間復(fù)雜度， 快速排序的時間性能蛻化為O(n2) 。,排序方法的穩(wěn)定性能,1. 穩(wěn)定的排序方法指的是，對于兩個關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。,2. 當(dāng)對多關(guān)鍵字的記錄序列進行LSD方法排序時，必須采用穩(wěn)定的排序方法。,排序之前 : Ri(K) Rj(K

43、) ,排序之后 : Ri(K) Rj(K) ,例如：,排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 ),若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 則稱該排序方法是穩(wěn)定的;,若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 則稱該排序方法是不穩(wěn)定的。,3. 對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。,4. 快速排序、所有選擇排序(包括堆排序）和希爾排序是不穩(wěn)定的排序方法。,例如 : 對 4, 3, 4, 2 進行快速排序， 得到 2, 3, 4, 4 ,外 部 排 序,一. 問

44、題的提出,待排序的記錄數(shù)量很大，不能一次裝入內(nèi)存，則無法利用前幾節(jié) 討論的排序方法 ；,按可用內(nèi)存大小，利用內(nèi)部排序 方法，構(gòu)造若干( 記錄的) 有序子序列，通常稱外存中這些記錄有序子序列為 “歸并段”；,二、外部排序的基本過程,由相對獨立的兩個步驟組成：,通過“歸并”，逐步擴大 (記錄的)有序子序列的長度，直至外存中整個記錄序列按關(guān)鍵字有序為止。,例如：假設(shè)有一個含10,000個記錄的磁盤 文件，而當(dāng)前所用的計算機一次只 能對1000個記錄進行內(nèi)部排序，則 首先利用內(nèi)部排序的方法得到10個 初始歸并段，然后進行逐趟歸并。,假設(shè)進行2路歸并(即兩兩歸并)，則 第一趟由10個歸并段得到5個歸并段

45、；,最后一趟歸并得到整個記錄的有序序列。,第三趟由 3 個歸并段得到2個歸并段；,第二趟由 5 個歸并段得到3個歸并段；,假設(shè)“數(shù)據(jù)塊”的大小為200，即每一次訪問外存可以讀/寫200個記錄。 則對于10,000個記錄，處理一遍需訪問外存100次(讀和寫各50次)。,分析上述外排過程中訪問外存(對外 存進行讀/寫)的次數(shù)：,由此，對上述例子而言，,1)求得10個初始歸并段需訪問外存100次； 2)每進行一趟歸并需訪問外存100次； 3)總計訪問外存 100 + 4 100 = 500次。,外排總的時間還應(yīng)包括內(nèi)部排序 所需時間和逐趟歸并時進行內(nèi)部歸并 的時間，顯然，除去內(nèi)部排序的因素 外，外部

46、排序的時間取決于逐趟歸并 所需進行的“趟數(shù)”。,例如，若對上述例子采用5路歸并， 則只需進行2趟歸并，總的訪問外存的 次數(shù)將壓縮到 100 + 2 100 = 300 次。,一般情況下，假設(shè)待排記錄序列 含 m 個初始歸并段，外排時采用 k路 歸并，則歸并趟數(shù)為 logkm，顯然， 隨之k的增大歸并的趟數(shù)將減少，因此 對外排而言，通常采用多路歸并。k 的 大小可選，但需綜合考慮各種因素。,第10章 文件,有關(guān)文件的基本概念,一、文件即為記錄的集合，和“查找 表”的差別在于，“文件”指的是存 儲在外存儲器中的記錄的集合。 記錄是文件中可以存取的數(shù)據(jù)的 基本單位。,二、文件可按其中記錄的類型不同而

47、 分成兩類：,其一為操作系統(tǒng)的文件，文件中的記 錄僅是一個字符組。由于操作系 統(tǒng)中的文件僅是一維的連續(xù)字符 序列，為了用戶存取和加工的方 便，將文件中的信息劃分為若干 組，其中每一組信息稱作一個記 錄；,其二為數(shù)據(jù)庫文件，文件中的記錄帶 有結(jié)構(gòu)，是數(shù)據(jù)項的集合。記錄 是文件中可以存取的數(shù)據(jù)基本單 位，數(shù)據(jù)項是文件中可以使用的 數(shù)據(jù)最小單位。,三、記錄中能識別不同記錄的數(shù)據(jù)項 被稱為關(guān)鍵字，若該數(shù)據(jù)項能唯 一識別一個記錄，則稱為主關(guān)鍵 字，若能識別多個記錄則稱為次 關(guān)鍵字。,四、文件的邏輯結(jié)構(gòu)指的是呈現(xiàn)在用 戶面前的文件中記錄之間的邏輯 關(guān)系；文件的物理結(jié)構(gòu)指的是文 件中的邏輯記錄在存儲器中的組

48、 織方式。,順 序 文 件,結(jié) 構(gòu) 特 點：,記錄在文件中的排列順序是由記 錄進入存儲介質(zhì)的次序決定的， 即文 件物理結(jié)構(gòu)中記錄的排列順序和文件 的邏輯結(jié)構(gòu)中記錄的排列順序一致。,操作特點：,1便于進行順序存取； 2不便于進行直接存取，為取第i個記錄，必須先讀出前i-1個記錄；,3插入新的記錄只能加在文件的末尾； 4刪除記錄時，只作標記； 5更新記錄必須生成新的文件。,索 引 文 件,1索引文件由“主文件”和“索引”組成； 2索引中的每個記錄由“關(guān)鍵字”和“指針”組成； 3通常，索引文件中的主文件是無序文件，索引是 (按關(guān)鍵字有序)的有序文件； 4“索引”是在輸入數(shù)據(jù)建立文件時自動生成。,二、

49、VSAM文件 VSAM(Vistual Storage Access Method),文件是利用操作系統(tǒng)中提供的虛擬存儲器的功能組織的文件，免除了用戶為讀/寫記錄時直接對外存進行的操作，對用戶而言，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位。, .,.,.,.,索引集 B+樹 順序集,控制區(qū)域,控制區(qū)間,數(shù)據(jù)集,1文件的結(jié)構(gòu),2. 控制區(qū)間是用戶進行一次存取的 邏輯單位，可看成是一個邏輯磁道。 但它的實際大小和物理磁道無關(guān)。,VSAM文件初建時，每個控制區(qū) 間內(nèi)的記錄數(shù)不足額定數(shù)，并且有的 控制區(qū)間內(nèi)的記錄數(shù)為零。,控制區(qū)域由若干控制區(qū)間和它們 的索引項組成，可看成是一個邏輯柱面。,順序集本身是

50、一個單鏈表，它 包含文件的全部索引項，同時，順 序集中的每個結(jié)點即為B+樹的葉子 結(jié)點，索引集中的結(jié)點即為B+樹的 非葉結(jié)點。,文件的操作,檢索：可進行順序存取和按關(guān)鍵字存??； 插入：按關(guān)鍵字大小插入在某個適當(dāng)?shù)目刂茀^(qū)間中，當(dāng)控制區(qū)間中的記錄數(shù)超過文件規(guī)定的大小時，要“分裂”控制區(qū)間，必要時，還需要“分裂”控制區(qū)域； 刪除：必須“真實地”刪除記錄，因此要在控制區(qū)間內(nèi)“移動”記錄。,直 接 存 取 文 件,和前幾節(jié)討論的文件組織方法 不同，直接存取文件的特點是，由 記錄的關(guān)鍵字“直接”得到記錄在外 存上的映象地址。,類似于哈希表的構(gòu)造方法，根 據(jù)文件中關(guān)鍵字的特點設(shè)計一種“哈 希函數(shù)”和“處理沖

51、突的方法”將記錄 散列到外存儲設(shè)備上，又稱“散列文件”。,哈希文件的結(jié)構(gòu),由于記錄在外存上是成組存放的， 因此允許多個記錄映象到同一個地址 上。在此，稱外存儲器中存放多個記 錄的“數(shù)據(jù)塊”為“桶”。 因此由哈希函 數(shù)得到的映象地址為“桶地址”。,例如：有一組關(guān)鍵字如下所列 589，063，269，505，764，182，166，330 假設(shè)哈希函數(shù)為 key MOD 7，每個桶可以容納 3個記錄（稱桶的容量為3），則哈希文件如下:,基桶,063 182,589 505 764,269,166,330,溢出桶,文件的操作,檢索：只能進行按關(guān)鍵字的查找，不能進行順序查找。檢索時，先在基桶內(nèi)進行查找

52、，若不存在，則再到溢出桶中進行查找； 插入：當(dāng)查找不成功時，將記錄插入在相應(yīng)的基桶或溢出桶內(nèi)； 刪除：對被刪記錄作特殊標記。, 優(yōu)點：記錄隨機存放，不需要進行排 序；插入、刪除方便，存取速 度快；節(jié)省存儲空間，不需要 索引區(qū)。,缺點：不能進行順序存?。辉诮?jīng)過多 次插入和刪除操作之后，需進 行“重組文件”的操作。,第11講 算法設(shè)計與分析,算法設(shè)計,通常求解一個問題可能會有多種算法可供選擇，選擇的主要標準是算法的正確性、可靠性、簡單性和易理解性。其次是算法所需要的存儲空間少和執(zhí)行更快等因素。,遞歸算法,一個直接或間接地調(diào)用自身的算法稱為遞歸算法，一個直接或間接地調(diào)用自身的函數(shù)稱為遞歸函數(shù)。 在算法設(shè)計中，使用遞歸技術(shù)往往能使函數(shù)的定義和算法的描述簡捷并且便于理解。,一般遞歸具有如下的形式： if () /*遞歸結(jié)束條件成立，結(jié)束遞歸調(diào)用 */ 遞歸結(jié)束部分; else /*遞歸結(jié)束條件不成立，繼續(xù)進行遞歸調(diào)用 */ 遞歸調(diào)用部分; 或 if () /* 遞歸調(diào)用條件成立，繼續(xù)進行遞歸調(diào)用 */ 遞歸調(diào)用部分; else /* 遞歸調(diào)用條件不成立，結(jié)束遞歸調(diào)用 */ 遞歸結(jié)束部分; ,例：用遞歸求階乘n!。 階乘可用迭代表示如下：,int Factorial(int n) / 操作結(jié)果: 用遞歸求階乘n!