数据结构课程设计报告.doc

数据结构课程设计报告（2013）数据结构课程设计报告贪心算法任务调度问题专业计算机科学与技术学生姓名吴小会班级M计算机112学号1151401225指导教师吴 素 芹1目 录1 课程设计目的及要求12课题总体设计12.1系统流程图22.2功能模块图32.3 概念设计32.3逻辑设计44详细设计44.1 for循环模块设计44.2 希尔排序模块设计54.3输出调度结果模块设计75调试与测试96小结11参考文献13附 录14附录1 源程序清单141贪心算法的设计1 课程设计目的及要求 （1）、课程设计的内容及目的 有n项任务，要求按顺序执行，并设定第i项任务需要ti单位时间。如果任务完成的顺序为1,2，n，那么第i项任务完成的时间为ci=t1+ti,平均完成时间（Average Completion Time, ACT）即为（c1+cn）/n。本题要求找到最小的任务平均完成时间。本实验的目的是设计一个程序，并且通过运用贪心算法来解决该题的任务调度问题。认识且熟练运用贪心算法，掌握贪心选择性质和最优子结构性质。清晰了解运用贪心算法解决任务调度问题的步骤。（2）、要求输入要求： 输入数据中包含几个测试案例。每一个案例的第一行给出不大于2000000的整数n，接着下面一行开始列出n个非负整数t（t=0;) /*当n小于0的时候，退出程序*/ scanf(“%1d”,&n); if(n0) 建立一个具有n个元素的数组；for（i=0;i=0YN输入任务i=0i1），把数组的全部元素分成个组。所有距离为的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量重复上述的分组和排序，直至所取的增量=1（1;increment0;increment1)/*每次的步长都是通过n值又移位来得到的*/ for(i=increment;i=increment;j-=increment) if(temp0NY把最有调度时间存入rj中j+ri=-1Y输出一个空格输出riN结束功能流程图4.35调试与测试调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施这个程序主要需要测试一下几个方面：l 当任务个数为0时，需要对应输出一个空行。l 当输入的作业数目大于2000000，或者单个作业完成的时间大于1000000000的时候，程序要求报错。l 另外，当任务数比较大的时候，输入对应的任务时间时要仔细，务必保证输入的任务个数与要求的任务数一致。如果出现输入的任务数与n值不相符时，程序会报错，输出“input error！”的错误。下图5.1-5.3为执行使各种不同的正确结果：图5.1 图5.2图5.3在开始编译的时候不是很顺利，出现了各种不同的小错误比如忘记分号，小括号等等。经过一一修改后开始执行。因为对该程序不是特别熟悉总是输入错误不知怎么输入。后来经过查书和同学讨论最终完成执行这个阶段。以下几幅图是我执行时发现的错误： 图5.4该图错误的原因是，已知输入5个任务但是输入的时间单位只有4个。图5.5该图错误的原因是，已知输入5个任务但是输入的时间单位却有6个。图5.6该图的错误原因是，作业数目大于200000。6小结这周的课程设计就要结束了。从最开始的选题到现在的报告总结我完成了一个过程。在这个过程里我领悟了很多。 开始上实验课的时候老师给我们这样一个题目，当时感觉挺好笑的挺奇怪的。因为当时我根本就没有听过谈心算法这个词，“贪心”貌似都是在生活中被提起但是突然出现在我的课程设计中感觉挺好玩的。后来贪心算法基本知识的阅读我才了解什么叫贪心算法，如何应用贪心算法来解决问题。这是我感觉一切的方法都来源于生活，再难懂的问题通过生活的解释都变得言简意赅。虽然在中间写的过程中还有很多不会的东西，但是通过查看书本和资料还有问同学，基本上都解决了。但仍然有一些有待提高的地方，比如在排序前后的结果比较和如果运行时间长的任务在等待很长时间都没有运行等较高的要求还没有解决。 我觉得课程设计的作用一方面是最基本的就是要完成这一科目，差不多也是对自己的一个阶段性的总结；还有就是在整个设计的过程中，让我们认真的独立思考，在和同学交流的过程中也增强了我们的语言组织能力和彼此之间的友谊。通过课程设计让我们不断的发现自己的不足从而去改善，这是一种学习的态度，不仅仅是在这次的课程设计中，在以后的无论生活还是学习方面都应该注意和努力改善。参考文献1 刘振安,刘燕君.C程序设计课程设计M.北京机械工业出版社,2004年9月2 谭浩强.C程序设计（第三版）.清华大学出版社,2005年7月3 严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,1997年4月4 何钦铭，陈根才.数据结构课程设计.浙江大学出版社，2007年8月5 魏宝钢，陈越，王申康.数据结构与算法分析.浙江大学出版社，20046 Mark Allen Weiss,陈越改编.Data Structures and Algorithm Analysis in C(second edition).人民邮电出版社，20057 美S巴斯.计算计算法：设计和分析引论.朱洪等译.复旦大学出版社，19858 Donovan JJ.Operating System.McGraw-Hill,Inc.,19769 Gotlieb CC,Gotlieb L R.Data Types and Structures. Prentice-Hall Inc,197810姚施斌 .数据库系统基础 .计算机工程应用，1981年第8期附 录附录1 源程序清单#include void Shellsort( long *a, long n );int main() long n,i,j; long *a,*b;double r100;/* 用来存放每个测试案例的计算结果 */j=0;/* 记录测试案例的个数 */*读入用户的输入，若当前输入为负数，则程序终止*/ for( n = 0; n = 0 ; ) scanf( %ld, &n );if(n 2000000)printf(too much for the project!n);exit(0); if( n 0 ) b = (long*)malloc( n * sizeof( long ) ); a = b; for(i=0; i 1000000000)printf(too much for the project!n);exit(0); /* 对输入中出现任务时间为负数的异常处理 */ if(*(b+i) 0 ; i-,a+ ) rj+= (double)*a/(double)n * i; j+; free( b ); /* 当n为0时，标志相应的r数组值为1，输出时碰到1则输出一个空行*/ else if ( n = 0 ) rj+=-1; for(i=0;i1; increment0; in