数据结构课设报告

《数据结构课设报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《敷据穡构》襦程筱计报告姓名：学号：院系：计算机学院软件工程班级：指导教师：目录《数据结构》课程设计报告1一、必做题3I、设计内容和要求3Ik算法思想3Ilk程序结构4IV、使用说明5V、测试结果7VI、问题以及解决方案8Vlk收获与体会8Vllk参考文献9二、选做题9㈠、设计内容和要求9㈡、算法思想9㈢、程序结构10测试结果12收获与休会15I、设计内容和要求设计内容：四种排序算法的实现以及性能比较要求：编程实现希尔、快速、堆排序、归并排序算法。要求随机产生10000个数据存入磁盘文件，然后读入数据文件，分别采用不同的排序方法进行排序，并将结果存入文件屮。II、算法思想在木课题屮，我们根据要

2、求对大量的随机数分别使用希尔排序，快速排序,堆排序，归并排序进行排序，并根拯随机数数量的增加观察四种排序运行所耗时间,进而分析出四种排序方法在不同情况下的性能好坏。1.希尔排序希尔排序是对直接插入排序的一种改进，它的基本思想是：先将整个待排序记录序列划分为若干个小序列，在这些小序列屮分别进行直接插入排序；逐步扩大小序列的长度，减少小序列的个数，这样使待排序序列逐渐处于更冇序的状态；最后对全体序列进行一次直接插入排序，从而完成整个排序过程。2.快速排序快速排序是一个递归的过程，其基木思想是：从待排序记录中选区一个记录（通常选取第一个记录）为枢轴，其关键字为k,将关键字值小于k的记录移到前而，而将

3、关键字值大于k的移到后而，结果将待排序记录序列分成两个了表，最后将关键字值为k的记录插到分界线处，我们将这个过程成为“划分”，对划分后的子表继续按上述原则进行划分，直到所冇子表不超过1为止，此时待排序记录序列就编程了一个冇序序列。1.堆排序堆排序是选择排序的一种改进，其基本思想是：首先用待排序的记录序列构造成一个堆，此时选出堆屮所有记录的最大者，即堆顶记录,然后将它从堆中移走(通常将堆顶记录和堆中最后一个记录交换)，并将剩余的记录再调整成堆，这样又找岀了次大的记录，依此类推，直到堆屮只有一个记录为止。2.归并排序归并排序是通过“归并”进行排序的一种方法。归并就是将两个或两个以上的有序序列合并成

4、一个有序序列的过程。其基本思想是：将若干冇序序列逐步归并，最终归并为一个冇序序列。3.计时函数计时函数使用了高精度时间函数QueryPerformanceFrequency()和QueryPerformanceCounter()来实现毫秒级的计吋功能。该函数接受一个指向函数的指针参数，用于在两次查询机器内部计时器的位置插入所需要被计时的代码,再将两次杳询Z茅除以CPU时钟频率即可得到事件执行的精确时间。m、程序结构本程序由Sort,cpp、Sort,h和Sorts,h三部分组成。Sort,h头文件中实现了希尔排序，快速排序，堆排序以及归并排序这四种排序；Sorts,h头文件中实现了产生随机待排

5、数据，将数据写入文件,从文件读数据，计算排序所消耗吋间，以及输出执行时间的功能；Sort,cpp主函数负责提示操作以及调用头文件里的函数。IV.使用说明首先，运行程序，出现如下界面，提示用户按照步骤操作，从1到4依次逐步执,C:UsersadminDesktopSortDebugSort.exeR你有5秒钟的时间浏览说明，5秒钟之后程序开始。ifeif扁各楷™™袖程序开始？将待排数据存入磁盘文件3=0wftlffiwli，并记录运行时间,打印岀四种排序算法的运行时间4：W序结果写入另一不文件0=71di请按照步骤完成排序算法的实现与比较：丄请按照步骤完成排序算法的实现与比较：丄请从

6、1000050000100000200000中选岀待排数据的个数1000010000个待排数据已经随机产生.待排数据已经存入名为&的文本文档中.❷请按照步骤完成排序算法的实现与比较：2磁盘文件读取完毕.❸请按照步骤完成排序算法的实现与比较：3待排数据已经排序，各排序算法的执行时间已分别被记录.4种排序算法的执行时间分别为:ShellSort：8msQuickSort：5nsHeapSort：7nsMergeSort：9ns请按照步骤完成排序算法的实现与比较：4待排数据已经存入名为b的文本文档中.—次程序运行结束，你可以开始新的程序?请按照步骤完成排序算法的实现与比较：0退岀程序？Pressan

7、ykeytocontinueV、测试结果未完成排序的待排数据已经存入名为a的文本文档屮.a・记事本o回一：文件(F)務(E)格式(O)查看(V)帮助(H)4118467633426500191691572411478293582696224464•5705281452328116827996149129951194248275436323911460439021532921238217421187