数据结构总和排序 下载本文

课 程 设 计

学生姓名: 梁钰 学 号: 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):定义快速排序函数