《数据结构》课程设计总结报告
学号：
姓名：
专业：
第二部分 综合应用设计说明
2.1 题目
6.已知假想的工程活动 AOE 网，试设计一个算法，要求：
（1）判断工程是否可行；
（2）求出工程中每个活动的最早开始时间 e(i)，最迟开始时间 l(i)，和全工程可以
完成的最早时间；
（3）确定工程中的关键路劲和可使整个工程的工期缩短的关键活动。
说明：可以给出一个假想的工程活动 AOE 网，也可以给出工程的活动情况，画出
AOE 网。
2.2 软件功能
该软件可以实现以下功能：
由用户任意创建出一个工程活动 AOE 网络，通过单击创建事件，通过点选两个事件来
创建活动，创建事件与创建活动的行为同步进行，相互之间不影响。创建过程不支持撤
销动作，用户创建时需要小心，这也是本软件的一大缺点。用户创建网络完成后，可选
择求解工程，若工程不可行则会显示提示，简单说明不可行的原因，之后用户可重新
创建工程；若工程可行，则会在网络上用红色标出关键路径，并以列表方式列出所有
活动的最早开始时间、最迟开始时间和持续时间，并会以黄色标出关键活动，每个活
动用其起始事件与结束事件来表示。最后还会给出全工程可以完成的最早时间。完成一
项工程的求解后用户可选择继续创建新的工程。
2.3 设计思想
本软件采用 C#语言编写，实现了界面的图形化。
AOE 网络采用类似邻接表的方式存储，因 C#不支持指针，故本程序中以下标可变长数
组来替代原来邻接表中指示节点后继的链表。为实现 AOE 网络的表示，我采用了三个
类：AOE 网络类，事件类和活动类。事件类和活动类仅有成员变量和构造函数，所有
对网络的操作均在 AOE 网络类的方法中。事件类包含有以该事件为起点所有活动的可
变长数组，每个活动以其开始和结束事件在网络类中的事件可变长数组中的位置表示。
AOE 网络类中主要有以下方法：求解工程是否可行、求各事件的最早和最迟开始时间、
求各活动的最早和最迟开始时间。
求解工程是否可行分以下四种情况：
1.工程中是否存在活动：
遍历所有事件节点，检查其活动可变长数组是否为空，若所有节点均为空则工程中不
存在活动，工程不可行。
2.工程是否有多个源点：
遍历所有事件，统计入度为 0 的事件节点的数量，若数量大于 1，则 工程有多个源点，
不能对工程进行求解。
3.工程是否有多个汇点：
遍历所有事件，统计活动可变长数组为空的事件节点的数量，若数量大于 1，则工程
有多个汇点，不能对工程进行求解。
4.工程中是否含有向环：
（1）对工程中的事件进行拓扑排序；
（2）若事件节点全部被排序，则工程可行，将结果存入一可变长数组，数组存储的是
事件在事件节点可变长数组中的位置；若 有节点未被插入拓扑排序序列，则工程
中包含有向环，工程不可行。
求各事件的最早和最迟开始时间：
1.事件最早开始时间：
按拓扑排序结果，从前向后，取大值：直接前驱结点的最早开始时间 + 指向顶点的
边的权值，有多个值的取较大者。
2.事件最迟开始时间：
按拓扑排序结果，从后向前，取小值：直接后继结点的最迟开始时间 - 从顶点发出
的边的权值，有多个值的取较小者。
求各活动的最早和最迟开始时间：
1.活动的最早开始时间 = 它的发出顶点的最早发生时间；
2.活动的最迟开始时间 = 它的到达顶点的最晚发生时间减去活动的权值。
求关键路径和关键活动（该功能包含在求各活动的最早和最迟开始时间的方法中
）：
遍历所有活动，标记出最早和最迟开始时间相同的活动，重绘网络时将其标为红色，在
列表中以黄色标出该活动。
2.4 逻辑结构与物理结构
AOE 网络类（Net）：
