这是完成了的程序#include <stdio.h>
#define MAX_VERTEX_NUM 20
#define len sizeof(struct stack)
#define gen sizeof(struct Arc)
#define maxsize 100
#define null 0
int ve[20];
int indegree[20];
int *y;
int *w;
/*---------------------------------------------------------------------------------------------*/
typedef struct Arc{
int
adjvex;
/*该弧所指向的顶点位置*/
struct Arc *nextarc;
/*指向下一条弧的指针*/
int
*info;
/*该弧相关信息的指针*/
}ArcNode;
typedef struct Vnd{
int
data;
/*顶点信息*/
ArcNode
*firstarc;
/*指向第一条依附该顶点的弧的指针*/
}VNode,AdjList[MAX_VERTEX_NUM];
struct ALGraph {
AdjList vertices;
int
vexnum,arcnum;
/*图的当前顶点数和弧数*/
int
kind;
/*图的种类标志*/
};
/*-------------------------------------图的邻接表定义------------------------------------------*/
typedef struct stack {
int *top;
int *base;
int stacksize;
}*sqstack;
/*-------------------------------------栈定义--------------------------------------------------*/
main()
{int i,j,n,m,h,k;
struct ALGraph G;
ArcNode *p1;
ArcNode *p2;
sqstack S1;
sqstack S2;
y=&S1;
w=&S2;
initstack(y);
initstack(w);
printf("\nYou should input all the information of your AOE Net.\n");
printf("How many facts are there in your AOE Net: ");
scanf("%d",&n);
G.vexnum=n;
for(i=0;i<n;i++)
{indegree[i]=0;}
printf("\nAnd now you will input more about the AOE Net.\n");
for(i=0;i<n;i++)
{G.vertices[i].data=i+1;
p1=p2=G.vertices[i].firstarc=(ArcNode *)malloc(gen);
printf("Input the information of the facts connecting to V%d.\n",i+1);
printf("how many vertex connect to V%d:",i+1);
scanf("%d",&m);
if(m==0)
{
G.vertices[i].firstarc=null;
break;
}
printf("The first vertex connect to V%d\n:",i+1);
printf("adjvex=");
scanf("%d",&p1->adjvex);
k=p1->adjvex;
indegree[k]++;
printf("right=");
scanf("%d",p1->info);
for(j=1;j<m;j++)
{p1=(ArcNode *)malloc(gen);
printf("\nThe %d vertex connect to V%d\n:",j+1,i+1);
printf("adjvex=");
scanf("%d",&p1->adjvex);
k=p1->adjvex;
indegree[k]++;
printf("right=");
scanf("%d",p1->info);
p2->nextarc=p1;
p2=p1;
}
p1->nextarc=null;
}
printf("the critical active stands with '*'\n");
CriticalPath(G);
getch();
}
/*---------------------------------------------------------------------------------------------*/
initstack(sqstack *s)
{
(*s)->base=(int *)malloc(maxsize*len);
if(!(*s)->base) {printf("error\n"); exit(0);}
(*s)->top=(*s)->base;
(*s)->stacksize=maxsize;
}
/*------------------------------------栈的初始化-----------------------------------------------*/
void push(sqstack *s,int e)
{int stackincrement;
stackincrement=(*s)->top-(*s)->base-(*s)->stacksize;
if((*s)->top-(*s)->base>=(*s)->stacksize)
{(*s)->base=(int *)realloc((*s)->base,((*s)->stacksize+stackincrement)*len);
if(!(*s)->base) exit(0);
(*s)->top=(*s)->base+(*s)->stacksize;
(*s)->stacksize+=stackincrement;
}
(*((*s)->top++))=e;
}
/*------------------------------------入栈函数-------------------------------------------------*/
int pop(sqstack *s)
{int e;
if((*s)->top==(*s)->base) return 0;
e=(*(--(*s)->top));
return e;
}
/*------------------------------------出栈函数-------------------------------------------------*/
int stackempty(sqstack *s)
/*如果栈为空，返回真，否则返回假*/
{if((*s)->top==(*s)->base)
return 1;
else return 0;
}
/*--------------------------------------------------------------------------------------------*/
int TopologicalOrder(struct ALGraph G)
{int i,j,k,p,count;
ArcNode *q;
initstack(w);
count=0;
initstack(y);
for(i=0;i<G.vexnum;i++)
{if(!indegree[i])
push(y,i);
}
for(i=0;i<G.vexnum;i++)
{ve[i]=0;}
while(!stackempty(y)) {
j=pop(y);
push(w,j);
++count;
for(q=G.vertices[j].firstarc;q!=null;q=q->nextarc)
{k=q->adjvex;
if(--indegree[k]==0)
push(y,k);
if(ve[j]+*(q->info)>ve[k])
ve[k]=ve[j]+*(q->info);
}
}
if(count<G.vexnum)
return 0;
else return 1;
}
/*-----------------------------求各顶点事件的最早发生时间ve---------------------------------*/
int CriticalPath(struct ALGraph G)
{int ee,el,dut,k,i,j,h,sum=0,vl[20];
char tag;
ArcNode *p;
if(!TopologicalOrder(G))
{printf("The project cannot be applied.\n");
return 0;
}
for(i=0;i<G.vexnum;i++)
{vl[i]=ve[G.vexnum-1];}
while(!stackempty(w))
{ for(j=pop(w),p=G.vertices[j].firstarc;p!=null;p=p->nextarc)
{k=p->adjvex;
dut=*(p->info);
if(vl[k]-dut<vl[j])
vl[j]=vl[k]-dut;
}
}
for(j=0;j<G.vexnum;++j)
{for(p=G.vertices[j].firstarc;p!=null;p=p->nextarc)
{k=p->adjvex;
dut=*(p->info);
ee=ve[j];
el=vl[k]-dut;
tag=(ee==el)?'*':'-';
printf("\nR%d%d duringtime=%d eearly=%d elate=%d critical=%c",j,k,dut,ee,el,tag);
}
}
}
/*---------------------------------输出G的各项关键活动-------------------------------------*/
2004-09-06 14:19
