數(shù)據(jù)結(jié)構(gòu)排序綜合課程設(shè)計報告

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

數(shù)據(jù)結(jié)構(gòu)排序綜合課程設(shè)計報告_第1頁

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

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

文檔簡介

1、　　《數(shù)據(jù)結(jié)構(gòu)》　　課程設(shè)計報告　　專業(yè) 計算機(jī)科學(xué)與技術(shù) 　　班級 (1) 　　姓名

2、 　　學(xué) 號 　　指導(dǎo)教師 　　起止時間 2011.10~2011.12 　　課程設(shè)計：排序綜合

3、　　一、任務(wù)描述　?。?）至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。　?。?）統(tǒng)計每一種排序方法的性能（以上機(jī)運行程序所花費的時間為準(zhǔn)進(jìn)行對比），找出其中兩種

4、較快的方法。　　二、問題分析　　1、功能分析　　分析設(shè)計課題的要求，要求編程實現(xiàn)以下功能：　?。?）顯示隨機(jī)數(shù)：調(diào)用Dip()函數(shù)輸出數(shù)組a[]。數(shù)組a[]中保存有隨機(jī)產(chǎn)生的隨機(jī)數(shù)。</p&

5、gt;　?。?）直接選擇排序：通過n-I次關(guān)鍵字間的比較，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i個記錄交換之。　?。?）冒泡排序：如果有n個數(shù)，則要進(jìn)行n-1趟比較。在第1趟比較中要進(jìn)行n-1次兩兩比較，在第j趟比較中要進(jìn)行n-j次兩兩比較。　?。?）希爾排序：先將整個待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，

6、待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行一次直接插入排序。　　（5）直接插入排序：將一個記錄插入到已排序好的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。設(shè)整個排序有n個數(shù)，則進(jìn)行n-1趟插入，即：先將序列中的第1個記錄看成是一個有序的子序列，然后從第2個記錄起逐個進(jìn)行插入，直至整個序列變成按關(guān)鍵字非遞減有序列為止。　?。?）顯示各排序算法排

7、序后的的數(shù)據(jù)和時間效率，并比較找出其中2種較快的方法。　　2、數(shù)據(jù)對象分析　　排序方式：直接選擇排序、冒泡排序、希爾排序、直接插入排序　　顯示排序后的的數(shù)據(jù)和時間效率。　　三、數(shù)據(jù)結(jié)構(gòu)設(shè)計<

8、/p>　　1.主要全程變量及數(shù)據(jù)結(jié)構(gòu)　　數(shù)據(jù)結(jié)構(gòu)：　　typedef struct　　{ 　　KeyType key;

9、InfoType otherinfo; 　　}RedType;　　typedef struct　　{ 　　RedType r[MAXSIZE+1]; <p

10、>　　int length; 　　}SqList; 　　2.算法的入口參數(shù)及說明　　#include <stdio.h>　　#define MAXSIZE 20　　#define LT(a,b) ((a)<

11、;(b)) //宏定義　　typedef int KeyType; //定義關(guān)鍵字KeyType為int　　typedef int InfoType; //定義關(guān)鍵字InfoType為int　　typedef struct{ //RedType結(jié)構(gòu)定義

12、KeyType key;　　InfoType otherinfo; //記錄中其他信息域的類型　　}RedType;　　typedef struct{ //SqList結(jié)構(gòu)定義　　RedType r[MAXSIZE+1];

13、 //定義大小　　int length; //length為待排記錄個數(shù)　　}SqList;　　四、功能設(shè)計　?。ㄒ唬┲骺夭藛卧O(shè)計&

14、lt;p>　　為實現(xiàn)排序的操作功能，首先設(shè)計一個含有多個菜單項的主控菜單程序，然后再為這些菜單項配上相應(yīng)的功能。　　程序運行后，給出11個菜單項的內(nèi)容和輸入提示，如下：　　歡迎來到排序綜合系統(tǒng)！　　菜單　　(1)---直接插入排

15、序　　(2)---直接選擇排序　　(3)---冒泡排序　　(4)---快速排序　　(5)---堆排序 　　(6)---時間效率比較　　(7)---顯示隨機(jī)數(shù) &

16、lt;p>　　(0)---退出系統(tǒng)　　請在上述序號中選擇一個并輸入：　　（二）程序模塊結(jié)構(gòu)　　由課題要求可將程序劃分為以下幾個模塊（即實現(xiàn)程序功能所需的函數(shù)）：　　主控菜單項選擇函數(shù)menu_select()

17、　　插入排序函數(shù)：InsertSort()　　選擇排序函數(shù)：SelectSort()　　冒泡排序函數(shù)：BubbleSort()　　堆排序函數(shù)：heapsort()　　（三）函數(shù)調(diào)用關(guān)系&l

18、t;p>　　程序的主要結(jié)構(gòu)（函數(shù)調(diào)用關(guān)系）如下圖所示。 　　其中main()是主函數(shù)，它進(jìn)行菜單驅(qū)動，根據(jù)選擇項1~0調(diào)用相應(yīng)的函數(shù)。　　（四）函數(shù)實現(xiàn)　　#include <stdio.h>

19、;　　#include <conio.h> 　　#include <stdlib.h>　　#include <windows.h>　　#include <time.h>　　#define N 30000

20、;　　void Wrong() 　　{　　printf("\n=====>按鍵錯誤!\n");　　getchar();　　}

21、　　void Disp(int a[])　　{　　int i;　　system("cls");　　for(i=0;i<N;i++)

22、　　{　　if((i-1)%10==9)　　printf("\n"); 　　printf("%-7d",a[i]); 　　}</p

23、>　　}　　void InsertSort(int a[],int p) //插入排序　　{ 　　int i,j,temp; 　　for(i=1;i<N;i++)

24、 　　{ 　　temp=a[i]; 　　for(j=i;j>0&&a[j-1]>temp;j--) 　　a[j]=a[j-1]; 　　a[j]=temp; <

25、/p>　　} 　　}　　void SelectSort(int a[],int p) //選擇排序　　{ 　　int i,j,

26、k; 　　for(i=0;i<N-1;i++) 　　{ 　　k=i;　　for(j=i+1;j<N;j++) 　　if(a[j]<a[k

27、])　　k=j;　　if(k!=i) 　　{ 　　int temp; 　　temp=a[k];

28、　　a[k]=a[i]; 　　a[i]=temp; 　　} 　　} 　　}　　void Bub

29、bleSort(int a[],int p) /*冒泡排序算法*/　　{　　int i,j,temp;　　for (i=0;i<N-1;i++) 　　{ <p&

30、gt;　　for (j=N-1;j>i;j--) /*比較,找出本趟最小關(guān)鍵字的記錄*/　　if (a[j]<a[j-1]) 　　{ 　　temp=a[j]; /*進(jìn)行交換,將最小關(guān)鍵字記錄前移*/　　a[j]=a[j

31、-1];　　a[j-1]=temp;　　}　　}　　}　　void creatheap(int a[],int i,

32、int n) //創(chuàng)建堆　　{　　int j;　　int t;　　t=a[i];<p&

33、gt;　　j=2*(i+1)-1;　　while(j<=n)　　{　　if((j<n)&&(a[j]<a[j+1]))　　j++;<

34、p>　　if(t<a[j])　　{　　a[i]=a[j];　　i=j;　　j=2*(i+1)-1;　　}

35、　　else　　j=n+1;　　}　　a[i]=t;　　}&

36、lt;/b>　　void heapsort(int a[],int n,int p) //堆排序　　{　　int i;　　int t;&l

37、t;/p>　　for(i=n/2-1;i>=0;i--)　　creatheap(a,i,n-1);　　for(i=n-1;i>=1;i--)　　{　　t=a[0];</b

38、>　　a[0]=a[i];　　a[i]=t;　　creatheap(a,0,i-1);}　　}　　void quicksort(int a[],in

39、t n,int p)　　{ 　　int i,j,low,high,temp,top=-1;　　struct node　　{　　int low,hig

40、h;　　}st[N];　　top++;　　st[top].low=0;st[top].high=n-1;　　while(top>-1)　　{

41、 low=st[top].low;high=st[top].high;　　top--;　　i=low;j=high;　　if(low<high)　　{ temp=a[low];

42、;　　while(i!=j)　　{ while(i<j&&a[j]>temp)j--;　　if(i<j){a[i]=a[j];i++;}　　while(i<j&&a[i]<temp)i++;　　if(i&l

43、t;j){a[j]=a[i];j--;}　　}　　a[i]=temp;　　top++;st[top].low=low;st[top].high=i-1;　　top++;st[top].low=i+1;st[top].high=high

44、;　　}　　}　　}　　double TInsertSort(int a[],int p)　　{&

45、lt;/b>　　int i;　　int b[N];　　for(i=0;i<N;i++)　　b[i]=a[i];　　LARGE_INTEGER

46、m_liPerfFreq={0};　　QueryPerformanceFrequency(&m_liPerfFreq); 　　LARGE_INTEGER m_liPerfStart={0};　　QueryPerformanceCounter(&m_liPerfStart);</p&g

47、t;　　InsertSort(b,p);　　LARGE_INTEGER liPerfNow={0};　　QueryPerformanceCounter(&liPerfNow);　　double time=liPerfNow.QuadPart - m_liPerfStart.QuadP

48、art;　　time/=m_liPerfFreq.QuadPart;　　if(p!=6)　　{Disp(b);getchar();}　　printf("\n用直接插入排序法用的時間為%f秒；",time);<

49、/p>　　FILE *fp;　　fp=fopen("直接插入排序.txt","w"); 　　for(i=0;i<N;i++)　　fprintf(fp,"%d ",b[i]);<

50、;/p>　　fclose(fp);　　return(time);　　}　　double TSelectSort(int a[],int p)　　{

51、　　int i;　　int b[N];　　for(i=0;i<N;i++)　　b[i]=a[i];　　LARGE_INTEGER m_liPerfFreq={0};<

52、;/p>　　QueryPerformanceFrequency(&m_liPerfFreq); 　　LARGE_INTEGER m_liPerfStart={0};　　QueryPerformanceCounter(&m_liPerfStart);　　Selec

53、tSort(b,p);　　if(p!=6)　　{Disp(b);getchar();}　　LARGE_INTEGER liPerfNow={0};　　QueryPerformanceCounter(&liPerfNow);&l

54、t;/p>　　double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;　　time/=m_liPerfFreq.QuadPart;　　printf("\n用直接選擇排序法用的時間為%f秒；",time);<

55、;b>　　FILE *fp;　　fp=fopen("直接選擇排序.txt","w");　　for(i=0;i<N;i++)　　fprintf(fp,"%d ",b[i]);　　fc

56、lose(fp);return(time);　　}　　double TBubbleSort(int a[],int p)　　{　　int i;</p&g

57、t;　　int b[N];　　for(i=0;i<N;i++)　　b[i]=a[i];　　LARGE_INTEGER m_liPerfFreq={0};　　QueryPerformanceFrequency

58、(&m_liPerfFreq); 　　LARGE_INTEGER m_liPerfStart={0};　　QueryPerformanceCounter(&m_liPerfStart);　　BubbleSort(b,p);　　LARGE_INTEG

59、ER liPerfNow={0};　　QueryPerformanceCounter(&liPerfNow);　　double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;　　time/=m_liPerfFreq.QuadPart;

60、　　if(p!=6)　　{Disp(b);getchar();}　　printf("\n用冒泡排序法用的時間為%f秒；",time);　　FILE *fp;

61、;　　fp=fopen("冒泡排序.txt","w");　　for(i=0;i<N;i++)　　fprintf(fp,"%d ",b[i]);　　fclose(fp);return(time);<b&

62、gt;　　}　　double Theapsort(int a[],int n,int p) 　　{　　int i;　　int b[N];&

63、lt;/p>　　for(i=0;i<N;i++)　　b[i]=a[i];　　LARGE_INTEGER m_liPerfFreq={0};　　QueryPerformanceFrequency(&m_liPerfFreq); <p&g

64、t;　　LARGE_INTEGER m_liPerfStart={0};　　QueryPerformanceCounter(&m_liPerfStart);　　heapsort(b,N,p);　　LARGE_INTEGER liPerfNow={0};　　Quer

65、yPerformanceCounter(&liPerfNow);　　double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;　　time/=m_liPerfFreq.QuadPart;　　if(p!=6)<

66、/p>　　{Disp(b);getchar();}　　printf("\n用堆排序法用的時間為%f秒；",time);　　FILE *fp;　　fp=fopen("堆排序.txt","w"

67、);　　for(i=0;i<N;i++)　　fprintf(fp,"%d ",b[i]);　　fclose(fp);return(time);　　}　　double

68、Tquicksort(int a[],int n,int p)　　{　　int i;　　int b[N];　　for(i=0;i<N;i++)</

69、p>　　b[i]=a[i];　　LARGE_INTEGER m_liPerfFreq={0};　　QueryPerformanceFrequency(&m_liPerfFreq); 　　LARGE_INTEGER m_liPerfStart={0};

70、　　QueryPerformanceCounter(&m_liPerfStart);　　quicksort(b,N,p);　　LARGE_INTEGER liPerfNow={0};　　QueryPerformanceCounter(&liPerfNow);

71、;　　double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;　　time/=m_liPerfFreq.QuadPart;　　if(p!=6)　　{Disp(b);getchar(); }<

72、/p>　　printf("\n用快速排序法用的時間為%f秒；",time);　　FILE *fp;fp=fopen("快速排序.txt","w"); 　　for(i=0;i<N;i++)　　fprintf(fp,&quo

73、t;%d ",b[i]);　　fclose(fp); return(time);　　}　　void BubleSort(double a[]) //時間數(shù)組的冒泡排序　　{ </p

74、>　　int i,j; 　　double temp; 　　for(i=1;i<6;i++) 　　{ 　　for(j=4;j>=i;j--) 　　if(

75、a[j+1]<a[j]) 　　{ 　　temp=a[j+1]; 　　a[j+1]=a[j]; 　　a[j]=temp; 　　}

76、　　} 　　} 　　void menu()　　{　　printf(" 歡迎來到排序綜合

77、系統(tǒng)! \n");　　printf(" ============================================== \n");　　printf("

78、 \n");　　printf(" 菜單 \n");　　printf("

79、 \n");　　printf(" \n");　　printf(" (1)---直接插入排序

80、 \n");　　printf(" (2)---直接選擇排序 \n");　　printf(" (3)---冒泡排序 \n");&

81、lt;/p>　　printf(" (4)---快速排序 \n");　　printf(" (5)---堆排序 \n");

82、　　printf(" (6)---時間效率比較 \n");　　printf(" (7)---顯示隨機(jī)數(shù) \n");　　prin

83、tf(" (0)---退出系統(tǒng) \n");　　printf("\n 請在上述序號中選擇一個并輸入: ");　　}</p&g

84、t;　　void main() 　　{ 　　int i,p,a[N];　　srand((int)time(NULL)); /*隨機(jī)種子*/　　for(i=0;i<N;i++)

85、　　a[i]=rand()%50000+1;　　while(1)　　{　　system("cls");　　menu();</b&g

86、t;　　scanf("%d",&p); 　　if(p==0)　　{　　printf("===>謝謝使用!\n");&l

87、t;p>　　getchar();　　break;　　}　　double TIMES[5],TIMES1[5];//時間數(shù)組　　switch(p)<

88、/p>　　{　　case 1:TInsertSort(a,p);printf("\n請按任意鍵繼續(xù)...");getchar();break;　　case 2:TSelectSort(a,p);printf("\n請按任意鍵繼續(xù)...");getch

89、ar();break;　　case 3:TBubbleSort(a,p);printf("\n請按任意鍵繼續(xù)...");getchar();break;　　case 4:Tquicksort(a,N,p);printf("\n請按任意鍵繼續(xù)...");getchar();break;<

90、p>　　case 5:Theapsort(a,N,p);printf("\n請按任意鍵繼續(xù)...");getchar();break;　　case 6:system("cls");　　TIMES1[1]=TIMES[1]=TInsertSort(a,p);TIMES1[2]=TIMES[2]=TSelectS

91、ort(a,p); TIMES1[3]=TIMES[3]=TBubbleSort(a,p);TIMES1[4]=TIMES[4]=Tquicksort(a,N,p);TIMES1[5]=TIMES[5]=Theapsort(a,N,p);getchar();　　BubleSort(TIMES);　　printf("\n\n");

92、　　{　　printf("排序這組數(shù)據(jù)兩種較快的排序法分別是：\n");　　if(TIMES[1]==TIMES1[1]) printf("直接插入排序:%f秒!\n",TIMES[1]); <

93、p>　　if(TIMES[1]==TIMES1[2]) printf("直接選擇排序:%f秒!\n",TIMES[1]); 　　if(TIMES[1]==TIMES1[3]) printf("冒泡排序:%f秒!\n",TIMES[1]); 　　if(TIMES[1]==TIMES1[4]) pri

94、ntf("快速排序:%f秒!\n",TIMES[1]); 　　if(TIMES[1]==TIMES1[5]) printf("堆排序:%f秒!\n",TIMES[1]);　　if(TIMES[1]!=TIMES[2])　　{</p

95、>　　if(TIMES[2]==TIMES1[1]) printf("直接插入排序:%f秒!\n",TIMES[2]); 　　if(TIMES[2]==TIMES1[2]) printf("直接選擇排序%f秒!\n",TIMES[2]); 　　if(TIMES[2]

96、==TIMES1[3]) printf("冒泡排序%f秒!\n",TIMES[2]); 　　if(TIMES[2]==TIMES1[4]) printf("快速排序%f秒!\n",TIMES[2]); 　　if(TIMES[2]==TIMES1[5]) printf("堆排序%f秒!\n&quo

97、t;,TIMES[2]); 　　}　　} printf("\n請按任意鍵繼續(xù)...");srand((int)time(NULL));　　for(i=0;i<N;i++) {a[i]=rand()%30000+1;} getchar();break

98、;　　case 7:Disp(a);FILE *fp;fp=fopen("隨機(jī)數(shù).txt","w");　　for(i=0;i<N;i++)fprintf(fp,"%d ",a[i]);fclose(fp);getchar();printf("\n請按任意鍵繼續(xù)...")

99、;getchar();break;　　default:Wrong();printf("\n請按任意鍵繼續(xù)...");getchar();break;　　}　　}

100、;　　}　　五、測試數(shù)據(jù)和結(jié)果 　　本程序在VC++環(huán)境下實現(xiàn)，下面是對以上測試數(shù)據(jù)的運行結(jié)果。　　(1) 主菜單顯示如下：　　(2)各分界面：　　主菜

101、單　　測試　　結(jié)果　　六、結(jié)束語　　在這次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計中,排序綜合,通過該題目的設(shè)計過程,加深了對排序算法的理解,對排序算法上基本運

眾賞文庫> 全部分類> 畢業(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è)計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載