当前位置:文档之家› 数据结构课程设计排序实验报告

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

《数据结构》课程设计报告专业班级姓名学号指导教师起止时间课程设计:排序综合一、任务描述利用随机函数产生n个随机整数(20000以上),对这些数进行多种方法进行排序。

(1)至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。

并把排序后的结果保存在不同的文件中。

(2)统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。

要求:根据以上任务说明,设计程序完成功能。

二、问题分析1、功能分析分析设计课题的要求,要求编程实现以下功能:(1)随机生成N个整数,存放到线性表中;(2)起泡排序并计算所需时间;(3)简单选择排序并计算时间;(4)希尔排序并计算时间;(5)直接插入排序并计算所需时间;(6)时间效率比较。

2、数据对象分析存储数据的线性表应为顺序存储。

三、数据结构设计使用顺序表实现,有关定义如下:typedef int Status;typedef int KeyType ; //设排序码为整型量typedef int InfoType;typedef struct { //定义被排序记录结构类型KeyType key ; //排序码I nfoType otherinfo; //其它数据项} RedType ;typedef struct {RedType * r; //存储带排序记录的顺序表//r[0]作哨兵或缓冲区int length ; //顺序表的长度} SqList ; //定义顺序表类型四、功能设计(一)主控菜单设计为实现通各种排序的功能,首先设计一个含有多个菜单项的主控菜单程序,然后再为这些菜单项配上相应的功能。

程序运行后,给出5个菜单项的内容和输入提示,如下:1.起泡排序2.简单选择排序3.希尔排序4. 直接插入排序0. 退出系统(二)程序模块结构由课题要求可将程序划分为以下几个模块(即实现程序功能所需的函数):●主控菜单项选择函数menu()●创建排序表函数InitList_Sq()●起泡排序函数Bubble_sort()●简单选择排序函数SelectSort()●希尔排序函数ShellSort();●对顺序表L进行直接插入排序函数Insertsort()(三)函数调用关系程序的主要结构(函数调用关系)如下图所示。

其中main()是主函数,它负责调用各函数。

进行调用菜单函数menu(),根据选择项0~4调用相应的函数。

main()函数使for循环实现重复选择。

其循环结构如下:for (;;){long start,end;switch(menu()){case 1:printf("* 起泡排序*\n");start=clock();Bubble_sort(L);end=clock();printf("%d ms\n",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.r[i]);fclose(fp);break;case 2:printf("* 简单选择排序*\n");start=clock();SelectSort(L);end=clock();printf("%d ms\n",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.r[i]);fclose(fp);break;case 3:printf("* 希尔排序*\n");start=clock();ShellSort(L,an,14);end=clock();printf("%d ms\n",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.r[i]);fclose(fp);break;case 4:printf("* 直接插入排序*\n");start=clock();Insertsort(L);end=clock();printf("%d ms\n",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.r[i]);fclose(fp);break;case 0:printf("\t 退出!\n");return ;}}(四)文件结构1、sort.h:单链表相关的定义与声明2、sort.cpp:单链表运算的实现3、menu.h:主菜单函数的声明4、menu.cpp:主菜单函数的实现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(NULL));for(int i=1;i<=L.length;i++)L.r[i].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.r[i]);fclose(fp);return OK;}//InitList_Sq算法的时间复杂度分析:O(n)2.Bubble_sort()算法原理:每趟不断将记录两两比较,若发现逆序,则交换两个记录,使排序码较小的元素逐渐从后部移向前部(就象水底的气泡一样逐渐向上冒)。

流程图:N代码描述:void Bubble_sort(SqList &L){RedType x;int n;n=L.length; //表长for (int i=1; i<n; i++){ int flag=0; //进入循环,清标志for (int j=n-1; j>=i; j--)if(LT(L.r[j+1].key,L.r[j].key)){flag=1; //有交换,置标志x=L.r[j]; //L.r[j] ←→L.r[j+1]L.r[j]=L.r[j+1];L.r[j+1]=x;}if(flag==0) break; //若无交换则可结束冒泡排序}}算法的时间复杂度分析:O(n2)3、SelectSort()算法原理:第1趟:从R[1]~R[n]中选取最小值,与R[1]交换;第2趟:从R[2]~R[n]中选取最小值,与R[2]交换;第i 趟:从R[i]~R[n]中选取最小值,与R[i]交换;………………………第n -1趟:从R[n-1]~R[n]中选取最小值,与R[n-1]交换.共通过n-1趟,得到一个按排序码从小到大排列的有序序列流程图:N N代码描述:void SelectSort(SqList &L){ //对顺序表进行简单选择排序RedType x;for (int i=1; i<L.length; ++i){ //在L.r[i..L.length] 中选择key最小的记录int k=i;for(int j=i+1;j<=L.length ; j++)if ( LT(L.r[j].key,L.r[k].key)) k=j;if(k!=i){x=L.r[i];L.r[i]=L.r[j];L.r[j]=x;}}} //SelectSort算法的时间复杂度分析:O(n2)4、ShellInsert()算法原理:(1)、分组、组内直接插入排序;(2)、组数逐次减小;(3)、组数=1,结束。

代码描述:void ShellInsert(SqList &L,int dk){ //一趟Shell排序,dk为步长int i;for(i=dk+1;i<=L.length;i++){if(LT(L.r [i].key ,L.r [i-dk].key )){L.r [0]=L.r [i];int j;for(j=i-dk;(j>0)&&(LT(L.r [0].key ,L.r [j].key ));j-=dk) 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;k<t;k++)ShellInsert(L,dlta[k]);}// ShellSort算法的时间复杂度分析:O(n(㏒2n)2)5、Insertsort()算法原理:每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。

相关主题