ch7_critical_path.c

本人讲授数据结构课程时的所写的示例程序

#include <stdio.h>
#include <malloc.h>
#define M 20
#define MAX 100
typedef struct node
{   int vex;
    int dur;
  int act;
    struct node *next;
}JD;
typedef struct tnode
{   int vexdata;
    int in;
    struct node *link;
}TD;


int crt_linklist(TD g[])
{   int n,e,i,j,k,dur,m=1;
    JD *p;
    printf("Input and the number of node,arc:");
    scanf("%d,%d",&n,&e);
    for(i=1;i<=n;i++)
    {  g[i].vexdata=i;
       g[i].in=0;
       g[i].link=NULL;
    }
    for(k=1;k<=e;k++)
    {   printf("i,j,dur:");
  scanf("%d,%d,%d",&i,&j,&dur);
  p=(JD *)malloc(sizeof(JD));
  p->vex=j;
  p->dur=dur;
  p->act=m;
  m++;
  p->next=g[i].link;
  g[i].link=p;
    }
    return(n);
}

void cal_in(TD g[],int n)
{  int i,k;
   JD *p;
   for(i=1;i<=n;i++)
   {  p=g[i].link;
      while(p!=NULL)
      {  k=p->vex;
   g[k].in++;
   p=p->next;
      }
   }
}


int toporder(TD g[],int n,int ve[],int top2[],int *t2)
{  int top1[M];
   int m,k,j,top;
   JD *p;
   top=0; m=0;
   for(j=1;j<=n;j++)
      ve[j]=0;
   for(j=1;j<=n;j++)
     if(g[j].in==0)
     {  top1[top]=j;
  top++;
     }
   while(top>0)
   {  j=top1[--top];
      top2[*t2]=j;
      (*t2)++;
      m++;
      p=g[j].link;
      while(p!=NULL)
      {  k=p->vex;
   g[k].in--;
   if(g[k].in==0)
      top1[top++]=k;
   if(ve[j]+p->dur>ve[k])
      ve[k]=ve[j]+p->dur;
   p=p->next;
      }
   }
   if(m<n)  return(0);
   else     return(1);
}

void critical_path(TD g[],int n)
{   int i,t2=0,j,k,ee,el;
    char tag;
    JD *p;
    int ve[M],vl[M],top2[M];
    i=toporder(g,n,ve,top2,&t2);
    if(!i)
       printf("Has a cycle!");
    else
    {  for(i=1;i<=n;i++)
    vl[i]=MAX;
       vl[n]=ve[n];
       while(t2>0)
       {  j=top2[--t2];
    p=g[j].link;
    while(p!=NULL)
    {  k=p->vex;
       if(vl[k]-p->dur<vl[j])
      vl[j]=vl[k]-p->dur;
       p=p->next;
    }
       }
       for(j=1;j<=n;j++)
       {  p=g[j].link;
    while(p!=NULL)
    {  k=p->vex;
       ee=ve[j];
       el=vl[k]-p->dur;
       if(ee==el)
     tag='*';
       else
     tag=' ';
       printf("(%d,%d),w=%d,act=%d,ee=%d,el=%d,%c\n",j,k,p->dur,p->act,ee,el,tag);
       p=p->next;
    }
       }
    }
}

void main()
{  int n;
   TD g[M];
   n=crt_linklist(g);
   cal_in(g,n);
   critical_path(g,n);
   getch();
}