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

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

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

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

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

文檔簡(jiǎn)介

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

2、 　　學(xué) 號(hào) 　　指導(dǎo)教師 　　起止時(shí)間 2013.5.6~2013.5.20 　　課程設(shè)計(jì)：排序綜合</p

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

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

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

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

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

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ù)及說(shuō)明　　#include <stdio.h>　　#define MAXSIZE 20　　#define LT(a,b) ((a)<(b))

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

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

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

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

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

16、t;　　(0)---退出系統(tǒng)　　請(qǐng)?jiān)谏鲜鲂蛱?hào)中選擇一個(gè)并輸入：　　（二）程序模塊結(jié)構(gòu)　　由課題要求可將程序劃分為以下幾個(gè)模塊（即實(shí)現(xiàn)程序功能所需的函數(shù)）：　　主控菜單項(xiàng)選擇函數(shù)menu_select()<

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

18、;　　程序的主要結(jié)構(gòu)（函數(shù)調(diào)用關(guān)系）如下圖所示。 　　其中main()是主函數(shù)，它進(jìn)行菜單驅(qū)動(dòng)，根據(jù)選擇項(xiàng)1~0調(diào)用相應(yīng)的函數(shù)。　?。ㄋ模┖瘮?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=====>按鍵錯(cuò)誤!\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--) /*比較,找出本趟最小關(guān)鍵字的記錄*/　　if (a[j]<a[j-1]) 　　{ 　　temp=a[j]; /*進(jìn)行交換,將最小關(guān)鍵字記錄前移*/　　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用直接插入排序法用的時(shí)間為%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用直接選擇排序法用的時(shí)間為%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用冒泡排序法用的時(shí)間為%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用堆排序法用的時(shí)間為%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用快速排序法用的時(shí)間為%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í)間數(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(" 歡迎來(lái)到排序綜合系統(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)---時(shí)間效率比較 \n");　　printf(" (7)---顯示隨機(jī)數(shù) \n");　　printf(&qu

83、ot; (0)---退出系統(tǒng) \n");　　printf("\n 請(qǐng)?jiān)谏鲜鲂蛱?hào)中選擇一個(gè)并輸入: ");　　}&l

84、t;p>　　void main() 　　{ 　　int i,p,a[N];　　srand((int)time(NULL)); /*隨機(jī)種子*/　　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í)間數(shù)組　　switch(p)

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

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

90、　case 5:Theapsort(a,N,p);printf("\n請(qǐng)按任意鍵繼續(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請(qǐng)按任意鍵繼續(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("隨機(jī)數(shù).txt","w");　　for(i=0;i<N;i++)fprintf(fp,"%d ",a[i]);fclose(fp);getchar();printf("\n請(qǐng)按任意鍵繼續(xù)...");getch

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

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

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

眾賞文庫(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)益歸上傳用戶所有。
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ì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載