数据结构排序综合.doc

目 录 1.需求分析 1 2.概要设计 1 3.详细设计 2 4.测试分析 19 课程设计总结 22 参 考 文 献 24 一、需求分析 ①问题描述：此次的任务是利用随机函数产生N个随机整数，对这些数进行多种方法进行排序，分别是插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。然后统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 ②基本要求： 数据输入的形式和输入值的范围：设定的随机数据的范围是0到30000，产生30000个，类型均为整型。 数据输出的形式：程序以一个排序完成后的有序数组来输出。 程序所设计的功能： （1）构建菜单，为每种排序方法设定一个选项数字，用户可根据需要选择不同的排序方法。可以选择的方法有：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序共七种。 每种排序结束后自动计算该排序的耗时。 将排序后的数据保存到相应的文件里面。 （4）数据由随机函数产生。 二、概要设计 为了实现需求分析中的功能，可以从以下3个方面着手设计。 主界面设计 利用switch函数设计出菜单，即通过case分别调用不同的排序方法。 2、存储结构设计 本次存储结构仅用到了数组的储存结构。原因：需要存储的数据是连续的，数据类型也只有一种，所以用数组的存储结构能合理利用存储空间。而且我们所学的排序算法是基于数组的储存结构实现的。 系统功能设计 Head.h：用于声明必要的头文件，函数及结构体 Srand.c：用于产生随机数 Writefile.c：用于将排序结果存入文件 Print.c：用于输出文件中的排序结果 Insertsort.c：用于将产生的随机数进行插入排序 Shellsort.c：用于将产生的随机数进行希尔排序 Bubblesort.c：用于将产生的随机数进行冒泡排序 Quicksort.c：用于将产生的随机数进行快速排序 Selectsort.c：用于将产生的随机数进行选择排序 Heapsort.c：用于将产生的随机数进行堆排序 Mergesort.c：用于将产生的随机数进行归并排序 各个程序模块之间的层次（调用）关系： 三、详细设计 1、数据类型设计： typedef int KeyType; //定义关键字类型 typedef char InfoType[10]; typedef struct { //记录类型 KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; 详细算法： 头文件： /*Head.h*/ #includestdio.h #include stdlib.h #include time.h #define MaxSize 20000 typedef int KeyType; //定义关键字类型 typedef char InfoType[10]; typedef struct { //记录类型 KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; //排序的记录类型定义 void InsertSort(RecType R[],int n);//1.插入排序 void Srand(RecType R[]);//随机函数 void print(RecType R[],int a);//打印函数 void BubbleSort(RecType R[],int n);//2.冒泡排序 void ShellSort(RecType R[],int n);//3.希尔排序 void QuickSort(RecType R[],int s,int t);//4.快速排序 void SelectSort(RecType R[],int n);//5.选择排序 void Heapsort(RecType R[],int n);//6.堆排序 void MergeSort(RecType R[],int n);//7.归并排序 void Writefile(RecType R[],int n,int k);//写入文件 主程序： /*Main.c*/ #includeHead.h RecType R[MaxSize],R1[MaxSize+1]; void Menu() { int i; clock_t start,finish; double duration; int a,n=Max