发布时间 : 星期六 文章数据结构总和排序更新完毕开始阅读7d84e0cd591b6bd97f192279168884868662b863
数 据 结 构 课 程 设 计
测试数据:
1:随机数若干组 2:希尔排序
(1)自定义随机取一组数据 (9,3,5,1,6,2,8,4,7) (2)取增量为5,得到:(2,3,4,1,6,8,5,7,9) 3:直接插入排序
(1)自定义随机取一组数据(43 ,21,89,15 ,43,28) (2)得到(15,21,28,43,43,89) 4:直接插入排序
(1)自定义随机取一组数据(7,2,5,1,9,6,8,3) (2)得到(1,2,3,4,5,6,7,8) 5:选择排序
(1)自定义随机取一组数据(7,2,5,1,9,6,8,3) (2)得到(1,2,3,4,5,6,7,8)
2 概要设计说明
模块调用图:
主函数模块
排序综合及输出子模块 菜单界面子模块 存储界面子模块 读取文件子模块 时间效率比较子模块 图一
退出系统子模块 操作函数说明:
void creat():定义随机函数,产生随机数据 void save(int f1[]):保存文件 void read():读取文件
void DirectInsertSort(int p[], int len):直接插入排序 void ShellSort(int a[],int n):希尔排序
void BinSort(int r[],int length):折半插入排序 void sort(int a[N],int n):冒泡排序
int my_quick(int a[],int low,int high):定义快速排序函数
2
数 据 结 构 课 程 设 计
void buuble(int a[],int n):简单选择排序
void merge(int a[N],int l_start,int l_end,int r_end):归并排序1 int msort(int a[N],int start,int end):归并排序2 void end():定义结束函数
void menu():函数声明//控制输出格式 void display(int a[],int n):菜单函数 void menu():菜单函数
3 详细设计说明
1. 主函数模块
首先定义creat()函数用来生成不同的随机数。该函数是用两个函数来生成随机数:rand()和srand(),前者是生成随机数,后者是获取随机种子,使随机数不断变化。
2. 菜单界面子模块
菜单函数void menu() 显示了系统操作的整个界面,包括第一个界面“选择存储生成的随机数还是读取文件”和第二个界面“进行综合排序”。在选择排序的函数时,同时计算其运行时间。在综合排序界面可以选择退出程序或进入第一个界面或打开已有文件进行排序。
3. 存储界面子模块
保存文件函数void save()中,FILE为系统结构体,定义指向文件的指针*fp,输入存储的文件名,打开文件(若文件存在,则删除文件中的原有元素;若文件不存在,则新建一个文件),并将参数数组中的元素存储到文件中
4. 读取文件面子模块
读取文件函数void read()中,定义*fp指向文件的指针,提示输入要读取文件的文件名,读取文件中的元素,输出到数组中,并打印出来。且跳转至排序综合界面,提供用户选择排序方法。
5. 直接插入排序
第1遍,将初始文件中的记录K1看作有序子文件,将K2插入这个子文件中。若R2的关键字小于K1的关键字,则R2插在K1的前面,否则K2插在K1的后面。第2遍,将K3插入前面的两个记录的有序子文件中,得到3个记录的有序子文件。依此类推,继续进行下去,直到将Kn插入到前面的n-1个记录的有序子文件中,最后得到n个记录的有序文件。
6. 希尔排序
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。
所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2 3 数 据 结 构 课 程 设 计 7.堆排序 堆排序(包括建立最大堆和堆排序两个过程) 堆排序算法的基本思想是: a.对排序表中的数据元素,利用堆的调整算法形成初始堆。 b.输出堆顶元素。 c.对剩余元素重新调整形成堆。 d.重复执行第b、c步,直到所有数据元素被输出。 8.起泡排序 起泡排序的过程很简单。首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换之,然后比较第二个记录和第三个记录的关键字。依次类推,直至第n-1个记录和第n个记录的关键字进行过比较为止。这一过程称做第一趟冒泡排序,其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后用同样方法进行第一趟以后的排序,直到排序结束。 9.快速排序 快速排序是对冒泡排序的一种改进。 它的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 10.选择排序 待排序文件有n个记录,第一趟进行n-1次比较,选出关键字最小的记录,和第一个记录交换。第二趟进行n-2次比较,选出关键字次小记录,和第二个记录交换,……,如此下去,进行n-1趟,直至待排序文件全部有序。 11.归并排序 二路归并排序的基本操作是将两个有序表合并为一个有序表。 设r[u…t]由两个有序子表r[u…v-1]和r[v…t]组成,两个子表长度分别为v-u、t-v+1。合并方法为: ⑴ i=u;j=v;k=u; 置两个子表的起始下标及辅助数组的起始下标 ⑵ 若i>v 或 j>t,转⑷,其中一个子表已合并完,比较选取结束 ⑶ 选取r[i]和r[j]关键码较小的存入辅助数组rf 如果r[i].key 如果i 12. 退出函数 考虑到当用户使用完系统时,就会使用退出函数。当选择退出时,用户还会二次确 认是否退出。不退出时,可以选择返回菜单。退出程序函数:void end()。 4 数 据 结 构 课 程 设 计 系统总体流程图(如图二所示) 开始 选择1、生成随机数并存储文件2、打开文件并进入排序界面 If m=1 输入文件名,产生随机数并保存 打开文件进 入排序界面 23674589退出系统直接插入排序希尔排序堆排序起泡排序快速排序选择排序归并排序时间效率比较打开文件并进入排序界面 10 结束 5