C 创建AOV网进行拓扑排序

ing

这有2个AOV的创建方法，下面这个是可运行的



这个创建AOV方法将会导致异常



我实在没看懂这有什么区别，为什么第二张图片将会导致异常

#include<malloc.h>
#include<stdio.h>
#include<stdbool.h>

#define VType int
#define MAX 20

typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *next;
}ArcNode;

typedef struct
{
    VType vertex;
    ArcNode *firstArc;
}AdjList[MAX];

typedef struct
{
    int arcNum, vertexNum;
    AdjList vertices;
}MGraph;

int locate(MGraph **g, VType rear)
{
    for (size_t i = 0; i < (*g)->vertexNum; i++)
    {
        if ((*g)->vertices[i].vertex == rear)
        {
            return i;
        }
    }
    return -1;
}

void createAOV(MGraph **g)
{
    printf("请输入顶点数和弧边数\n");
    scanf("%d,%d", &(*g)->vertexNum, &(*g)->arcNum);

    printf("请输入顶点元素\n");
    for (size_t i = 0; i < (*g)->vertexNum; i++)
    {
        scanf("%d", &(*g)->vertices[i].vertex);
        (*g)->vertices->firstArc = NULL;
    }

    printf("请输入弧尾和弧头\n");
    VType arc_t, arc_h;
    for (size_t i = 0; i < (*g)->arcNum; i++)
    {
        //存储弧头
        scanf("%d,%d", &arc_t, &arc_h);
        ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = locate(g, arc_h);

        int t_locate = locate(g, arc_t);
        p->next = (*g)->vertices[t_locate].firstArc;
        (*g)->vertices[t_locate].firstArc = p;
    }
}

//void createAOV(MGraph **g)
//{
//    printf("请输入顶点和弧边数\n");
//    scanf("%d,%d", &(*g)->vertexNum, &(*g)->arcNum);
//
//    printf("请输入顶点元素\n");
//    for (int i = 0; i < (*g)->vertexNum; ++i) {
//        scanf("%d", &(*g)->vertices[i].vertex);
//        (*g)->vertices[i].firstArc = NULL;
//    }
//
//    printf("请输入弧尾和弧头\n");
//    VType h, t;
//    for (int j = 0; j < (*g)->arcNum; ++j) {
//        scanf("%d,%d", &t, &h);
//        //用结点存储弧头
//        ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
//        p->adjvex = locate(g, h);
//
//        //弧尾结点的数据域存储弧头的数组下标
//        int t_locate = locate(g, t);
//        p->next = (*g)->vertices[t_locate].firstArc;
//        (*g)->vertices[t_locate].firstArc = p;
//    }
//}

typedef struct Stack
{
    VType data;
    struct Stack *next;
}Stack;

void init(Stack **s)
{
    *s = (Stack*)malloc(sizeof(Stack));
    (*s)->next = NULL;
}

void push(Stack *s, int index)
{
    Stack *p = (Stack*)malloc(sizeof(Stack));
    p->data = index;
    p->next = s->next;
    s->next = p;
}

void findInDegree(MGraph **g, int *indegree)
{
    for (size_t i = 0; i < (*g)->vertexNum; i++)
    {
        indegree[i] = 0;
    }
    for (size_t i = 0; i < (*g)->vertexNum; i++)
    {
        ArcNode *p = (*g)->vertices[i].firstArc;
        //结点数据域存储了弧头数组下标，入度即为在数据域出现的次数
        while (p)
        {
            ++indegree[p->adjvex];
            p = p->next;
        }
    }
}

bool isEmpty(Stack *s)
{
    if (s->next)
        return false;
    return true;
}

void pop(Stack *s, VType *d)
{
    Stack *p = s->next;
    *d = p->data;
    s->next = s->next->next;
    free(p);
}

void topological_sort(MGraph **g)
{
        int n = (*g)->vertexNum;
        int *indegree = (int*)malloc(n*sizeof(int));

        findInDegree(g, indegree);
        Stack *s;
        init(&s);
        //查找入度为0的顶点，作为起始点
        for (int i = 0; i < (*g)->vertexNum; ++i) {
                if (!indegree[i])
                        push(s, i);
        }
        int count = 0;
        VType d;
        while (!isEmpty(s))
        {
                pop(s, &d);
                ++count;
                printf("%d ", (*g)->vertices[d].vertex);
                //依次查找跟该顶点相链接的顶点，如果初始入度为1，当删除前一个顶点后，该顶点入度为0
                for (ArcNode *p = (*g)->vertices[d].firstArc; p; p = p->next) {
                        if (!(--indegree[p->adjvex]))
                                push(s, p->adjvex);
                }
        }
        //如果count值小于顶点数量，表明该有向图有环
        if (count < (*g)->vertexNum)
        {
                printf("AOV网有环");
                return;
        }
}

int main(int argc, char* argv[])
{
    MGraph *g = (MGraph*)malloc(sizeof(MGraph));
    createAOV(&g);
    topological_sort(&g);
}