sy7_7.c

数据结构实验与学习指导

#include "stdio.h"
#define VEX_NUM 30/*顶点个数*/
#define ARC_NUM 50/*弧的条数*/
typedef int Status;
typedef char Vextype[3];
typedef struct ArcNode
{int adjvex;
   int dut;  /*权值*/
   struct ArcNode *nextarc;
}ArcNode;   /*定义表结点*/
typedef struct VNode
{  Vextype data;
   int indegree;  /*入度*/
   ArcNode *firstarc;
}VNode;/*定义头结点*/
typedef VNode ALgraph[VEX_NUM];
typedef struct   /*事件信息*/
{
    int no;  /*事件对应的边的序号,也可以用数组下标来表示*/
    int ve;  /*事件最早发生时间*/
    int vl;   /*事件最迟发生时间*/
}eventnode;
typedef struct   /*活动信息*/
{
    int beginnode,endnode;  /*活动对应的两个顶点序号*/
    int w;  /*权值*/
    int e;  /*活动最早发生时间*/
    int l;   /*活动最迟发生时间*/
}actionnode;
int vexnum,arcnum;/*AOE中实际的顶点数和弧数*/
void creat_ALgraph(ALgraph G)   /*通过邻接表创建AOE网*/
{int i,j,k,w;
   ArcNode *p;
   printf("请输入顶点数和弧数:");    /*输入顶点数n和弧数m*/
   scanf("%d,%d",&vexnum,&arcnum);
   printf("请输入顶点信息:");  /*输入顶点信息，如V0,V1等,创建头结点数组*/
   for (i=0;i<vexnum;i++)
   {
    scanf("%s",&G[i].data);
    G[i].indegree=0;
    G[i].firstarc=NULL;
    }
   printf("请输入边和权值:i,j,w\n");/*输入边和权值，注意顶点下标从0开始*/
   for(k=0;k<arcnum;k++)
   { scanf("%d,%d,%d",&i,&j,&w);
     G[j].indegree++;        /*顶点j的入度加1*/
     p=(ArcNode*)malloc(sizeof(ArcNode));
     p->adjvex=j;
     p->dut=w;
     p->nextarc=G[i].firstarc;
     G[i].firstarc=p;
   }
}
void Print_ALgraph(ALgraph G)  /*输出AOE网*/
{int i;
   ArcNode *p;
   for(i=0;i<vexnum;i++)
    { printf("%s  %d",G[i].data,G[i].indegree);
     p=G[i].firstarc;
     while(p!=NULL)
       {printf("->(%d,%d)",p->adjvex,p->dut);
        p=p->nextarc;
        }
     printf("\n");
     }
}
Status CriticalPath(ALgraph G)/*求AOE网的关键活动*/
{  int i,j,k,count;
   int tpord[VEX_NUM+1];   /*队列*/
   eventnode vexel[VEX_NUM];   /*事件数组*/
   actionnode arcel[ARC_NUM];    /*活动数组*/
   int front=-1,rear=-1;
   ArcNode *p;
   for(i=0;i<vexnum;i++)/*对事件进行初始化*/
   {
     vexel[i].no=i;
     vexel[i].ve=0;
   }
   for(i=0;i<vexnum;i++)   /*对活动进行初始化*/
   {
     p=G[i].firstarc;
     while(p!=NULL)
     { k=p->adjvex;
       arcel[j].w=p->dut;
       arcel[j].beginnode=i;
       arcel[j].endnode=k;
       j++;
       p=p->nextarc;
     }
   }
   for(i=0;i<vexnum;i++)
     if(G[i].indegree==0) tpord[++rear]=i; /*入度为0的顶点入队*/
       count=0;/*对输出顶点计数*/
   while(front!=rear)
    { front++;j=tpord[front];   /*出队*/
     count++;
     p=G[j].firstarc;
     while(p!=NULL)
      { k=p->adjvex;
        G[k].indegree--;   /*入度减1*/
        if(vexel[j].ve+p->dut>vexel[k].ve)  /*求顶点Vk的最早发生时间*/
         vexel[k].ve=vexel[j].ve+p->dut;
        if(G[k].indegree==0)
         tpord[++rear]=k;
        p=p->nextarc;
      }
     }
    if(count<vexnum) return  0;  /*AOE中存在回路*/
    for(i=0;i<vexnum;i++)
      vexel[i].vl=vexel[vexnum-1].ve;
    for(i=vexnum-1;i>=0;i--)  /*按逆序计算每个顶点的最迟发生时间Vl*/
     { j=tpord[i];
       p=G[j].firstarc;
       while(p!=NULL)
        { k=p->adjvex;
         if(vexel[k].vl-p->dut<vexel[j].vl)
           vexel[j].vl=vexel[k].vl-p->dut;
         p=p->nextarc;
       }
     }
    i=0;
    for(j=0;j<vexnum;j++)
     { p=G[j].firstarc;
      while(p!=NULL)                /*求每个活动的最早发生时间和最迟发生时间*/
       { k=p->adjvex;
        arcel[i].e=vexel[j].ve;
        arcel[i].l=vexel[k].vl-p->dut;
        if(arcel[i].l==arcel[i].e)  /*关键活动*/        
printf("\n-><%s,%s>:%d",G[arcel[i].beginnode].data,G[arcel[i].endnode].data, arcel[i].w);   /*输出关键路径*/
        p=p->nextarc;
        i++;
        }
      }
return 1;
}
void main()
{  ArcNode *p;
   ALgraph AG;
   int tag;
   creat_ALgraph(AG);    /*调用创建AOE网函数*/
   printf("\n输出AOE网:\n");
   Print_ALgraph(AG);
   printf("输出AOE网的关键活动:\n");
   printf(" 弧 : 权值\n");
   tag=CriticalPath(AG);
   if(!tag) printf("AOE网有回路！\n");
}