数据结构课程设计模板作业

1、数据结构课程设计班级 计算机科学与技术（2） 学号 20082308054 姓名 陈进胜 指导教师 李振宏 时间： 年 月 日 至 年 月 日成绩 指导教师签字 年 月 日 排序综合摘要：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3)如果采用4种或4种以上的方法者，可适当加分。1设计目的：利用随机

2、函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序2设计内容（1）显示随机数：调用Dip()函数输出数组a。数组a中保存有随机产生的随机数。（2）直接选择排序：通过n-I次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之。（4）冒泡排序：如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次两两比较，在第j趟比较中要进行n-j次两两比较。（5）希尔排序：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。（6）直接插入排序：将一个记录插入到已排序好的有序表中，从

3、而得到一个新的、记录数增1的有序表。设整个排序有n个数，则进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序列为止。各种函数的存储都是通过顺序存储来存储的3源程序system("cls");menu(); scanf("%d",&p); 包括加载头文件，定义结构体、常量和变量，并对它们进行初始化工作。 #include <stdio.h> /*标准输入输出函数库*/#include <conio.h> /*屏幕操作函数库*/#include

4、 <stdlib.h> /*标准函数库*/#include <time.h> /*时间函数库*/#define N 20000void Disp(int a) /数组输出函数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-)/*比较,找出本趟最小关键字的记录*/if (bj<bj-1) temp=bj; /*进行交换,将最小关键字记录前移*/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分别插入各组当前有序区中*/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() /主菜单显示函数/ printf(" *综合排序*n"); printf(" 08计算机二班 陈进胜 n"); printf(" * 菜 单 * n"); printf(" * n"); printf(" §1-显示随机数 § 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() /错误提示函数printf("n=>按键错误!n");getcha

11、r();void PRT1(double time) /输出运行时间函数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() /主函数 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;流程图调试分析系统运行图这个我们开始进入的选择菜单，我们只要选择06这7个数字就可以操作了。（如图1） （图1）选择1就会出现20000个随机数，在这里不能全部显示出来，只显示了一部分。（图2） （图2） 选择2就进行直接选择排序，（如图3）图中只出现了直接排序的时间，排好序的数已经从到了c盘中的“选择排序.txt”文件。分别选择3、4、5就会分别进入了冒泡排序（图4）、希尔排序（图5）、直接插入排序（图6）。显示同选择2。 （图3）（图4）（图5）（图6）选择6则会出现最快和其次的排序方法，（