數(shù)據(jù)結(jié)構(gòu)用C語言描述PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)用數(shù)據(jù)結(jié)構(gòu)用C語言描述語言描述。第1頁/共79頁全部對(duì)象個(gè)數(shù)太多，不能同時(shí)存全部對(duì)象個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過程的放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動(dòng)要求，不斷在內(nèi)、外存之間移動(dòng)的排序。的排序。第2頁/共79頁第3頁/共79頁-o(d.n)第4頁/共79頁基本思想基本思想 每步將一個(gè)待排序的對(duì)象每步將一個(gè)待排序的對(duì)象, 按其按其關(guān)鍵字大小關(guān)鍵字大小, 插入到前面已經(jīng)排好序的一組插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上對(duì)象的適當(dāng)位置上, 直到對(duì)象全部插入為止。直到對(duì)象全部插入為止。直接插入排序直接插入排序 (Insert Sort)第5頁/

2、共79頁直接插入直接插入排序過程排序過程0 1 2 3 4 5 temp i = 1i = 20 1 2 3 4 5 temp252525494949i = 3252525*第6頁/共79頁i = 4i = 5161616161616080808第7頁/共79頁直接插入排序的算法直接插入排序的算法 InsertSort ( rectype R , int n ) int i, j; for ( i = 2; i n; i+ ) R0= Ri; j = i 1 ; /從后向前順序比較從后向前順序比較 while ( R0.key Rj.key ) Rj+1 = Rj-; Rj+1 = R0; 第

3、8頁/共79頁第9頁/共79頁。因此，直接插入排序的時(shí)間復(fù)因此，直接插入排序的時(shí)間復(fù)雜度為雜度為 o(n2)。n直接插入排序是一種穩(wěn)定的排直接插入排序是一種穩(wěn)定的排序方法。序方法。111122142221nininnniRMNnnniKCN/)()( ,/)(22第10頁/共79頁折半插入排序的算法折半插入排序的算法第11頁/共79頁typedef int SortData; Roid BinInsSort ( SortData R , int n ) SortData temp; int Left, Right; for ( int i = 1; i n; i+) Left = 0; Rig

4、ht = i- -1; temp = Ri; while ( Left = Right ) int mid = ( Left + Right )/2; if ( temp = Left; k- ) Rk+1 = Rk;/記錄后移記錄后移 RLeft = temp; /插入插入 第12頁/共79頁0 1 2 3 4 5 temp i = 1i = 20 1 2 3 4 5 temp333i = 3555444i = 4888i = 5161616第13頁/共79頁次數(shù)為：次數(shù)為： 1122log1logninni算法分析算法分析 第14頁/共79頁n序方法。序方法。n折半插入排序的時(shí)間復(fù)雜度為折

5、半插入排序的時(shí)間復(fù)雜度為o(n2)。第15頁/共79頁個(gè)序列中排序?yàn)橹?。個(gè)序列中排序?yàn)橹埂希爾排序方法又稱為縮小增量排希爾排序方法又稱為縮小增量排序。序。第16頁/共79頁i = 3Gap = 30 1 2 3 4 50 1 2 3 4 5i = 2Gap = 2i = 1Gap = 1希爾排序過程希爾排序過程第17頁/共79頁 ShellSort ( rectype R , int n ) rectype temp; int gap = n / 2; /gap是間隔是間隔 while ( gap != 0 ) /循環(huán)循環(huán),直到直到gap為零為零 for ( int i = gap; i =

6、 gap; j = j- -gap ) if ( temp Rj- -gap ) Rj = Rj- -gap; else break; Rj = temp; gap = ( int ) ( gap / 2 ); 希爾排序的算法希爾排序的算法第18頁/共79頁n開始時(shí)開始時(shí) gap 的值較大的值較大, 子序列中的對(duì)象較少子序列中的對(duì)象較少, 排序速排序速度較快度較快; 隨著排序進(jìn)展隨著排序進(jìn)展, gap 值逐漸變小值逐漸變小, 子序列中子序列中對(duì)象個(gè)數(shù)逐漸變多對(duì)象個(gè)數(shù)逐漸變多, 由于前面大多數(shù)對(duì)象已基本有由于前面大多數(shù)對(duì)象已基本有序序, 所以排序速度仍然很快。所以排序速度仍然很快。nGap的取法

7、有多種。的取法有多種。 shell 提出取提出取 gap = n/2 ，gap = gap/2 ，直到，直到gap = 1。n對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算關(guān)鍵字對(duì)特定的待排序?qū)ο笮蛄校梢詼?zhǔn)確地估算關(guān)鍵字的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。n希爾排序所需的比較次數(shù)和移動(dòng)次數(shù)約為希爾排序所需的比較次數(shù)和移動(dòng)次數(shù)約為n 1.3當(dāng)當(dāng)n趨于無窮時(shí)可減少到趨于無窮時(shí)可減少到n(log2 n)2第19頁/共79頁基本思想基本思想是兩兩比較待排序?qū)ο蟮年P(guān)鍵字是兩兩比較待排序?qū)ο蟮年P(guān)鍵字, ,如發(fā)生逆序如發(fā)生逆序( (即排列順序與排序后的次序正即排列順序與排序后的次序正好相反好相反)

8、 )，則交換之，則交換之, ,直到所有對(duì)象都排好序直到所有對(duì)象都排好序?yàn)橹埂橹?。起泡排序起泡排?(Bubble Sort)第20頁/共79頁初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序起泡排序的過程起泡排序的過程第21頁/共79頁初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序起泡排序的過程起泡排序的過程第22頁/共79頁第23頁/共79頁 n第第 i 趟 對(duì) 待 排 序 對(duì) 象 序 列趟 對(duì) 待 排 序 對(duì) 象 序 列 R i - -1,Ri,Rn- -1進(jìn)行排序進(jìn)行排序, 結(jié)果將該序列結(jié)果將該序列中關(guān)鍵字最小的對(duì)象交換到序列的第一個(gè)中關(guān)鍵字最小的對(duì)象交換到序

9、列的第一個(gè)位置位置(i- -1), 其它對(duì)象也都向排序的最終位其它對(duì)象也都向排序的最終位置移動(dòng)。置移動(dòng)。n最多做最多做n- -1趟起泡就能把所有對(duì)象排好序趟起泡就能把所有對(duì)象排好序。n在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí)排好序時(shí), ,此算法只執(zhí)行一趟起泡此算法只執(zhí)行一趟起泡, ,做做n- -1次關(guān)鍵字比較次關(guān)鍵字比較, ,不移動(dòng)對(duì)象。這是最好的不移動(dòng)對(duì)象。這是最好的情形。情形。第24頁/共79頁11111233121nininninRMNnninKCN)()()()(n起泡排序是一個(gè)穩(wěn)定的排序方法。起泡排序是一個(gè)穩(wěn)定的排序方法。第25頁/共79頁第2

10、6頁/共79頁第27頁/共79頁QuickSort ( List ) if ( List的長度大于的長度大于1) 將序列將序列List劃分為兩個(gè)子序列劃分為兩個(gè)子序列 LeftList 和和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 將兩個(gè)子序列將兩個(gè)子序列 LeftList 和和 RightList 合并為一個(gè)序列合并為一個(gè)序列List; 快速排序算法描述快速排序算法描述第28頁/共79頁快速排序的過程快速排序的過程初始關(guān)鍵字初始關(guān)鍵字prikey一次交換一次交換二次交換二次交換三次交換三次交換四次交換四次交換完成

11、一趟排序完成一趟排序ijijjiijjiji第29頁/共79頁完成一趟排序完成一趟排序分別進(jìn)行快速排序分別進(jìn)行快速排序有序序列有序序列第30頁/共79頁快速排序的算法快速排序的算法 QuickSort ( rectype R , int low, int high ) /在序列在序列l(wèi)ow high 中遞歸地進(jìn)行快速排序中遞歸地進(jìn)行快速排序 if ( low high) int i = Partition ( R, low, high); /劃分劃分 QuickSort ( R, low, i - -1); /對(duì)左序列同樣處理對(duì)左序列同樣處理 QuickSort ( R, i +1, high

12、); /對(duì)右序列同樣處理對(duì)右序列同樣處理 第31頁/共79頁int Partition ( rectype R , int low, int high ) R0=Rlow;/子表的第一個(gè)記錄作基準(zhǔn)對(duì)象子表的第一個(gè)記錄作基準(zhǔn)對(duì)象 tempkey = Rlow.key; /基準(zhǔn)對(duì)象關(guān)鍵字基準(zhǔn)對(duì)象關(guān)鍵字 While(lowhigh) While(low= tempkey) high-; Rlow = Rhigh; /小于基準(zhǔn)的移到區(qū)間的左小于基準(zhǔn)的移到區(qū)間的左側(cè)側(cè) While(lowhigh& Rlow.key = tempkey) low+; Rhigh = Rlow ; /大于基準(zhǔn)的移到區(qū)間的右

13、大于基準(zhǔn)的移到區(qū)間的右側(cè)側(cè) Rlow = R0; return low; 第32頁/共79頁, 到位到位, 函數(shù)返回其位置。函數(shù)返回其位置。第33頁/共79頁, 對(duì)對(duì) 象正確定位后象正確定位后, 正好把序列劃正好把序列劃分為長度相等的兩個(gè)子序列分為長度相等的兩個(gè)子序列, 此此時(shí)時(shí), 總的計(jì)算時(shí)間為：總的計(jì)算時(shí)間為：第34頁/共79頁棧存放每層遞歸調(diào)用時(shí)的指針和棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)。參數(shù)。第35頁/共79頁n快速排序是一種不穩(wěn)定的排序快速排序是一種不穩(wěn)定的排序方法。方法。2121211nnninni)()(第36頁/共79頁基本思想基本思想 每一趟每一趟 (例如第例如第 i 趟趟,

14、i = 0, 1, , n- -2) 在后面在后面 n- -i 個(gè)待排序個(gè)待排序記錄中選出關(guān)鍵字最小的記錄記錄中選出關(guān)鍵字最小的記錄, 作為作為有序序列中的第有序序列中的第 i 個(gè)記錄。待到第個(gè)記錄。待到第n- -2 趟作完趟作完, 待排序記錄只剩下待排序記錄只剩下1個(gè)個(gè),就不用再選了。就不用再選了。第37頁/共79頁n直接選擇排序是一種簡單的排序方法直接選擇排序是一種簡單的排序方法, 它它的基本步驟是：的基本步驟是： 在一組對(duì)象在一組對(duì)象 RiRn- -1 中選擇具有中選擇具有最小關(guān)鍵字的對(duì)象；最小關(guān)鍵字的對(duì)象；若它不是這組對(duì)象中的第一個(gè)對(duì)象若它不是這組對(duì)象中的第一個(gè)對(duì)象, 則則將它與這組對(duì)

15、象中的第一個(gè)對(duì)象對(duì)調(diào)將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào); 在這組對(duì)象中剔除這個(gè)具有最小關(guān)鍵在這組對(duì)象中剔除這個(gè)具有最小關(guān)鍵字的對(duì)象。在剩下的對(duì)象字的對(duì)象。在剩下的對(duì)象Ri+1Rn-1中重復(fù)執(zhí)行第、步中重復(fù)執(zhí)行第、步, 直到剩余對(duì)直到剩余對(duì)象只有一個(gè)為止。象只有一個(gè)為止。直接選擇排序直接選擇排序 (Select Sort)第38頁/共79頁0 1 2 3 4 5最小者最小者最小者最小者最小者最小者 直接選擇排序的過程直接選擇排序的過程第39頁/共79頁最小者最小者0 1 2 3 4 5結(jié)果結(jié)果最小者最小者各趟排序后的結(jié)果各趟排序后的結(jié)果第40頁/共79頁直接選擇排序的算法直接選擇排序的算法Sele

16、ctSort ( rectype R , int n ) int i,j ,k; rectype temp; for ( i = 0; i n- -1; i+ ) k = i; /選擇具有最小關(guān)鍵字的對(duì)象選擇具有最小關(guān)鍵字的對(duì)象 for ( j = i+1; j n; j+) if ( Rj.key Rk.key ) k = j; /當(dāng)前具最小關(guān)鍵字的對(duì)象當(dāng)前具最小關(guān)鍵字的對(duì)象 if ( k != i ) /對(duì)換到第對(duì)換到第 i 個(gè)位置個(gè)位置 temp =Ri; Ri =Rk ; Rk = temp ; 第41頁/共79頁n直接選擇排序的關(guān)鍵字比較次數(shù)直接選擇排序的關(guān)鍵字比較次數(shù) KCN 與對(duì)

17、象的與對(duì)象的初始排列無關(guān)。設(shè)整個(gè)待排序?qū)ο笮蛄杏谐跏寂帕袩o關(guān)。設(shè)整個(gè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)個(gè)對(duì)象象, 則第則第 i 趟選擇具有最小關(guān)鍵字對(duì)象所需的比趟選擇具有最小關(guān)鍵字對(duì)象所需的比較次數(shù)總是較次數(shù)總是 n- -i- -1 次?？偟年P(guān)鍵字比較次數(shù)為次?？偟年P(guān)鍵字比較次數(shù)為20211ninninKCN)()(n對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)是按其關(guān)鍵字從小到大有序這組對(duì)象的初始狀態(tài)是按其關(guān)鍵字從小到大有序的時(shí)候的時(shí)候, 對(duì)象的移動(dòng)次數(shù)對(duì)象的移動(dòng)次數(shù)RMN = 0，達(dá)到最少。，達(dá)到最少。n最壞情況是每一趟都要進(jìn)行交換，總的對(duì)

18、象移動(dòng)最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為次數(shù)為 RMN = 3(n- -1)。n直接選擇排序是一種不穩(wěn)定的排序方法。直接選擇排序是一種不穩(wěn)定的排序方法。第42頁/共79頁堆堆 ( Heap )設(shè)有一個(gè)關(guān)鍵字集合，按完設(shè)有一個(gè)關(guān)鍵字集合，按完全二叉樹的順序存儲(chǔ)方式存放在一個(gè)一維全二叉樹的順序存儲(chǔ)方式存放在一個(gè)一維數(shù)組中。對(duì)它們從根開始，自頂向下，同數(shù)組中。對(duì)它們從根開始，自頂向下，同一層自左向右從一層自左向右從 0開始連續(xù)編號(hào)。若滿足開始連續(xù)編號(hào)。若滿足 Ki K2i & Ki K2i+1或或 Ki K2i & Ki K2i+1, 則稱該關(guān)鍵字集合構(gòu)成一個(gè)堆。則稱該關(guān)鍵字集合構(gòu)成一

19、個(gè)堆。 前者成為小根堆，后者稱為大根堆。前者成為小根堆，后者稱為大根堆。第43頁/共79頁完全二叉樹完全二叉樹 順序表示順序表示Ki K2i &Ki K2i+1完全二叉樹完全二叉樹 順序表示順序表示Ki K2i &Ki K2i+1090987877878454565653131532323531717第44頁/共79頁堆排序堆排序 (Heap Sort)n利用堆及其運(yùn)算利用堆及其運(yùn)算, 可以很容易地實(shí)現(xiàn)選擇排可以很容易地實(shí)現(xiàn)選擇排序的思路。序的思路。n堆排序分為兩個(gè)步驟堆排序分為兩個(gè)步驟u 根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法 SIFT( ) 形成初始堆形成初始

20、堆;u 通過一系列的對(duì)象交換和重新調(diào)整堆進(jìn)通過一系列的對(duì)象交換和重新調(diào)整堆進(jìn)行排序。行排序。第45頁/共79頁自下向上逐步調(diào)整為小根堆自下向上逐步調(diào)整為小根堆5353171778780923456587i0923456587 i = 4i = 3i初始小根堆的建立過程初始小根堆的建立過程第46頁/共79頁5353171778780923456587i0923456587i = 2i第47頁/共79頁53171778780923456587i0923456587i = 1i53第48頁/共79頁53171778780923456587i0923456587i53建成堆建成堆第49頁/共79頁初始

21、大根堆的建立過程初始大根堆的建立過程123456136542初始關(guān)鍵字集合初始關(guān)鍵字集合i = 3 時(shí)的局部調(diào)整時(shí)的局部調(diào)整第50頁/共79頁123456136542i = 1 時(shí)的局部調(diào)整時(shí)的局部調(diào)整形成大根堆形成大根堆i = 2 時(shí)的局部調(diào)整時(shí)的局部調(diào)整第51頁/共79頁SIFT ( rectype R , int i, int m ) int j =2*i; rectype temp = Ri; while ( j = m) if ( j m & Rj.key = Rj ) break; else 第52頁/共79頁 Ri = Rj; /大大子女上移子女上移 i = j; j = 2*i

22、; /向下繼續(xù)調(diào)整向下繼續(xù)調(diào)整 Ri = temp; /回放到合適位置回放到合適位置將表轉(zhuǎn)換成堆將表轉(zhuǎn)換成堆for ( i = n / 2 ; i = 1; i- ) SIFT ( R, i, n );第53頁/共79頁。n如此反復(fù)執(zhí)行，最后得到全部排如此反復(fù)執(zhí)行，最后得到全部排序好的對(duì)象序列。這個(gè)算法即堆序好的對(duì)象序列。這個(gè)算法即堆排序算法，排序算法，第54頁/共79頁012345025431基于初始堆進(jìn)行堆排序基于初始堆進(jìn)行堆排序第55頁/共79頁012345025431第56頁/共79頁012345025431第57頁/共79頁012345025431第58頁/共79頁012345025

23、431第59頁/共79頁堆排序的算法堆排序的算法HeapSort ( rectype R ) /對(duì)表對(duì)表R1到到Rn進(jìn)行排序進(jìn)行排序, 使得表中使得表中對(duì)象關(guān)鍵字非遞減有序。對(duì)象關(guān)鍵字非遞減有序。 int i; rectype temp; for ( i = n / 2; i = 1; i- ) SIFT ( R, i, n ); /初始堆初始堆 for ( i = n; i = 1; i-) temp = R1; R1= Ri; /交換交換 Ri =temp; SIFT ( R, 1, i- -1 ); /重建最大堆重建最大堆 第60頁/共79頁n其中其中, i 是層序號(hào)是層序號(hào), 2i 是

24、第是第 i 層的層的最大結(jié)點(diǎn)數(shù)最大結(jié)點(diǎn)數(shù), (k- -i- -1)是第是第 i 層結(jié)層結(jié)點(diǎn)能夠移動(dòng)的最大距離。點(diǎn)能夠移動(dòng)的最大距離。2022kiiik1 1堆排序的算法分析堆排序的算法分析第61頁/共79頁n堆排序是一個(gè)不穩(wěn)定的排序方法。堆排序是一個(gè)不穩(wěn)定的排序方法。njnjjikkjkjjjkkjjkkii4 411111111202222222122)(第62頁/共79頁第63頁/共79頁08 21 25 25* 49 62 72 93 16 37 54 low mid mid+1 highR08 16 21 25 25* 37 49 54 62 72 93 low highkR1ij第6

25、4頁/共79頁merge ( rectype R , rectype R1 , int low, int mid, int high ) int i = low, j = mid+1, k = low; while ( i = mid & j = high ) /兩兩比較將較小的并入兩兩比較將較小的并入 if ( Ri = Rj ) R1 k = Ri; i+; k+; else R1 k = Rj; j+; k+; while ( i = mid ) R1k = Ri; i+; k+; /將將mid前剩余的并入前剩余的并入 while ( j = high ) R1k = Rj; j+; k

26、+; /將將mid后剩余的并入后剩余的并入兩路歸并算法兩路歸并算法第65頁/共79頁len, 將它直接抄到將它直接抄到R1 中。中。第66頁/共79頁最后得到一個(gè)長度為最后得到一個(gè)長度為 n 的有序序的有序序列。列。第67頁/共79頁第68頁/共79頁 MergePass ( rectype R , rectype R1 , int len ) int i = 0; while (i+2*len- -1 = n- -1) merge( R, R1, i, i+len- -1, i+2*len- -1); i += 2 * len; /循環(huán)兩兩歸并循環(huán)兩兩歸并 if ( i+len = n- -

27、1 ) merge( R, R1, i, i+len- -1, n- -1); else for ( int j = i; j = n- -1; j+) R1 j = Rj; 第69頁/共79頁v歸并排序的主算法歸并排序的主算法 MergeSort ( rectype R , int n ) /按對(duì)象關(guān)鍵字非遞減的順序?qū)Ρ碇袑?duì)象排序按對(duì)象關(guān)鍵字非遞減的順序?qū)Ρ碇袑?duì)象排序 rectype R1n; int len = 1; while ( len n ) MergePass ( R, R1, len ); len *= 2;MergePass ( R1, R, len ); len *= 2; 第70頁/共79頁n歸并排序是一個(gè)穩(wěn)定的排序方法。歸并排序是一個(gè)穩(wěn)定的排序方法。第71頁/共79頁多關(guān)鍵字排序多關(guān)鍵字排序例例 對(duì)對(duì)52張撲克牌按以下次序排序：張撲克牌按以下次序排序：23A23A23A23A兩個(gè)關(guān)鍵字：花色兩個(gè)關(guān)鍵字：花色（ ） 面值面值（23A）并且并且“花色花色”地位高于地位高于“面值面值”多關(guān)鍵字排序方法多關(guān)鍵字排序方法最高位優(yōu)先法（最高位優(yōu)先法（MSD)：先對(duì)最高位關(guān)鍵字先對(duì)最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的k1值；然后讓每個(gè)子序列對(duì)次關(guān)鍵字值；然后讓每個(gè)子序列對(duì)次關(guān)鍵