1、 数 据 结 构 课 程 设 计数 据 结 构 课 程 设 计 报 告报 告 贪心算法贪心算法 任务调度问题任务调度问题 专业专业 计算机科学与技术 学生姓名学生姓名 班级班级 学号学号 指导教师指导教师 * 目目 录录 1 课程设计目的及要求 . 1 2 课题总体设计 . 1 2.1 系统流程图 错误错误!未定义书签。未定义书签。 2.2 概念设计 . 错误错误!未定义书签。未定义书签。 2.3 逻辑设计 . 错误错误!未定义书签。未定义书签。 3 详细设计 . 2 3.1 for 循环模块设计 2 3.2 希尔排序模块设计 . 3 3.3 输出调度结果模块设计 . 4 4 调试与测试 .
2、5 5 小结 . 7 参考文献 7 附 录 9 附录 1 源程序清单 . 9 数据结构课程设计报告（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
4、d=1 （ t d 1t d1;increment0;increment1) /*每次的步长都是通过 n 值又移位来得到的*/ for(i=increment;i=increment;j-=increment) if(temp= 0 ; ) scanf( “%ld“, 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 th
5、e 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; increment=1 ) for(i = increment; i =increment; j-= increment) if( temp *(a + (j-increment) ) *(a+j)= *( a+ (j-increment) ); else break; *(a+j) = temp; 数据结构课程设计报告（2013） 12
