guanjianlujing.txt

基于VISAUL C++开发的 关键路径求解 属于数据结构

关键路径
 
 
 #include<iostream.h>
#include<stdlib.h>
const int N=9;
const int SEED=33333;
int A[N][N];
int indgree[N],ve[N],vl[N];//ve 最早时间
struct vnode
{
 int nextv;
 int value;
 vnode *next;
};
struct array
{
 vnode *firstv;
}G[N];
struct queue
{
 int front;
 int rear;
 int vv[N];
}qh;
struct stack
{
 int top;
 int vv[N];
}qs;
void Init_queue()
{
 qh.front=qh.rear=-1;
}
void Enqueue(int i)
{
 qh.vv[++qh.rear]=i;
}
int Empty_queue()
{
 return (qh.rear==qh.front);
}
int  Top_off()
{
 if(Empty_queue())
  return 0;
 return qh.vv[++qh.front];
}
void Init_stack()
{
 qs.top=-1;
}
void Enstack(int i)
{
 qs.top++;
 qs.vv[qs.top]=i;
}
int Empty_stack()
{
 return qs.top==-1;
}
int Top_off_stack()
{
 if(Empty_stack())
  return 0;
 return qs.vv[qs.top--];
}
void init()
{
 A[0][1]=6;
 A[0][2]=4;
 A[0][3]=5;
 A[1][4]=1;
 A[2][4]=1;
 A[3][5]=2;
 A[4][6]=9;
 A[4][7]=7;
 A[5][7]=4;
 A[6][8]=2;
 A[7][8]=3;
}
void Init()
{
 init();
 int i,j;
 srand(SEED);
  for(i=0;i<N;i++)
  {
   G[i].firstv=0;
  }
  for(i=0;i<N;i++)
   for(j=0;j<N;j++)
   {
    if(A[i][j]!=0)
    {
     vnode *p=G[i].firstv;
     vnode *New=new vnode;
     New->next=0;
     New->nextv=j;
     New->value=A[i][j];
     if(p==0)
      G[i].firstv=New;
     else
     {
      New->next=p;
      G[i].firstv=New;
     }
    }
   }
   for(i=0;i<N;i++)
   {
    indgree[i]=0;
    ve[i]=0;
   }
    
}
void Get_in_degree()
{
 int i=0;
 while(i<N)
 {
  vnode *p=G[i].firstv;
  
  while(p)
  {
   indgree[p->nextv]++;
   p=p->next;
  }
  i++;
 }
}
void shortroad()
{
 int i;
 int u,v;
 int count=0;
 vnode *p;
 for(i=0;i<N;i++)
 {
  if(indgree[i]==0)
  {
   Enqueue(i);
   count++;
  }
 }
 while(!Empty_queue())
 {
  u=Top_off();
  Enstack(u);
  p=G[u].firstv;
  while(p)
  {
   v=p->nextv;
   indgree[v]--;
    if(indgree[v]==0)
    {
     Enqueue(v);
     count++;
    }
    if((ve[u]+p->value)>ve[v])
     ve[v]=ve[u]+p->value; 
    p=p->next;
  }
 }
 for(i=0;i<N;i++)
  vl[i]=ve[i];
 while(!Empty_stack())
 {
  u=Top_off_stack();
   i=0;
  while(i<N)
  {
   p=G[i].firstv;
   while(p)
   {
    if(p->nextv==u)
    {
     v=i;
     if((ve[u]-p->value)>vl[v])
      vl[v]=ve[u]-p->value;
    }
    p=p->next;
   }
   i++;
  }
 
 }
 for(i=0;i<N;i++)
  cout<<i<<'\t';
 cout<<endl;
 cout<<" the early time is : \n";
 for(i=0;i<N;i++)
  cout<<ve[i]<<'\t';
 cout<<endl;
 cout<<" the later time is : \n";
 for(i=0;i<N;i++)
  cout<<vl[i]<<'\t';
 cout<<endl;
 
 cout<<" the key road is : \n\t";
 for(i=0;i<N;i++) 
 if(vl[i]==ve[i])
 {
  if(i==N-1)
   cout<<i;
  else
  cout<<i<<"--------->";
 }
  cout<<endl;

}
void Print_A()
{
 int i;
 int j;
 for(i=0;i<N;i++)
 {
  for(j=0;j<N;j++)
  {
   cout<<A[i][j]<<"   ";
  }
  cout<<endl;
 }
}
void Print_G()
{
 int i;
 vnode *p;
 i=0;
 while(i<N)
 {
  p=G[i].firstv;
  cout<<i<<"  : ";
  while(p)
  {
   cout<<p->nextv<<"  ";
   p=p->next;
  }
  cout<<endl;
 i++;
 }
}
 
void main()
{
 Init_queue();
 Init_stack();
 Init();
 int i;
 cout<<" the Matrix is :\n";
 Print_A();
 cout<<" the Graph is  :\n";
 Print_G();
 Get_in_degree();
 shortroad();
}