数据结构1.doc

第五题：关键路径问题1、需求分析：当一项工程被划分为若干个子任务或活动后，人们不仅需要确定这些活动的先后次序，而且需要进一步计算完成整个工程的时间，确定哪些活动是影响工程进度的关键活动，以便合理组织人力、物力、财力，加快这些活动的进度，为按时或提前完成整个工程提供保证。要求：给定一个带权的有向图代表一个工程的AOE网络，研究如下问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键活动？示例图：2、设计21设计思想：（1）数据结构设计本题中的数据结构主要影响在于整个程序设计过程中数据的存储和拓扑排序、关键路径算法的实现，而在算法的实现过程中又要依赖数据的存储结构，而在图的存储结构中，比较适合实现拓扑排序算法的显然是邻接表的存储结构，所以本程序设计过程中均采用的是邻接表的存储方法。其主要数据的主要存储结构体声明如下：typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc;/指下一条弧的指针int info;/该弧相关信息 即权值int name;/弧的名字ArcNode;typedef struct VNodeint data;/顶点的信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/图中当前顶点数和弧数char kind,kind1;/图中的各类标志顶点和弧ALGraph;同时由于拓扑排序实现过程中要用到进栈和出栈的操作，因此还有栈的声明如下：typedef struct int *base;int *top;int stacksize;Stack;（2）算法设计本程序的算法设计主要体现在拓扑排序和求事件的最早发生时间和最迟发生时间的的过程中，因此算法设计主要也是针对拓扑排序和求事件发生的最早发生和最迟发生时间的算法设计。拓扑排序的思想是将入度为零的结点进行S1中的出栈操作，同时将其对T进行进栈，这主要是方便在进行完求最早发生时间后，通过出栈的操作直接求最迟发生时间。2.2设计表示（1）、函数调用关系图及其说明如下:(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）=然后便是求事件的最迟发生时间，该过程就是对上面的过程中得到的栈T进行依次出栈，同时求其最迟发生时间，其算法简要描述如下:从vl（n-1）=ve（n-1）起向后递推Vl（i）=具体实现见代码中int ToPoOrder(ALGraph &G,Stack &T)和int CriticalPath(ALGraph &G)函数；3、调试分析该程序的调试过程较为轻松，基本在算法实现的基础上没有出现什么错误，因而在调试的过程中并无什么深刻印象。4、用户手册点击运行程序，在弹出的窗口中，会提示要输入的信息：1、 提示信息为：“请输入图中的顶点数和弧数以及图的标志和弧的标志：”按要求输入即可，本题即输入9 11 v a2、 提示信息为“请完成该邻接表的输入”：由于邻接表的输入信息一般较多，而且均是采用的链表来存储，因而该部分的输入要特别的小心3、 在完成上面两步的输入后按enter键便能得到程序的运行结果，即输出完成整项工程至少需要多少时间和影响工程进度的关键活动 5 测试数据及测试结果测试数据如下：9 11 v a131 6 12 4 23 5 3214 1 4314 1 5415 2 6526 9 77 7 8617 4 9718 2 10818 4 1190程序运行结果如下：6、原程序清单如下：/*关键路径问题2010年07月31日晚上08：36开始动工#includeusing namespace std;const int MAX_V_NUM=20;/最大存储顶点的数目const int STACK_INIT_SIZE=20;/栈的存储空间分配量/数据存储部分/*一下是图的邻接表的存储表示，由于第一次用 用的比较的生疏*/typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc;/指下一条弧的指针int info;/该弧相关信息 即权值int name;/弧的名字ArcNode;typedef struct VNodeint data;/顶点的信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/图中当前顶点数和弧数char kind,kind1;/图中的各类标志顶点和弧ALGraph;typedef struct int *base;int *top;int stacksize;Stack;int veMAX_V_NUM;Stack T;/函数体描述部分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);/*下面是函数的具体实现部分*/构造一个空栈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;int i;for(i=0;iMAX_V_NUM;i+)indegreei=0;for(i=0;inextarc)indegreep-adjvex+;return 0;/拓扑排序同时求出各活动的最早发生时间int ToPoOrder(ALGraph &G,Stack &T)int count=0;int i,j,k;Stack S1;ArcNode *p;int indegreeMAX_V_NUM;InitStack(T);InitStack(S1);FindInDegree(G,indegree);for(i=0;iG.vnum;i+)if(indegreei=0)Push(S1,i);/建立0入度顶点栈Sfor(i=0;inextarc)k=p-adjvex;if(-indegreek=0)Push(S1,k);if(vej+(p-info)vek)vek=vej+(p-info);/for(i=0;iG.vnum;i+)/coutveiendl;if(countG.vnum)return 0;else return 1;/计算各顶点的最迟发生时间及进行输出int CriticalPath(ALGraph &G)int vlMAX_V_NUM;int dut;int i,j,k,ee,el;ArcNode *p;/char tag;if(!ToPoOrder(G,T)return 0;cout完成整项工程至少需要的时间是：veG.vnum-1endl;for(i=0;inextarc)k=p-adjvex;dut=(p-info);if(vlk-dutvlj)vlj=vlk-dut;/for(i=0;iG.vnum;i+)/coutvliendl;cout影响工程进度的关键活动是:endl;for(j=0;jnextarc)k=p-adjvex;dut=(p-info);ee=vej;el=vlk-dut;/coutj=jK=kdut=dutee=eeel=elendl;if(ee=el)/tag=(ee=el)?*:;coutG.kind1nameendl;return 1;int main()ALGraph G;int i,j,Hnum;ArcNode *p,*q;/int indegreeMAX_V_NUM;/ALGraph G;cout请输入图中的顶点数和弧数以及图的标志和弧的标志：G.vnum;cinG.arcnum;cinG.kind;cinG.kind1;cout请完成该邻接表的输入：endl;for(i=0;iG.vnum;i+)cout请输入该顶点的信息G.verticesi.data;cout请输入与G.kindG.verticesi.data号顶点相邻的弧的数目:Hnum;if(Hnum=0)G.verticesi.firstarc=0;elsecout请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）nextarc=0;cinp-adjvex;cinp-info;cinp-name;for(j=0;jHnum-1;j+)cout请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）q-adjvex;cinq-info;cinq-name;q-nextarc=p-nextarc;p-nextarc=q;/ToPoOrder(G,T