课 程 设 计

学生姓名： 梁钰 学 号： 130702216 专业班级： 计算机科学与技术132班 课程名称： 数据结构 学年学期： 2015—2016学年第2学期

指导教师： 白云飞 2016年6月

13

数据结构课程设计成绩评定表

学生姓名 梁钰 学 号 130702216 成绩 专业班级 计算机132 起止时间 2016-6-20——2016-6-24 设计题目 排序综合 学习态度出勤情况： 好 □ 较好 □ 一般 □ 较差 □ 课 题 工 作 量： 饱满 □ 较大 □ 合理 □ 较小 □ 综合运用知识能力： 好 □ 较好 □ 一般 □ 较差 □ 方 案 设 计 情况： 合理 □ 较合理 □ 基本合理□ 不合理 □ 课题结果分析能力： 强 □ 较强 □ 一般 □ 较差 □ 设 计 实 现 情况： 全部 □ 大部分 □ 部分 □ 未实现 □ 指 导 教 师 评 语 设 计 报 告 内容： 详细□ 完整 □ 较完整 □ 不完整 □ 设计报告文档格式： 规范 □ 较规范 □ 基本规范□ 不规范 □ 独 立 动 手 能力： 强 □ 较强 □ 一般 □ 较差 □ 指导教师： 年 月 日 13

目 录

1．需求分析说明 2．概要设计说明 3．详细设计说明 4．调试分析

5．用户使用说明 6．课程设计总结 7．测试结果 8．参考书目

13

-1 -2 -3 -6 -6 -9 -9 -10

数 据 结 构 课 程 设 计

1 需求分析说明

内部排序教学软件的总体功能要求：

排序综合的总体目标：在Visual C++6.0的开发环境下，利用所学C语言或C++和数据结构的相关知识，设计一个利用随机函数生成N个的随机整数（2000以上），对这些数进行综合排序的程序，进行七种排序算法，并计算时间复杂度，选出两种较快的方法。 基本功能如下：

（1）至少采用七种方法实现上述问题要求（可采用的方法有：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同文件中。

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

以下是各功能模块的功能描述：

1．主函数模块

本模块的主要功能是初始化图形界面，调用各模块，实现软件功能。

2．菜单界面子模块

本模块的主要功能是根据用户的选择，引导用户使用软件所提供的各种功能。并在用户提供必要数据，转入到存储文件子模块或者排序功能及输出子模块。

3．排序功能及输出子模块

本模块的主要功能是根据用户的选择排序功能后，进行数组的创建，随机函数产生随机数据并且显示，随后转入排序方法选择界面进行选择。

4.时间效率比较子模块

本模块的主要功能是以计算花费的时间为准进行对比，选出两种较快的排序算法。以此

分析在每种存储结构的下九种排序算法的优劣，输出每种算法的所用时间。并且每种排序算法所用的时间结果都能保存到指定文件中。

5.读取文件子模块

本模块的主要功能是通过存储文件名读取已储存的文件，并进入排序界面。

6.退出系统子模块

本模块的主要功能是退出排序综合系统或者回到主模块菜单选项界面。

7.存储文件子模块

本模块的主要功能是根据用户的选择，并在用户输入文件名后存储随机生成数。

１

数 据 结 构 课 程 设 计

测试数据：

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)：定义快速排序函数

２

数 据 结 构 课 程 设 计

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

３

数 据 结 构 课 程 设 计

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()。

４

数 据 结 构 课 程 设 计

系统总体流程图（如图二所示）

开始 选择1、生成随机数并存储文件2、打开文件并进入排序界面 If m=1 输入文件名，产生随机数并保存 打开文件进 入排序界面 23674589退出系统直接插入排序希尔排序堆排序起泡排序快速排序选择排序归并排序时间效率比较打开文件并进入排序界面 10 结束 ５

数 据 结 构 课 程 设 计

4 调试分析

我遇到的问题：

? 运用多种算法，算法使用遇到苦难 由于要对随机产生的整数，运用七种不同的排序方法进行排序，对一些算法不够熟悉，导致写程序时多出碰壁，也由于写的不够完善，导致有些排序的时间过长，是因为调用多个函数造成的。不过好在都能正确运行。

? 时间效率比较未能正确执行

由于对知识点掌握的欠缺，少写程序，导致未能正确的实现这一功能，在寻求帮助后也未能成功，这是本次课设最大的遗憾。

5 用户使用说明

用户运行程序时的主界面如图3所示

图3

６

数 据 结 构 课 程 设 计

用户选择1生成随机数并保存文件后的界面图四

图4

文件保存成功提示界面如图5

图5

７

数 据 结 构 课 程 设 计

用户选择2打开文件进入排序界面后，如图6所示

图6

选择1执行直接插入排序后，排序的结果如图7所示

图7

８

数 据 结 构 课 程 设 计

6 课程设计总结

通过这次课程设计的学习让我学会了许多。让我对我们的专业知识有了很大理解！我对专业的课程有了初步的认识。

首先学会了随机数的产生。熟练的撑握了C和C++的文件读写操作。撑握了每种排序算法的基本思想，并学会编写代码的基本思路，写出解决方案，完成代码，调试程序。条理清晰的书写代码，使编写过程变得简单，修改时也清楚易查。 但我还是认为自己有很多的不足，课程设计作品并不完善，以后我会更努力的学习相关知识，多亲手编写代码，勤学多练，希望以后能弥补这些不足。 这次的课程设计我学会了很多，不光让我认识了本专业知识，还让我锻炼了独立思考，不轻言放弃的精神。从刚开始的无从下手，到查阅资料后的编写，再到后期修改，才有了如今的模样。期间做了许多调整和修改，所以说一切美好的事物都离不开认真和努力！通过这次数据结构课程设计，使我对软件的界面设计有了一个比较深刻的了解，对各种内部排序方法的性能有了清晰的认识，使我感觉到到，一个优秀的软件，不仅仅是可以运行的，更应该具有人性化的界面，协调的布局，合理的结构，良好的性能和一定的容错性。

7 测试结果

希尔排序： 堆排序：

最快的两种排序： 1.希尔排序 2.堆排序

９

数 据 结 构 课 程 设 计

8 参考书目

[1] [2]

数据结构（C语言版），严蔚敏，吴伟民，清华大学出版社 C语言课程设计案例精编，郭翠英，中国水利出版社

１０