《数据结构》课程.pdf

《数据结构》课程 设计报告 2007-9-6 课题：排序算法的实现与比较 作者：粟遥 学号 指导教师：陈波 《数据结构》课程设计报告 《数据结构》课程设计报告 排序算法的实现与比较 设计内容及要求 编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。将 待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。 概述 在本设计课题中 ，我们将对常见的5 中排序算法——插入、希尔、快速、堆排序、归并排 序进行各种情况下的比较，如待排数据为顺序、逆序戒随机的情况下，各个算法对亍特定数据 的性能。基亍此点考虑，在程序中选择采用以毫秒为单位的执行时间来衡量算法对特定数据的 性能高低。本文将主要介绉《排序之谜》程序 （以下简称“程序”）的数据结构的设计、功能 设计以及相关技术讨论等。本程序在Microsoft Windows Server 2003/Microsoft Visual C++ 2005 的命令行编译器cl.exe 环境编译下通过。 分发包说明 程序分发包中将包含以下文件，其用途分别如表格1 所示。 文件名 说明 algorithm_lib.h 头文件，包含所有排序算法的实现 functions.h 头文件，包含所有程序调用函数的实现 main.cpp C++源文件，包含主程序界面的实现 makefile Makefile ，包含源文件间依存关系及自动化编译选项 sort.exe Windows 二进制可执行程序 src.dat 数据文件，包含一组测试用数据 report.pdf PDF 文档，即本设计报告 表格1 数据结构设计 主程序数据结构 1 《数据结构》课程设计报告 主程序中采用两个整型数组input_array 和output_array ，其长度均为10000 ，分别作为待 排序数据和已排序数据的存放空间，并设置一整型数组 sort_time 用来存放5 个算法的执行时间。 之所以这样设计，是因为所有的用户定义函数都完全按照既定的“标准”设计实现，使得整个 程序的可伸缩性大大增强。 #define LENGTH 10000 int length = LENGTH; int input_array[LENGTH] = {0}; int output_array[LENGTH] = {0}; int sort_time[5] = {0}; // 0 InsertionSort, 1 QuickSort, 2 MergeSort, // 3 HeapSort, 4 ShellSort 排序算法的设计实现 程序中的全部5 中排序算法均按照标准化的函数名、返回值和形参表设计，其形式为： void SomeSortMethod (const int *array_to_sort, int *sorted_array, const int length); 1 算法的设计和实现参照了现有教科书 上的算法描述，下面将逐一列出各个排序算法的C++ 实现。 插入排序 插