自己初始化邻接表数据有问题 (注视是瞎写的)如果还有其他问题也请帮忙改一下 20C

#include"stdio.h"
#include"stdlib.h"
#define MAX_VERTEX_NUM 20
#define InfoType int
#define VertexType char
#define MaxSize 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define SElemType int
#define Status int
#define OVERFLOW -1
typedef struct
{
SElemType base;
SElemType *top;
int stacksize;
}SqStack;
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 1;
}
Status GetTop(SqStack S, SElemType &e)
{
if (S.base == S.top)return 0;
e = (S.top - 1);
return 1;
}
Status Push(SqStack &S, SElemType e)
{
if (S.top - S.base == 0)
{
S.base = (SElemType
)realloc(S.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SElemType));
if (!S.base)exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize = STACK_INIT_SIZE + STACKINCREMENT;
}
(S.top++) = e;
return 1;
}
Status Pop(SqStack &S, SElemType &e)
{
if (S.base == S.top) return 0;
e = *--S.top;
return 1;
}
Status StackEmpty(SqStack S)
{
if (S.top - S.base == 0)
return 1;
else
return 0;
}
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
int weight;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertex;
int vexnum, arcnum;
int kind;
}ALGraph;

int indegree[MaxSize];
int ve[MaxSize];//定义事件最早发生 (vertex earliest)
int vl[MaxSize];//定义事件最迟发生 (vertex lastest)
void CreateDGAOV(ALGraph *G)
{
int i, j, k;
ArcNode *e;
printf("输入顶点和边:\n");
scanf_s("%d,%d", &G->vexnum, &G->arcnum);
getchar();
printf("请初始化顶点\n");
for (i = 0; i < G->vexnum; i++)
{
printf("输入顶点字符:\n");
scanf_s("%c", &G->vertex[i].data);
G->vertex[i].firstarc = NULL;

getchar();
}
for (k = 0; k < G->arcnum; k++)
{
printf("输入边(vi,vj)上的顶点序号:\n");
scanf_s("%d,%d", &i, &j);
e = (ArcNode
)malloc(sizeof(ArcNode));
e->adjvex = j;
e->nextarc = G->vertex[i].firstarc;
G->vertex[i].firstarc = e;
}
}
Status CreateDGAOE(ALGraph *G)
{

VNode v1, v2;
int i, j, sign1, sign2;
int value;
printf("创建AOE\n");
printf("请输入顶点数和边数:");
scanf_s("%d,%d", &G->vexnum, &G->arcnum);
getchar();
printf("请初始化顶点\n");
for (i = 0; i < G->vexnum; i++)
{
    printf("输入顶点字符:\n");
    scanf_s("%c", &G->vertex[i].data);
    G->vertex[i].firstarc = NULL;
    getchar();
}
printf("请初始化弧\n");
printf("输入格式:顶点1 顶点2 权值(表示顶点1邻接到顶点2)\n\n");
for (i = 0; i < G->arcnum; i++)
{
    ArcNode *p, *q;
    sign1 = -1;
    sign2 = -1;
    scanf_s("%c%c%d", &v1.data, &v2.data, &value);
    getchar();
    for (j= 0; j< G->vexnum; j++)
    {

        if (v1.data == G->vertex[j].data)
            sign1 = j;
        if (v2.data == G->vertex[j].data)
            sign2 = j;
    }
    p = (ArcNode*)malloc(sizeof(ArcNode));
    if (!p)
        exit(OVERFLOW);
    p->nextarc = NULL;
    p->weight = value;
    p->adjvex = sign2;
    q = G->vertex[sign1].firstarc;
    if (!q)
        G->vertex[sign1].firstarc = p;
    else
    {
        while (q->nextarc != NULL)
            q = q->nextarc;
        q->nextarc = p;
    }
}
return 1;

}
void FindInDegree(ALGraph G)//计算每个节点的入度;
{
ArcNode *p;
int i, k;
for (i = 0; i < G.vexnum; i++)
indegree[i] = 0;
for (i = 0; i < G.vexnum; i++)
{
p = G.vertex[i].firstarc;
while (p != NULL)
{
k = p->adjvex;
indegree[k]++;
p = p->nextarc;
}
}
}
int TopologicalSort(ALGraph &G)//拓扑排序的实现
{
int i, k, count = 0;
SqStack S;
ArcNode *p;
FindInDegree(G);
InitStack(S);
printf("TopologicalSort:");
for (i = 0; i < G.vexnum; i++)//将入度为0的顶点的下标号压入顺序栈S
if (!indegree[i])
Push(S, i);
while (!StackEmpty(S))//如果栈不为空
{
Pop(S, i);//弹出栈顶存储的顶点的下标号
printf("%3c", G.vertex[i].data);//输出下标号为i的顶点中的数据;
count++;//每弹出一次,count就加一,全部输出后应该是vexnum的值,可由这个来判断G有没有环;
for (p = G.vertex[i].firstarc; p; p = p->nextarc)//令p指向顶点的firstarc也就是指向顶点节点后的第一个边结点,等到p指向NULL时循环结束
{
k = p->adjvex;//令k指向p节点的下标号;
if (--indegree[k] == 0)//先将这个节点的入度-1如果=0,那么就将它入栈
Push(S, k);
}
}
if (count < G.vexnum)
{
printf("The directed graph has a loop\n");
return 0;
}
else
return 1;
}
Status TopologicalOrder(ALGraph G, SqStack &T)
{
SqStack S;
ArcNode *p;
int i, x, k, count = 0;

FindInDegree(G);
InitStack(T);
for (i = 0; i < G.vexnum; i++)//将时间最早发生初始化
    ve[i] = 0;
for (i = 0; i < G.vexnum; i++)//将入度为0的顶点入栈;
{
    if (indegree[i] == 0)
        Push(S, i);
}
while (!StackEmpty(S))
{
    Pop(S, x);
    Push(T, x);//将弹出来的顶点下标压入栈T
    count++;
    for (p = G.vertex[x].firstarc; p; p = p->nextarc)//注意p指向的是边节点
    {
        k = p->adjvex;
        if (--indegree[k] == 0)
        {
            Push(S, k);
        }
        if (ve[x] + (p->weight) > ve[k])//取最早完成时间里的最大值
        {
            ve[k] = ve[x] + (p->weight);
        }
    }
    if (count < G.vexnum)
        return 0;
    else
        return 1;
}

}
Status CriticalPath(ALGraph G)
{
int i, k, x;
int ee, el;
ArcNode *p;
SqStack T;
InitStack(T);
TopologicalOrder(G, T);
for (i = 0; i < G.vexnum; i++)
vl[i] = ve[G.vexnum - 1];
while (!StackEmpty(T))
{
Pop(T, x);
for (p = G.vertex[i].firstarc; p; p = p->nextarc)
{
k = p->adjvex;
if (vl[x] > vl[k] - p->weight)//取最迟时间中最小值
vl[x] = vl[k] - p->weight;
}
}
for (i = 0; i < G.vexnum; i++);
{
for (p = G.vertex[i].firstarc; p; p = p->nextarc)
{
k = p->adjvex;
ee = ve[i];
el = vl[k] - p->weight;
}
printf("Criticalpath:<%d,%d>length:%d\n", i, k, p->weight);
}
return 1;
}
int main()
{
//ALGraph G;
//CreateDGAOV(&G);
//TopologicalSort(G);
//printf("\n");
ALGraph N;
CreateDGAOE(&N);
CriticalPath(N);
return 0;
}

weixin_42968148
张忘川 这是数据结构 AOV 求AOE的关键路径
大约一年之前 回复

1个回答

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

相似问题

1
数据结构采用邻接表算法实现KAMI问题,怎么实现的,采用的C语言
1
用数组表示法(邻接矩阵)和邻接表两种存储结构分别表示下面的无向图。
2
数据结构图(用C语言)当中为什么邻接表用结构体变量报错,用邻接矩阵不报错?
1
请教数据结构#邻接链表表示图?
0
大佬们,这道题能用c语言写吗?
1
有向图任意两顶点之间存在的双边,则删除shuang bi an
1
邻接表双向BFS算法数组越界问题
1
编程实现有向图的深度和广度优先遍历
0
用邻接矩阵创建有向网,求最小生成树,最短路径(c语言)。
1
求教大佬们,这个“读取位置 0xCCCCCCCC 时发生访问冲突。”的异常该如何解决?
1
C#调用纯C的DLL时,结构体指针、数组、二维数组 怎么转换?
0
CCPC2019-秦皇岛F HDU-6736为什么这个题目把前向星换成邻接表就能AC啊?
0
在Windows7 64位+VS2015上运行求解AOE网关键路径的算法,邻接表表示的AOE网提示网中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?
1
Kruskal算法实现最小生成树主函数的第一行的aaa就无法输出是为什么
1
用c语言版写的求解关键路径,调试到一半按任意键继续就关了,求大神看看我的代码
0
floyd算法求任意两点最短路径,为什么输出的邻接矩阵总不正确
0
利用普利姆算法和克鲁斯卡尔算法实现最小生成树问题C语言或者C++语言实现
1
c语言实现的套汇问题 钱的种类多了就就不行了
1
交通咨询问题:求任意两个顶点间最短路径,为什么无论输入哪两个顶点,都会显示无路径?