gjlj.cpp

这是一个求关键路径的C++程序源代码.里面已经把注释文字都写好了,放心下载.

#include<stdio.h>
#include<stdlib.h>
//#include<iomanip.h>
//#include <process.h>
//#define PROJECTNUMBER  9//10
//#define PLANNUMBER 11//13
typedef struct node
{
       int adjvex;
       int dut;
       struct node *next;
}edgenode;
typedef struct 
{
       int  projectname;
       int  id;
       edgenode *link;
}vexnode;
//vexnode Graphicmap[PROJECTNUMBER];
void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)    //建立AOE图
{
       int begin,end,duttem,i,k;
       edgenode *p;
       for(i=0;i<projectnumber;i++)
	   {
		   Graphicmap[i].projectname=i;   //标实符
           Graphicmap[i].id =0;           //位置
           Graphicmap[i].link =NULL;      //是否连接
	   }     
       printf("输入连接点和活动时间<起始节点,目标节点,活动时间>:\n");
	   printf("(如:1,2,3 回车表示第1节点到第2节点之间的活动用了3个单位时间)\n\n");
       for(k=0;k<activenumber;k++)        //建立节点之间的连接，完成AOE图
	   {
           scanf("%d,%d,%d",&begin,&end,&duttem);
           p=(edgenode*)malloc(sizeof(edgenode));
           p->adjvex =end-1;
           p->dut =duttem;
           Graphicmap[end-1].id ++;
           p->next =Graphicmap[begin-1].link ;
           Graphicmap[begin-1].link =p;
	   }
}
int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime)  //求最大路径并打印关键路径
{
       int i,j,k,m=0;
       int front=-1,rear=-1;
	   int* topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列
       int* vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间
       int* ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间
       int* l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间
       int* e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间
       edgenode *p;
       totaltime=0;
       for(i=0;i<projectnumber;i++) ve[i]=0;
       for(i=0;i<projectnumber;i++)
	   {
		   if(Graphicmap[i].id==0)
		   {
			   topologystack[++rear]=i;
               m++;
		   }
	   }
       while(front!=rear)
	   {
		   front++;
		   j=topologystack[front];
		   m++;
		   p=Graphicmap[j].link ;
		   while(p)
		   {
			   k=p->adjvex ;
			   Graphicmap[k].id --;
			   if(ve[j]+p->dut >ve[k])
				   ve[k]=ve[j]+p->dut ;
			   if(Graphicmap[k].id ==0)
				   topologystack[++rear]=k;
			   p=p->next ;
		   }
	   }
	   if(m<projectnumber)
	   {
		   printf("\n此次建立的图有错误,无法计算关键路径\n");
		   printf("将退出本程序\n");
		   return 0;
	   }
	   totaltime=ve[projectnumber-1];   //此工程的最短完成时间
	   for(i=0;i<projectnumber;i++)
		   vl[i]=totaltime;
	   for(i=projectnumber-2;i>=0;i--)
	   {
		   j=topologystack[i];
		   p=Graphicmap[j].link ;
		   while(p)
		   {
			   k=p->adjvex ;
			   if((vl[k]-p->dut )<vl[j])
				   vl[j]=vl[k]-p->dut ;
			   p=p->next ;
		   }
	   }
	   i=0;
	   /*printf("|  起点  |  终点  |   最早开始时间   |   最迟完成时间   |  差值  |    备注    |\n");   //打印结果并输出关键路径
	   for(j=0;j<projectnumber;j++)
	   {
		   p=Graphicmap[j].link;
		   while(p)
		   {
			   k=p->adjvex ;
			   e[++i]=ve[j];
			   l[i]=vl[k]-p->dut;
			   printf("|  %4d  |  %4d  |       %4d       |       %4d       |  %4d  |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]);
			   if(l[i]==e[i]) printf("  关键活动  |");
			   else printf("            |");
			   printf("\n");
			   p=p->next ;
		   }
	   }*/

	   printf("\n此次工程图的关键路径为: ");   //关键路径输出
	   for(j=0;j<projectnumber;j++)
	   {
		   p=Graphicmap[j].link;
		   while(p)
		   {
			   k=p->adjvex ;
			   e[++i]=ve[j];
			   l[i]=vl[k]-p->dut;
			   if(l[i]==e[i]) printf("%d->",Graphicmap[j].projectname +1);
			   p=p->next;
		   }
	   }
       printf("%d",Graphicmap[k].projectname +1);
	   printf("\n");
	   return 1;
}
void caozuobufen()     //操作部分
{
	   int projectnumber,activenumber,totaltime=0;
	   //system("cls");
	   printf("请输入这个工程图的节点数:");
	   scanf("%d",&projectnumber);
	   printf("请输入这个工程图的边数:");
	   scanf("%d",&activenumber);
	   vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));   //分配空间并赋给G
	   CreateGraphic(Graphicmap,projectnumber,activenumber);
	   SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);
	   printf("整个工程所用的最短时间为: %d个单位时间\n",totaltime);
	   system("pause");
}
int main()
{
       char ch;
	   for(;;)     //菜单，可循环操作
	   {
		   do 
		   {
			   system("cls");
			   printf("                         ****************************                           ");
			   printf("                         *这是一个求关键路径的小程序*                           ");
			   printf("                         *                          *                           ");
			   printf("                         *       S: 进入程序        *                           ");
			   printf("                         *       E: 退出程序        *                           ");
			   printf("                         ****************************                           ");
			   printf("\n");
			   printf("请输入选择并回车:");
			   scanf("%c",&ch);
			   ch=toupper(ch);      //如果是小写的转换成大写字母
		   }while(ch!='S'&&ch!='E');
		   switch(ch)
		   {
		   case'S':
			   caozuobufen();      //跳转到操作部分
			   break;
		   case'E': 
			   return 1;
		   }
	   }
}