數(shù)據庫課程設計--綜合排序軟件

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

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

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

文檔簡介

1、　　綜合排序軟件　　1．題目：　　利用隨機函數(shù)產生N個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。　　1)至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排

2、序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。　　2)統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。　　3)如果采用4種或4種以上的方法者，可適當加分。　　2. 課題研究的目的和意義：　　排序是計算機程序設計中一

3、種重要的操作，它的功能是將一個數(shù)據元素的任意序列，重新排列成一個按關鍵字有序的序列。目前我們已經掌握的排序方法很多，每一種方法都有其各自的優(yōu)點，通過對各種算法的研究以及不同方法之間的比較研究，能讓我們可以從更高的層次上理解和掌握排序算法，而且能夠在不同環(huán)境下，根據數(shù)據的不同特點，選擇不同的方法。因此，我們開展對排序算法的研究將更有利于我們解決問題，提高效率。 　　3.可行

4、性論證：　?。?）就算法本身而言，它們是穩(wěn)定的，時間復雜度是有限階的，每種算法的思想是可行的。　?。?）處理數(shù)據（20000個隨機數(shù)）是有限的，并且同過這些排序方法可以實現(xiàn)排序。　　4．課程總體設計方案：　　（1）對小組內個成員進行分配，每位小組成員負

5、責一種算法。　　（2）討論研究流程：制定算法的總體思路,查閱相關資料，按照預先分配編寫程序，程序整合，實驗并修改。　　（3）對程序中的排序方法進行擴充，小組集體研究了簡單選擇排序，希爾排序，快速排序三種方法。　?。?）最后總結。　　5

6、.若干關鍵技術及設計結果　　源程序：　　#include <stdio.h>　　#include <stdlib.h>　　#include <time.h>

7、　　#define MAXSIZE 2300　　typedef int KeyType;　　typedef int InfoType;　　typedef struct{　　KeyType key;　　InfoType other

8、info;　　}RcdType;　　typedef struct{　　RcdType r[MAXSIZE+1];　　long length;　　}SqList;&l

9、t;/b>　　SqList CreaList ()　　{//建立　　long i;　　SqList L;　　f

10、or(i=1;i<MAXSIZE+1;i++)　　{　　L.r[i].key=(rand()%MAXSIZE);　　}　　L.length=MAXSIZE;<p

11、>　　return L;　　}//建立　　void PrintfList(SqList * L)　　{//打印　　long i;<

12、;/b>　　for(i=1;i<MAXSIZE+1;i++)　　{　　printf("%8d",L->r[i].key);　　}<

13、;p>　　}　　//1折半　　SqList BInsertSort(SqList L,long bj1[],long jh1[])　　{　　bj1[0]

14、=0;jh1[0]=0;　　long i,j,low,high,k;　　for(i=2; i<=L.length; ++i)　　{　　L.r[0]=L.r[i];　　jh1[0]+=1;

15、　　low=1;high=i-1;　　while(low<=high)　　{　　k=(low+high)/2;　　if(L.r[0].key <L.r[k].key)</p&

16、gt;　　{high=k-1;bj1[0]+=1;}　　else {low=k+1;bj1[0]+=1;}　　}　　for(j=i-1;j>=high+1;j--)　　{ L.r[j+1]=L.r[j];

17、jh1[0]+=1;}　　L.r[high+1]=L.r[0];　　jh1[0]+=1;　　}　　return L;　　}//折半<

18、;/b>　　//2直接　　SqList InsertSort(SqList L,long bj2[],long jh2[])　　{ 　　long j,k;

19、;　　bj2[0]=0;　　jh2[0]=0;　　for(k=2; k<=L.length; ++k)　　if(L.r[k].key< L.r[k-1].key )

20、　　{　　bj2[0]+=1;　　L.r[0] = L.r[k];　　L.r[k]=L.r[k-1];　　jh2[0]+=2;　　for(j=k-2; L.r[0].ke

21、y<L.r[j].key; --j)　　{　　L.r[j+1]=L.r[j]; jh2[0]+=1;bj2[0]+=1;　　}　　L.r[j+1]=L.r[0]; &

22、lt;p>　　jh2[0]+=1;　　}　　elsebj2[0]+=1;　　return L;　　}//直接

23、　　//3冒泡　　SqList Bubble(SqList L,long bj3[],long jh3[])　　{　　long i,j;

24、bj3[0]=0;　　jh3[0]=0;　　for(j=L.length;j>=2;j--)　　for(i=1;i<j;i++)　　{ if(L.r[i].key>L.r[i+1].key)<

25、;/p>　　{　　L.r[0]=L.r[i];　　L.r[i]=L.r[i+1];　　L.r[i+1]=L.r[0];　　jh3[0]+=3;　　bj3[0]+=1

26、;　　}　　else bj3[0]+=1;　　}　　return L;　　}//冒泡</b&

27、gt;　　//4堆排序　　SqList HeapAdjust(SqList L,int s,int m ,long bj4[],long jh4[])　　{//建堆　　RcdType rc;<

28、;/p>　　long j;　　rc=L.r[s];　　for(j=2*s;j<=m;j*=2)　　{　　if(j<m&&L.r[j].key

29、<L.r[j+1].key)　　{　　j++;　　if(j<m) bj4[0]+=1;　　}　　if(L

30、.r[j].key<rc.key)　　{　　bj4[0]+=1;　　break;　　}　　L.r[s]=L.r

31、[j];　　jh4[0]+=1;　　s=j;　　}　　L.r[s]=rc;　　jh4[0]+=1;<b&g

32、t;　　return L;　　}　　SqList HeapSort(SqList L,long bj4[],long jh4[])　　{//堆排序　　long

33、 i;　　bj4[0]=0;　　jh4[0]=0;　　for (i=L.length/2;i>0;i--)　　L=HeapAdjust(L,i,L.length,bj4,

34、jh4);　　for(i=L.length;i>1;i--)　　{　　L.r[0]=L.r[i];　　L.r[i]=L.r[1];　　L.r[1]=L.r[0];

35、　　jh4[0]+=3;　　L=HeapAdjust(L,1,i-1,bj4,jh4);　　}　　return L;　　}

36、;　　//堆排序　　//5簡單選擇排序　　SqList SeledSort(SqList L,long bj5[],long jh5[])　　{ <

37、p>　　long i,j,k;　　bj5[0]=0;　　jh5[0]=0;　　for(i=1; i<=L.length; ++i)　　{</

38、p>　　j=i;　　for(k=i+1; k<=L.length; ++k)　　{　　if(L.r[k].key<L.r[j].key)

39、　{ 　　{j=k;bj5[0]+=1;}　　if(i!=j)　　{　　L.r[0] = L.r[i];　　L.r[i] = L.r[

40、j];　　L.r[j] = L.r[0];　　jh5[0]+=3;　　}　　}　　else bj5[0]+=1;

41、　　}　　}　　return L;　　}//簡單選擇排序　　//6希爾</p

42、>　　SqList ShellSort(SqList L,int dk ,long bj6[],long jh6[])　　{　　long i,j;　　for(i=1+dk;i<=L.length;i++)

43、　　{　　if(L.r[i].key<L.r[i-dk].key)　　{　　L.r[0]=L.r[i];　　jh6[0]+=1;

44、　　bj6[0]+=1;　　for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)　　{ 　　{ 　　L.r[j

45、+dk]=L.r[j];jh6[0]+=1;　　if(j>0)bj6[0]+=1;　　} 　　L.r[j+dk]=L.r[0];　　jh6[0]+=1;　　}</

46、b>　　}　　else bj6[0]+=1;　　}　　return L;　　} </

47、b>　　SqList ShallSort(SqList L,long bj6[],long jh6[])　　{　　jh6[0]=0;　　bj6[0]=0;

48、;　　int dlta[]={64,32,16,8,4,2,1};　　long i;　　for(i=0;i<7;i++)　　L=ShellSort(L,dlta[i],bj6,jh6);

49、　　return L;　　}//希爾　　//7快速　　int Partition(SqList * L,int low,int high,long bj7[],long jh7[])

50、;　　{//快排　　long pivotkey;　　L->r[0].key=L->r[low].key;　　pivotkey=L->r[low].key;　　jh7[0]+=2;</p&g

51、t;　　while(low<high)　　{　　while(low<high && pivotkey<=(L->r[high].key)) 　　{--high;if(low<high)bj7[0]+=1;}&

52、lt;/p>　　{L->r[low].key=L->r[high].key;jh7[0]+=1;}　　while(low<high && (L->r[low].key)<=pivotkey) 　　{++low;if(low<high)bj7[0]+=1;}

53、　　{ L->r[high].key=L->r[low].key;jh7[0]+=1;}　　}　　{L->r[low].key=L->r[0].key ;jh7[0]+=1;} 　　return low;&

54、lt;p>　　}　　void QSort(SqList * L,int low,int high,long bj7[],long jh7[] )　　{　　long pivotloc;　　if

55、(low<high)　　{　　pivotloc=Partition(L,low,high, bj7,jh7);　　QSort(L,low,pivotloc-1, bj7,jh7 );　　QSort(L,pivotloc+1,hi

56、gh, bj7,jh7 );　　}　　}　　SqList QuickSort(SqList L,long bj7[],long jh7[] )　　{<

57、/p>　　bj7[0]=0;　　jh7[0]=0;　　QSort(&L,1,L.length, bj7,jh7 );　　return L;&

58、lt;p>　　}　　//快速　　void time( void )　　{//時間　　struct tm *newtime;<

59、;p>　　char tmpbuf[128];　　time_t lt1;　　time( &lt1 );　　newtime=localtime(&lt1);　　strftime( tmpbuf, 128, " 今天是： %A, da

60、y %d of %B in the year %Y.\n", newtime);　　printf(tmpbuf);　　}　　void time1(void)　　{//時間</p&g

61、t;　　struct tm *ptr;　　time_t lt;　　lt =time(NULL);　　ptr=gmtime(&lt);　　printf(" 現(xiàn)在是：");

62、　　printf(ctime(&lt));　　}　　main()　　{　　long i,n,k;　　SqLi

63、st L,Q;　　long bj1[1],bj2[1],bj3[1],bj4[1],bj5[1],bj6[1],bj7[1];//比較　　long jh1[1],jh2[1],jh3[1],jh4[1],jh5[1],jh6[1],jh7[1];//交換　　clock_t start1,start2,start3

64、, start4,start5, start6,start7;//開始　　clock_t finish1,finish2,finish3,finish4,finish5,finish6,finish7;//結束　　//long start,finish;　　long m,t;

65、　　SqList CreaList ();　　printf("\n***********************************************************\n");　　time();&

66、lt;b>　　time1();　　printf("***********************************************************\n");　　printf("20000個數(shù)沒能實現(xiàn)。暫時只實現(xiàn)2400個數(shù)。希望老師能給分析一下。謝謝！");</

67、p>　　start1:　　printf("\n請選擇：\n1.進入；\n2.退出。\n");　　scanf("%d",&n);　　if(n==1)</p&g

68、t;　　{　　start: 　　printf("\n請選擇：\n0.全部排序；\n1.折半插入排序；\n2.直接插入排序；\n3.冒泡排序；\n4.堆排序；");　　printf("\n5.簡單選擇排序；\n6.希爾

69、排序；\n7.快速排序；\n8.退出。\n");　　scanf("%d",&k);　　if(k!=8&&k!=0)　　{　　printf("是不是顯示結果：\n1.顯示。

70、2。不顯示。\n");　　scanf("%d",&m);　　}　　switch(k)　　{<

71、;p>　　case 0:　　Q=CreaList();　　L=Q;　　printf("是不是顯示生成的數(shù)：\n1.顯示。2。不顯示。\n");　　scanf("

72、%d",&m);　　if(m==1)　　{　　printf("\n20000個隨機的數(shù)為:\n");　　PrintfList(&L) ;</p&

73、gt;　　}　　start1=clock();　　L=BInsertSort(L,bj1,jh1);　　if(m==1)　　{</

74、p>　　printf("\n20000個排好序的數(shù)為:\n");　　PrintfList(&L);　　}　　finish1=clock();　　printf("\n1.

75、用折半插入排序法用的時間為%f秒；",((double)((finish1 - start1)/CLOCKS_PER_SEC)));　　printf("\n 交換%ld次,比較%ld次。\n",jh1[0],bj1[0]);　　L=Q;　　st

76、art2=clock();　　L=InsertSort(L,bj2,jh2);　　finish2=clock();　　printf("\n2.用直接插入排序法用的時間為%f秒；",((double)((finish2 - start2)/CLOCKS_PER_SEC)));

77、　　printf("\n 交換%ld次,比較%ld次。\n",jh2[0],bj2[0]);　　L=Q;　　start3=clock();　　L=Bubble(L,bj3,jh3);　　fi

78、nish3=clock();　　printf("\n3.用冒泡排序法用的時間為%f秒；",((double)((finish3 - start3)/CLOCKS_PER_SEC)));　　printf("\n 交換%ld次,比較%ld次。\n",jh3[0],bj3[0]);<p&g

79、t;　　L=Q;　　start4=clock();　　L=HeapSort(L,bj4,jh4);　　finish4=clock();　　printf("\n4.用堆排序法用的時間為%f秒；",((double)(

80、(finish4 - start4)/CLOCKS_PER_SEC)));　　printf("\n 交換%ld次,比較%ld次。\n",jh4[0],bj4[0]);　　L=Q;　　start5=clock();

81、　　L=SeledSort(L,bj5,jh5);　　finish5=clock();　　printf("\n5.用簡單選擇排序法用的時間為%f秒；",((double)((finish5-start5)/CLOCKS_PER_SEC)));　　printf("\n 交換%ld次,

82、比較%ld次。\n",jh5[0],bj5[0]);　　L=Q;　　start6=clock();　　L=ShallSort(L,bj6,jh6);　　finish6=clock();

83、;　　printf("\n6.用希爾排序法用的時間為%f秒；",((double)((finish6-start6)/CLOCKS_PER_SEC)));　　printf("\n 交換%ld次,比較%ld次。\n",jh6[0],bj6[0]);　　L=Q;

84、;　　start7=clock();　　L=QuickSort(L,bj7,jh7);　　finish7=clock();　　printf("\n7.用快速排序法用的時間為%f秒；",((double)((finish7-start7)/CLOCKS_PER_SEC)))

85、;　　printf("\n 交換%ld次,比較%ld次。\n",jh7[0],bj7[0]); 　　goto start;　　case 1:　　L=CreaList();<p

86、>　　start1=clock();　　printf("%f\n",start1);　　L=BInsertSort(L,bj1,jh1);　　finish1=clock(); 　　printf("%f\n",finis

87、h1);　　if(m==1)　　{　　printf("\n20000個用折半插入排序法排好序的數(shù)為:\n");　　PrintfList(&L);

88、　　}　　printf("\n用折半插入排序法用的時間為%f秒；",((double)((finish1 - start1)/CLOCKS_PER_SEC)));　　printf("\n交換%ld次,比較%ld次。\n",jh1[0],bj1[0]);<

89、/p>　　goto start;　　case 2:　　L=CreaList();　　start2=clock();　　L=InsertSort(L,bj2,jh2);

90、;　　finish2=clock();　　if(m==1)　　{　　printf("\n20000個用直接插入排序法排好序的數(shù)為:\n");　　PrintfList(&

91、L);　　}　　printf("\n用直接插入排序法用的時間為%f秒；",((double)((finish2 - start2)/CLOCKS_PER_SEC)));　　printf("\n交換%ld次,比較%ld次。\n",jh2[

92、0],bj2[0]);　　goto start;　　case 3:　　L=CreaList();　　start3=clock();　　L=Bubble(L,bj3,jh3);

93、;　　finish3=clock();　　if(m==1)　　{　　printf("\n20000個用冒泡排序法排好序的數(shù)為:\n");　　PrintfL

94、ist(&L);　　}　　printf("\n用冒泡排序法用的時間為%f秒；",((double)((finish3 - start3)/CLOCKS_PER_SEC)));　　printf("\n交換%ld次,比較%ld次。\n&qu

95、ot;,jh3[0],bj3[0]);　　goto start;　　case 4:　　L=CreaList();　　start4=clock();　　L=HeapSort(L,bj4,jh4)

96、;　　finish4=clock();　　if(m==1)　　{　　printf("\n20000個用堆排序法排好序的數(shù)為:\n");

97、　　PrintfList(&L);　　} 　　printf("\n用堆排序法用的時間為%f秒；",((double)((finish4 - start4)/CLOCKS_PER_SEC)));　　printf("\n交換%ld次,比較%

98、ld次。\n",jh4[0],bj4[0]);　　goto start;　　case 5:　　L=CreaList();　　start5=clock();　　L=SeledSort(

99、L,bj6,jh6);　　finish5=clock();　　if(m==1)　　{　　printf("\n20000個用簡單選擇排序法排好序的數(shù)為:\n");</p&g

100、t;　　PrintfList(&L);　　} 　　printf("\n用簡單選擇排序法用的時間為%f秒；",((double)((finish5 - start5)/CLOCKS_PER_SEC)));　　printf(&q

101、uot;\n交換%ld次,比較%ld次。\n",jh5[0],bj5[0]);　　goto start;　　case 6: 　　L=CreaList();　　start6=clock();<p&

102、gt;　　L=ShallSort(L,bj6,jh6);　　finish6=clock();　　if(m==1)　　{　　printf("\n20000個用希爾排序法排好序的數(shù)為:\n&

103、quot;);　　PrintfList(&L);　　}　　printf("\n用希爾排序法用的時間為%f秒；",((double)((finish6 - start6)/CLOCKS_PER_SEC)));

104、　　printf("\n交換%ld次,比較%ld次。\n",jh6[0],bj6[0]);　　goto start;　　case 7: 　　L=CreaList();　　start7=clock();</p&

105、gt;　　L=QuickSort(L,bj7,jh7);　　finish7=clock();　　if(m==1)　　{　　printf("\n20000個用快速排序

106、法排好序的數(shù)為:\n");　　PrintfList(&L);　　}　　printf("\n用快速排序法用的時間為%f秒；",((double)((finish7-start7)/CLOCKS_PER_SEC)));

107、　　printf("\n交換%ld次,比較%ld次。\n",jh7[0],bj7[0]);　　goto start;　　case 8: 　　{　　end:

108、 　　printf("確定退出嗎？\n1.確定。2.取消。\n");　　scanf("%d",&t);　　if(t==1)&l

109、t;b>　　{　　printf(" \n***************************************************\n 謝謝!\n");　　printf(" \n*************************************************

110、**\n") ;　　for(i=0;i<10000000000L;++i);　　break;　　}　　else goto start1;&

111、lt;b>　　}　　default : goto start1;　　}　　}　　else if(n==2) 　　goto end

112、;　　else goto start1;　　return 1;　　}　　運行結果截圖：　　程序運

113、行初始界面：　　菜單選擇：　　產生隨機數(shù)：　　數(shù)據排序：　　排序結果：<

114、;p>　　折半插入排序方法部分截圖：　　6．參考文獻及總結　　總結：通過此次課程設計，增強了對平時所學薄弱環(huán)節(jié)的學習與加強，作為本組組長，除了對數(shù)據結構及C語言學習加強之外，更學會了如何與他人合作。　　參考文獻：譚浩強《C程序設計（第三版）》清華大學出版

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

溫馨提示

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

數(shù)據庫課程設計--綜合排序軟件

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據庫課程設計--綜合排序軟件

文檔簡介

溫馨提示

最新文檔

評論

免費下載