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

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

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

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

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

文檔簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、碼的注釋?zhuān)?lt;/p>　　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折半排序　?、潘惴ㄋ枷耄河捎谡郯氩迦肱判虻幕静僮魇窃谝粋€(gè)有序表中進(jìn)行查找和插入

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

20、gt;　　{ //對(duì)順序表作折半插入排序　　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 希爾排序　?、潘惴ㄋ枷耄合葘⒄麄€(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。其中，子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將分隔某個(gè)“增量”的記錄組成一個(gè)子序列。　　⑵程序?qū)崿F(xiàn)及核心代碼的注釋?zhuān)?lt;/p><

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簡(jiǎn)單選擇排序　?、潘惴ㄋ枷耄涸谝判虻囊唤M數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。　　⑵程序?qū)崿F(xiàn)及核心代碼的注釋?zhuān)?lt;/p><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堆排序　?、潘惴ㄋ枷耄憾雅判蛑恍枰粋€(gè)記錄大小的輔助空間，每個(gè)待排序的記錄僅占有一個(gè)存儲(chǔ)空間。將序列所存儲(chǔ)的元素A[N]看做是一棵完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉結(jié)點(diǎn)的元素均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的元素。算法的平均時(shí)間復(fù)雜

34、度為O(N log N)。　?、瞥绦?qū)崿F(xiàn)及核心代碼的注釋?zhuān)?lt;/p>　　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é)點(diǎn)向下篩選<

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插入到該位置，元素插入實(shí)現(xiàn)　　}　　3.6歸并排序　　算法思想：

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

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

44、的第二組元素的第一個(gè)數(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) 　　{ //對(duì)數(shù)據(jù)進(jìn)行每組s個(gè)數(shù)的歸并排序；

49、　int i=1; //i為要合并兩組元素的第一個(gè)數(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 為要合并的兩組元素　　//最后一個(gè)數(shù)位置；　　i=i+2*s;　　}<p&g

51、t;　　if(i<(n-s+1)) //考慮n不能被s整除，如果余下的數(shù)少于　　//2*s 但大于s，也就是余下的數(shù)不能湊成　　//兩組，湊一組有余,則把余下的數(shù)進(jìn)行組　　//合，并對(duì)其進(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申請(qǐng)內(nèi)存；　　while(s<n) //每組元素不斷增加循環(huán)進(jìn)行合并排序；

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

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

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

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

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

60、個(gè)數(shù)與倒數(shù)第二個(gè)數(shù)進(jìn)行比較，并將較小的數(shù)放于兩個(gè)數(shù)中較前的位置，依次比較到第二個(gè)數(shù)，3、如此循環(huán)到只剩最后兩個(gè)比較，即得到排好序的一組數(shù)。　　⑵程序?qū)崿F(xiàn)及核心代碼的注釋?zhuān)?lt;/p>　　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]) //比較相鄰兩個(gè)數(shù)，如果后面的小于前面的

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

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

64、主函數(shù)是否能夠穩(wěn)定運(yùn)行(如圖4-1)：　　圖4-1　　5.調(diào)試及檢驗(yàn)　　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簡(jiǎn)單選擇排序　　輸入字符并保存（如圖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.測(cè)試與比較

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

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

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

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

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

79、以運(yùn)行后，程序的運(yùn)行過(guò)程中同樣也也出現(xiàn)了很多錯(cuò)誤，甚至出現(xiàn)了不兼容的情況。不過(guò)，后來(lái)在隊(duì)員及老師的幫助下也均得到了解決。然而，我們的程序還有一點(diǎn)瑕疵讓我們感到美中不足。那就是在歸并算法運(yùn)行過(guò)程中，當(dāng)輸入為9個(gè)字符時(shí)，排序結(jié)果會(huì)出現(xiàn)偶然誤差。經(jīng)過(guò)分析，我們認(rèn)為這點(diǎn)是系統(tǒng)的問(wèn)題。不過(guò)，這仍然是一點(diǎn)讓我們感到遺憾的地方。　　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簡(jiǎn)單選擇排序　　#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)*

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

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

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載