数据结构课程设计工程的工期计算(7页).doc

《数据结构课程设计工程的工期计算(7页).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计工程的工期计算(7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构课程设计工程的工期计算-第 7 页数据结构课程设计指导意见1、 课程设计的题目和适用范围题目：工程的工期计算。该指导意见只供2015级计算机科学与技术16班同学参考。2、 课程设计的目的数据结构是计算机科学与技术、信息管理、数媒专业的重要的专业基础课，是计算机系统软件和应用软件开发的重要理论和技术。课程设计内容主要用到图的结构。所以课程设计目的要求掌握AOE网，关键路径、事件的最早发生时间、事件的最迟发生时间、活动的最早开始时间、活动的最迟开始时间的计算，以便求出关键路径的长度和完成一项工挰所需时间。（即工程的工期 ）3、课程设计的内容已知有向网，图中各顶点代表事件，有向边代表活动，

2、权表示完成活动所需时间(天数) 。求以下内容：事件的最早开始时间和最晚开始时间。每项活动的最早开始时间和最迟开始时间。关键活动和关键路径。完成工程最少需要的天数。（工期）是否存在某项活动，当其提高速度后能使整个工程缩短工期？462a3=3a7=4 a1=5a12=4110a4=6a6=37a10=5953 a2=6a8=1a13=28a5=3a9=4a11=2(1) 事件计算公式 事件Vk的最早发生时间Ve(k)，是指从源点V1到Vk的最长路径长度。这个时间决定了所有从VK发出的弧所表示的活动能够开工的最早日期。计算公式如下： Ve(1)=0 Ve(k)=maxVe(j)+dut() 上的权。

3、上述公式是一个从源点开始的递推公式，Ve(K)的计算必须在Vk的所有前驱顶点的最早发生时间全部求出后才能进行。事件Vi 的最迟发生时间Vl(i) ,是指在不拖延整个工程工期的情况下，事件Vi所允许的最晚发生时间。其数值是从汇点的最早发生时间Ve(n)=Vl(n). 其它顶点的最晚发生时间都应从汇点开始，向源点方向递推求得，计算公式事下：Vl(n)= Ve(n)Vl(i)= minVl(j)dut() 上的权.Vl(i) 的计算必须在顶点I 的所有后继顶点的最晚发生时间全部求出后才能进行。（2）活动计算公式活动ai 的最早开始时间e(i),（ 设边 表示活动ai,） 则有:e(i)=Ve(j)说

4、明活动ai的最早开始时间等于事件Vj 的最早发生时间。 活动ai 的最迟开始时间 l(i), （设边 表示活动ai） ,是指不推迟整个工程工期的情况下，允许该活动最晚开始的时间。则计算公式如下： l(i) = Vl(k)-dut()即该活动的终点所表示的事件最迟发生时间与该活动所需时间之差。 （3）关键路径计算 l(i) e(i) 0，即l(i)=e(i)的活动ai 是关键活动。若l(i) e(i) 0 ，其时间余量表示不影响工期的情况下，活动可以拖延的时间。4、要求（1）完成程序设计。并计算出正确结果。 （2） 按照课程设计的报告的要求。完成课程设计报告。5、时间按排 按本学期教务处课程设计

5、时间表执行。（20162017第一学期）。1316周.共16学时。6、评分标准 平时成绩 20%，程序50%，课程设计报告 30%。7、算法分析 第一步：建 立邻接表。 第二步：拓扑排序。 第三步：事件的最早发生时间。 第四步：事件的最晚发生时间。 第五步：求关键路径。 第六步：求活动的最 早、最晚发生时间。 第七步：计算关键路径并输出。输出事件最早和最晚发生时间：输出关键路径上的数据和总工期：输出关键路径：附计算结果：（以下内容要求在程序中输出） 要求输出邻接表和以下内容：1、 所有事件的最早发生时间：Ve(1)=0Ve(2)=5Ve(3)=6Ve(4)=maxve(2)+3,ve(3)+6

6、=12Ve(5)=maxve(3)+3,ve(4)+3=15Ve(6)=ve(4)+4=16Ve(7)=ve(5)+1=16Ve(8)=ve(5)+4=19Ve(9)=maxve(8)+2,ve(7)+5=21Ve(10)=maxve(6)+4,ve(9)+2=232、 所有事件的最迟发生时间：Vl(10)=23Vl(9)=vl(10)-2=21Vl(8)=vl(9)-2=19Vl(7)=vi(9)-5=16Vl(6)=vl(10)-4=19Vl(5)=minvl(7)-1,vl(8)-4=15Vl(4)=minvl(6)-4,vl(5)-3=12Vl(3)=minvl(4)-6,vl(5)-

7、3=6Vl(2)=vl(4)-3=9Vl(1)=minvl(2)-5,vl(3)-6=03、 活动的最早开始时间、最迟开始时间、及最早、最迟之差。 最早 最迟 差活动a1:e(1)=ve(1)=0 l(1)=vl(2)-5=4 d(1)=4A2:e(2)=ve(1)=0 l(2)=vl(3)-6=0 d(2)=0 A3:e(3)=ve(2)=5 l(3)=vl(4)-3=9 d(3)=4 A4:e(4)=ve(3)=6 l(4)=vl(4)-6=6 d(4)=0 A5:e(5)=ve(3)=6 l(5)=vl(5)-3=12 d(5)=6 A6:e(6)=ve(4)=12 l(6)=vl(5)

8、-3=12 d(6)=0 A7:e(7)=ve(4)=12 l(7)=vl(6)-4=15 d(7)=3 A8: e(8)=ve(5)=15 l(8) =vl(7)-1=15 d(8)=0 A9: e(9)=ve(5)=15 l(9)=vl(8)-4=15 d(9)=0 A10: e(10)=ve(7)=16 l(10)=vl(9)-5=16 d(10)=0 A11: e(11)=ve(8)=19 l(11)=vl(9)-2=19 d(11)=0 A12: e(12)=ve(6)=16 l(12)=vl(10)-4=19 d(12)=3 A13: e(13)=ve(9)=21 l(13)=vl(10)-2=21 d(13)=04、 此工程 要23天完成。5、 关键活动：a2 ,a4 , a6, a8, a9, a10, a11, a13.6、 关键路径：a2-a4-a6-a8-a10-a13 a2-a4-a6-a9-a11-a137、 若关键活动：a2,a4,a6,a13 加速完成，整个工程工期可以缩短。（选择关键活动加速后，计算总工期）