文档详情

数据结构(课程设计)排序算法时间性能的分析.doc

发布:2018-08-25约1.36万字共21页下载文档
文本预览下载声明
《数据结构》课程设计报告 目录 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
显示全部
相似文档