數(shù)據(jù)結(jié)構(gòu)各種排序算法的課程設(shè)計實驗報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數(shù)：34 大?。?75.97KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)各種排序算法的課程設(shè)計實驗報告_第1頁

已閱讀1頁，還剩33頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè)計報告　　課程名稱：數(shù)據(jù)結(jié)構(gòu) 　　設(shè)計題目：排序算法實現(xiàn)及比較 　　系別：計算機信

2、息工程學(xué)院 　　專業(yè)：計算機科學(xué)與技術(shù) 　　組別：第*組 　　起止日期: 12 年 5 月 1 日 ~ 12

3、年 6月 1 日 　　指導(dǎo)教師: *** 　　計算機與信息工程學(xué)院二○一二年制　　課程設(shè)計任務(wù)書　　目錄</p&g

4、t;　　1.引言4　　2.需求分析4　　3.詳細(xì)設(shè)計4　　3.1 直接插入排序4　　3.2折半排序5<

5、/b>　　3.3 希爾排序6　　3.4簡單選擇排序6　　3.5堆排序6　　3.6歸并排序7　　3.7冒泡排序9</

6、b>　　4.調(diào)試10　　5.調(diào)試及檢驗11　　5.1 直接插入排序11　　5.2折半插入排序11　　5.3 希爾排序12　　5.4簡單

7、選擇排序12　　5.5堆排序13　　5.6歸并排序14　　5.7冒泡排序14　　6.測試與比較15　　6.1調(diào)試步驟15

8、　　6.2結(jié)論16　　7.實驗心得與分析16　　8.附錄17　　8.1直接插入排序17　　8.2折半插入排序18　　8.3希爾排序20&

9、lt;p>　　8.4簡單選擇排序22　　8.5堆排序23　　8.6歸并排序26　　8.7冒泡排序29　　8.8主程序30

10、　　1.引言　　伴隨著社會的發(fā)展，數(shù)據(jù)也變得越來越龐大。如何將龐大的數(shù)據(jù)進(jìn)行很好的排序，使用戶更加方便的查找資料，成了一件越來越重要的問題。對于程序員來說，這將是一個挑戰(zhàn)。　　經(jīng)常查找資料的朋友都會知道，面對海量的資料，如果其查找的資料沒有進(jìn)行排序，那么其查找資料將會是一件非常痛苦的事情。針對這一問題，我們自此通過一個課程設(shè)計來解決它

11、。　　理論上排序算法有很多種，不過本課程設(shè)計只涉及到七種算法。這七種算法共包括：直接插入排序，折半插入排序，希爾排序，簡單選擇排序，堆排序，歸并排序，冒泡排序。　　本課程設(shè)計通過對這七種算法的運行情況進(jìn)行對比，選擇最優(yōu)秀的算法來提供給用戶。希望通過我們的努力能給用戶解決一些問題，帶來一些方便。

12、　2.需求分析　　本課程題目是排序算法的實現(xiàn)，由于各方面的原因，本課程設(shè)計一共要設(shè)計七種排序算法。這七種算法共包括：直接插入排序，折半插入排序，希爾排序，簡單選擇排序，堆排序，歸并排序，冒泡排序。七種排序各有獨到之處，因此我們要通過各種調(diào)試分析來比較其優(yōu)劣長短。　　為了小組分工的方便，我們特意把子函數(shù)寫成Header File文件。這

13、樣操作不僅可以使小組分工更加簡潔明了，還可以方便子函數(shù)的調(diào)用，更可以使寫主函數(shù)時一目了然。　　為了運行時的方便，我們將七種排序方法進(jìn)行編號，其中1為直接插入排序，2為折半插入排序，3為希爾排序，4為簡單選擇排序，5為堆排序，6為歸并排序，7為冒泡排序。通過這七種選項，可以讓用戶簡單明了的去選擇使用哪一種排序方法。　　本課程就是通過對5組占用內(nèi)存大小不同的

14、數(shù)據(jù)調(diào)試來測試這七種算法運行的時間長短，從中選擇面對不同大小的文件時，哪一種算法更為快捷。　　軟件環(huán)境本課程設(shè)計所用操作系統(tǒng)為Windows-XP操作系統(tǒng)，所使用的軟件為Microsoft Visual C++ 6.0；　　3.詳細(xì)設(shè)計　　3.1 直接插入排序</p&g

15、t;　?、潘惴ㄋ枷耄褐苯硬迦肱判蚴且环N最簡單的排序方法，它的基本操作是將一個記錄插入到一個已排好序的有序表中，從而得到一個新的、記錄數(shù)增一的有序表。在自i-1起往前搜索的過程中，可以同時后移記錄。整個排序過程為進(jìn)行n-1趟插入，即：先將序列中的第一個記錄看成是一個有序的子序列，然后從第二個記錄起逐個進(jìn)行插入，直至整個序列變成按關(guān)鍵字非遞減有序序列為止。　?、瞥绦?qū)崿F(xiàn)及核心代

16、碼的注釋：　　for (i = 1 ; i < r.length ;++i )　　for(j=0;j < i;++j)　　if(r.base[i] < r.base[j])　　{<p&

17、gt;　　temp = r.base[i]; //保存待插入記錄　　for(i= i ;i > j; --i )　　r.base[i] = r.base[i-1]; //記錄后移　　r.base[j] = temp;

18、 //插入到正確的為位置　　}　　r.base[r.length] ='\0';　　3.2折半排序　?、潘惴ㄋ枷耄河捎谡郯氩迦肱判虻幕静僮魇窃谝粋€有序表中進(jìn)行查找和插入

19、，這個“查找”操作可利用折半查找來實現(xiàn)，由此進(jìn)行的插入排序稱之為折半插入排序。折半插入排序所需附加存儲空間和直接插入排序相同，從時間上比較，這般插入排序僅減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動次數(shù) 不變。因此，這般插入排序的時間復(fù)雜度仍為O（n2）。　　⑵程序?qū)崿F(xiàn)及核心代碼的注釋：　　void zb(FILE *fp)<p&

20、gt;　　{ //對順序表作折半插入排序　　for ( i = 1 ; i < r.length ; i++ )　　{　　temp=r.base[i];

21、 //將r.base[i]寄存在temp中　　low=0;　　high=i-1; 　　while( low <= high ) //在base[low]到key[high]中折 </p&

22、gt;　　半查找有序插入的位置　　{ 　　m = (low+high)/2; //折半　　if ( temp < r.base[m] )　　high = m-1;

23、 //插入低半?yún)^(qū)　　else　　low = m+1; //插入高半?yún)^(qū)　　}　　for( j=i-1; j>=

24、high+1; --j ) 　　r.base[j+1]= r.base[j]; //記錄后移 　　r.base[high+1]=temp; //插入　　}<p&g

25、t;　　3.3 希爾排序　　⑴算法思想：先將整個待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行一次直接插入排序。其中，子序列的構(gòu)成不是簡單的“逐段分割”，而是將分隔某個“增量”的記錄組成一個子序列。　?、瞥绦?qū)崿F(xiàn)及核心代碼的注釋：<

26、p>　　for(k = 0; k < 10 ; k++)　　{　　m = 10 - k;　　for( i = m ; i < r.length; i ++ )　　if(r.base[i] < r.base[i

27、- m]) 　　{　　temp = r.base[i]; //保存待插記錄 　　for(j = i - m ; j >= 0 && temp < r.base[j]; j -= m)</p&

28、gt;　　r.base[ j + m ] = r.base[j]; //記錄后移，查找插入位置 　　r.base[ j + m ] = temp; //插入　　}　　}

29、　　3.4簡單選擇排序　　⑴算法思想：在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。　?、瞥绦?qū)崿F(xiàn)及核心代碼的注釋：<p

30、>　　for ( i = 0 ; i < r.length ; i++ ) 　　{ //i為排好序的數(shù)的下標(biāo)，依次往后存放排 //好序的數(shù)　　temp=r.base[i];

31、 //將待放入排好序的數(shù)的下標(biāo)的數(shù)保存　　for( j = i,m = j +1 ; m < r.length ; m++) //找出未排序的數(shù)中最小的數(shù)的循環(huán)；　　if(r.base[j] > r.base[m]) 　　j = m

32、; 　　r.base[i] = r.base[j]; //把下標(biāo)為j的數(shù)與i數(shù)互換；　　r.base[j] = temp;

33、　　}　　3.5堆排序　?、潘惴ㄋ枷耄憾雅判蛑恍枰粋€記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。將序列所存儲的元素A[N]看做是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的元素均不大于(或不小于)其左右孩子(若存在)結(jié)點的元素。算法的平均時間復(fù)雜

34、度為O(N log N)。　?、瞥绦?qū)崿F(xiàn)及核心代碼的注釋：　　void dp(FILE *fp)　　{　　for(i = r.length / 2;i >= 1 ; --i) //把r.base[1

35、...r.length]建成大頂堆　　HeapAdjust(r.base,i,r.length); 　　for(i = r.length ;i >= 2 ; --i)　　{ 　　temp

36、 = r.base[1]; 　　r.base[1] = r.base[i]; 　　r.base[i] = temp;　　HeapAdjust(r.base,1,i-1); //將r.base[1...i-1]重新調(diào)整為大頂堆<p&

37、gt;　　}　　void HeapAdjust(char *r,int k,int m) 　　{ 　　i=k; x=r[i]; j=2*i; //沿key 較大的孩子節(jié)點向下篩選<

38、/p>　　while(j<=m) //j為key較大的記錄的下標(biāo)　　{ 　　if( (j<m) && (r[j]>r[j+1]) )

39、j++;　　if(x>r[j]) 　　{ //插入字符比當(dāng)前的大，交換　　r[i] =r[j];　　i = j;

40、　　j *= 2;　　}　　else //否則比較停止。　　j = m + 1;<

41、b>　　}　　r[i] = x; //把字符x插入到該位置，元素插入實現(xiàn)　　}　　3.6歸并排序　　算法思想：

42、先將相鄰的個數(shù)為1的每兩組數(shù)據(jù)進(jìn)行排序合并；然后對上次歸并所得到的大小為2的組進(jìn)行相鄰歸并；如此反復(fù)，直到最后并成一組，即排好序的一組數(shù)據(jù)。　?、瞥绦?qū)崿F(xiàn)及核心代碼的注釋：　　void merge(SqList6 r,int h ,int m ,int w ,SqList6 t) 　　{

43、 //對相鄰兩組數(shù)據(jù)進(jìn)行組合排序；　　int i,j,k;　　i = h ; 　　j = m + 1; //j為合并

44、的第二組元素的第一個數(shù)位置　　k =h-1； // k為存入t中的數(shù)的位置；　　while((i <= m)&&(j <= w)) 　　{

45、 //依次排列兩組數(shù)據(jù)　　k++;　　if(r.base[i] <= r.base[j]) //將第一組數(shù)據(jù)與第二組數(shù)據(jù)分別比較；　　t.base[k] = r.ba

46、se[i++];　　else　　t.base[k] = r.base[j++];　　} 　　if(i > m) /

47、/第一組數(shù)據(jù)先排完的情況　　while(j <= w) t.base[++k]=r.base[j++];　　else 　　while(i <= m) t.base[++k]=r.base[i++];</p&g

48、t;　　}　　void tgb(int s,int n,SqList6 r,SqList6 t) 　　{ //對數(shù)據(jù)進(jìn)行每組s個數(shù)的歸并排序；

49、　int i=1; //i為要合并兩組元素的第一個數(shù)位置；　　while(i<=(n-2*s+1))　　{ 　　merge(r,i,i+s-1,i+2*s-1,t);

50、 //i+s-1為要合并的第一組元素的最后一　　//數(shù)位置、i+2*s-1 為要合并的兩組元素　　//最后一個數(shù)位置；　　i=i+2*s;　　}<p&g

51、t;　　if(i<(n-s+1)) //考慮n不能被s整除，如果余下的數(shù)少于　　//2*s 但大于s，也就是余下的數(shù)不能湊成　　//兩組，湊一組有余,則把余下的數(shù)進(jìn)行組　　//合，并對其進(jìn)行排序；

52、;　　merge(r,i,i+s-1,n,t);　　else //如果余下的數(shù)少于s，則余下的數(shù)進(jìn)行組//合，并進(jìn)行排序；　　while(i<=n) 　　t.base[i]=r.base[i++];

53、;　　}　　void gb(FILE *fp) // 歸并主函數(shù)；　　{ 　　n = r.length;　　SqList6 t;<

54、;/p>　　t.base=(char *) malloc(r.stacksize*sizeof(char)); 　　//給待排序的數(shù)組t申請內(nèi)存；　　while(s<n) //每組元素不斷增加循環(huán)進(jìn)行合并排序；

55、;　　{ 　　tgb(s,n,r,t); // s為每組元素的個數(shù)、n為元素總個數(shù)、r　　//為原數(shù)組，t為待排序的數(shù)組，進(jìn)行歸并排　　s*=2; /

56、/序；把元素個數(shù)相同的兩組合并并進(jìn)行重新　　//定義成新的一組，此組元素個數(shù)為2*s；　　if(s<n){ tgb(s,n,t,r); s *= 2; } 　　//當(dāng)元素個數(shù)小于n時，對其進(jìn)行合并排序；　　else

57、 //當(dāng)元素個數(shù)大于n時，對剩下的數(shù)排序；　　{ 　　i=0;　　while(i<=n) 　　{

58、　　r.base[i]=t.base[i+1];　　i++;　　}　　}　　}

59、　　}　　3.7冒泡排序　?、潘惴ㄋ枷耄?、先將一組未排序的數(shù)組的最后一個數(shù)與倒數(shù)第二個數(shù)進(jìn)行比較，并將較小的數(shù)放于兩個數(shù)中較前的位置，然后將比較后的較小的數(shù)與倒數(shù)第三個進(jìn)行比較，依次比較到第一個數(shù)，即可得到第一個數(shù)是所有數(shù)中最小的數(shù)；2、然后再將數(shù)組的最后一

60、個數(shù)與倒數(shù)第二個數(shù)進(jìn)行比較，并將較小的數(shù)放于兩個數(shù)中較前的位置，依次比較到第二個數(shù)，3、如此循環(huán)到只剩最后兩個比較，即得到排好序的一組數(shù)。　?、瞥绦?qū)崿F(xiàn)及核心代碼的注釋：　　for( i=0; i < r.length ;i++ ) // i為排好序的數(shù)的下標(biāo)，依次往后存放排好序的數(shù)； &l

61、t;p>　　{ 　　for( j = r.length-2;j >= i;j -- ) //從后往前依次兩兩比較，較小的被調(diào)換到前面；　　if(r.base[j+1] < r.base[j]) //比較相鄰兩個數(shù)，如果后面的小于前面的

62、，向下執(zhí)行；　　{ 　　temp = r.base[j+1]; //將后面的較小的數(shù)保存起來；　　r.base[j+1] = r.base[j]; //將前面的較大的數(shù)放在后面較小的數(shù)的位置；<

63、;p>　　r.base[j] = temp; //將較小的數(shù)放在前面的較大的數(shù)的位置；　　}　　}　　4.調(diào)試　　檢測

64、主函數(shù)是否能夠穩(wěn)定運行(如圖4-1)：　　圖4-1　　5.調(diào)試及檢驗　　5.1 直接插入排序　　輸入字符并保存（如圖5-1.1）：　　調(diào)用算法【1】處理

65、文件（如圖5-1.2）：　　處理結(jié)果（如圖5-1.3）：　　圖5-1.1 圖5-1.2　　圖5-1.3　　5.2折半插入排序</b

66、>　　輸入字符并保存（如圖5-2.1）：　　調(diào)用算法【2】處理文件（如圖5-2.2）：　　處理結(jié)果（如圖5-2.3）：　　圖5-2.1 圖5-2.2圖5-2.3&

67、lt;p>　　5.3 希爾排序　　輸入字符并保存（如圖5-3.1）：　　調(diào)用算法【3】處理文件（如圖5-3.2）：　　處理結(jié)果（如圖5-3.3）：　　圖5-3.1

68、圖5-3.2　　圖5-3.3　　5.4簡單選擇排序　　輸入字符并保存（如圖5-4.1）：　　調(diào)用算法【4】處理文件（如圖5-4.2）：

69、處理結(jié)果（如圖5-4.3）：　　圖5-4.1 圖5-4.2　　圖5-4.3　　5.5堆排序　　輸入字符并保存（如圖5

70、-5.1）：　　調(diào)用算法【5】處理文件（如圖5-5.2）：　　處理結(jié)果（如圖5-5.3）：　　圖5-5.1 圖5-5.2　　圖5-5.3

71、;　　5.6歸并排序　　輸入字符并保存（如圖5-6.1）：　　調(diào)用算法【6】處理文件（如圖5-6.2）：　　處理結(jié)果（如圖5-6.3）：　　圖5-6.1

72、圖5-6.2　　圖5-6.3　　5.7冒泡排序　　輸入字符并保存（如圖5-7.1）：　　調(diào)用算法【7】處理文件（如圖5-7.2）：

73、　處理結(jié)果（如圖5-7.3）：　　圖5-7.1 圖5-7.2　　圖5-7.3　　6.測試與比較

74、6.1調(diào)試步驟　?、旁趉csj文本文件中隨機輸入一串字符串，然后保存下來并且復(fù)制備份在桌面上。運行程序，調(diào)用不算法去處理文件。用秒表計算從開始到結(jié)束所用的時間，并記錄下來。　?、茖⑽募A中的kcsj文本文件刪除，將桌面上的備份文件考入文件夾來代替原文件，以保障被操作數(shù)據(jù)的一致性。　?、怯猛瑯拥?/p>

75、方法依次測試七種算法所用的時間，并記錄下來。　?、仍賹?shù)據(jù)依次改變?yōu)檎加脙?nèi)存大小為50KB 、100KB、200KB、512KB、1024KB的數(shù)字串，重復(fù)以上的操作。　?、蓪⒂涗浀臄?shù)據(jù)（如表6-1）。　　表6-1 同一文件不同算法處理的時間表　　--：

76、表示時間過長　　6.2結(jié)論　　通過實驗結(jié)果的比較與分析我們發(fā)現(xiàn)：直接插入排序、冒泡排序、簡單選擇排序及折半插入排序是低效率的排序方式；所以我們實際編程重要盡可能的避免他們的出現(xiàn)；我們應(yīng)該用較先進(jìn)的歸并排序及堆排序。　　7.實驗心得與分析&

77、lt;/b>　　通過本次課程設(shè)計，我們小組的每個成員都學(xué)到了很多東西。首先要說的是我們的編程能力，在這一次的課程設(shè)計中我們的編程能力均得到了一定程度的提升。并且通過這次課程設(shè)計，我們更加熟悉了如何使用Header File文件。本次課程設(shè)計，讓我們對于直接插入排序，折半插入排序，希爾排序，簡單選擇排序，堆排序，歸并排序，冒泡排序等七種排序算法的思想有了進(jìn)一步的認(rèn)識，同時對七種算法的應(yīng)用有了

78、更進(jìn)一步的掌握。通過這次課程設(shè)計，我們對于解決實際問題的能力有了進(jìn)一步提高。最重要的是，這次課程設(shè)計大大的訓(xùn)練了我們的小組團隊協(xié)作能力。通過這次課程設(shè)計我們小組各成員的團隊協(xié)作能力都有了很大的提升。這種團隊協(xié)作能力對于我們學(xué)編程的來說是極其重要的，同時也是必不可少的。　　當(dāng)然，我們寫程序的時候遇到了很多困難。而且在程序調(diào)試過程中出現(xiàn)了很多錯誤與警告，不過在隊員及老師的幫助下均得到了解決。當(dāng)程序可

79、以運行后，程序的運行過程中同樣也也出現(xiàn)了很多錯誤，甚至出現(xiàn)了不兼容的情況。不過，后來在隊員及老師的幫助下也均得到了解決。然而，我們的程序還有一點瑕疵讓我們感到美中不足。那就是在歸并算法運行過程中，當(dāng)輸入為9個字符時，排序結(jié)果會出現(xiàn)偶然誤差。經(jīng)過分析，我們認(rèn)為這點是系統(tǒng)的問題。不過，這仍然是一點讓我們感到遺憾的地方。　　8.附錄<

80、p>　　8.1直接插入排序　　#include<stdio.h>　　#include<stdlib.h>　　#define Q 1000　　typedef struct {<

81、;p>　　char *base ; 　　int stacksize ; 　　int length;　　}SqList1; 　　void zj(FILE *fp)　　{</p&g

82、t;　　SqList1 r;　　int i,j;　　char temp,*p;　　r.base=(char *) malloc(Q*sizeof(char));　　r.stacksize = Q;</p&g

83、t;　　r.length = 0;　　while(!feof(fp))　　{　　fscanf(fp,"%c",r.base); 　　r.base++;

84、　　r.length++;　　if(r.length == r.stacksize )　　{　　r.base= r.base - r.length;　　r.base=(char *) rea

85、lloc(r.base,(r.stacksize + Q) * sizeof(char));　　if(!r.base)　　{　　printf("ERROR");　　return ; &l

86、t;p>　　}　　r.base = r.base + r.stacksize;　　r.stacksize += Q;　　} 　　}

87、　　r.length --;　　r.base --;　　r.base= r.base - r.length;　　for (i = 1 ; i < r.length ;++i )　　for(j=0;j < i;++j)

88、　　if(r.base[i] < r.base[j])　　{　　temp = r.base[i];　　for(i= i ;i > j; --i )　　r.base[i] = r.base[i-1]

89、;　　r.base[j] = temp;　　}　　r.base[r.length] ='\0';　　rewind(fp);　　fprintf(fp,"%s"

90、,r.base);　　fclose(fp);　　free(r.base);　　}　　8.2折半插入排序　　#include<stdio.h>&

91、lt;/p>　　#include<stdlib.h>　　#define Q 1000　　typedef struct {　　char *base ; 　　int stacksize ;

92、　int length;　　}SqList2; 　　void zb(FILE *fp)　　{　　SqList2 r;　　int i,j ,m, low, high;&

93、lt;p>　　char temp;　　r.base=(char *) malloc(1000*sizeof(char));　　r.stacksize = 1000;　　r.length = 0;　　while(!feof(fp))<p&

94、gt;　　{　　fscanf(fp,"%c",r.base);　　r.base++;　　r.length++;　　if(r.length == r.stacksize )&l

95、t;/p>　　{　　r.base= r.base - r.length;　　r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char));　　if(!r.base)</p&g

96、t;　　{　　printf("ERROR");　　return ; 　　}　　r.base = r.base + r.stacksize;</p

97、>　　r.stacksize += Q;　　} 　　}　　r.length --;　　r.base --;　　r.base=

98、 r.base - r.length;　　for ( i = 1 ; i < r.length ; i++ )　　{　　temp=r.base[i]; 　　low=0;</p&

99、gt;　　high=i-1;　　while( low <= high )　　{ 　　m = (low+high)/2; 　　if ( temp < r.b

100、ase[m] )　　high = m-1; 　　else　　low = m+1; 　　}　　for( j=i-1; j>=high+1; --j )

101、　　r.base[j+1]= r.base[j]; 　　r.base[high+1]=temp; 　　}　　r.base[r.length] ='\0';　　rewind(fp

102、);　　fprintf(fp,"%s",r.base);　　fclose(fp);　　free(r.base);　　}　　8.3希爾排序

103、;　　#include<stdio.h>　　#include<stdlib.h>　　#define Q 1000　　typedef struct {　　char *base ; &

104、lt;p>　　int stacksize ;　　int length;　　}SqList3; 　　void xe(FILE *fp)　　{　　SqList3 r;

105、　　int i,j,k,m;　　char temp;　　r.length = 0;　　r.base=(char *) malloc(1000*sizeof(char));　　r.stacksize = 1000;<p&g

106、t;　　while(!feof(fp))　　{　　fscanf(fp,"%c",r.base);　　r.base++;　　r.length++;<

107、p>　　if(r.length == r.stacksize )　　{　　r.base= r.base - r.length;　　r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char));<

108、/p>　　if(!r.base)　　{　　printf("ERROR");　　return ; 　　}

109、　　r.base = r.base + r.stacksize;　　r.stacksize += Q;　　} 　　}　　r.length --;　　r.

110、base --;　　r.base= r.base - r.length;　　for(k = 0; k < 10 ; k++)　　{　　m = 10 - k;　　for( i = m ;

111、i < r.length; i ++ )　　if(r.base[i] < r.base[i - m]) 　　{　　temp = r.base[i]; 　　for(j =

112、i - m ; j >= 0 && temp < r.base[j]; j -= m)　　r.base[ j + m ] = r.base[j]; 　　r.base[ j + m ] = temp;　　}&

113、lt;p>　　} 　　rewind(fp);　　fprintf(fp,"%s",r.base);　　fclose(fp);　　free(r.base);<b&g

114、t;　　}　　8.4簡單選擇排序　　#include<stdio.h>　　#include<stdlib.h>　　#define Q 1000

115、typedef struct {　　char *base ; 　　int stacksize ;　　int length;　　}SqList4; 　　void jd(FILE *fp)

116、　　{　　SqList4 r;　　int i,j ,m;　　char temp;　　r.base=(char *) malloc(1000*sizeof(char));　　r.stacksiz

117、e = 1000;　　r.length = 0;　　while(!feof(fp))　　{　　fscanf(fp,"%c",r.base);　　r.bas

118、e++;　　r.length++;　　if(r.length == r.stacksize )　　{　　r.base= r.base - r.length;　　r.bas

119、e=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char));　　if(!r.base)　　{　　printf("ERROR");　　return ;

120、　　}　　r.base = r.base + r.stacksize;　　r.stacksize += Q;　　} 　　}</b

121、>　　r.length --;　　r.base --;　　r.base= r.base - r.length;　　for ( i = 0 ; i < r.length ; i++ )　　{&l

122、t;/b>　　temp=r.base[i]; 　　for( j = i,m = j +1 ; m < r.length ; m++)　　if(r.base[j] > r.base[m])　　j = m;<

123、;/p>　　r.base[i] = r.base[j];　　r.base[j] = temp;　　}　　r.base[r.length] ='\0';　　rewind(fp);</p&

124、gt;　　fprintf(fp,"%s",r.base);　　fclose(fp);　　free(r.base);　　}　　8.5堆排序

125、;　　#include<stdio.h>　　#include<stdlib.h>　　#define Q 1000　　typedef struct {　　char *base ;

126、int stacksize ; 　　int length;　　}SqList5; 　　void HeapAdjust(char *r,int s,int m);　　void dp(FILE *fp)　　{&l

127、t;/b>　　SqList5 r;　　int i,j;　　char temp,*k;　　r.length = 0;　　r.base=(char *) malloc(1000*sizeof

128、(char));　　r.stacksize = 1000;　　r.base += 1;　　while(!feof(fp))　　{　　fscanf(fp,"%c",r.bas

129、e);　　r.base++;　　r.length++;　　if(r.length == (r.stacksize - 1) )　　{　　r.base=

130、r.base - r.length - 1;　　r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char));　　if(!r.base)　　{　　printf(&qu

131、ot;ERROR");　　return ; 　　}　　r.base = r.base + r.stacksize;　　r.stacksize += Q;　　}

132、 　　}　　r.length --;　　r.base --;　　r.base= r.base - r.length - 1;　　for(i = r.length / 2;i

133、 >= 1 ; --i)　　HeapAdjust(r.base,i,r.length);　　for(i = r.length ;i >= 2 ; --i)　　{　　temp = r.base[1];

134、　　r.base[1] = r.base[i];　　r.base[i] = temp;　　HeapAdjust(r.base,1,i-1);　　}　　k = (char *) malloc((r.length+1)*

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)各種排序算法的課程設(shè)計實驗報告

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)各種排序算法的課程設(shè)計實驗報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載