数据结构排序综合.doc

《数据结构排序综合.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.目录1.需求分析12.概要设计13.详细设计24.测试分析19课程设计总结22参考文献24教育资料.一、需求分析①问题描述：此次的任务是利用随机函数产生N个随机整数，对这些数进行多种方法进行排序，分别是插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。然后统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。②基本要求：数据输入的形式和输入值的围：设定的随机数据的围是0到30000，产生30000个，类型均为整型。

2、数据输出的形式：程序以一个排序完成后的有序数组来输出。程序所设计的功能：（1）构建菜单，为每种排序方法设定一个选项数字，用户可根据需要选择不同的排序方法。可以选择的方法有：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序共七种。（2）每种排序结束后自动计算该排序的耗时。（3）将排序后的数据保存到相应的文件里面。（4）数据由随机函数产生。二、概要设计为了实现需求分析中的功能，可以从以下3个方面着手设计。1、主界面设计利用switch函数设计出菜单，即通过case分别调用不同的排序方法。2、存储

3、结构设计本次存储结构仅用到了数组的储存结构。原因：需要存储的数据是连续的，数据类型也只有一种，所以用数组的存储结构能合理利用存储空间。而且我们所学的排序算法是基于数组的储存结构实现的。3、系统功能设计Head.h：用于声明必要的头文件，函数及结构体Srand.c：用于产生随机数Writefile.c：用于将排序结果存入文件Print.c：用于输出文件中的排序结果教育资料.Insertsort.c：用于将产生的随机数进行插入排序Shellsort.c：用于将产生的随机数进行希尔排序Bubblesort.c：用于

4、将产生的随机数进行冒泡排序Quicksort.c：用于将产生的随机数进行快速排序Selectsort.c：用于将产生的随机数进行选择排序Heapsort.c：用于将产生的随机数进行堆排序Mergesort.c：用于将产生的随机数进行归并排序3、各个程序模块之间的层次（调用）关系：三、详细设计1、数据类型设计：typedefintKeyType;//定义关键字类型typedefcharInfoType[10];typedefstruct{//记录类型KeyTypekey;//关键字项InfoTypedata;/

5、/其他数据项,类型为InfoType}RecType;2、详细算法：头文件：/*Head.h*/#include教育资料.#include#include#defineMaxSize20000typedefintKeyType;//定义关键字类型typedefcharInfoType[10];typedefstruct{//记录类型KeyTypekey;//关键字项InfoTypedata;//其他数据项,类型为InfoType}RecType;//排序的

6、记录类型定义voidInsertSort(RecTypeR[],intn);//1.插入排序voidSrand(RecTypeR[]);//随机函数voidprint(RecTypeR[],inta);//打印函数voidBubbleSort(RecTypeR[],intn);//2.冒泡排序voidShellSort(RecTypeR[],intn);//3.希尔排序voidQuickSort(RecTypeR[],ints,intt);//4.快速排序voidSelectSort(RecTypeR[],i

7、ntn);//5.选择排序voidHeapsort(RecTypeR[],intn);//6.堆排序voidMergeSort(RecTypeR[],intn);//7.归并排序voidWritefile(RecTypeR[],intn,intk);//写入文件主程序：/*Main.c*/#include"Head.h"RecTypeR[MaxSize],R1[MaxSize+1];voidMenu(){inti;clock_tstart,finish;doubleduration;inta,n=MaxSiz

8、e;printf("1.产生随机数");教育资料.printf("2.插入排序");printf("3.冒泡排序");printf("4.希尔排序");printf("5.快速排序");printf("6.选择排序");printf("7.堆排序");printf("8.归并排序");printf("9.打印各种排序方法排序后的序列");printf("10.清空