1、 数 据 结 构 课 程 设 计数 据 结 构 课 程 设 计 报 告报 告 贪心算法贪心算法 任务调度问题任务调度问题 专业专业 计算机科学与技术 学生姓名学生姓名 班级班级 学号学号 指导教师指导教师 数据结构课程设计报告（2013） 目目 录录 1 课程设计目的及要求 . 1 2 课题总体设计 . 1 2.1 系统流程图 2 2.2 功能模块图 . 3 2.3 概念设计 3 2.3 逻辑设计 4 4 详细设计 . 4 4.1 for 循环模块设计. 4 4.2 希尔排序模块设计 . 5 4.3 输出调度结果模块设计 7 5 调试与测试 . 9 6 小结 11 参考文献 13 附 录 14
2、 附录 1 源程序清单 . 14 数据结构课程设计报告（2013） 1 贪心算法贪心算法的设计的设计 1 1 课程设计目的课程设计目的及要求及要求 （1） 、课程设计的内容及目的 有 n 项任务，要求按顺序执行，并设定第 i 项任务需要 ti单位时间。如果任 务完成的顺序为 1,2，n，那么第 i 项任务完成的时间为 ci=t1+ti, 平均完成时间（Average Completion Time, ACT）即为（c1+cn）/n。本题 要求找到最小的任务平均完成时间。 本实验的目的是设计一个程序，并且通过运用贪心算法来解决该题的任务调度问 题。认识且熟练运用贪心算法，掌握贪心选择性质和最优子
3、结构性质。清晰了解运 用贪心算法解决任务调度问题的步骤。 （2） 、要求 输入要求： 输入数据中包含几个测试案例。 每一个案例的第一行给出不大于 2000000 的整数 n，接着下面一行开始列出 n 个非负整数 t（t=0;) /*当 n 小于 0 的时候，退出程序*/ scanf(“%1d”, if(n0) 建立一个具有 n 个元素的数组； for（i=0;i1），把数组的全部元素分成 1 d个组。所有距离 为 1 d的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二 个增量 2 d 1 d重复上述的分组和排序， 直至所取的增量 t d=1 （ t d 1t d 1;inc
4、rement0;increment1) /*每次的步长都是通过 n 值又移位来得到的*/ for(i=increment;i=increment;j-=increment) if(temp0 N Y 把最有调度时间存入 rj中 j+ ri=-1 Y 输出一个空格 输出 ri N 结束 功能流程图 4.3 数据结构课程设计报告（2013） 9 5 调试与测试调试与测试 调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决 措施 这个程序主要需要测试一下几个方面： 当任务个数为 0 时，需要对应输出一个空行。 当输入的作业数目大于 2000000，或者单个作业完成的时间大于 100
5、0000000 的时候，程序要求报错。 另外，当任务数比较大的时候，输入对应的任务时间时要仔细，务必保证 输入的任务个数与要求的任务数一致。如果出现输入的任务数与 n 值不相 符时，程序会报错，输出“input error！”的错误。 下图 5.1-5.3 为执行使各种不同的正确结果： 图 5.1 数据结构课程设计报告（2013） 10 图 5.2 图 5.3 在开始编译的时候不是很顺利，出现了各种不同的小错误比如忘记分号，小括号等等。经 过一一修改后开始执行。因为对该程序不是特别熟悉总是输入错误不知怎么输入。后来经过查 书和同学讨论最终完成执行这个阶段。 以下几幅图是我执行时发现的错误： 图
6、 5.4 该图错误的原因是，已知输入 5 个任务但是输入的时间单位只有 4 个。 数据结构课程设计报告（2013） 11 图 5.5 该图错误的原因是，已知输入 5 个任务但是输入的时间单位却有 6 个。 图 5.6 该图的错误原因是，作业数目大于 200000。 6 小结小结 这周的课程设计就要结束了。从最开始的选题到现在的报告总结我完成了 一个过程。在这个过程里我领悟了很多。 开始上实验课的时候老师给我们这样一个题目，当时感觉挺好笑的挺奇怪 的。因为当时我根本就没有听过谈心算法这个词， “贪心”貌似都是在生活中被 提起但是突然出现在我的课程设计中感觉挺好玩的。后来贪心算法基本知识的 阅读我才了解什么叫贪心算法，如何应用贪心算法来解决问题。这是我感觉一 切的方法都来源于生活，再难懂的问题通过生活的解释都变得言简意赅。虽然 在中间写的过程中还有很多不会的东西， 但是通过查看书本和资料还有问同学， 基本上都解决了。但仍然有一些有待提高的地方，比如在排序前后的结果比较 和如果
