《数据结构》课程设计指导意见
1、 课程设计的题目和适用范围
题目：工程的工期计算。
该指导意见只供2015级计算机科学与技术1~6班同学参考。
2、 课程设计的目的
数据结构是计算机科学与技术、信息管理、数媒专业的重要的专业基础课，是计算机系统软件和应用软件开发的重要理论和技术。课程设计内容主要用到图的结构。所以课程设计目的要求掌握AOE网，关键路径、事件的最早发生时间、事件的最迟发生时间、活动的最早开始时间、活动的最迟开始时间的计算，以便求出关键路径的长度和完成一项工挰所需时间。（即工程的工期 ）
3、课程设计的内容
已知有向网，图中各顶点代表事件，有向边代表活动，权表示完成活动所需时间(天数) 。求以下内容：
·事件的最早开始时间和最晚开始时间。
·每项活动的最早开始时间和最迟开始时间。
·关键活动和关键路径。
·完成工程最少需要的天数。（工期）
·是否存在某项活动，当其提高速度后能使整个工程缩短工期？
4
6
2
a3=3a7=4
a1=5a12=4
1
10
a4=6a6=3
7
a10=5
9
5
3
a2=6a8=1a13=2
8
a5=3a9=4a11=2
(1) 事件计算公式
· 事件Vk的最早发生时间Ve(k)，是指从源点V1到Vk的最长路径长度。这个时间决定了所有从VK发出的弧所表示的活动能够开工的最早日期。计算公式如下：
Ve(1)=0
Ve(k)=max{Ve(j)+dut() }上的权。
上述公式是一个从源点开始的递推公式，Ve(K)的计算必须在Vk的所有前驱顶点的最早发生时间全部求出后才能进行。
·事件Vi 的最迟发生时间Vl(i) ,是指在不拖延整个工程工期的情况下，事件Vi所允许的最晚发生时间。其数值是从汇点的最早发生时间Ve(n)=Vl(n). 其它顶点的最晚发生时间都应从汇点开始，向源点方向递推求得，计算公式事下：
Vl(n)= Ve(n)
Vl(i)= min{Vl(j)－dut() }上的权.
Vl(i) 的计算必须在顶点I 的所有后继顶点的最晚发生时间全部求出后才能进行。
（2）活动计算公式
·活动ai 的最早开始时间e(i),（ 设边< Vj,Vk> 表示活动ai,） 则有:
e(i)=Ve(j)
说明活动ai的最早开始时间等于事件Vj 的最早发生时间。
·活动ai 的最迟开始时间 l(i), （设边< Vj,Vk> 表示活动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、时间按排
按本学期教务处课程设计时间表执行。（2016~2017第一学期）。13~16周.共16学时。
6、评分标准
平时成绩 20%，程序50%，课程设计报告 30%。
7、算法分析
第一步：建 立邻接表。
第二步：拓扑排序。
第三步：事件的最早发生时间。
第四步：事件的最晚发生时间。
第五步：求关键路径。
第六步：求活动的最 早、最晚发生时间。
第七步：计算关键路径并输出。
输出事件最早和最晚发生时间：
输出关键路径上的数据和总工期：
输出关键路径：
附计算结果：（以下内容要求在程序中输出）
要求输出邻接表和以下内容：
1、 所有事件的最早发生时间：
Ve(1)=0
Ve(2)=5
Ve(3)=6
Ve(4)=max{ve(2)+3,ve(3)+6}=12
Ve(5)=max{ve(3)+3,ve(4)+3}=15
Ve(6)=ve(4)+4=16
Ve(7)=ve(5)+1=16
Ve(8)=ve(5)+4=19
Ve(9)=max{ve(8)+2,ve(7)+5}=21
Ve(10)=max{ve(6)+4,ve(9)+2}=23
2、 所有事件的最迟发生时间：
Vl(10)=23
Vl(9)=vl(10)-2=21
Vl(8)=vl(9)-2=19
Vl(7)=vi(9)-5=16
Vl(6)=vl(10)-4=19
Vl(5)=min{vl(7)-1,vl(8)-4}=15
Vl(4)=min{vl(6)-4,vl(5)-3}=12
Vl(3)=min{vl(4)-6,vl(5)-3}=6
Vl(2)=vl(4)-3=9
Vl(1)=min{vl(2)-5,vl(3)-6}=0
3、 活动的最早开始时间、最迟开始时间、及最早、最迟之差。
最早 最迟 差
活动a1:e(1)=ve(1)=0 l(1)=vl(2)-5=4 d(1)=4
A2: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)-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)=0
4、 此工程 要23天完成。
5、 关键活动：a2 ,a4 , a6, a8, a9, a10, a11, a13.
6、 关键路径：a2->a4->a6->a8->a10->a13
a2->a4->a6->a9->a11->a13
7、 若关键活动：a2,a4,a6,a13 加速完成，整个工程工期可以缩短。（选择关键活动加速后，计算总工期）
