Aqing. 2016-12-21 04:18 采纳率: 0%
浏览 930

关键路径的一道题,T T,好不容易能运行出来结果求不出来结果,中断异常

/*在网络计划技术中, 把工程计划表述为带权的有向无环图,
以顶点表示事件, 以有向边表示活动, 边上的权值表示该活动的待续时间,
则此带权的有向图称为用边表示“活动”的网(Ac tivity On Edge Network)简称AOE网。
通常AOE网上列出了完成预定工程计划所需要进行的活动, 每项活动的计划完成时间,
要发生哪些事件, 及这些事件和活动的关系。为了进行人力、物力的调度和分配,
以缩短工期, 我们必须找出影响工程进度的关键活动, 这就是关键路径的求解问题。
给出下图,关键路径为:v1v2v5v7v9、v1v2v5v8v9, 其长度为。
写出求出该图的关键路径的算法。*/
#include
#include
#include
#include
#include
typedef struct node
{
int adjvex;
int dut;
struct node next;
}edgenode;
typedef struct
{
int projectname;
int id;
edgenode *link;
}vexnode;
//建立图存储结构
void CreateGraphic(vexnode
Graphicmap,int projectnumber,int activenumber)
//projectnumber为工程的节点数,activenumber
{
int begin,end,duttem;
edgenode p;
for(int i=0;i {
Graphicmap[i].projectname=i;
Graphicmap[i].id =0;
Graphicmap[i].link =NULL;
}
printf("某项目的开始到结束在图中的工程输入\n");
printf("如:3 6 回车表示第一个工程到第三各工程之间的活动用了个小时\n");
for(int k=0;k<activenumber;k++)
{
scanf("%d %d %d",&begin,&end,&duttem);
p=(edgenode
)malloc(sizeof(edgenode));
p->adjvex =end-1; //将邻接点序号j赋给新结点的邻接点域
p->dut =duttem;
Graphicmap[end-1].id ++; // 将入度加
p->next =Graphicmap[begin-1].link ;
Graphicmap[begin-1].link =p; //将新结点插入到顶点vi的边表头部
}
}
//求关键路径
int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime)
{
int i,j,k,m=0;
int front=-1,rear=-1;
int* topologystack=(int*)malloc(projectnumber*sizeof(int)) ; //用来保存拓扑排列
int* vl=(int*)malloc(projectnumber*sizeof(int)); //用来表示在不推迟整个工程的前提下,VJ允许最迟发生的时间
int* ve=(int*)malloc(projectnumber*sizeof(int)); //用来表示Vj最早发生时间int* l=(int*)malloc(activenumber*sizeof(int));
int* e=(int*)malloc(activenumber*sizeof(int)); //表示活动最早开始时间
edgenode p;
totaltime=0;
for(i=0;i ve[i]=0;
{
if(Graphicmap[i].id==0)
{
topologystack[++rear]=i;
m++;
}
for(i=0;i }
while(front!=rear)
{
front++;
j=topologystack[front];
m++;
p=Graphicmap[j].link ;
while(p)
{
k=p->adjvex ;
Graphicmap[k].id --;
if(ve[j]+p->dut >ve[k])
ve[k]=ve[j]+p->dut ;
if(Graphicmap[k].id ==0)
topologystack[++rear]=k;
p=p->next ;
}
{
printf("\n本程序所建立的图有回路不可计算出关键路径\n");
}
if(m printf("将退出本程序\n");
return 0;
}
totaltime=ve[projectnumber-1];
for(i=0;i vl[i]=totaltime;
for(i=projectnumber-2;i>=0;i--)
{
j=topologystack[i];
p=Graphicmap[j].link ;
while(p)
{
k=p->adjvex ;
if((vl[k]-p->dut ) vl[j]=vl[k]-p->dut ;
p=p->next ;
}
}
i=0;
printf("| 起点| 终点| 最早开始时间| 最迟完成时间| 差值| 备注|\n");
for(j=0;j {
p=Graphicmap[j].link;
{
k=p->adjvex ;
while(p)
e[++i]=ve[j];
vl[i]=vl[k]-p->dut;
printf("| %5d | %5d | %5d | %5d | %5d |",Graphicmap[j].projectname+1,Graphicmap[k].projectname +1,e[i],vl[i],vl[i]-e[i]);
if(vl[i]==e[i])
printf(" 关键活动|");
printf("\n");
p=p->next ;
}
}
return 1;
}
//寻找关键路径
void seekkeyroot()
{
int projectnumber,activenumber,totaltime=0;
system("cls");
printf("请输入这个工程个数:");
scanf("%d",&projectnumber);
printf("请输入这个工程和工程之间的边数:");
scanf("%d",&activenumber);
vexnode
Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));
CreateGraphic(Graphicmap,projectnumber,activenumber);
SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);
printf("整个工程所用的最短时间为:%d个小时\n",totaltime);
system("pause");
}
int main()
{
char ch;
for(;;)
{
do
{
system("cls");
printf(" ===========================================\n");
printf(" | 欢迎进入求关键路径算法程序|\n");
printf("%s"," (S)tart开始输入工程数据并求出关键路径\n");
printf("%s"," (E)xit 退出!\n");
printf(" ===========================================\n");
printf("%s"," 请输入选择(S,E):");
scanf("%c",&ch);
ch=toupper(ch);
}
while(ch!='S'&&ch!='E');
{
switch(ch)
{
case'S': seekkeyroot();
break;
case'E': return 1;
}
}
}
}

  • 写回答

1条回答 默认 最新

  • mianbaohebg 2016-12-31 08:55
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题