数据结构课程设计排序实验报告

1、数据结构课程设计报告专业班级姓名学号指导教师起止时间课程设计：排序综合一、任务描述利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。要求：根据以上任务说明，设计程序完成功能。二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：（1）随机生成N个整数，存放到线性表中；（2）起泡排序并计算所需时间

2、；（3）简单选择排序并计算时间；（4）希尔排序并计算时间；（5）直接插入排序并计算所需时间；（6）时间效率比较。2、数据对象分析存储数据的线性表应为顺序存储。三、数据结构设计使用顺序表实现，有关定义如下：typedefintStatus;设排序码为整型量定义被排序记录结构类型排序码其它数据项typedefintKeyType;/typedefintInfoType;typedefstruct/KeyTypekey;/InfoTypeotherinfo;/RedType;typedefstructRedType*r;/存储带排序记录的顺序表/r0作哨兵或缓冲区intlength;/顺序表的长度S

3、qList;/定义顺序表类型四、功能设计（一）主控菜单设计为实现通各种排序的功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出5个菜单项的内容和输入提示，如下：1 .起泡排序2 .简单选择排序3 .希尔排序4 .直接插入排序0.退出系统(二)程序模块结构由课题要求可将程序划分为以下几个模块(即实现程序功能所需的函数)主控菜单项选择函数menu()创建排序表函数InitList_Sq()起泡排序函数Bubble_sort()简单选择排序函数SelectSort()希尔排序函数ShellSort();对顺序表L进行直接插入排序函数Insertsort

4、()(三)函数调用关系程序的主要结构(函数调用关系)如下图所示。其中main()是主函数，它负责调用各函数。进行调用菜单函数menu(),根据选择项04调用相应的函数。main()函数使for循环实现重复选择。其循环结构如下：for(;)longstart,end;switch(menu()case 1:printf("*起泡排序*n");start=clock();Bubble_sort(L);end=clock();printf("%dmsn",end-start);fp=fopen("D:起泡排序.txt","w&qu

5、ot;);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("%dmsn",end-start);fp=fopen("D:直接插入排序.txt","w");if(

6、fp=NULL)/打开文件失败printf("简单选择排序!n");exit(1);for(i=1;i<=L.length;i+)fprintf(fp,"%d",L.ri);fclose(fp);break;case 3:printf("*希尔排序*n");start=clock();ShellSort(L,an,14);end=clock();printf("%dmsn",end-start);fp=fopen("D:希尔排序.txt","w");if(fp=NULL

7、)/打开文件失败printf("打开文件失败!n");exit(1);for(i=1;i<=L.length;i+)fprintf(fp,"%d",L.ri);fclose(fp);break;case 4:printf("*直接插入排序*n");start=clock();Insertsort(L);end=clock();printf("%dmsn",end-start);fp=fopen("D:直接插入排序.txt","w");if(fp=NULL)/打开文件失败

8、printf("打开文件失败!n");exit(1);for(i=1;i<=L.length;i+)fprintf(fp,"%d",L.ri);fclose(fp);break;case0:printf("t退出！n");return;（四）文件结构1、 、sort.h：单链表相关的定义与声明2、 、sort.cpp：单链表运算的实现3、 menu.h：主菜单函数的声明4、 menu.cpp：主菜单函数的实现5、 mn.cpp：主函数（五）各函数的算法设计1、InitList_Sq（）算法原理：数组指针r指示线性表的基址，len

9、gth指示线性表的当前长度，将随机生成的数赋给线性表，并生成相应文件。开始流程图:代码描述：StatusInitList_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(NULL);for(inti=1;i<=L.length;i+)L.ri.key=rand()%30001+1;fp=fopen("D:构造一个线性

10、表.txt","w");if(fp=NULL)/打开文件失败printf("打开文件失败!n");exit(1);for(i=1;i<=L.length;i+)fprintf(fp,"%d",L.ri);fclose(fp);returnOK;/InitList_Sq算法的时间复杂度分析：O(n)2.Bubble_sort()算法原理：每趟不断将记录两两比较，若发现逆序，则交换两个记录，使排序码较小的元素逐渐从后部移向前部(就象水底的气泡一样逐渐向上冒)。流程图：开始结束代码描述：voidBubble_sort(SqL

11、ist&L)RedTypex;intn;n=L.length;/表长for(inti=1;i<n;i+)intflag=0;/进入循环，清标志for(intj=n-1;j>=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趟：从R1Rn中选取最小值,与R1交换;第2趟：从R2Rn中选取最小值,与R2交换;

12、第i趟：从RiRn中选取最小值,与Ri交换;第n-1趟：从Rn1Rn中选取最小值,与Rn1交换.共通过n1趟,得到一个按排序码从小到大排列的有序序列流程图：开始结束代码描述：voidSelectSort(SqList&L)/对顺序表进行简单选择排序RedTypex;for(inti=1;i<L.length;+i)/在L.ri.L.length中选择key最小的记录intk=i;for(intj=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

13、算法的时间复杂度分析：O(n2)4、 ShellInsert()算法原理：(1)、分组、组内直接插入排序；(2)、组数逐次减小；(3)、组数=1，结束。代码描述：voidShellInsert(SqList&L,intdk)/一趟Shell排序，dk为步长inti;for(i=dk+1;i<=L.length;i+)if(LT(L.ri.key,L.ri-dk.key)L.r0=L.ri;intj;for(j=i-dk;(j>0)&&(LT(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj;L.rj+dk=L.r0;voidShel

14、lSort(SqList&L,intdlta,intt)/Shell排序，dlta为增量序列，t为增量个数intk;for(k=0;k<t;k+)ShellInsert(L,dltak);/ShellSort算法的时间复杂度分析：O(n(log2n)2)5、 Insertsort()算法原理：每步将一个待排序的对象，按其排序码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。在已形成的有序表中顺序查找，并在适当位置插入，把原来位置上的元素向后顺移。流程图：代码描述：voidInsertsort(SqList&L)对顺序表L进行直接插入排序for(in

15、ti=2;i<=L.length;i+)if(LT(L.ri.key,L.ri-1.key)需将L.ri插入有序表L.r0=L.ri;/复制为“哨兵”，暂存for(intj=i-1;LT(L.r0.key,L.rj.key);j-)L.rj+1=L.rj;/位置j指示了第一个key<L.ri.key的元素L.rj+1=L.r0;/将暂存在r0中的记录插入到正确位置/printf("%d",L.ri);算法的时间复杂度分析：O(n2)五、测试数据和结果1、测试数据随机产生30000个数2、测试结果本程序在VC+部境下实现，下面是对以上测试数据的运行结果。(1)主菜

16、单显示如下：Tv：,BnMicrooi：VisualStudcIVy?rojects-5Q1bug5?n.exe'排序序序F厂 ;厂序择序人统/单尔茬越131左且退请选择F»%*C：BnMicr0soitVisualStudioMyProjectssortDebugson.exe"清选搔04：起泡排序4b4URS一，序LEIfl序序thktr团吊序择序人统二匕上一二<，rm.、由羊尔簟1234040s.-出请3序序-i-bh“序探序人统-suf-=泡单尔标上起退=12340请选择tJQ：»简单选择排序1550ns排序序序kLTkt.苗书序择序人统r-IS尔：！起退12340请选择0-4：序序tF ktrtiu瘴序人统b - L J UL- T 1屯里了¥sfsfi1 2 3 4 w请选择0-4 Lf希尔排序*I EH排序序序br tF 序挥序A统 suf- 范单<in|返1 2 3 4 0rTC：,BnMicroGQitVisuilStudic'l,VyPrcject&50rtbug53n.exe"lb70ms排序请选择0-4：WB力Wi口Visualitud