數(shù)據(jù)結(jié)構(gòu)課程設(shè)計模板作業(yè)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計班級 計算機科學(xué)與技術(shù)（2） 學(xué)號 20082308054 姓名 陳進(jìn)勝 指導(dǎo)教師 李振宏 時間： 年 月 日 至 年 月 日成績 指導(dǎo)教師簽字 年 月 日 排序綜合摘要：利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)（20000以上），對這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：1)至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。2)統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準(zhǔn)進(jìn)行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當(dāng)加分。1設(shè)計目的：利用隨機

2、函數(shù)產(chǎn)生N個隨機整數(shù)（20000以上），對這些數(shù)進(jìn)行多種方法進(jìn)行排序2設(shè)計內(nèi)容（1）顯示隨機數(shù)：調(diào)用Dip()函數(shù)輸出數(shù)組a。數(shù)組a中保存有隨機產(chǎn)生的隨機數(shù)。（2）直接選擇排序：通過n-I次關(guān)鍵字間的比較，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i個記錄交換之。（4）冒泡排序：如果有n個數(shù)，則要進(jìn)行n-1趟比較。在第1趟比較中要進(jìn)行n-1次兩兩比較，在第j趟比較中要進(jìn)行n-j次兩兩比較。（5）希爾排序：先將整個待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行一次直接插入排序。（6）直接插入排序：將一個記錄插入到已排序好的有序表中，從

3、而得到一個新的、記錄數(shù)增1的有序表。設(shè)整個排序有n個數(shù)，則進(jìn)行n-1趟插入，即：先將序列中的第1個記錄看成是一個有序的子序列，然后從第2個記錄起逐個進(jìn)行插入，直至整個序列變成按關(guān)鍵字非遞減有序列為止。各種函數(shù)的存儲都是通過順序存儲來存儲的3源程序system("cls");menu(); scanf("%d",&p); 包括加載頭文件，定義結(jié)構(gòu)體、常量和變量，并對它們進(jìn)行初始化工作。 #include <stdio.h> /*標(biāo)準(zhǔn)輸入輸出函數(shù)庫*/#include <conio.h> /*屏幕操作函數(shù)庫*/#include

4、 <stdlib.h> /*標(biāo)準(zhǔn)函數(shù)庫*/#include <time.h> /*時間函數(shù)庫*/#define N 20000void Disp(int a) /數(shù)組輸出函數(shù)int i;system("cls");for(i=0;i<N;i+)if(i-1)%10=9) printf("n"); printf("%-7d",ai); getchar();void InsertSort(int a) /插入排序 FILE *fp; fp=fopen("c:插入排序.txt","

5、w"); int i,j,temp; int bN; for(i=0;i<N;i+) bi=ai; for(i=1;i<N;i+) temp=bi; for(j=i;j>0&&bj-1>temp;j-) bj=bj-1; bj=temp; for(i=0;i<N;i+) fprintf(fp,"%d ",bi); fclose(fp); void SelectSort(int a) /選擇排序 FILE *fp; fp=fopen("c:選擇排序.txt","w"); int i

6、,j,k; int bN; for(i=0;i<N;i+) bi=ai; for(i=0;i<N-1;i+) k=i; for(j=i+1;j<N;j+) if(bj<bk) k=j; if(k!=i) int temp; temp=bk; bk=bi; bi=temp; for(i=0;i<N;i+) fprintf(fp,"%d ",bi);fclose(fp);void BubbleSort(int a)/*冒泡排序算法*/ FILE *fp; fp=fopen("c:冒泡排序.txt","w");

7、int i,j,temp; int bN; for(i=0;i<N;i+) bi=ai;for (i=0;i<N-1;i+) for (j=N-1;j>i;j-)/*比較,找出本趟最小關(guān)鍵字的記錄*/if (bj<bj-1) temp=bj; /*進(jìn)行交換,將最小關(guān)鍵字記錄前移*/bj=bj-1;bj-1=temp; for(i=0;i<N;i+) fprintf(fp,"%d ",bi);fclose(fp); void ShellSort(int a)/*希爾排序算法*/FILE *fp; fp=fopen("c:希爾排序.txt

8、","w");int i,j,d,temp;int bN; for(i=0;i<N;i+) bi=ai;d=N/2;/*d取初值n/2*/while (d>0) for (i=d;i<N;i+)/*將bd.n-1分別插入各組當(dāng)前有序區(qū)中*/j=i-d;while (j>=0 && bj>bj+d) temp=bj; /*bj與bj+d交換*/bj=bj+d;bj+d=temp;j=j-d; d=d/2; /*遞減增量d*/ for(i=0;i<N;i+) fprintf(fp,"%d ",bi

9、);fclose(fp);void menu() /主菜單顯示函數(shù)/ printf(" *綜合排序*n"); printf(" 08計算機二班 陳進(jìn)勝 n"); printf(" * 菜 單 * n"); printf(" * n"); printf(" §1-顯示隨機數(shù) § n"); printf(" §2-直接選擇排序 § n"); printf(" §3-冒泡排序 § n");printf(

10、" §4-希爾排序 § n"); printf(" §5-直接插入排序 § n"); printf(" §6-輸出最短兩個排序 § n"); printf(" §0-退出 § n"); printf(" *n"); printf("n=>請在上述序號中選擇一個并輸入:"); void Wrong() /錯誤提示函數(shù)printf("n=>按鍵錯誤!n");getcha

11、r();void PRT1(double time) /輸出運行時間函數(shù)system("cls");printf("=>程序運行時間為%f秒。",time);printf("n請輸入回車鍵返回!");getchar();getchar();double Min(double x,double y) /求最小值if(x>y)return y;else return x;void main() /主函數(shù) int i,p,aN; double time1,time2,time3,time4,temp;double one,two

12、;clock_t start,end; srand(int)time(NULL); /*隨機種子*/ for(i=0;i<N;i+) ai=rand()%30000+1; while(1)if(p=0) printf("=>謝謝使用!n"); getchar(); break;switch(p)case 1:Disp(a);getchar();break; case 2: start=clock();SelectSort(a);end=clock();time1=(double)(end-start)/CLOCKS_PER_SEC; PRT1(time1);br

13、eak; case 3: start=clock();BubbleSort(a);end=clock();time2=(double)(end-start)/CLOCKS_PER_SEC; PRT1(time2); break;case 4: start=clock();ShellSort(a);end=clock();time3=(double)(end-start)/CLOCKS_PER_SEC; PRT1(time3); break; case 5: start=clock(); InsertSort(a); end=clock(); time4=(double)(end-start)/

14、CLOCKS_PER_SEC; PRT1(time4); break; case 6: one=Min(Min(time1,time2),Min(time3,time4); if(one=time1) two=Min(Min(time2,time3),time4); printf("=>時間最短的排序是“直接選擇排序”。n"); if(one=time2) two=Min(Min(time1,time3),time4); printf("=>時間最短的排序是“冒泡排序”。n"); if(one=time3) two=Min(Min(time1

15、,time2),time4); printf("=>時間最短的排序是“希爾排序”。n"); if(one=time4) two=Min(Min(time1,time2),time3); printf("=>時間最短的排序是“直接插入排序”。n"); if(two=time1) printf("=>其次的排序是“直接選擇排序”。n"); if(two=time2) printf("=>其次的排序是“冒泡排序”。n"); if(two=time3) printf("=>其次的排序

16、是“希爾排序”。n"); if(two=time4) printf("=>其次的排序是“直接插入排序”。n"); getchar();getchar();break;default:Wrong();getchar();break;流程圖調(diào)試分析系統(tǒng)運行圖這個我們開始進(jìn)入的選擇菜單，我們只要選擇06這7個數(shù)字就可以操作了。（如圖1） （圖1）選擇1就會出現(xiàn)20000個隨機數(shù)，在這里不能全部顯示出來，只顯示了一部分。（圖2） （圖2） 選擇2就進(jìn)行直接選擇排序，（如圖3）圖中只出現(xiàn)了直接排序的時間，排好序的數(shù)已經(jīng)從到了c盤中的“選擇排序.txt”文件。分別選擇3、4、5就會分別進(jìn)入了冒泡排序（圖4）、希爾排序（圖5）、直接插入排序（圖6）。顯示同選擇2。 （圖3）（圖4）（圖5）（圖6）選擇6則會出現(xiàn)最快和其次的排序方法，（