第三题.cpp

自己设计一个项目

//3．自己设计一个项目，排出AOE网络，并将数据输入计算机，用程序进行分析。

#include<iostream.h>
#include<stdlib.h>
#define MAX 20

class Stack                                  //队列类
{  public:
	int stack[200];
	int top;int base;
	void InitStack();
	void push(int & x);
	void pop(int & x);
};
void Stack::InitStack()
{
	top=0;base=0;
}
void Stack::push(int & x)
{
   top++;stack[top]=x;
}
void Stack::pop(int & x)
{
	x=stack[top];top--;
} 

struct ArcNode
{   
	int adjvex;                          //该弧弧头的位置
	int imf;                             //权值
	ArcNode * nextarc;	
};

struct VNode
{   int indegree;
	char data;
	ArcNode * firstarc;
};

class Graph                                  //图类
{  public:
	VNode AdjList[MAX];
	int vexnum,arcnum;
	Graph();
	void Initiate();
	void Display();
	void Locate(int & pos,char & x);
	bool TopoOrder();
	void CriticalPath();
	
};

Graph::Graph()
{
	vexnum=0;arcnum=0;
	for(int i=0;i<MAX;i++)
	{AdjList[i].firstarc=NULL;AdjList[i].data=' ';}
}

void Graph::Locate(int & pos,char & x)
{ 
    for(int a=1;a<=vexnum;a++)
	{
		if(AdjList[a].data==x)
		{pos=a;return;}
	}
	cout<<"图中没有含有这个值的定点!"<<endl;abort();
}

void Graph::Initiate()
{  
	cout<<"请输入有多少个顶点：";cin>>vexnum;
	for(int i=1;i<=vexnum;i++)
	{
		cout<<"请输入第"<<i<<"个顶点的值："; cin>>AdjList[i].data;AdjList[i].indegree=0 ;
	}
	cout<<"请输入有多少条弧：  ";cin>>arcnum;
	for(i=1;i<=arcnum;i++)
	{   char head,tail;int imformation;
		cout<<"请输入第"<<i<<"条弧的弧头/弧尾/权值：";
		cin>>head>>tail>>imformation;
		int hpos,tpos;Locate(hpos,head);Locate(tpos,tail);
		ArcNode * temp =new ArcNode;temp->adjvex=tpos;temp->imf=imformation;
		temp->nextarc=AdjList[hpos].firstarc;
		AdjList[hpos].firstarc=temp;
		AdjList[tpos].indegree++;
	}
}

void Graph::Display()
{       cout<<"位置  顶点信息  邻接点的位置"<<endl;
    for(int i=1;i<=vexnum;i++)       
	{	cout<<"   "<<i<<"      "<<AdjList[i].data<<" ---->";
		for(ArcNode * p=AdjList[i].firstarc;p!=NULL;p=p->nextarc)
			cout<<p->adjvex<<"---->";
		cout<<"NULL"<<endl;
	}
}

Stack T;                   //拓扑序列顶点栈T
Stack S;                   //零入度顶点栈S
int ve[MAX];
int vl[MAX];
bool Graph::TopoOrder( )
{  
  T.InitStack();
  S.InitStack();
  int count=0;
  for(int a=1;a<=vexnum;a++) 
  {ve[a]=0;                         //初始化事件最早发生时间数组
   if(AdjList[a].indegree==0)
	   S.push(a);                   //零入度顶点入栈
  }
   while(S.top!=S.base)
  {   int j;
	  S.pop(j);T.push(j);++count;  //cout<<"hello "<<j<<endl; //j号顶点入栈并计数
	  for(ArcNode * p=AdjList[j].firstarc;p!=NULL;p=p->nextarc)
	  {
		  AdjList[p->adjvex].indegree--;        //对j号顶点的每个邻接点的入度减1
		  if(AdjList[p->adjvex].indegree==0)
			  S.push(p->adjvex);                //若入度减为0，则入栈
		  if((ve[j]+p->imf)>ve[p->adjvex]) 
			  ve[p->adjvex]=ve[j]+p->imf;
	  }
  }
  if(count<vexnum) return false;
  else return true;  
}

void Graph::CriticalPath()
{
	if(!TopoOrder()) {cout<<"该有向网有回路!"<<endl;abort();}
	for(int a=1;a<=vexnum;a++) vl[a]=ve[a];      //初始化事件最迟发生时间数组 
	while (T.base!=T.top)                        //按拓扑逆序求各顶点的vl值
	{   int j;   T.pop(j);
		for(ArcNode * p=AdjList[j].firstarc;p!=NULL;p=p->nextarc)
		{
			int k=p->adjvex; int dut=p->imf;
			if(vl[k]-dut<vl[j])   vl[j]=vl[k]-dut;
		}
	}
	for(int i=1;i<=vexnum;i++)             //求ee el 和关键活动
		for(ArcNode * p=AdjList[i].firstarc;p!=NULL;p=p->nextarc)
		{
				int k=p->adjvex;int dut=p->imf;
				int ee=ve[i]; int el=vl[k]-dut;
				char tag=' '; if(ee==el) tag='*';
				cout<<"弧头:"<<i<<"  弧尾:"<<k<<"    持续:"<<dut<<"  最早:"<<ee<<"  最迟:"<<el<<"  关键:"<<tag<<endl; //输出关键活动
		}	
	
}

void main()
{
	cout<<"---开始输入你的AOE网络"<<endl;
	Graph graph;	
	graph.Initiate();
	graph.Display();
   cout<<"分析AOE网如下，关键活动带*号:"<<endl;
   graph.CriticalPath();//	for(int i =1;i<=graph.vexnum;i++)cout<<ve[i]<<" ";
   for( int i =1;i<=graph.vexnum;i++)cout<<ve[i]<<" ";   
   for(int j =1;j<=graph.vexnum;j++)cout<<vl[j]<<" ";
}