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

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

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

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

文檔簡介

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

2、 　　學號 　　指導教師 　　起止時間 2013.5.6~2013.5.20 　　課程設計：排序綜合</p

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

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

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

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

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

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

9、pe otherinfo; 　　}RedType;　　typedef struct　　{ 　　RedType r[MAXSIZE+1];

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

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

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

13、小　　int length; //length為待排記錄個數(shù)　　}SqList;　　四、功能設計　　（一）主控菜單設計<p&g

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

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

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

17、p>　　插入排序函數(shù)：InsertSort()　　選擇排序函數(shù)：SelectSort()　　冒泡排序函數(shù)：BubbleSort()　　堆排序函數(shù)：heapsort()　?。ㄈ┖瘮?shù)調(diào)用關系

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

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

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

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

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

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

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

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

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

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

28、p>　　a[k]=a[i]; 　　a[i]=temp; 　　} 　　} 　　}　　void BubbleSor

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

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

31、t;/p>　　a[j-1]=temp;　　}　　}　　}　　void creatheap(int a[],int i,int n)

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

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

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

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

36、gt;　　void heapsort(int a[],int n,int p) //堆排序　　{　　int i;　　int t;</p&g

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

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

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

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

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

42、le(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<j){a

43、[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、p>　　}　　}　　}　　double TInsertSort(int a[],int p)　　{</b&

45、gt;　　int i;　　int b[N];　　for(i=0;i<N;i++)　　b[i]=a[i];　　LARGE_INTEGER m_liPe

46、rfFreq={0};　　QueryPerformanceFrequency(&m_liPerfFreq); 　　LARGE_INTEGER m_liPerfStart={0};　　QueryPerformanceCounter(&m_liPerfStart);&l

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

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

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

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

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

52、;　　QueryPerformanceFrequency(&m_liPerfFreq); 　　LARGE_INTEGER m_liPerfStart={0};　　QueryPerformanceCounter(&m_liPerfStart);　　SelectSort(

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

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

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

56、p);return(time);　　}　　double TBubbleSort(int a[],int p)　　{　　int i;&l

57、t;p>　　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_INTEGER liP

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

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

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

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

63、gt;　　for(i=0;i<N;i++)　　b[i]=a[i];　　LARGE_INTEGER m_liPerfFreq={0};　　QueryPerformanceFrequency(&m_liPerfFreq); 　　LA

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

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

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

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

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

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

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

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

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

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

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

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

76、p>　　} 　　} 　　void menu()　　{　　printf(" 歡迎來到排序綜合系統(tǒng)!

77、 \n");　　printf(" ============================================== \n");　　printf("

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

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

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

81、gt;　　printf(" (4)---快速排序 \n");　　printf(" (5)---堆排序 \n");<p&

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

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

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

85、p>　　a[i]=rand()%50000+1;　　while(1)　　{　　system("cls");　　menu();<

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

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

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

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

90、　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]=TSelectSort(a,

91、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");</p

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

93、　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]) printf(&q

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

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

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

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

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

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

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

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

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

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載