数据结构(课程设计)排序算法时间性能的分析.doc
文本预览下载声明
《数据结构》课程设计报告
目录
TOC \o 1-3 \h \z \u HYPERLINK \l _Toc 1 需求分析 PAGEREF _Toc \h 1
HYPERLINK \l _Toc 1.1 问题描述 PAGEREF _Toc \h 1
HYPERLINK \l _Toc 1.2 设计内容 PAGEREF _Toc \h 1
HYPERLINK \l _Toc 2概要设计 PAGEREF _Toc \h 2
HYPERLINK \l _Toc 2.1 原始数据 PAGEREF _Toc \h 2
HYPERLINK \l _Toc 2.2 程序的流程 PAGEREF _Toc \h 2
HYPERLINK \l _Toc 2.3 总体设计图 PAGEREF _Toc \h 3
HYPERLINK \l _Toc 3详细设计和编码 PAGEREF _Toc \h 4
HYPERLINK \l _Toc 3.1 算法基本思想 PAGEREF _Toc \h 4
HYPERLINK \l _Toc 3.2 算法描述 PAGEREF _Toc \h 4
HYPERLINK \l _Toc 3.3 算法设计 PAGEREF _Toc \h 5
HYPERLINK \l _Toc 3.4算法时间分析 PAGEREF _Toc \h 8
HYPERLINK \l _Toc 4测试结果 PAGEREF _Toc \h 9
HYPERLINK \l _Toc 5小结 PAGEREF _Toc \h 9
HYPERLINK \l _Toc 参考文献 PAGEREF _Toc \h 10
HYPERLINK \l _Toc 附录:程序源代码 PAGEREF _Toc \h 10
PAGE \* MERGEFORMAT
PAGE \* MERGEFORMAT 1
1 需求分析
1.1 问题描述
(1) 输入的形式和输入值的范围:本程序要求实现各种算法的时间性能的比较,由于需要比较的数目较大,不能手动输入,于是采用系统生成随机数。用户输入随机数的个数n,然后调用随机事件函数产生n个随机数,对这些随机数进行排序。于是数据为整数。
(2) 输出的形式:输出在各种数目的随机数下,各种排序算法所用的时较次数。
(3) 程序所能达到的功能:该程序可以根据用户的输入而产生相应的随机数,然后对随机数进行各种排序,根据排序进行时间和次数的比较。
(4)测试数据。
1.2 设计内容
对各种排序方法(快速排序、堆排序、希尔排序、冒泡排序、归并排序)的时间性能进行比较。
设计并实现上述各种排序算法;
在排序中实现比较时间性能;
在输入中分别调用上述排序算法,并比较时间性能。
2概要设计
2.1 原始数据
1.抽象数据类型
ADT List
数据对象 D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系 R1={ ai-1 ,ai |ai-1 ,ai∈D, i=2,...,n }
基本操作 virtual void clear() = 0;
bool insert(const Elem) = 0;
bool append(const Elem) = 0;
lbool remove(Elem) = 0;
void setStart() = 0;
void setEnd() = 0;
void prev() = 0;
void next() = 0;
int leftLength() const = 0;
int rightLength() const = 0;
bool setPos(int pos) = 0;
bool getValue(Elem) const = 0;
void print() const = 0;
2.2 程序的流程
(1)输入模块:输入要排序的数的数量n。
(2)处理模块:系统产生n个随机数,对随机数进行排序。
(3)输出模块:将排序的结果输出。
2.3 总体设计图
主程序
主程序
冒泡排序
快速排序
堆排序
希尔排序
归并排序
主程序堆排序
主程序
堆排序
快速排序
冒泡排序
希尔排序
归并排序
输出整理排序数据,作出分析。
输入数据
图 SEQ 图 \* ARABIC 1
3详细设计和编码
3.1 算法基本思想
1.随机数的产生:利用sra
显示全部