| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 636 人关注过本帖
标题:关键路径问题
只看楼主 加入收藏
shines
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2007-7-3
收藏
 问题点数:0 回复次数:0 
关键路径问题


请问一下这个程序错哪啦?急急。。。相当急急。。。谢谢哦!!!!!!

#include<stdio.h>
#include<malloc.h>
#define MAX_VERTEX_NUM 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -1
#define OK 1
#define ERROR 0
typedef int SElemType;
typedef int Status;
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
int time;

}ArcNode;
typedef struct VNode{
char vertex;
int id;
ArcNode *firstarc;
}VNode,Adjlist[MAX_VERTEX_NUM];
typedef struct{
Adjlist vertices;
int vexnum,arcnum;
}AlGraph;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
void CreatAlGraph(AlGraph *G){
int i,j,k;
ArcNode *s;
printf("please input vexnum and arcnum:");
scanf("%d%d",&(G->vexnum),&(G->arcnum));
printf("please input vertices and indegree:");
for(i=0;i<G->vexnum;i++){
scanf("%c%d",&(G->vertices[i].vertex),&(G->vertices[i].id));
G->vertices[i].firstarc=NULL;
}
for(k=0;k<G->arcnum;k++){
printf("please input adjvnode i and j:");
scanf("%d%d",&i,&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j;
printf("please input time:");
scanf("%d",&(s->time));
s->nextarc= G->vertices[i].firstarc;
G->vertices[i].firstarc=s;
}
}
Status InitStack(SqStack *S) {
S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S->base)exit(OVERFLOW);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack *S,SElemType e) {
if(S->top-S->base>=S->stacksize) {
S->base=(SElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S->base)exit(OVERFLOW);
S->top=S->stacksize+S->base;
S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e) {
if(S->top==S->base)return ERROR;
*e=*--S->top;
return OK;
}
Status StackEmpty(SqStack *S){
if(S->top==S->base)
return OK;
}
Status TopologicalOrder(AlGraph *G,SqStack *T,int *ve){
int i,j,k,count;
ArcNode *p;
SqStack *S;
InitStack(T);count=0;
for(i=0;i<G->vexnum;i++)
ve[i]=0;
while(!StackEmpty(S)){
Pop(S,&j);Push(T,j);++count;
for(p=G->vertices[j].firstarc;p;p=p->nextarc){
k=p->adjvex;
if(--ve[k]==0)Push(S,k);
if(ve[j]+(p->time)>ve[k]) ve[k]=ve[j]+(p->time);
}
}
if(count<G->vexnum)return ERROR;
else return OK;
}
Status CriticalPath(AlGraph *G,int *ve,SqStack *T){
int *vl,i,j;
int k,dut,ee,el;
char tag;
ArcNode *p;

for(i=0;i<G->vexnum;i++)
vl[i]=ve[G->vexnum-1];
while(!StackEmpty(T))
for(Pop(T,&j),p=G->vertices[j].firstarc;p;p=p->nextarc){
k=p->adjvex;
dut=p->time;
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;p=p->nextarc){
k=p->adjvex;
dut=p->time;
ee=ve[j];
el=vl[k]-dut;
tag=(ee==el)?'*':'';
printf("%d %d %d %d %d%c",j,k,ee,el,tag);
}
}
main(){
AlGraph G;
SqStack T;
int ve;
CreatAlGraph(&G);
TopologicalOrder(&G,&T,&ve);
CriticalPath(&G,&ve,&T);
}

搜索更多相关主题的帖子: 路径 关键 
2007-07-03 21:31
快速回复:关键路径问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.011755 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved