数据结构课程设计报告(完整版本)-

ArcNode *p,*q;

// int indegree[MAX_V_NUM]; //ALGraph G;

cout<<\请输入图中的顶点数和弧数以及图的标志和弧的标志：\

cin>>G.vnum; cin>>G.arcnum; cin>>G.kind; cin>>G.kind1;

cout<<\请完成该邻接表的输入：\ for(i=0;i

{ cout<<\请输入该顶点的信息\ cin>>G.vertices[i].data; cout<<\请输入与\.kind<>Hnum; if(Hnum==0) { G.vertices[i].firstarc=0; } else { cout<<\请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）\ p=(ArcNode *)malloc(sizeof(ArcNode)); G.vertices[i].firstarc=p; p->nextarc=0; cin>>p->adjvex; cin>>p->info; cin>>p->name; for(j=0;j>q->adjvex; cin>>q->info; cin>>q->name; q->nextarc=p->nextarc; p->nextarc=q;

9 / 33

数据结构课程设计报告(完整版本)-

} } }

//ToPoOrder(G,T); //CriticalPath(G); ////////test//////////

/* for(i=0;inextarc) { cout<adjvex].data<

// FindInDegree(G,indegree); //for(i=0;i

// cout<<\ CriticalPath(G);

////////////test end///////////

return 0;

system(“pause”); }

10 / 33

数据结构课程设计报告(完整版本)-

第五题：关键路径问题

1、需求分析：

当一项工程被划分为若干个子任务或活动后，人们不仅需要确定这些活动的先后次序，而且需要进一步计算完成整个工程的时间，确定哪些活动是影响工程进度的关键活动，以便合理组织人力、物力、财力，加快这些活动的进度，为按时或提前完成整个工程提供保证。

要求：

给定一个带权的有向图代表一个工程的AOE网络，研究如下问题： （1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键活动？ 示例图：

a1a2=4a3=5

61=2a4=134=a519=a75a8=77a10=2984=1a1a6=2=a94 62、设计 2．1设计思想： （1）数据结构设计

本题中的数据结构主要影响在于整个程序设计过程中数据的存储和拓扑排序、关键路径算法的实现，而在算法的实现过程中又要依赖数据的存储结构，而在图的存储结构中，比较适合实现拓扑排序算法的显然是邻接表的存储结构，所以本程序设计过程中均采用的是邻接表的存储方法。其主要数据的主要存储结构体声明如下：

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

11 / 33

数据结构课程设计报告(完整版本)-

{ AdjList vertices; int vnum,arcnum;//图中当前顶点数和弧数 char kind,kind1;//图中的各类标志顶点和弧

}ALGraph;

同时由于拓扑排序实现过程中要用到进栈和出栈的操作，因此还有栈的声明如下：

typedef struct { int *base; int *top; int stacksize;

}Stack;

（2）算法设计

本程序的算法设计主要体现在拓扑排序和求事件的最早发生时间和最迟发生时间的的过程中，因此算法设计主要也是针对拓扑排序和求事件发生的最早发生和最迟发生时间的算法设计。拓扑排序的思想是将入度为零的结点进行S1中的出栈操作，同时将其对T进行进栈，这主要是方便在进行完求最早发生时间后，通过出栈的操作直接求最迟发生时间。

2.2设计表示 （1）、函数调用关系图及其说明如下 :

12 / 33