/*This program calcuate the critical rote when you input the dat in a file */#include <stdio.h>#include <string.h>#include <stdlib.h>#include "stack.c"       /* include stack */#define LETTER  'A'    /* The first letter */#define Max 50         /* at most 50 vex */#define BUFF 30#define DAT_TFILE "topo3.dat"   /*輸入數據文件"topo＊.dat"*/typedef struct Arcnode{       char adjvex;         struct Arcnode *nextarc;}Arcnode;typedef struct {       char vex;           /*data's tag*/       int time;                  Arcnode *firstarc;}Vertexnode;typedef struct {       Vertexnode vertex[Max];       int vexnum;}Adjlist;void Creatadjlist(Adjlist *G){     FILE *dat;     dat = fopen(DAT_TFILE,"r");     Arcnode *newarc;     int i;     int flag;     char a[BUFF];     char yn[BUFF];          fscanf (dat,"%d",&G->vexnum);     for(i=0;i<G->vexnum;i++){        flag=1;        fscanf(dat,"%s", a);        G->vertex[i].vex=a[0];                        fscanf(dat,"%d",&G->vertex[i].time);        fscanf(dat,"%s",yn);        G->vertex[i].firstarc = (Arcnode *)malloc(sizeof(Arcnode));   /*Because firstarc has nextarc in it so it has to allocate memory*/                if (strcmp(yn,"no")==0)        G->vertex[i].firstarc = NULL;        else{             /*else 1*/        fscanf(dat,"%s",a);        G->vertex[i].firstarc->adjvex = a[0];        G->vertex[i].firstarc->nextarc=NULL;         while(flag){        fscanf(dat,"%s",yn);              if (strcmp(yn,"no")==0)                          flag=0;                     else{               fscanf(dat,"%s",a);               newarc = (Arcnode *)malloc(sizeof(Arcnode));              newarc->adjvex=a[0];              newarc->nextarc = G->vertex[i].firstarc->nextarc;              G->vertex[i].firstarc->nextarc= newarc;                                  }         }     /*while 1*/        }     /*else 1*/        }   /*for*/     fclose(dat);   }void Findid(Adjlist G, int indegree[Max]){      /* find every vex'indegree */    int i;    int k;    Arcnode *arc;    for(i=0; i<G.vexnum; i++)       indegree[i]=0;    for(i=0; i<G.vexnum; i++){           arc = G.vertex[i].firstarc;           while (arc != NULL){             k=arc->adjvex-LETTER;       /*A-65=0*/             indegree[k]++;                     arc = arc->nextarc;           }           }}void Toposort(Adjlist G,seqstack *T,int ve[Max]){     int i;     int m;     int count;     char vex[Max];     int k;     Arcnode *arc;     int indegree[Max];     seqstack S;     Initstack(&S);     Initstack(T);     Findid( G, indegree);     for(i=0; i<G.vexnum; i++){       if(!indegree[i])         Push(&S,G.vertex[i].vex);       ve[i]=0;                      /* init start time */     }     count=0;     while(S.top != -1){         Pop(&S,&vex[count]);     m = vex[count]-LETTER;      Push(T,vex[count]);     count++;     arc = G.vertex[m].firstarc;                 while( arc != NULL){                  k = arc->adjvex-LETTER;                        indegree[k]--;                         if(!indegree[k])                 Push(&S,arc->adjvex);                  if(ve[m]+G.vertex[m].time > ve[k])                 ve[k] = ve[m]+G.vertex[m].time;                         arc = arc->nextarc;            }       }   }void Criticalpath(Adjlist G){     seqstack T;     char tag;     int ei,li;     int i;     int m;     int k;     char x;     int ve[Max];     int vl[Max];     Arcnode *arc;     Toposort(G,&T,ve);     for(i=0; i<G.vexnum; i++){      vl[i]=ve[i];     }    while(T.top != -1){     Pop(&T,&x);     m = x-LETTER;                    arc = G.vertex[m].firstarc;        while( arc != NULL){          k = arc->adjvex-LETTER;                    if(vl[k]-G.vertex[m].time < vl[m])         vl[m] = vl[k]-G.vertex[m].time;                 arc = arc->nextarc;        }           }    for(i=0; i< G.vexnum; i++)    /*求ei,li 和關鍵活動*/     {        arc = G.vertex[i].firstarc;        while( arc != NULL){           k = arc->adjvex-LETTER;          ei=ve[i];li=vl[k]-G.vertex[i].time;          tag= (ei==li)?'*':' ';          printf ("%c,%c,%d,%d %c\n",G.vertex[i].vex,G.vertex[k].vex,ei,li,tag);          arc = arc->nextarc;        }     }}int main(){    Adjlist G;    int i;    char vex[Max];    int indegree[Max];    Creatadjlist(&G);    Criticalpath(G);}