《数据结构课程设计排序实验报告》由会员分享，可在线阅读，更多相关《数据结构课程设计排序实验报告（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告专业班级姓名学号指导教师起止时间课程设计：排序综合一、任务描述利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、 起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文 件中。（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中 两种较快的方法。要求：根据以上任务说明，设计程序完成功能。二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：（1）随机生成N个整数，存放到线性表中；（ 2）起泡排序并计算
2、所需时间；（ 3）简单选择排序并计算时间；（ 4）希尔排序并计算时间；（ 5）直接插入排序并计算所需时间；（ 6 ）时间效率比较。2、数据对象分析存储数据的线性表应为顺序存储。三、数据结构设计使用顺序表实现，有关定义如下：typedef int Status;typedefint KeyType ;/设排序码为整型量typedefint InfoType;typedefstruct /定义被排序记录结构类型KeyTypekey ;/排序码I nfoType otherinfo;/其它数据项 RedType ;typedef struct RedType * r;/存储带排序记录的顺序表r0作哨
3、兵或缓冲区int length ;/顺序表的长度 SqList ; /定义顺序表类型四、功能设计（一）主控菜单设计 为实现通各种排序的功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这 些菜单项配上相应的功能。程序运行后，给出5 个菜单项的内容和输入提示，如下：1. 起泡排序2. 简单选择排序3. 希尔排序4. 直接插入排序0. 退出系统(二) 程序模块结构由课题要求可将程序划分为以下几个模块(即实现程序功能所需的函数) 主控菜单项选择函数menu() 创建排序表函数InitList_Sq() 起泡排序函数 Bubble_sort() 简单选择排序函数 SelectSort() 希尔排
4、序函数 ShellSort(); 对顺序表 L 进行直接插入排序函数 Insertsort()(三) 函数调用关系 程序的主要结构(函数调用关系)如下图所示。其中main()是主函数，它负责调用各函数。进行调用菜单函数menu(),根据选择项04调用相应的函数。main ()函数使for 循环实现重复选择。其循环结构如下：for (;)long start,end;switch(menu()case 1:printf(* 起泡排序 *n); start=clock();Bubble_sort(L);end=clock();printf(%d msn,end-start); fp=fopen(D
5、: 起泡排序 .txt,w);if(fp=NULL)打开文件失败printf(打开文件失败!n); exit(1);for(i=1;i=L.length;i+)fprintf(fp,%d ,L.ri); fclose(fp);break;case 2:printf(*简单选择排序 *n);start=clock();SelectSort(L);end=clock();printf(%d msn,end-start);fp=fopen(D:直接插入排序.txt,w);if(fp=NULL)打开文件失败printf(”简单选择排序!n); exit(1);for(i=1;i=L.length;i+
6、)fprintf(fp,%d ,L.ri); fclose(fp);break;case 3:printf(* 希尔排序 *n); start=clock();ShellSort(L,an,14);end=clock();printf(%d msn,end-start);fp=fopen(D:希尔排序.txt,w); if(fp=NULL)打开文件失败printf(打开文件失败!n); exit(1);for(i=1;i=L.length;i+) fprintf(fp,%d ,L.ri);fclose(fp);break;case 4:printf(* 直接插入排序 *n); start=cl
7、ock();Insertsort(L);end=clock(); printf(%d msn,end-start); fp=fopen(D:直接插入排序.txt,w);if(fp=NULL)打开文件失败printf(打开文件失败!n); exit(1);for(i=1;i=L.length;i+) fprintf(fp,%d ,L.ri);fclose(fp);break;case 0:printf(t 退 出 ！n); return ;（四）文件结构1、sort.h:单链表相关的定义与声明2、sort.cpp:单链表运算的实现3、menu.h:主菜单函数的声明4、menu.cpp:主菜单函数
8、的实现5、mn.cpp:主函数（五）各函数的算法设计1 、 InitList_Sq（）算法原理：数组指针r指示线性表的基址length指示线性表的当前长度，将随机生成的数 赋给线性表，并生成相应文件。开始关闭文件流程图：代码描述： Status InitList_Sq(SqList &L) /构造一个线性表FILE *fp;L.r=(RedType *) malloc(LIST_INIT_SIZE*sizeof(RedType); if (! L.r) exit(OVERFLOW); /存储分配失败 L.length=30001; /表长度为 30001srand(unsigned)time(
9、NULL);for(int i=1;i=L.length;i+)L.ri.key=rand()%30001+1;fp=fopen(D:构造一个线性表.txt,w); if(fp=NULL)打开文件失败printf(打开文件失败!n);exit(1);for(i=1;i=L.length;i+)fprintf(fp,%d ,L.ri); fclose(fp);return OK;/InitList_Sq算法的时间复杂度分析： O(n)2.Bubble_sort() 算法原理：每趟不断将记录两两比较，若发现逆序，则交换两个记录，使排序码较小的元素 逐渐从后部移向前部(就象水底的气泡一样逐渐向上冒)
10、。流程图：开始i=1N-,iL .1 engthYJ=iL.lngthiYNL.jL.j+1YJ+i+结束L.jL.j+1N代码描述：void Bubble_sort(SqList &L)RedType x;int n;n=L.length;/表长for (int i=1; i=i; j-) if(LT(L.rj+1.key,L.rj.key) flag=1;/有交换，置标志x=L.rj;/L.rj L.rj+1L.rj=L.rj+1;L.rj+1=x;if(flag=0) break;/若无交换则可结束冒泡排序算法的时间复杂度分析：O(n2)3、SelectSort()算法原理：第1趟：从R
11、1Rn中选取最小值，与R1交换； 第2趟：从R2Rn中选取最小值，与R2交换； 第i趟：从RiRn中选取最小值，与Ri交换;第n -1趟：从Rn-1Rn中选取最小值，与Rn1交换.共通过 n1 趟，得到一个按排序码从小到大排列的有序序列流程图：开始i=1iL.I engthKvL.lengthYL.rjL.rkYJ=kK+Ni!=jY结束L.riL. rj冃K=j+1代码描述：void SelectSort(SqList &L) /对顺序表进行简单选择排序RedType x;for (int i=1; iL.length; +i) /在 L.ri.L.length 中选择 key 最小的记录
12、int k=i;for(int j=i+1;j=L.length ; j+)if ( LT(L.rj.key,L.rk.key) k=j; if(k!=i)x=L.ri;L.ri=L.rj;L.rj=x; /SelectSort算法的时间复杂度分析：O(n2)4、ShellInsert()算法原理：(1) 、 分组、组内直接插入排序；(2) 、组数逐次减小；(3) 、组数=1，结束。代码描述：void ShellInsert(SqList &L,int dk) 一趟Shell排序，dk为步长int i;for(i=dk+1;i0)&(LT(L.r 0.key ,L.r j.key );j-=d
13、k) L.r j+dk=L.r j;L.r j+dk=L.r 0;void ShellSort(SqList &L,int dlta,int t) /Shell排序，dlta为增量序列，t为增量个数int k;for(k=0;kt;k+)ShellInsert(L,dltak);/ ShellSort算法的时间复杂度分析：O(n(log 2n)2)5、Insertsort() 算法原理：每步将一个待排序的对象，按其排序码大小，插入到前面已经排好序的一组对象 的适当位置上，直到对象全部插入为止。在已形成的有序表中顺序查找，并在适当位置插入， 把原来位置上的元素向后顺移。流程图：N代码描述：void Insertsort(SqList &L) /对顺序表L进行直接插入排序 for(int i=2;i=L.length;i+)if (LT(L.ri.key,L.ri-1
