数据结构课程设计报告

数据结构课程设计

设计题目：内部排序算法的性能分析

目录

1. 需求分析................................................................................................................

1.1 课程设计目的 1.2 设计内容及要求 1.3

问题描述

1.4 实现方法描述

2.实现步骤...........................................................................................................

2.1 程序实现思路 2.2 划分程序功能模块 2.3 系统流程图

2.4 定义数据结构和各个功能子函数 2.5 代码的编写 2.6 调试程序

3.测试程序................................................................................................

3.1 测试数据及方法 3.2 选择测试方法的原因 3.3 测试结果 3.4 测试结果分析

4.总结

1 / 10

一、需求分析： 1.1课程设计目的

通过布置具有一定难度的实际程序设计项目，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法；使学生掌握分析问题，求解问题的方法并提高学生设计编程实现的能力。

1.2设计内容及要求

基本要求：

1. 要求利用C\\C++语言来完成系统的设计；

2. 突出C语言的函数特征（以多个函数实现每一个子功能）或者C++语言面向对象的编

程思想； 3. 画出功能模块图；

4. 进行简单界面设计，能够实现友好的交互； 5. 具有清晰的程序流程图和数据结构的详细定义； 6. 熟练掌握C语言或者C++语言的各种操作。 创新要求：

在基本要求达到后，可进行创新设计，如系统用户功能控制，改进算法的实现，实现友好的人机交互等等 。

1.3问题描述

功能：

设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数。 要求：

1) 界面友好，函数功能要划分好 2) 总体设计应画出流程图 3) 程序要加必要的注释

2 / 10

4) 要提供程序测试方案

5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值

1.4 实现方法描述

1) 对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较； 2)

排序表中数据数目不小于100 ，表中数据随机产生，至少用5组不同数据集作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）； 3) 输出比较结果。

4）用描点法绘出各种排序算法对着问题规模增长关键字比较次数和交换次数的变化趋势，同算法本身时间复杂度进行比较。

二、实现步骤 2.1程序实现思路

排序，顾名思义是把一组无序的数据表排列成一组有序的表。为保证程序的高效性，我从以下几方面考虑了程序的设计。 1）数据输入

往电脑里输入数据是一件很令人头痛的事，更何况为测试排序的效率，往往要对成千上万个数据进行排序，为保证程序测试的快速与高效，数据的输入由随机数产生器生成。 2）数据输出

由于数据输出到屏幕与程序排序是两个独立的过程，由于排序数据量的往往输出的时间要比排序所花的时间要长很多，所以我准备构建两个独立的功能，一个排序之后输出结果，便于让用户查看排序结果是否正确。在排序的结果得到保证之后，就没有必要输出排序结果了，只需把算法的比较次数、移动次数、运行时间输出即可。 3）程序功能基本框架

通过对以上两方面的分析，程序的基本功能可为下图：

3 / 10

2.2 划分程序功能模块

1)概要

算法测试：选择一个算法，对其进行5组测试，其实就是对某一个算法的分析。

算法比较：对所有的排序算法都测试，然后输出排序算法所用的比较次数、移动次数、运行时间，方便用户比较各算法的性能。

验证排序争取性：测试各算法的排序结果是否正确。

2）模块图 对所有的排序算法都测试，然后输出排序算法所用的比较次数、移动次数、运行时间，方便用户比较各4 / 10 算法的性能。 退出 比较算法 验证算法正确性 测试算法 内部排序算法性能分析