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

1、四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造與算法分析分析(C+版版)課件課件下下四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍第第8講講 查找查找第第9講講 排序排序第第10講講 文件文件第第11講講 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍第第8章章 查找查找四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，

2、主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍查找算法的評(píng)價(jià)目的查找算法的評(píng)價(jià)目的 查找勝利查找勝利: :最少比較次數(shù)最少比較次數(shù) 最多比較次數(shù)最多比較次數(shù) 平均比較次數(shù)平均比較次數(shù) 查找失敗查找失敗: :最少比較次數(shù)最少比較次數(shù) 最多比較次數(shù)最多比較次數(shù) 平均比較次數(shù)平均比較次數(shù)四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 以順序表或線性鏈表表示靜態(tài)查找表順序查找順序查找四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍elem順序查找過(guò)程順序查找過(guò)程假設(shè)給定值假設(shè)給定值 e=64,要求要求 ST.e

3、lemk = e, 問(wèn)問(wèn): k = ?kk四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 上述順序查找表的查找算法簡(jiǎn)單，但平均查找長(zhǎng)度較大，特別不適用于表長(zhǎng)較大的查找表折半查找折半查找 假設(shè)以有序表表示靜態(tài)查找表，那么查找過(guò)程可以基于“折半進(jìn)展四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍elem例如例如: key=64 的查找過(guò)

4、程如下的查找過(guò)程如下lowhighmidlow mid high midmid = (low+high)/2Low 指示查找區(qū)間的下界指示查找區(qū)間的下界high 指示查找區(qū)間的上界指示查找區(qū)間的上界四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍二叉排序樹(shù)二叉排序樹(shù)二叉查找樹(shù)二叉查找樹(shù)四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍1假設(shè)它的左子樹(shù)不空，那么左子假設(shè)它的左子樹(shù)不空，那么左子樹(shù)上樹(shù)上 一切結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值一切結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值 二叉排序樹(shù)或者是一棵

5、空樹(shù)；或者是具有如下特性的二叉樹(shù)3它的左、右子樹(shù)也都分別是二叉它的左、右子樹(shù)也都分別是二叉 排序樹(shù)排序樹(shù)2假設(shè)它的右子樹(shù)不空，那么右子假設(shè)它的右子樹(shù)不空，那么右子樹(shù)上樹(shù)上 一切結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值一切結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍503080209010854035252388是二叉排序樹(shù)是二叉排序樹(shù)66不不四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍二叉排序樹(shù)的二叉排序樹(shù)的查找算法查找算法四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 1假設(shè)給定值等于根結(jié)點(diǎn)的關(guān)鍵字，假

6、設(shè)給定值等于根結(jié)點(diǎn)的關(guān)鍵字， 那么查找勝利那么查找勝利 2假設(shè)給定值小于根結(jié)點(diǎn)的關(guān)鍵字，假設(shè)給定值小于根結(jié)點(diǎn)的關(guān)鍵字， 那么繼續(xù)在左子樹(shù)上進(jìn)展查找那么繼續(xù)在左子樹(shù)上進(jìn)展查找 3假設(shè)給定值大于根結(jié)點(diǎn)的關(guān)鍵字，假設(shè)給定值大于根結(jié)點(diǎn)的關(guān)鍵字， 那么繼續(xù)在右子樹(shù)上進(jìn)展查找那么繼續(xù)在右子樹(shù)上進(jìn)展查找否那么否那么: 假設(shè)二叉排序樹(shù)為空，那么查找不勝假設(shè)二叉排序樹(shù)為空，那么查找不勝利利四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍50308020908540358832查找關(guān)鍵字查找關(guān)鍵字50505030403550508090= 50 , 35 , 90 , 95四川大學(xué)計(jì)算機(jī)學(xué)

7、院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍51*2*34*5*6*41C13133*2122133132123123n*n2C1n1四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍在查找過(guò)程中，生成了一條查找途徑在查找過(guò)程中，生成了一條查找途徑 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn)或者或者 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹(shù)為止 查找勝利查找勝利 查找不勝利查找不勝利四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游

8、洪躍30201040352523fT key = 48fTfT22pfTfTTTTfffp四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍351545504025102030四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍查找性能的分析查找性能的分析 對(duì)于每一棵特定的二叉排序樹(shù)，均可按照平均查找長(zhǎng)度的定義來(lái)求它的 ASL 值，顯然，由值一樣的 n個(gè)關(guān)鍵字，構(gòu)造所得的不同形狀的各棵二叉排序樹(shù)的平均查找長(zhǎng) 度的值不同，甚至能夠差別很大四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍由關(guān)鍵字序列由關(guān)鍵字序列 3，1，2，5，4構(gòu)

9、造而得的二叉排序樹(shù)構(gòu)造而得的二叉排序樹(shù)由關(guān)鍵字序列由關(guān)鍵字序列 1，2，3，4，5構(gòu)造而得的二叉排序樹(shù)構(gòu)造而得的二叉排序樹(shù)2134535412ASL =1+2+3+4+5/ 5 = 3ASL =1+2+3+2+3/ 5 = 2.2四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 輸入數(shù)據(jù)，建立二叉查找樹(shù)的過(guò)程535378537865537865175378658717537865091787537865811787095378651517870981四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)

10、學(xué)院，主講教師：游洪躍123111132223323四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍二叉平衡樹(shù)二叉平衡樹(shù)AVLAVL樹(shù)樹(shù)四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 不平衡不平衡 平衡平衡ABCABCDEDE四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍548254821是平衡樹(shù)是平衡樹(shù)不是平衡樹(shù)不是平衡樹(shù)四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院

11、，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍構(gòu)造二叉平衡查找樹(shù)的方法構(gòu)造二叉平衡查找樹(shù)的方法在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)依次插入的關(guān)鍵字為依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字繼續(xù)插入關(guān)

12、鍵字 9四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍B - 樹(shù)樹(shù)四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍B-樹(shù)是一種樹(shù)是一種 平衡平衡 的的 多路多路 查找查找 樹(shù)樹(shù) root 50 15 71 84 3 8 20 26 43 56 62 78 89 96四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 在 m 階的B-樹(shù)上，每個(gè)非終端結(jié)點(diǎn)能夠含有： n 個(gè)關(guān)鍵字 Ki1 in nm n 個(gè)指向記錄的指針 Di1in n+1 個(gè)指向子樹(shù)的指針 Ai0in多叉樹(shù)的特性多叉樹(shù)的特性四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪

13、躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字均自小至大非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字均自小至大有序陳列，即：有序陳列，即：K1 K2 KnK1 K2 = 0 & elem0elem j; -j); / 從后往前找從后往前找j=i-1插入位置插入位置四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 對(duì)于在查找過(guò)程中找到的那些關(guān)鍵字大于elemi(=e)的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后挪動(dòng)；for (j=i-1; e elemj; -j); elemj+1 = elemjjelemij= i-1上述循環(huán)終了后可以直接進(jìn)展“插入插入位置插入位置四川大學(xué)計(jì)算機(jī)學(xué)院，

14、主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍令 i = 1，3，, n, 實(shí)現(xiàn)整個(gè)序列的排序。for ( i=1; in; +i ) if (elemi elemi-1) 在在 elem0.i-1中查找中查找elemi的插入位置的插入位置; 插入插入elemi ; 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 二、希爾排序又稱減少增量排序二、希爾排序又稱減少增量排序 根本思想：對(duì)待排記錄序列先作“宏觀調(diào)整，再作“微觀調(diào)整。 所謂“宏觀調(diào)整，指的是，“騰躍式的插入排序。 詳細(xì)做法為：四川大

15、學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍將記錄序列分成假設(shè)干子序列，分別對(duì)每個(gè)子序列進(jìn)展插入排序。其中，d 稱為增量，它的值在排序過(guò)程中從大到小逐漸減少，直至最后一趟排序減為 1。例如：將 n 個(gè)記錄分成 d 個(gè)子序列： elem0，elem0+d，elem0+2d， elem0+kd elem1，elem1+d，elem1+2d， elem1+kd elemd-1, elem2d-1, elem3d-1, , elem(k+1)d-1四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍例如：16 25 12 30 47 11 23 36 9 18

16、 31 第一趟希爾排序，設(shè)增量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序，設(shè)增量 d = 39 18 12 11 23 16 25 31 30 47 36第三趟希爾排序，設(shè)增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍歸并排序四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍歸歸

17、 并并 排排 序序歸并排序的過(guò)程基于以下根本思想進(jìn)展： 將兩個(gè)或兩個(gè)以上的有序子序列 “歸并 為一個(gè)有序序列。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰的記錄有序子序列歸并為一個(gè)記錄的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m 有序子序列有序子序列 Rm+1.n這個(gè)操作對(duì)順序表而言，是輕而易舉的。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍歸并排序的算法歸并排序的算法假設(shè)記錄無(wú)序序列 Rs.t 的兩部分 Rs.(s+t)/2 和 R(s+t)/2+

18、1.t分別按關(guān)鍵字有序，那么利用上述歸并算法很容易將它們歸并成整個(gè)記錄序列是一個(gè)有序序列。 由此，應(yīng)該先分別對(duì)這兩部分進(jìn)展 2-路歸并排序。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍快速排序四川大學(xué)計(jì)算機(jī)學(xué)院

19、，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍一、起泡排序一、起泡排序假設(shè)在排序過(guò)程中，記錄序列R0.n-1的形狀為：第 i 趟起泡排序無(wú)序序列R0.n-i有序序列 Rn-i+1.n-1n-i無(wú)序序列R0.n-i-1有序序列 Rn-i.n-1比較相鄰記錄，將關(guān)鍵字最大的記錄交換到 n-i 的位置上四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍二、一趟快速排序一次劃分二、一趟快速排序一次劃分目的：找一個(gè)記錄，以它的關(guān)鍵字作為目的：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸，凡其關(guān)鍵字小于樞軸的記錄均

20、樞軸，凡其關(guān)鍵字小于樞軸的記錄均挪動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于挪動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均挪動(dòng)至該記錄之后。樞軸的記錄均挪動(dòng)至該記錄之后。致使一趟排序之后，記錄的無(wú)序序列Rs.t將分割成兩部分：Rs.i-1和Ri+1.t，且 Rj Ri Rk (sji-1) 樞軸 (i+1kt)。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍52 49 80 36 14 58 61 97 23 75stlowhigh設(shè)設(shè) Rs=52 為樞軸為樞軸 將 Rhigh.key 和 樞軸的關(guān)鍵字進(jìn)展比較，要求Rhigh.key 樞軸的關(guān)鍵字 將 Rlow.key 和

21、 樞軸的關(guān)鍵字進(jìn)展比較，要求Rlow.key 樞軸的關(guān)鍵字high23low80high14low52例如例如R052lowhighhighhighlow四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 可見(jiàn)，經(jīng)過(guò)“一次劃分 ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調(diào)整過(guò)程中，設(shè)立了兩個(gè)指針： low 和high，它們的初值分別為： s 和 t， 之后逐漸減小 high，添加 low，并保證 Rhigh52，和 Rlow52,

22、否那么進(jìn)展記錄的“交換。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍快速排序快速排序 首先對(duì)無(wú)序的記錄序列進(jìn)展“一次劃分，之后分別對(duì)分割所得兩個(gè)子序列“遞歸進(jìn)展快速排序。無(wú) 序 的 記 錄 序 列無(wú)序記錄子序列(1)無(wú)序子序列(2)樞軸樞軸一次劃分分別進(jìn)展快速排序四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍堆排序四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍一、簡(jiǎn)單項(xiàng)選擇擇排序一、簡(jiǎn)單項(xiàng)選擇擇排序假設(shè)排序過(guò)程中，待排記錄序列的形狀為：有序序列R1.i-1無(wú)序序列 Ri.n 第 i 趟簡(jiǎn)單項(xiàng)選擇擇排序從中選出關(guān)鍵字

23、最小的記錄有序序列R1.i無(wú)序序列 Ri+1.n四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍二、堆排序二、堆排序堆是滿足以下性質(zhì)的數(shù)列r0, r1, ，rn-1：或或2212iiiirrrr2212iiiirrrr堆的定義堆的定義:(小頂堆)(大頂堆)四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍riR2i+1 r2i+2 假設(shè)將該數(shù)列視作完全二叉樹(shù)，那么 r2i+1 是 ri 的左孩子； r2i+2 是 ri 的右孩子。1236276549817355403498例如

24、例如:是堆是堆14不不四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍堆排序即是利用堆的特性對(duì)記錄序列進(jìn)展排序的一種排序方法。例如：例如：建大頂堆 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, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 經(jīng)過(guò)挑選四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪

25、躍如何如何“建堆？建堆？?jī)蓚€(gè)問(wèn)題兩個(gè)問(wèn)題:如何如何“挑選？挑選？四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍所謂“挑選指的是，對(duì)一棵左/右子樹(shù)均為堆的完全二叉樹(shù)，“調(diào)整根結(jié)點(diǎn)使整個(gè)二叉樹(shù)也成為一個(gè)堆。堆堆挑選挑選四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍98814973556412362740例如例如:是大頂堆是大頂堆12但在 98 和 12 進(jìn)展互換之后，它就不是堆了，因此，需求對(duì)它進(jìn)展“挑選。98128173641298比較比較比較四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍建堆是一個(gè)從下往上進(jìn)展建堆是一

26、個(gè)從下往上進(jìn)展“挑選的過(guò)程。挑選的過(guò)程。40554973816436122798例如例如: 排序之前的關(guān)鍵字序列為排序之前的關(guān)鍵字序列為123681734998817355 如今，左/右子樹(shù)都曾經(jīng)調(diào)整為堆，最后只需調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹(shù)是個(gè)“堆即可。98494064361227四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍基基 數(shù)數(shù) 排排 序序四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍基數(shù)排序是一種借助“多關(guān)鍵字排序的思想來(lái)實(shí)現(xiàn)“單關(guān)鍵字排序的內(nèi)部排序算法。多關(guān)鍵字的排序多關(guān)鍵字的排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師

27、：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍多關(guān)鍵字的排序多關(guān)鍵字的排序 n 個(gè)記錄的序列個(gè)記錄的序列 R1, R2, ，Rn對(duì)關(guān)鍵字對(duì)關(guān)鍵字 (Ki0, Ki1,Kid-1) 有序是有序是指：指： 其中其中: K0 : K0 被稱為被稱為 “最主位關(guān)鍵字最主位關(guān)鍵字Kd-1 被稱為被稱為 “最次位關(guān)鍵字最次位關(guān)鍵字 對(duì)于序列中恣意兩個(gè)記錄 Ri 和 Rj(1ijn) 都滿足以下(詞典)有序關(guān)系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1)四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種作法:最低位優(yōu)先最低位優(yōu)

28、先LSDLSD法法最高位優(yōu)先最高位優(yōu)先MSDMSD法法四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍最高位優(yōu)先最高位優(yōu)先MSDMSD法法先對(duì)先對(duì)K0K0進(jìn)展排序，并按進(jìn)展排序，并按 K0 K0 的不的不同值將記錄序列分成假設(shè)干子序同值將記錄序列分成假設(shè)干子序列之后，分別對(duì)列之后，分別對(duì) K1 K1 進(jìn)展排進(jìn)展排序，序，.， 依次類推，直至最依次類推，直至最后對(duì)最次位關(guān)鍵字排序完成為止。后對(duì)最次位關(guān)鍵字排序完成為止。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍最低位優(yōu)先最低位優(yōu)先LSDLSD法法先對(duì)先對(duì) Kd-1 Kd-1 進(jìn)展排序，然后對(duì)進(jìn)

29、展排序，然后對(duì) Kd-2 Kd-2 進(jìn)展排序，依次類推，直進(jìn)展排序，依次類推，直至對(duì)最主位關(guān)鍵字至對(duì)最主位關(guān)鍵字 K0 K0 排序完成為排序完成為止。止。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍例如例如: :學(xué)生記錄含三個(gè)關(guān)鍵字學(xué)生記錄含三個(gè)關(guān)鍵字: :系別、班號(hào)和班內(nèi)的序列號(hào)，其中以系別、班號(hào)和班內(nèi)的序列號(hào)，其中以系別為最主位關(guān)鍵字。系別為最主位關(guān)鍵字。 無(wú)序序列對(duì)對(duì)K2排序排序?qū)?duì)K1排序排序?qū)?duì)K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,

30、153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序過(guò)程如下的排序過(guò)程如下:四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序假設(shè)多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的取值范圍一樣，那么按LSD法進(jìn)展排序時(shí)，可以采用“分配-搜集的方法，其益處是不需求進(jìn)展關(guān)鍵字間的比較。對(duì)于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用這種“分配-搜集的方法進(jìn)展排序，稱作基數(shù)排序法。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍例如：對(duì)以下這組關(guān)鍵字例如：對(duì)

31、以下這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “個(gè)位數(shù) 取值分別為 0, 1, , 9 “分配 成 10 組，之后按從 0 至 9 的順序?qū)?它們 “搜集 在一同； 然后按其 “十位數(shù) 取值分別為 0, 1, , 9 “分配 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈?“搜集 在一同；最后按其“百位數(shù)反復(fù)一遍上述操作。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍在計(jì)算機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，應(yīng)采用鏈表作存儲(chǔ)構(gòu)造，即鏈?zhǔn)交鶖?shù)排序，詳細(xì)作法為： 待排序記錄以指針相鏈，構(gòu)成一個(gè)

32、鏈表；“分配分配 時(shí)，按當(dāng)前時(shí)，按當(dāng)前“關(guān)鍵字位所關(guān)鍵字位所取值，將記錄分配到不同的取值，將記錄分配到不同的 “鏈隊(duì)列鏈隊(duì)列 中，每個(gè)隊(duì)列中記錄的中，每個(gè)隊(duì)列中記錄的 “關(guān)鍵字位關(guān)鍵字位 一一樣；樣；“搜集時(shí)，按當(dāng)前關(guān)鍵字位取值從搜集時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大將各隊(duì)列首尾相鏈成一個(gè)鏈表小到大將各隊(duì)列首尾相鏈成一個(gè)鏈表; ;對(duì)每個(gè)關(guān)鍵字位均反復(fù)對(duì)每個(gè)關(guān)鍵字位均反復(fù) 2) 2) 和和 3) 3) 兩步。兩步。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍例如：p369367167239237230進(jìn)展第一次分配進(jìn)展第一次分配進(jìn)展第一次搜集進(jìn)展第一次搜集f0 r0f7

33、r7f8 r8f9 r9p230230367 167237367167237368239369 239四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍進(jìn)展第二次分配進(jìn)展第二次分配p230237239p230367167237368239f3 r3f6 r6230 237239367 167368367167368進(jìn)展第二次搜集四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 進(jìn)展第三次搜集之后便得到記錄的有序序列f1 r1p230237239367167368進(jìn)展第三次分配進(jìn)展第三次分配f2 r2f3 r3 167230 237239367 36

34、8p167230237239367368四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+rd)其中：分配為O(n) 搜集為O(rd)(rd為“基) d為“分配-搜集的趟數(shù)四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍各種排序方法的綜合比較各種排序方法的綜合比較四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍一、時(shí)間性能一、時(shí)間性能1. 平均的時(shí)間性能平均的時(shí)間性能基數(shù)排序基數(shù)排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(nlogn)：快速排序、堆排序和歸并排序快速排序、堆排序和歸并排序時(shí)間復(fù)雜度為

35、時(shí)間復(fù)雜度為 O(n2) O(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和簡(jiǎn)單項(xiàng)選擇擇排序簡(jiǎn)單項(xiàng)選擇擇排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n):四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍2. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)3. 簡(jiǎn)單項(xiàng)選擇擇排序、堆排序和歸并排簡(jiǎn)單項(xiàng)選擇擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改動(dòng)。分布而改動(dòng)。 直接插入排序和起泡排序能到達(dá)O(n)的時(shí)間復(fù)雜度， 快速排序的時(shí)間性能蛻化為O(n2) 。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)

36、學(xué)院，主講教師：游洪躍排序方法的穩(wěn)定性能排序方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對(duì)于兩個(gè)關(guān)鍵字相等的記錄，它們?cè)谛蛄兄械南鄬?duì)位置，在排序之前和經(jīng)過(guò)排序之后，沒(méi)有改動(dòng)。 2. 當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)展當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)展LSD方法排序時(shí)，必需采用穩(wěn)定的排序方方法排序時(shí)，必需采用穩(wěn)定的排序方法。法。排序之前 : Ri(K) Rj(K) 排序之后 : Ri(K) Rj(K) 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍例如：例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )假設(shè)排序后得到結(jié)果 ( 18, 23, 34, 4

37、7, 47, 56, 66, 82 )那么稱該排序方法是穩(wěn)定的;假設(shè)排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 )那么稱該排序方法是不穩(wěn)定的。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 3. 對(duì)于不穩(wěn)定的排序方法，只需能對(duì)于不穩(wěn)定的排序方法，只需能舉出一個(gè)實(shí)例闡明即可。舉出一個(gè)實(shí)例闡明即可。 4. 快速排序、一切選擇排序快速排序、一切選擇排序(包括堆排序包括堆排序和希爾排序是不穩(wěn)定的排序方法。和希爾排序是不穩(wěn)定的排序方法。例如例如 : 對(duì)對(duì) 4, 3, 4, 2 進(jìn)展快速排序，進(jìn)展快速排序， 得到得到 2, 3, 4, 4 四

38、川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍外外 部部 排排 序序四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍一一. 問(wèn)題的提出問(wèn)題的提出 待排序的記錄數(shù)量很大，不能一次裝入內(nèi)存，那么無(wú)法利用前幾節(jié)討論的排序方法 ；四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 按可用內(nèi)存大小，利用內(nèi)部排序按可用內(nèi)存大小，利用內(nèi)部排序 方法，構(gòu)造假設(shè)干方法，構(gòu)造假設(shè)干( 記錄的記錄的) 有序子序列，有序子序列，通常稱外存中這些記錄有序子序列為通常稱外存中這些記錄有序子序列為 “歸并段；歸并段；二、外部排序的根本過(guò)程二、外部排序的根

39、本過(guò)程由相對(duì)獨(dú)立的兩個(gè)步驟組成： 經(jīng)過(guò)經(jīng)過(guò)“歸并，逐漸擴(kuò)展歸并，逐漸擴(kuò)展 (記錄的記錄的)有序子序列的長(zhǎng)度，直至外存中整個(gè)記有序子序列的長(zhǎng)度，直至外存中整個(gè)記錄序列按關(guān)鍵字有序?yàn)橹埂ｄ浶蛄邪搓P(guān)鍵字有序?yàn)橹?。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍例如：假設(shè)有一個(gè)含例如：假設(shè)有一個(gè)含10,000個(gè)記錄的磁盤個(gè)記錄的磁盤 文件，而當(dāng)前所用的計(jì)算機(jī)一次只文件，而當(dāng)前所用的計(jì)算機(jī)一次只 能對(duì)能對(duì)1000個(gè)記錄進(jìn)展內(nèi)部排序，那么個(gè)記錄進(jìn)展內(nèi)部排序，那么 首先利用內(nèi)部排序的方法得到首先利用內(nèi)部排序的方法得到10個(gè)個(gè) 初始?xì)w并段，然后進(jìn)展逐趟歸并。初始?xì)w并段，然后進(jìn)展逐趟歸并

40、。假設(shè)進(jìn)展2路歸并(即兩兩歸并)，那么第一趟由10個(gè)歸并段得到5個(gè)歸并段；最后一趟歸并得到整個(gè)記錄的有序序列。最后一趟歸并得到整個(gè)記錄的有序序列。第三趟由第三趟由 3 個(gè)歸并段得到個(gè)歸并段得到2個(gè)歸并段；個(gè)歸并段；第二趟由第二趟由 5 個(gè)歸并段得到個(gè)歸并段得到3個(gè)歸并段；個(gè)歸并段；四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍假設(shè)“數(shù)據(jù)塊的大小為200，即每一次訪問(wèn)外存可以讀/寫200個(gè)記錄。那么對(duì)于10,000個(gè)記錄，處置一遍需訪問(wèn)外存100次(讀和寫各50次)。分析上述外排過(guò)程中訪問(wèn)外存(對(duì)外存進(jìn)展讀/寫)的次數(shù)：四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)

41、學(xué)院，主講教師：游洪躍由此，對(duì)上述例子而言， 1)求得10個(gè)初始?xì)w并段需訪問(wèn)外存100次； 2)每進(jìn)展一趟歸并需訪問(wèn)外存100次； 3)總計(jì)訪問(wèn)外存 100 + 4 100 = 500次。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 外排總的時(shí)間還應(yīng)包括內(nèi)部排序所需時(shí)間和逐趟歸并時(shí)進(jìn)展內(nèi)部歸并的時(shí)間，顯然，除去內(nèi)部排序的要素外，外部排序的時(shí)間取決于逐趟歸并所需進(jìn)展的“趟數(shù)。例如，假設(shè)對(duì)上述例子采用例如，假設(shè)對(duì)上述例子采用5路歸并，路歸并，那么只需進(jìn)展那么只需進(jìn)展2趟歸并，總的訪問(wèn)外存的趟歸并，總的訪問(wèn)外存的次數(shù)將緊縮到次數(shù)將緊縮到 100 + 2 100 = 300

42、 次。次。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 普通情況下，假設(shè)待排記錄序列含 m 個(gè)初始?xì)w并段，外排時(shí)采用 k路歸并，那么歸并趟數(shù)為 logkm，顯然，隨之k的增大歸并的趟數(shù)將減少，因此對(duì)外排而言，通常采用多路歸并。k 的大小可選，但需綜合思索各種要素。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍第第10章章 文件文件四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍有關(guān)文件的根本概念有關(guān)文件的根本概念四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍一、文件即為記錄的集合，和一、文件

43、即為記錄的集合，和“查找查找 表的差別在于，表的差別在于，“文件指的是存文件指的是存 儲(chǔ)在外存儲(chǔ)器中的記錄的集合。儲(chǔ)在外存儲(chǔ)器中的記錄的集合。 記錄是文件中可以存取的數(shù)據(jù)的記錄是文件中可以存取的數(shù)據(jù)的 根本單位。根本單位。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍二、文件可按其中記錄的類型不同而二、文件可按其中記錄的類型不同而 分成兩類：分成兩類：其一為操作系統(tǒng)的文件，文件中的記 錄僅是一個(gè)字符組。由于操作系 統(tǒng)中的文件僅是一維的延續(xù)字符 序列，為了用戶存取和加工的方 便，將文件中的信息劃分為假設(shè)干 組，其中每一組信息稱作一個(gè)記 錄；四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：

44、游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍其二為數(shù)據(jù)庫(kù)文件，文件中的記錄帶 有構(gòu)造，是數(shù)據(jù)項(xiàng)的集合。記錄 是文件中可以存取的數(shù)據(jù)根本單 位，數(shù)據(jù)項(xiàng)是文件中可以運(yùn)用的 數(shù)據(jù)最小單位。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍三、記錄中能識(shí)別不同記錄的數(shù)據(jù)項(xiàng)三、記錄中能識(shí)別不同記錄的數(shù)據(jù)項(xiàng) 被稱為關(guān)鍵字，假設(shè)該數(shù)據(jù)項(xiàng)能唯被稱為關(guān)鍵字，假設(shè)該數(shù)據(jù)項(xiàng)能唯 一識(shí)別一個(gè)記錄，那么稱為主關(guān)鍵一識(shí)別一個(gè)記錄，那么稱為主關(guān)鍵 字，假設(shè)能識(shí)別多個(gè)記錄那么稱為次字，假設(shè)能識(shí)別多個(gè)記錄那么稱為次 關(guān)鍵字。關(guān)鍵字。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四、

45、文件的邏輯構(gòu)造指的是呈如今用四、文件的邏輯構(gòu)造指的是呈如今用 戶面前的文件中記錄之間的邏輯戶面前的文件中記錄之間的邏輯 關(guān)系；文件的物理構(gòu)造指的是文關(guān)系；文件的物理構(gòu)造指的是文 件中的邏輯記錄在存儲(chǔ)器中的組件中的邏輯記錄在存儲(chǔ)器中的組 織方式。織方式。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍順順 序序 文文 件件四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍結(jié)結(jié) 構(gòu)構(gòu) 特特 點(diǎn)：點(diǎn)： 記錄在文件中的陳列順序是由記錄進(jìn)入存儲(chǔ)介質(zhì)的次序決議的， 即文件物理構(gòu)造中記錄的陳列順序和文件的邏輯構(gòu)造中記錄的陳列順序一致。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師

46、：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍操作特點(diǎn)：操作特點(diǎn)： 1便于進(jìn)展順序存??； 2不便于進(jìn)展直接存取，為取第i個(gè)記錄，必需先讀出前i-1個(gè)記錄；四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 3插入新的記錄只能加在文件的末尾； 4刪除記錄時(shí)，只作標(biāo)志； 5更新記錄必需生成新的文件。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍索索 引引 文文 件件四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 1索引文件由“主文件和“索引組成； 2索引中的每個(gè)記錄由“關(guān)鍵字和“指針組成； 3通常，索引文件中的主文件是無(wú)序文件

47、，索引是 (按關(guān)鍵字有序)的有序文件； 4“索引是在輸入數(shù)據(jù)建立文件時(shí)自動(dòng)生成。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍二、二、VSAM文件文件VSAM(Vistual Storage Access Method) 文件是利用操作系統(tǒng)中提供的虛擬存儲(chǔ)器的功能組織的文件，免除了用戶為讀/寫記錄時(shí)直接對(duì)外存進(jìn)展的操作，對(duì)用戶而言，文件只需控制區(qū)間和控制區(qū)域等邏輯存儲(chǔ)單位。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 . 索引集B+樹(shù) 順序集控制區(qū)域控制區(qū)間數(shù)據(jù)集數(shù)據(jù)集1 1文件的構(gòu)造文件的構(gòu)造四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)

48、算機(jī)學(xué)院，主講教師：游洪躍 2. 控制區(qū)間是用戶進(jìn)展一次存取的邏輯單位，可看成是一個(gè)邏輯磁道。但它的實(shí)踐大小和物理磁道無(wú)關(guān)。 VSAM文件初建時(shí)，每個(gè)控制區(qū)間內(nèi)的記錄數(shù)缺乏額定數(shù)，并且有的控制區(qū)間內(nèi)的記錄數(shù)為零。 控制區(qū)域由假設(shè)干控制區(qū)間和它們控制區(qū)域由假設(shè)干控制區(qū)間和它們的索引項(xiàng)組成，可看成是一個(gè)邏輯柱面。的索引項(xiàng)組成，可看成是一個(gè)邏輯柱面。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍順序集本身是一個(gè)單鏈表，它包含文件的全部索引項(xiàng)，同時(shí)，順序集中的每個(gè)結(jié)點(diǎn)即為B+樹(shù)的葉子結(jié)點(diǎn)，索引集中的結(jié)點(diǎn)即為B+樹(shù)的非葉結(jié)點(diǎn)。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)

49、院，主講教師：游洪躍文件的操作文件的操作 檢索：可進(jìn)展順序存取和按關(guān)鍵字存取；檢索：可進(jìn)展順序存取和按關(guān)鍵字存取； 插入：按關(guān)鍵字大小插入在某個(gè)適當(dāng)?shù)牟迦耄喊搓P(guān)鍵字大小插入在某個(gè)適當(dāng)?shù)目刂茀^(qū)間中，當(dāng)控制區(qū)間中的記錄數(shù)超控制區(qū)間中，當(dāng)控制區(qū)間中的記錄數(shù)超越文件規(guī)定的大小時(shí)，要越文件規(guī)定的大小時(shí)，要“分裂控制分裂控制區(qū)間，必要時(shí)，還需求區(qū)間，必要時(shí)，還需求“分裂控制區(qū)分裂控制區(qū)域；域； 刪除：必需刪除：必需“真實(shí)地刪除記錄，因此真實(shí)地刪除記錄，因此要在控制區(qū)間內(nèi)要在控制區(qū)間內(nèi)“挪動(dòng)記錄。挪動(dòng)記錄。四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍直直 接接 存存 取取 文文 件件四川大學(xué)計(jì)算機(jī)學(xué)院，