用c语言版写的求解关键路径,调试到一半按任意键继续就关了,求大神看看我的代码

c语言版写的求解关键路径,调试到一半按任意键继续就关了,求大神看看我的代码,大一刚学 只能到建立完邻接表

``
#include < stdio.h>
#include< stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 100
#define MVNum 100 //最大顶点
#define NUM 10000 //最大边数
typedef int SElemType;
typedef int Status;
typedef char VerTexType;
typedef int Status;
typedef struct ArcNode //邻接表存储表示
{
int adjvex; //顶点所在位置
int weight; //权值
struct ArcNode *nextarc; //链域 (指向下一条边结点)
}ArcNode;
typedef struct VNode
{
VerTexType data;
ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct
{
AdjList vertices; //邻接表
int vexnum,arcnum; //图的当前顶点数和边数
}ALGraph;
typedef struct //定义栈
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
SqStack S;
int indegree[MVNum]; ///用数组indegree来存放各顶点的入度
int ve[NUM]; //事件发生最早的时间
int vl[NUM]; //事件发生最迟的时间
int topo[MVNum];

//初始化
void InitStack(SqStack S)
{
S->base=(SElemType
)malloc(sizeof MAXSIZE);
if(!S->base)
return ;
S->top=S->base;
S->stacksize=MVNum;
}
//入栈
void Push(SqStack S,SElemType e)
{
if(S->top-S->base==S->stacksize)
return ;
*S->top++=e;
}
//出栈
void Pop(SqStack *S,SElemType e)
{
if(S->top==S->base)
return ;
e=
--S->top;
}
//判断是否为空
Status StackEmpty(SqStack *S)
{
if(S->top==S->base)
return OK;
else
return ERROR;
}
int LocateVex(ALGraph G,VerTexType v)
{
int i;
for(i=0;i<G.vexnum;++i)
if(v==G.vertices[i].data)
return i;
return -1;
}

int CreateUDG(ALGraph *G) ////建立邻接表
{
ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode));
int i,k;
printf("请输入总的顶点数:");
scanf("%d",&G->vexnum);///图的顶点数
printf("请输入总的边数:");
scanf("%d",&G->arcnum);///图的边数
for(i=0;ivexnum;++i)
{
printf("请输入每个顶点的值:");
scanf("%d",&G->vertices[i].data);
G->vertices[i].firstarc=NULL; //顶点的第一个指针域为空
}
for(k=0;karcnum;++k)
{
int v1,v2;
int i,j,w;
printf("请依次输入起点 权值 终点(空格分开):");
scanf("%d %d %d",&v1,&w,&v2);
i=LocateVex(*G,v1);
j=LocateVex(*G,v2);
p->adjvex=j; //顶点
p->nextarc=G->vertices[i].firstarc;
G->vertices[i].firstarc=p; //有向图
p->weight=w;////权值
}
return OK;
}

void FindInDegree(ALGraph G,int indegree[]) //把顶点的入度放到数组中
{
int i,t;
ArcNode *p=(ArcNode *)malloc(sizeof(G.vertices[i].firstarc));

for(i=0;i {
t=0;
//使p指向第一个邻接点
if(p){
while(p){
p=p->nextarc; //p指向下一个邻接点
t++; //有指向的话 就加一
}
}
indegree[i]=t;
}
}

////拓扑排序
int TopologicalSort(ALGraph G,int topo[])
{
int i,m;
FindInDegree(G,indegree); //各顶点的入度
InitStack(&S); //初始栈
for(i=0;i if(!indegree[i]) //如果没有前驱的话
Push(&S,i); //进栈 (等于图中没有那个顶点了)
m=0;//计数
while(!StackEmpty(&S))
{
ArcNode *p=(ArcNode *)malloc(sizeof(G.vertices[i].firstarc));
Pop(&S,i);//出栈
topo[m]=i;
++m;
p=G.vertices[i].firstarc;
while(p!=NULL)
{
int k;
k=p->adjvex;
--indegree[k];
if(indegree[k]==0) //就剩一个了 直接入栈
Push(&S,k) ;
p=p->nextarc;
}
}
if(m<G.vexnum)
return ERROR; //拓扑排序不能有回路
else
return OK;

}

////关键路径
int CriticalPath(ALGraph G)
{
int n,i,k,j,e,l;
ArcNode *p=(ArcNode *)malloc(sizeof(G.vertices[i].firstarc));
if(!TopologicalSort(G,topo))
return ERROR;
n=G.vexnum;
for(i=0;i {
ve[i]=0; //最早发生的时间初值为零
}
for(i=0;i {
k=topo[i];
p=G.vertices[k].firstarc; //p指向第一个邻接点
while(p!=NULL)
{
j=p->adjvex;
if(ve[j]weight)
ve[j]=ve[k]+p->weight; ///最早发生时间更新
p=p->nextarc;///p指向下一个邻接点
}
}

for(i=0;i<n;i++)
{
    vl[i]=ve[n-1];   //最迟发生时间初值
}
for(i=n-1;i>=0;i--)
{
    k=topo[i];
    p=G.vertices[k].firstarc;   //p指向第一个邻接点
    while(p!=NULL)
    {
        j=p->adjvex;   //邻接点的序号
        if(vl[k]<vl[j]-p->weight)
            vl[k]=vl[j]-p->weight;  ///最迟发生时间更新
        p=p->nextarc;///p指向下一个邻接点
    }
}
///判断是否为关键活动
printf("关键路径:");
for(i=0;i<n;i++)
{
    ArcNode *p=(ArcNode *)malloc(sizeof(G.vertices[i].firstarc));
    p=G.vertices[i].firstarc;
        while(p!=NULL)
    {
        j=p->adjvex;    //顶点的位置
        e=ve[i];
        l=vl[j]-p->weight;
        if(e==1)
            printf("<v%d,v%d>",G.vertices[i].data,G.vertices[j].data);
             printf("为关键路径");
          p=p->nextarc;
        }
}
return OK;

}
int main()
{
ALGraph *G=(ALGraph *)malloc(sizeof(ALGraph));
CreateUDG(G);
TopologicalSort(*G,topo);
CriticalPath(*G);
return 0;
}`

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

2
萌新求解!!!!!vs2017写c语言,函数参数间不能传址吗?
0
求解根据路径的指令找到对应的用户名,怎么使用C语言的文件的方法的代码去实现程序编写?
1
c#语言编程的问题求解
2
C语言问题 数组问题 求解
1
成绩转换问题的求解思路,用C语言
2
用Java写基于遗传算法求解图论中任意两点的最短路径应该怎么写,求大神指导
0
C语言求解,Obfuscation
2
VS Code写C语言头文件报错,小白求解~~
0
Play with Sequence的求解,用C语言
1
求助!!c语言编程求解。
1
C语言结构体基础题目求解(感谢)
2
C语言结构体基础 按照成绩顺序输出学生信息 求解(感谢)
1
Matlab的simulink如何使用写好的C语言?
1
C语言 判断输入数字是否为素数 输入1到17判断都是正确的(只试到17) 但是输入9判断结果是“9是素数” 而且就9这一个数字这样 求解??
0
用邻接矩阵创建有向网,求最小生成树,最短路径(c语言)。
1
c语言菜鸟求解`~~按规律生成NxN二维数组,每一行递增其余为0
1
C语言菜鸟求解~一个数组已经从小到大排序 加入一个数字后按照原来从小到大排序
1
c语言菜鸟求解`生成随机数组 将其中偶数存在b中
0
在Windows7 64位+VS2015上运行求解AOE网关键路径的算法,邻接表表示的AOE网提示网中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?