guanjianlujing.cpp

自己编写的关键路径

#include<stdlib.h>
#include<conio.h>
#include<string.h>
#include<stdio.h>
#include <iostream.h>

typedef struct ArcCell{
	int adj;/*顶点关系类型，用1表示相邻，0表示不相邻*/
}ArcCell,**AdjMatrix;/*邻接矩阵*/

typedef struct type{ 
	char data[3];/*顶点值*/
	int info;/*弧的长度*/
	struct type *next;/*顶点的下一个指针*/
}VertexType;

typedef struct{
	VertexType *vexs;/*顶点向量*/
	AdjMatrix arcs;/*邻接矩阵*/
	int vexnum,arcnum;/*图的顶点数和边数*/
}MGraph;

/* ****************** */
typedef int Status;
#define STACK_INIT_SIZE 50
typedef int ElemType;
typedef struct STACK /*定义栈类型*/
{
  ElemType *base;
  ElemType *top;
  int stacksize;
  int length;
}SqStack,*Stack;

void InitStack(Stack *S) /*初始化栈*/
{
  *S=(SqStack *)malloc(sizeof(SqStack));
  (*S)->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
  if(!(*S)->base)exit(-1);
  (*S)->top=(*S)->base;
  (*S)->stacksize=STACK_INIT_SIZE;
  (*S)->length=0;
}


Status DestroyStack(Stack *S) /* 销毁栈*/
{
	free((*S)->base);
	free((*S));
	return 1;
}

Status StackEmpty(SqStack S) /*判断栈空否*/
{
	if(S.top==S.base)
		return 1;
	else
		return 0;
}
void Push(Stack *S,ElemType e)  /*把数据压入栈*/
{
  if((*S)->top - (*S)->base>=(*S)->stacksize)
   {
	  (*S)->base=(ElemType *) realloc((*S)->base,
     ((*S)->stacksize + 10) * sizeof(ElemType));
	  if(!(*S)->base)
		  exit(-1);
     (*S)->top=(*S)->base+(*S)->stacksize;
     (*S)->stacksize +=10;
   }
  *((*S)->top++)=e;
  ++(*S)->length;
}

Status Pop(Stack *S,ElemType *e)/*删除栈顶元素*/
{
  if((*S)->top==(*S)->base) return 0;
  *e=*((*S)->top-1);
  --(*S)->length;
  (*S)->top--;
  return 1;
}


/* ******************** */
void InitGraph(MGraph *G)/*初始图*/
{ 
	int i,nu,mu;
	printf("\n输入顶点的个数和（边）弧的个数：");
	scanf("%d%d",&nu,&mu);
	G->arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *));
	for(i=0;i<nu;i++)/*分配邻接矩阵空间*/
		G->arcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell));
	G->vexs=(VertexType *)malloc(nu*sizeof(VertexType));/*分配顶点空间*/
	G->vexnum=nu;G->arcnum=mu;/*图的顶点数和边数*/
}


void DestroyGraph(MGraph *G)/* 销毁图*/
{
	int i;
	free(G->vexs);
	for(i=0;i<G->vexnum;i++)
		free(G->arcs[i]);
}

void InsertGraph(MGraph *G,int i,VertexType e)
{ 
	if(i<0||i>G->vexnum)
		return;
	G->vexs[i].next=e.next;
	G->vexs[i].info=e.info;
	strcpy(G->vexs[i].data,e.data);
}

int Locate(MGraph G,VertexType v1)/*确定v1在图顶点中的位置*/
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(strcmp(v1.data,G.vexs[i].data)==0)
			return i;
		return -1;
}


void CreateUND(MGraph *G)/*采用数组（邻接矩阵）和邻接表表示无向图*/
{
	int i,j,k,*p,d,w;
	VertexType v1,v2,*q2,*q;
	p=(int *)malloc(G->vexnum*sizeof(int)); 
	for(i=0;i<G->vexnum;i++) 
		p[i]=0;
	for(i=0;i<G->vexnum;++i)/*初始邻接表*/
	{ 
		for(j=0;j<G->vexnum;++j)
			G->arcs[i][j].adj=0;
	}
	printf("\n");
	printf("按顺序输入顶点(方向)和它们的间长度再顶点：如 'v1 3 v2' : \n");
	for(k=0;k<G->arcnum;++k)
	{
		printf("输入第 %d 条弧: \n",k+1);
		d=0;
		scanf("%s%d%s",v1.data,&w,v2.data);/*输入相邻的两个点值*/
		i=Locate(*G,v1);j=Locate(*G,v2);/*用i 和j来确定它们的位置*/
		G->arcs[i][j].adj=1;
		q2=(VertexType *)malloc(sizeof(VertexType));/*分配一个空间*/
		strcpy(q2->data,G->vexs[j].data);q2->info=w;
		q2->next=NULL;
		if(p[i]==0) 
		{
			G->vexs[i].next=q2;p[i]++;
		}
		else 
		{
			q=&(G->vexs[i]);
			while(d!=p[i])
			{
				d++;q=q->next;
			}
			p[i]++;
			q->next=q2;/*接在最后*/
		}   
	}
 free(p);
}


void FindInDegree(MGraph G,int *indegree)/*对各顶点求入度，邻接矩阵的列*/
{
	int i,j;
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
			if(G.arcs[j][i].adj==1)
				indegree[i]++;
}


int *ve,*vl;/*最早发生时间和最迟发生时间数组，全局的*/
int TopologicalOrder(MGraph G,Stack *T)/*有向图采用邻接表存储结构，
									   欢迎光临学网,收藏本篇文章 [1] [2] [3] [4]无回路返回1*/
{
	Stack S;
	int i,k,count,*indegree;
	VertexType *p;
	indegree=(int *)malloc(G.vexnum*sizeof(int));/*度数组空间*/
	ve=(int *)malloc(G.vexnum*sizeof(int));/*最早发生时间的数组空间*/
	for(i=0;i<G.vexnum;i++)
		indegree[i]=0;/*初始化*/
	for(i=0;i<G.vexnum;i++)
		ve[i]=0;/*初始化*/
	FindInDegree(G,indegree);/*求各点入度*/
	InitStack(&S);/*初始化栈*/
	InitStack(T);
	for(i=0;i<G.vexnum;++i)
		if(!indegree[i]) 
			Push(&S,i);/*入度为0进栈*/
		count=0;/*对输出顶点计数*/
		while(!StackEmpty(*S))
		{
			Pop(&S,&i);/*拿出入度为0 的*/
			Push(T,i);/*i号顶点入T栈*/
			++count;/*计数*/
			p=G.vexs[i].next;
			while(p)
			{
				k=Locate(G,*p);
				if(!(--indegree[k])) Push(&S,k);/*减一后为0就入栈*/
				if(ve[i]+p->info>ve[k]) ve[k]=ve[i]+p->info;/*在它的所有邻点中找出能使最大*/
				p=p->next;
			}
		}
		DestroyStack(&S);
		free(indegree);
		if(count<G.vexnum)
			return 0;/*有向图有回路*/
		else 
			return 1;
}


int CriticalPath(MGraph G)/*G为有向网，输出G的各项关键活动*/
{
	Stack T;
	int j,k,dut,e1,e2;
	char tag;
	VertexType *p;
	if(!TopologicalOrder(G,&T))
		return 0;/*有回路就不做*/
	vl=(int *)malloc(G.vexnum*sizeof(int));/*最迟发生时间数组空间*/
	for(j=0;j<G.vexnum;j++)/*初始化事件的最迟发生时间*/
		vl[j]=ve[j];
	while(!StackEmpty(*T))/*按拓扑逆序求各事件的 vl 值*/
	{ 
		Pop(&T,&j);/*从最后一个开始*/
		p=G.vexs[j].next;
		while(p)
		{
			k=Locate(G,*p);/*邻点的位置*/
			dut=p->info;/*两点间的长度*/
			if(vl[k]-dut>vl[j]) 
				vl[j]=vl[k]-dut;
			p=p->next;
		}
	}
	for(j=0;j<G.vexnum;j++)
		printf("事件 %s 的最早和最迟发生时间分别为 *%d* 和 *%d*\n",G.vexs[j].data,ve[j],vl[j]);
	printf("关键活动为：\n");
	for(j=0;j<G.vexnum;j++)/*求关键活动和它的值，顶点是事件，弧是活动*/
	{
		p=G.vexs[j].next;/*每个事件要依赖它的邻点才可知是否最早=最迟*/
		while(p)
		{
			k=Locate(G,*p);/*邻点的位置*/
			dut=p->info;/*弧长*/
			e1=ve[j];e2=vl[k]-dut;/*如果最早开始时间=最迟开始时间，最迟为邻点减去弧长*/
			if(e1==e2) 
				tag='*';
			else 
				tag=' ';
			if(tag=='*')
				printf("*%s* 到 *%s* 长度为*%d* 发生时间为 *%d*\n",G.vexs[j].data,G.vexs[k].data,dut,e2); 
			p=p->next;
		}
	}
	free(vl);free(ve);DestroyStack(&T);
	return 1;
}


void main()
{
	MGraph G;
	VertexType e,*p;
	int i;
	InitGraph(&G);
	printf("顶点值： \n");
	for(i=0;i<G.vexnum;++i)/*给图顶点向量付值*/
	{
		scanf("%s",e.data);
		e.next=NULL;
		e.info=9999;
		InsertGraph(&G,i,e);
	}
	CreateUND(&G);/*构造图结构*/
	printf("邻接表为：\n");
	for(i=0;i<G.vexnum;i++)/*输出邻接表*/
	{
		printf(" *%s* ",G.vexs[i].data);
		p=G.vexs[i].next;
		while(p)
		{
			printf(" *%s* ",p->data);
			p=p->next;
		}
		printf("\n");
	}
	getch();/*暂停*/
	CriticalPath(G);/*关键活动函数*/
	DestroyGraph(&G);/*销毁图*/
	getch();
}