关键路径.txt

使用C++编写的数据结构中的图的关键路径。

#include<iostream>
using namespace std;

typedef int Status;
typedef int InfoType;
typedef int VertexType;
typedef int SElemType;
const int MAX_VERTEX_NUM=10;
const int OK=1;
const int STACK_INIT_SIZE=10;
const int OVERFLOW=-2;
const int STACKINCREMENT=5;
const int ERROR=0;
int ArcArray[16]={1,2,1,3,2,4,2,5,3,4,3,6,4,6,5,6};
int InfoArray[8]={3,2,2,3,4,3,2,1};
int *ve=NULL;
int *vl=NULL;
unsigned short InfoPlace=0;



typedef struct ArcNode									//表结点
{
	int				adjvex;								//该弧所指向顶点的位置
	struct ArcNode	*nextarc;							//指向下一条弧的位置
	InfoType		info;								//该弧相关信息的指针
}ArcNode;
typedef struct VNode								
{
	VertexType		data;								//顶点信息
	ArcNode			*firstarc;								
}VNode,AdjList[MAX_VERTEX_NUM];							//指向第一条依附该顶点的弧的指针
typedef struct 
{
	AdjList vertices;									 
	int		vexnum,arcnum;								//图的当前顶点　数各弧数
	int		kind;										//图的种类标志
}ALGraph; 
typedef class
{
public:
	SElemType *base;
	SElemType *top;											//指向待插入元素的位置
	int Stacksize;
}SqStack;

Status CreateALGraph(ALGraph &G);
void FindInDegree(ALGraph);
Status FindInDegree(ALGraph G,int indegree[]);
int Locate(int i);
Status InitStack(SqStack &S);
Status Pop(SqStack &S,SElemType &e);
Status Push(SqStack &S,SElemType e);
Status StackEmpty(SqStack S);
Status CriticalPath(ALGraph G);

void main()
{
	cout<<"\t\t\t*******************************"<<endl;
	cout<<"\t\t\t　　　  　图--关键路径　　　　　"<<endl;
	cout<<"\t\t\t    海川工作室出品(2007.6.27)　"<<endl;
	cout<<"\t\t\t*******************************"<<endl;
	ALGraph G;
	CreateALGraph(G);
	CriticalPath(G);

	
	
/*	for(;;)
	{
		cout<<"(1).创建邻接表。(书186页)"<<endl;
		cout<<"请输入你的选择:"<<endl;
		unsigned short choose;
		cin>>choose;
	
		
	}*/

}
/**************************/
Status TopologicalOrder(ALGraph G,SqStack &T)
{
	//有向图G采用邻接表存储结构　，求各顶点事件的最早发生时间ve(全局变量)。
	//T为拓扑序列顶点栈，S为零入度顶点栈。
	//若G无回路，则用栈T返回G的一个看不顺眼扑序列，且函数值为OK，否则为ERROR
	//算法7.13
	unsigned short count=0;
	int *indegree=new int[G.vexnum];
	FindInDegree(G,indegree);
	InitStack(T);
	count=0;
	ve=new int[G.vexnum];
	for(unsigned short place=0;place<G.vexnum;place++)
	{
		ve[place]=0;
	}
	
	SqStack S;
	S.base=NULL;
	S.top=NULL;
	S.Stacksize=0;
	int j=0;
	for(int i=0;i<G.vexnum;i++)
	{
		if(!indegree[i])
		{
			Push(S,i);
		}
	}
	count=0;
	while (!StackEmpty(S))
	{
		int k=0;
		for(ArcNode *p=G.vertices[i].firstarc;p;p=p->nextarc)
		{
			
			k=p->adjvex;
			if(!(--indegree[k]))
			{
				Push(S,k);
			}
		
		}
	}
	count++;
	while(!StackEmpty(S))
	{
		Pop(S,j);
		Push(T,j);
		count++;
		for(ArcNode *p=G.vertices[j].firstarc;p;p=p->nextarc)
		{
			int k=p->adjvex;
			if(--indegree[k]==0)
			{
				Push(S,k);
			}
			if(ve[j]+(p->info)>ve[k])
			{
				ve[k]=ve[j]+(p->info);
			}
		}
	}
	if(count<G.vexnum)
	{
		return ERROR;
	}
	else
	{
		return OK;
	}
}
/****************************/
Status CreateALGraph(ALGraph &G)
{
	//创建一个书上P183页的图
	cout<<"创建书上P183页的图."<<endl;
	cout<<"创建的图一共有9个结点."<<endl;
	G.vexnum=6;
	cout<<"创建的图一共有11调弧."<<endl;
	G.arcnum=8;
	for(unsigned short place=0;place<G.vexnum;place++)
	{
		G.vertices[place].data=place+1;
		G.vertices[place].firstarc=NULL;
	}
	place=0;
	for(unsigned short counter=1;counter<=G.arcnum;counter++)
	{
	
		cout<<"第"<<counter<<"条弧:";
		int head=Locate(ArcArray[place]);
		cout<<"尾结点是"<<ArcArray[place];
		place++;
		cout<<"头结点是"<<ArcArray[place]<<endl;
		int rail=Locate(ArcArray[place]);
		place++;
		ArcNode *pNode=new ArcNode;
		pNode->adjvex=rail;
		pNode->info=InfoArray[InfoPlace];
		InfoPlace++;
		pNode->nextarc=G.vertices[head].firstarc;
		G.vertices[head].firstarc=pNode;
}
	return OK;
}
int Locate(int i)
{
	return i-1;
}
/***************************/
Status CriticalPath(ALGraph G)
{
	//G为有向网，输出G的各项关键活动。
	//算法7.14
	vl=new int[G.vexnum];
	SqStack T;
	if(!TopologicalOrder(G,T))
	{
		return ERROR;
	}
	for(unsigned short place=0;place<G.vexnum;place++)
	{
		vl[place]=ve[G.vexnum];
	}
	while(!StackEmpty(T))
	{
		int j=0,k=0,dut=0;
		Pop(T,j);
		for(ArcNode *p=G.vertices[j].firstarc;p;p=p->nextarc)
		{
			k=p->adjvex;
			dut=p->info;
			if(vl[k]-dut<vl[j])
			{
				vl[j]=vl[k]-dut;
			}
		}
		for(j=0;j<G.vexnum;j++)
		{
			int ee,el;
			char tag;
			for(p=G.vertices[j].firstarc;p;p=p->nextarc)
			{
				k=p->adjvex;
				dut=p->info;
				ee=ve[j];
				el=vl[k]-dut;
				tag=(ee==el) ? '*' : ' ';
				cout<<j<<k<<dut<<ee<<el<<tag<<endl;
			
			}
		}
	}
	return OK;
}
/****************/
Status FindInDegree(ALGraph G,int indegree[])
{
	for(unsigned short counter=1;counter<=G.vexnum;counter++)
	{
		unsigned short sum=0;
		unsigned short place=0;
		ArcNode *p;
		for(unsigned short i=0;i<G.vexnum;i++)
		{
			
			for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc)
			{
				if(p->adjvex==Locate(counter))
				{
					sum++;
				}
			}
		}
		indegree[Locate(counter)]=sum;
	}
	return OK;
}
/*********************************创建一个栈**********************************************/
Status InitStack(SqStack &S)
{
	//构造一个空栈
	S.base=new SElemType[STACK_INIT_SIZE];					//初始化一个大小100的栈
	if(!S.base)
	{
		exit(OVERFLOW);
	}
	S.top=S.base;
	S.Stacksize=STACK_INIT_SIZE;
	return OK;
}
//********************************压入一个元素******************************************/
Status Push(SqStack &S,SElemType e)
{
	//插入元素e为新栈顶元素
	if(S.top-S.base>=S.Stacksize)							//如果栈满
	{	
		SElemType *exchange=new SElemType[S.Stacksize+STACKINCREMENT];
		for(unsigned short counter=0;counter<S.top-S.base;counter++)
		{
			exchange[counter]=S.base[counter];				
		}
		delete []S.base;
		S.base=exchange;							
		if(!S.base)
		{
			exit(OVERFLOW);
		}
		S.top=S.base+S.Stacksize;							//S.top为待插入元素的位置	
		S.Stacksize=S.Stacksize+STACKINCREMENT;
	}
	*S.top=e;												//S.top始终指向带插入元素的位置
	S.top++;
	return OK;
}
/**********************************弹出一个元素***************************************/
Status Pop(SqStack &S,SElemType &e)
{
	//若栈不空,则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
	if(S.top==S.base)
	{
		cout<<"弹出失败，这个栈什么都没有."<<endl<<endl;
		return ERROR;
	}
	S.top--;
	e=*S.top;
	return OK;
}
/*******************************判断一个栈空不空******************************************/
Status StackEmpty(SqStack S)
{

	if(S.base==S.top)
	{
		return OK;
	}
	else
	{
		return ERROR;
	}
}