数据结构各种排算法的课程设计实验报告(c语言版).docVIP

滁州学院 课程设计报告 课程名称： 数据结构 设计题目： 排序算法实现及比较 系 别： 计算机信息工程学院 专 业： 计算机科学与技术 组 别： 第组 起止日期: 12 年 5 月 1 日 ~ 12 年 6月 日 指导教师: 计算机与信息工程学院二○一二年制 课程设计任务书 课程设计题目 排序算法实现将比较 组长 学号 20 班级 系别 计算机与信息工程学院 专业 计算机科学与技术 组员 指导教师 课程设计目的 ⑴加深对常见排序算法理解 ⑵通过程序比较常见算法优越性 ⑶熟悉加深对数据结构的了解及认识 课程设计所需环境 Windows xp；VC++6.0 课程设计任务要求 ⑴实现常见排序算法程序化 ⑵测试程序比较算法优越性 ⑶了解常见算法的实际应用 课程设计工作进度计划 序号 起止日期 工 作 内 容 分工情况 1 分析实验类容 2 分工 3 算法改编成程序 4 将子程序合并及调试 数据测试及记录 5 编写报告 指导教师签字： 年 月 日 系（教研室）审核意见： 系（教研室）主任签字： 年 月 日 目 录 1.引言 4 2.需求分析 4 3.详细设计 4 3.1 直接插入排序 4 3.2折半排序 5 3.3 希尔排序 6 3.4简单选择排序 6 3.5堆排序 6 3.6归并排序 7 3.7冒泡排序 9 4.调试 10 5.调试及检验 11 5.1 直接插入排序 11 5.2折半插入排序 11 5.3 希尔排序 12 5.4简单选择排序 12 5.5堆排序 13 5.6归并排序 14 5.7冒泡排序 14 6.测试与比较 15 6.1调试步骤 15 6.2结论 16 7.实验心得与分析 16 8.附录 17 8.1直接插入排序 17 8.2折半插入排序 18 8.3希尔排序 20 8.4简单选择排序 22 8.5堆排序 23 8.6归并排序 26 8.7冒泡排序 29 8.8主程序 30 1.引言 伴随着社会的发展，数据也变得越来越庞大。如何将庞大的数据进行很好的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。对于程序员来说，这将是一个挑战。 经常查找资料的朋友都会知道，面对海量的资料，如果其查找的资料没有进行排序，那么其查找资料将会是一件非常痛苦的事情。针对这一问题，我们自此通过一个课程设计来解决它。 理论上排序算法有很多种，不过本课程设计只涉及到七种算法。这七种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。 本课程设计通过对这七种算法的运行情况进行对比，选择最优秀的算法来提供给用户。希望通过我们的努力能给用户解决一些问题，带来一些方便。 2.需求分析 本课程题目是排序算法的实现，由于各方面的原因，本课程设计一共要设计七种排序算法。这七种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。七种排序各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。 为了小组分工的方便，我们特意把子函数写成Header File文件。这样操作不仅可以使小组分工更加简洁明了，还可以方便子函数的调用，更可以使写主函数时一目了然。 为了运行时的方便，我们将七种排序方法进行编号，其中1为直接插入排序，2为折半插入排序，3为希尔排序，4为简单选择排序，5为堆排序，6为归并排序，7为冒泡排序。通过这七种选项，可以让用户简单明了的去选择使用哪一种排序方法。 本课程就是通过对5组占用内存大小不同的数据调试来测试这七种算法运行的时间长短，从中选择面对不同大小的文件时，哪一种算法更为快捷。 软件环境本课程设计所用操作系统为Windows-XP操作系统，所使用的软件为Microsoft Visual C++ 6.0； 3.详细设计 3.1 直接插入排序 ⑴算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前有哪些信誉好的足球投注网站的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。 ⑵程序实现及核心代码的注释： for i 1 ; i r.length ;++i for j 0;j i;++j if r.base[i] r.base[j] temp r.base[i]; //保存待插入记录 for i i ;i j; --i r.base[i] r.base[i-1]; //记录后移 r.base