数据结构排序综合课程设计报告 2.doc

数据结构课程设计报告 排序综合 专 业 信息管理与信息系统 班 级 110514 小组成员 110514128 汤文莹 110514129 王玉珏 110514130 张蓓蕾 110514131 张慕琦 课程设计：排序综合一、任务描述（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。二、问题分析1、模块功能分析 结构体模块：在结构体中定义数组，关键字为key,为整形。整数产生模块：MakeList()，自动产生20000以内的随机数，存入数组中。排序模块：有6个子函数分别代表6种排序方式，六种排序方式为（1）InsertSort()直接插入排序（2）BubleSort()冒泡排序（3）QuickSort()快速排（4）SeleSort()直接选择排序（5）ShellSort()希尔排序（6）HeapSort()堆排序显示模块：输出随机产生的整数，和排序后的整数。函数调用模块：在此模块中void main()定义结构体中的数据并调用所需子函数。2、数据对象分析 排序方式：直接插入排序、冒泡排序、快速排序、直接选择排序、希尔排序、堆排序显示排序后的的数据和时间效率。三、数据结构设计定义结构体typedef struct int key;RECNODE;叙述各种排序函数，并相应写出各种排序的算法及过程。定义数组的值，并输出所记录的值。按16数字键选择函数，可查找出各种排序的结果。输出排序结果及所用时间和交换次数按0键退出四、功能设计（一）主控菜单设计为实现排序的操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出菜单项的内容和输入提示，如下：*菜 单 * 1-直接插入排序 * 2-冒泡排序 * 3-快速排序 * 4-直接选择排序 * 5-堆排序 * 6-希尔排序 * 0-退出 *（二）程序模块结构由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：l 主控菜单项选择函数menu_select()l InsertSort()直接插入排序l BubleSort()冒泡排序l QuickSort()快速排序l SeleSort()直接选择排序l ShellSort()希尔排序l HeapSort()堆排序（三）函数调用关系程序的主要结构（函数调用关系）如下图所示。 SeleSort 其中main()是主函数，它进行菜单驱动，根据选择项10调用相应的函数。（四）函数实现#define MAXSIZE 20000#include #include #include #include typedef struct int key;RECNODE;int b,t;int MakeList(RECNODE *r) int j,k; time_t t1;/* 用于存放时间 */time(&t1);/* 取得当前系统时间 */srand(t1);for(k=0;kMAXSIZE;k+) rk+1.key = rand()%(MAXSIZE+30000); return k;void UndealoutList(RECNODE *r,int n) int i; printf(n未排序前的数据 ： ); for(i=0;in;i+) printf( %d,ri+1.key); printf(nn);void DealoutList(RECNODE*r,int n) int i;printf(排序后的数据 ： ); for(i=0;in;i+) printf( %d,ri+1.key); printf(nn); printf(交换或比较的次数： %dn,b); printf(排序的趟数： %dn,t);void InsertSort(RECNODE*r,int n)/直接插入排序/ int i,j; b=0,t=0; for(i=2;i=n;i+) r0=ri; j=i-1; while(r0.keyrj.key) rj+1=rj; j-; b+; rj+1=r0; b+; t+; void BubleSort(RECNODE *r,int n) /冒泡排序/int i,j; b=0,t=0; RECNODE temp; for(i=1;i=i;j-) if(rj+1.key=temp.key)&(ij) j-; w+; if(ij) ri=rj; i+; w+; while(ri.key=temp.key)&(ij) i+; w+; if(ij) rj=ri; j-; w+; while(i!=j); ri=temp; b=w; return i;void QuickSort(RECNODE*r,int start,int end)/快速排序/int i; static int q=0; if(startend) i= Partition(r,&start,&end); q+; QuickSort(r,start,i-1); QuickSort(r,i+1,end); t=q; void SeleSort(RECNODE*r,int n)/直接选择排序/int i,j,z; b=0,t=0; RECNODE temp; for(i=1;in;i+) z=i; for(j=i+1;j=n;j+) if(rj.key0) for(i=dk+1;i=n;+i) if(ri.key0&r0.keyrj.key;j-=dk) rj+dk=rj; b+; rj+dk=r0; dk=dk/2; t+; void Sift(RECNODE*r,int i,int m) int j; static int x=0; RECNODE temp; temp=ri; j=2*i; while(j=m) if(jm&(rj.keyrj+1.key) j+; x+; if(temp.key=1;i-) Sift(r,i,n); for(i=n;i=2;i-) temp=r1; r1=ri; ri=temp; Sift(r,1,i-1); t+; int main(int argc, char* argv)RECNODE aMAXSIZE; int len,p; do printf(*n); printf(* 菜 单 *n); printf(*n); printf(* 1-直接插入排序 *n); printf(* 2-冒泡排序 *n); printf(* 3-快速排序 *n); printf(* 4-直接选择排序 *n); printf(* 5-堆排序 *n); printf(* 6-希尔排序 *n); printf(* 0-退出 *n); printf(*n); printf(n请在上述序号中选择一个并输入： ); scanf(%d,&p); switch(p)case 1:len=MakeList(a); UndealoutList(a,len); InsertSort(a,len); DealoutList(a,len); break; case 2:len=MakeList(a); UndealoutList(a,len); BubleSort(a,len); DealoutList(a,len); break; case 3:len=MakeList(a); UndealoutList(a,len); QuickSort(a,1,len); DealoutList(a,len); break; case 4:len=MakeList(a); UndealoutList(a,len); SeleSort(a,len); DealoutList(a,len); break; case 5:len=MakeList(a); UndealoutList(a,len); HeapSort(a,len); DealoutList(a,len); break; case 6:len=MakeList(a); UndealoutList(a,len); ShellSort(a,len); DealoutList(a,len); break; case 0:break; default:printf(输入错误！请重新输入!n);break; while(p!=0);五、测试数据和结果 本程序在VC+环境下实现，下面是对以上测试数据的运行结果。(1) 主菜单显示如下：(2)各分界面：（1）主菜单（2）各分界面输入数字1，直接插入排序输入数字2，冒泡排序输入数字3，快速排序输入数字4，直接选择排序输入数字5，堆排序输入数字6，希尔排序通过比较，可以看出快速排序和希尔排序较快，交换的次数和排序趟数分别为336751、13671和351143、14六、结束语在此程序设计中我们的程序主要是运用各种排序的方法对有限个整数进行排序，运用所学过的，直接排序，冒泡排序，插入排序，选择排序等方法来实现。在资料查找和在程序设计当中，遇到很多困难。在调试的过程中会出现想不到的结果，这需要我们耐心的去研究讨论。遇到的问题便是过于复杂的资料看不太懂，在程序的调试和改进部分，也花费了较多的时间来查询书籍和网上的资料，并且请教一些精通C语言的人。程序设计让我们懂了许课程设计究竟是什么意思了，要用我们的双手编写出一个个程序来为他人带来方便。其中也遇到了现实中的一些问题，比如说，数据量很的问题，这在程序的各种算法上提出