数据结构课程设计报告(完整版本)-
(2)函数接口说明：
函数中的参数均是使用的全局变量的传递，因而在函数间进行传递的过程中比较简单，下面就将主要函数及他们之间的参数的关系列出如下：
int InitStack(Stack &S); int Push(Stack &S,int &e); int Pop(Stack &S,int &e); int CriticalPath(ALGraph &G);
int ToPoOrder(ALGraph &G,Stack &T);
int FindInDegree(ALGraph &G,int (&indegree)[MAX_V_NUM]); 2.3详细设计
该程序的算法主要在以下四个方面：拓扑排序、求出事件的最早发生时间、求出事件的最迟发生时间、求出关键活动，其中关键活动的算法设计较为简单，即是在求出各活动的最早发生时间和最迟发生时间的前提下根据判断两时间是否相等，来判断是否是关键活动，因而主要的算法设计便在前三个方面。
拓扑排序与求事件的最早发生时间相结合，拓扑排序即将入度为零的栈S中的元素依次出栈，同时将该元素进栈到栈T中，在进栈的同时求出其最早发生时间算法如下：
从ve（0）=0开始向前递推
Ve（j）=Max{ve(i)?dut(?i,j?)}
然后便是求事件的最迟发生时间，该过程就是对上面的过程中得到的栈T进行依次出栈，同时求其最迟发生时间，其算法简要描述如下:
从vl（n-1）=ve（n-1）起向后递推
Vl（i）=Min{vl(j)?dut(?i,j?)}
具体实现见代码中int ToPoOrder(ALGraph &G,Stack &T)和int CriticalPath(ALGraph &G)函数；
3、调试分析
该程序的调试过程较为轻松，基本在算法实现的基础上没有出现什么错误，因而在调试的过程中并无什么深刻印象。
4、用户手册
点击运行程序，在弹出的窗口中，会提示要输入的信息： 4、 提示信息为：“请输入图中的顶点数和弧数以及图的标志和弧
的标志：”按要求输入即可，本题即输入9 11 v a
5、 提示信息为“请完成该邻接表的输入”：由于邻接表的输入信
息一般较多，而且均是采用的链表来存储，因而该部分的输入要特别的小心
6、 在完成上面两步的输入后按enter键便能得到程序的运行结
果，即输出完成整项工程至少需要多少时间和影响工程进度的关键活动
13 / 33
数据结构课程设计报告(完整版本)-
5 测试数据及测试结果
测试数据如下： 9 11 v a 1 3 1 6 1 2 4 2 3 5 3 2 1 4 1 4 3 1 4 1 5 4 1 5 2 6 5 2 6 9 7 7 7 8 6 1 7 4 9 7 1
8 2 10 8 1
8 4 11 9 0
程序运行结果如下：
6、原程序清单如下： /*
关键路径问题
2010年07月31日晚上08：36开始动工
14 / 33
数据结构课程设计报告(完整版本)-
*/
#include
const int MAX_V_NUM=20;//最大存储顶点的数目 const int STACK_INIT_SIZE=20;//栈的存储空间分配量 ////数据存储部分 /*
一下是图的邻接表的存储表示，由于第一次用 用的比较的生疏…… */
typedef struct ArcNode {
int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc;//指下一条弧的指针 int info;//该弧相关信息 即权值 int name;//弧的名字 }ArcNode;
typedef struct VNode {
int data;//顶点的信息
ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
}AdjList[MAX_V_NUM]; typedef struct {
AdjList vertices;
int vnum,arcnum;//图中当前顶点数和弧数 char kind,kind1;//图中的各类标志顶点和弧
}ALGraph; typedef struct {
int *base; int *top; int stacksize;
}Stack;
int ve[MAX_V_NUM];
Stack T;
//函数体描述部分
int InitStack(Stack &S);
15 / 33
数据结构课程设计报告(完整版本)-
int Push(Stack &S,int &e); int Pop(Stack &S,int &e);
int CriticalPath(ALGraph &G);
int ToPoOrder(ALGraph &G,Stack &T);
int FindInDegree(ALGraph &G,int (&indegree)[MAX_V_NUM]); /*下面是函数的具体实现部分*/ //构造一个空栈
int InitStack(Stack &S) {
S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) return 0; S.top=S.base;
S.stacksize=STACK_INIT_SIZE;//可以用于当栈的存储空间不够的情况下 进行扩充 return 1; };
//元素进栈
int Push (Stack &S, int &e) {
*S.top++=e; return 1; };
//元素出栈
int Pop(Stack &S, int &e) {
if(S.top==S.base) return 0; e=*--S.top; return 1; };
//判断栈是否为空
int StackEmpty(Stack &S) {
if(S.top==S.base) return 1; else return 0; };
//找出每个顶点的入度
int FindInDegree(ALGraph &G,int (&indegree)[MAX_V_NUM]) {
ArcNode *p;
16 / 33