排序算法數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書

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

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

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

文檔簡介

1、　　數(shù) 據(jù) 結(jié) 構(gòu)　　課程設(shè) 計說明書　　2012 年 1月 8 日　　設(shè)計目的　　本系統(tǒng)是為了實現(xiàn)和比較各種不同排序方法的不同復(fù)雜度,而建立的,從不同的角度比較各

2、算法的優(yōu)劣,從而使使用者能對個排序方法有更清晰的了解.　　設(shè)計內(nèi)容和要求　　本次設(shè)計的內(nèi)容主要有實現(xiàn)各種排序算法以及比較各種算法。要求主要是要執(zhí)行對一種數(shù)據(jù)類型的序列進(jìn)行所有排序方法的排序計算，并返回序列及各算法的排序指標(biāo)。　　3．本設(shè)計所采用的數(shù)據(jù)結(jié)構(gòu)

3、　　本次設(shè)計主要采用的數(shù)據(jù)結(jié)構(gòu)有結(jié)構(gòu)體定義，直接排序，選擇排序，歸并排序，快速排序，冒泡排序，希爾排序，堆排序等。　　4．功能模塊詳細(xì)設(shè)計　　4.1 詳細(xì)設(shè)計思想　　本次設(shè)計分主題設(shè)計和模塊設(shè)計兩部分。　　主體設(shè)計方面，本系統(tǒng)的主要數(shù)據(jù)類型為含有一個關(guān)

4、鍵字的結(jié)構(gòu)體類型，命名為datatype；設(shè)置兩個全局變量數(shù)組，cn和mn，分別用于記錄每種排序方法中的各排序元素的比較次數(shù)和移動次數(shù)（關(guān)鍵字交換以3次計）的總和。　　模塊設(shè)計方面，本系統(tǒng)大致可分為排序模塊部分和運行模塊部分。排序模塊部分分為歸并排序模塊，快速排序模塊，冒泡排序模塊，選擇排序模塊，直接排序模塊，希爾排序模塊，堆排序模塊；運行模塊部分分為主函數(shù)，自行輸入模塊，隨機模塊，輸出模塊。&

5、lt;/p>　　以下是各排序算法的核心設(shè)計思想：　　運行模塊個算法如下：　　4.2 核心代碼　　#include<stdio.h>　　#include<stdlib.h></p

6、>　　#include<conio.h>　　#define MAXNUM 100　　typedef struct　　{ int key;　　} datatype;　　datatype R

7、[MAXNUM];/*定義類型*/　　int cn[MAXNUM],mn[MAXNUM];　　void D_InsertSort(datatype R[ ], int n)/*直接排序*/　　{　　int i,j;

8、　　extern int cn[MAXNUM],mn[MAXNUM];　　for(i=2; i<=n; i++)　　{ cn[0]++;　　if (R[i].key<R[i-1].key)　　{R[

9、0]=R[i]; mn[0]++;　　for(j=i-1; R[0].key<R[j].key; j--)　　R[j+1]=R[j];　　R[j+1]=R[0]; mn[0]+=2;　　}<p&

10、gt;　　}　　}　　void Select_Sort(datatype R[ ],int n)/*簡單選擇排序*/　　{　　int i,j,k;</p

11、>　　extern int cn[MAXNUM],mn[MAXNUM];　　for(i=1;i<n;i++)　　{ k=i;　　for(j=i+1; j<=n; j++)

12、　　{　　cn[1]++;　　if(R[j].key<R[k].key)　　k=j;　　}

13、　　if (i==k)　　{ R[0]=R[k];　　R[k]=R[i];　　R[i]=R[0]; mn[1]+=3; }　　}　　}

14、　　void Bubble_Sort (datatype R[ ], int n)/*冒泡排序*/　　{　　int i, j;　　extern int cn[MAXNUM],m

15、n[MAXNUM];　　int swap;　　for(i=1; i<n-1; i++)　　{swap=0;　　for(j=1; j<=n-i; j++)<

16、p>　　{　　cn[2]++;　　if (R[j].key<R[j+1].key)　　{R[0]=R[j];　　R[j]=R[j+1];　　R

17、[j+1]=R[0]; mn[2]+=3;　　swap=1;　　}}　　if(swap==0) break;　　}&

18、lt;b>　　}　　void HeapAdjust(datatype R[ ], int s, int t)　　{　　datatype rc;　　extern int cn[MAXNUM],mn[MAXNUM

19、];　　int i,j ;　　rc=R[s];　　i=s;　　for(j=2*i; j<=t; j=2*j)

20、　{ cn[3]++;　　if(j<t && R[j].key<R[j+1].key)j=j+1;　　if(rc.key > R[j].key) break;　　R[i]=R[j]; mn[3]++;　　i=j

21、;　　}　　R[i]=rc;　　}　　void HeapSort(datatype R[ ], int n)/*堆排序*/</p&g

22、t;　　{　　int i;　　extern int cn[MAXNUM],mn[MAXNUM];　　for(i=n/2; i>0; i-- )　　HeapAdjust(

23、R, i, n);　　for(i=n; i>1; i--)　　{ R[0]=R[1];　　R[1]=R[i];　　R[i]=R[0]; mn[3]+=3;　　HeapAdjust(R,1, i-1);

24、　　}　　}　　void Merge(datatype R[ ], datatype R1[ ], int s, int m , int t)　　{&l

25、t;p>　　int i,j,k;　　extern int cn[MAXNUM],mn[MAXNUM];　　i=s; j=m+1; k=s;　　while (i<=m&&j<=t)　　{<

26、/p>　　cn[4]++;　　if(R[i].key<R[j].key)　　{ R1[k++]=R[i++]; mn[4]++;}　　else　　{ R1[k+

27、+]=R[j++]; mn[4]++;}　　}　　while (i<=m) { R1[k++]=R[i++]; mn[4]++; }　　while (j<=t) { R1[k++]=R[j++]; mn[4]++;}&

28、lt;b>　　}　　void MSort(datatype R[ ], datatype R1[ ], int s, int t)　　{　　int m;　　extern

29、int cn[MAXNUM],mn[MAXNUM];　　if(s==t) { R1[s]=R[s]; mn[4]++;}　　else {m=(s+t)/2;　　MSort(R, R1, s, m);　　MSort(R, R1, m+1, t);

30、　　Merge(R1, R, s, m, t);　　}　　}　　void MergeSort(datatype R[ ], datatype R1[ ], int n)/*歸并排序*/<p&

31、gt;　　{　　MSort(R, R1,1, n);　　}　　int Partition(datatype R[ ], int low, int high)　　{</b&g

32、t;　　extern int cn[MAXNUM],mn[MAXNUM];　　R[0]=R[low]; mn[5]++;　　while(low<high)　　{ while(low<high&&R[high].key>=R[0].key)

33、 {cn[5]++; high--;}　　if(low<high) { R[low]=R[high]; low++; mn[5]++; }　　while(low<high&&R[low].key<R[0].key) { mn[5]++; low++; }　　if(low&

34、lt;high) {R[high]=R[low]; high--; mn[5]++; }　　}　　R[low]=R[0]; mn[5]++;　　return low;　　}

35、;　　void Quick_Sort(datatype R[ ], int s, int t)/*快速排序*/　　{　　int i;　　if( s<t )</p&g

36、t;　　{　　i = Partition(R, s, t);　　Quick_Sort(R, s, i-1);　　Quick_Sort(R, i+1, t);　　}</p

37、>　　}　　void prin(datatype R[],int n)　　{　　int i ;　　printf("排序的

38、結(jié)果為：");　　for(i=1;i<=n;i++)　　printf("%d ",R[i]);　　printf("\n ");　　}

39、　void sort(datatype R[],int n)/*希爾排序*/　　{　　int gap,i,j,temp;　　extern int cn[MAXNUM],mn[MAXNUM];　　for(gap=n/2;gap>0

40、;gap /= 2) /* 設(shè)置排序的步長，步長gap每次減半，直到減到1 */　　{　　for(i=gap;i<n;i++) /* 定位到每一個元素 */　　{　　for(j=i-gap

41、;(j >= 0) && (R[j].key > R[j+gap].key);j -= gap ) /* 比較相距gap遠(yuǎn)的兩個元素的大小，根據(jù)排序方向決定如何調(diào)換 */　　{　　temp=R[j].key;　　R[j].key=R[j+gap].

42、key;　　R[j+gap].key=temp;　　cn[6]+=1;　　mn[6]+=3;　　}

43、　　}　　}　　} 　　void sui_ji()　　{

44、　　int i,n;　　datatype R[MAXNUM]={0},R1[MAXNUM]={0};;　　a:printf("請輸入你要輸入的個數(shù):");　　scanf("%d",&n);

45、;　　if(n>100)　　{　　printf("超出范圍重新輸入!!!\n");　　goto a;　　}<

46、;/p>　　printf("排序前元素順序為:");　　for(i=1;i<n+1;i++)　　{　　R[i].key=rand();　　printf("%d &quo

47、t;,R[i].key);　　}　　printf("\n");　　D_InsertSort(R,n);/*直接排序*/　　prin(R,n);　　Select_Sort(R

48、,n);/*簡單選擇排序*/　　Bubble_Sort(R, n);/*冒泡排序*/　　HeapSort(R, n);/*堆排序*/　　MergeSort(R, R1, n);/*二路歸并排序*/　　Quick_Sort(R,0, n);/*快速排序*/

49、;　　sort(R,n);/*希爾排序*/　　}　　void zi_xing_input()　　{ int n,i;　　datatype R1[MAXNUM]={0};

50、;　　printf("請輸入你要輸入的個數(shù)（不大于100的整數(shù)）:");　　scanf("%d",&n);　　printf("請輸入各個元素:");　　for(i=1;i<n+1;i++)　　sca

51、nf("%d",&R1[i].key);　　printf("排序前元素順序為:");　　for(i=1;i<n+1;i++) printf("%d ",R1[i].key);　　printf("\n");</p

52、>　　D_InsertSort(R1,n);/*直接排序*/　　prin(R1,n);　　Select_Sort(R1,n);/*簡單選擇排序*/　　Bubble_Sort(R1, n);/*冒泡排序*/　　HeapSort(R1, n);/*

53、堆排序*/　　Quick_Sort(R1,0, n);/*快速排序*/　　sort(R,n);/*希爾排序*/　　}　　int main()　　{<

54、/p>　　extern int cn[MAXNUM],mn[MAXNUM];　　char s;　　printf(“ 排序算法實現(xiàn)與演示統(tǒng) \n ”);　　printf(" ┏*

55、*****************************┓\n");　　printf(" ┃------- 歡迎使用 ----┃\n");　　printf(" ┃-----（1）隨機取數(shù)-------┃\n");&l

56、t;p>　　printf(" ┃-----（2）自行輸入-------┃\n");　　printf(" ┃-----（0）退出使用-------┃\n");　　printf(" ┗***********************

57、*******┛\n");　　printf(" 請選擇操作方式： ");　　b:s=getch();　　switch(s)

58、　{　　case '1': system("cls") ; sui_ji(); break;　　case '2': system("cls"); zi_xing_input(); break;　　case '

59、;0': printf(" 謝謝使用！！ "); exit(0); break;　　default:printf("錯誤輸入，重新輸入！");goto b;　　}　　printf("\n &quo

60、t;);　　printf(" 比較結(jié) 果 \n");　　printf(" \n");　　printf(" 排序方式比較次數(shù) 移動次數(shù)

61、\n");　　printf(" \n");　　printf(" 直接 %d %d \n",cn[0],mn[0]/3);　　printf(" \n");<

62、/p>　　printf(" 簡單選擇 %d %d \n",cn[1],mn[1]/3);　　printf(" \n");　　printf(" 冒泡 %d

63、 %d \n",cn[2],mn[2]/3);　　printf(" \n");　　printf(" 堆排序 %d %d \n",cn[3],mn[3]/3);<p

64、>　　printf(" \n");　　printf(" 二路歸并 %d %d \n",cn[4],mn[4]/3);　　printf(" \n");　　printf(&q

65、uot; 快速 %d %d \n",cn[5],mn[5]/3);　　printf(" \n");　　printf(" 希爾排序 %d %d \n&qu

66、ot;,cn[6],mn[6]/3);　　getchar(); 　　printf("謝謝使用！^ _ ^\n");　　system("PAUSE");　　return 0;</p&g

眾賞文庫> 全部分類> 畢業(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)方式做保護(hù)處理，對用戶上傳分享的文檔內(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è)計說明書

文檔簡介

溫馨提示

最新文檔

評論

免費下載