在 C 中使用邻接表初始化基于数组的图时出现问题

Question

我以前玩过 Graphs，并且在 StackOverflow 的一些帮助下很好地管理了它，但我从未使用过像下面这样的结构。我似乎无法理解我在这里做错了什么...

#include "stdio.h"
#include "stdlib.h"

#define MaxV 100
#define MaxE 50

typedef struct edge {
    int dest;
    int cost;

    struct edge *next;
} Edge, *Graph[MaxV];

Graph *initGraph() {    
    Graph *g = (Graph*)malloc(sizeof(Edge) * MaxV);

    for(int i = 0; i < MaxV; i++)
        (*g[i])->next = NULL;

    return g;
}

int main(void) {
    Graph *g = initGraph();

    for(int i = 0; i < MaxV; i++) {
        if((*g[i])->next == NULL) printf("[%02d] NULL\n", i);
    }

    return 0;
}

我在 (*g[i])->next = NULL; 的第一次迭代中遇到分段错误不明白为什么。我已经尝试了无数的方法，但我似乎无法使用这种结构来管理图形初始化。另外，我声明和返回指向 Graph 的指针的方式对于该结构是否正确？

我是否在 init 函数中使用大量指针使事情变得复杂还是什么？

PS：请不要提出不同的结构定义，我无法更改上面的任何内容。这才是真正的问题。我知道如何使用图表滚动我自己的结构，但我需要使用上面的。

Answer 1

我不太明白你的第二个 typedef *Graph[MaxV]。

我要做的就是声明另一个结构，如下所示：

typedef struct graph {
    Edge *edges;
} Graph;

然后您可以按如下方式初始化图表：

Graph *initGraph() {  
    Graph *g = (Graph*)malloc(sizeof(Graph));

    g->edges = (Edge*)malloc(sizeof(Edge) * MaxV);
    for(int i = 0; i < MaxV; i++)
        g->edges[i].next = NULL;

    return g;
}

打印出图表如下：

for(int i = 0; i < MaxV; i++) {
    if(g->edges[i].next == NULL) printf("[%02d] NULL\n", i);
}

我想您会发现为图表添加一个额外的结构将证明更具可持续性时间也。 :)

Answer 2

鉴于OP要求不以任何方式更改typedef，对答案进行了完整修订。

我建议改为：

void initGraph(Graph g) {
    g[0] = malloc(sizeof(Edge) * MaxV);

    for(int i = 0; i < MaxV; i++)
        g[0][i].next = NULL;
    return;
}

int main(void) {
    Graph g;
    initGraph(g);

    for(int i = 0; i < MaxV; i++) {
        if(g[0][i].next == NULL) printf("[%02d] NULL\n", i);
    }

    free(g[0]);
    return 0;
}

这里的问题是“指针数组”综合症。即 Graph** g 相当于 Graph *g[10] ，但明显的条件是外部数组大小是固定的。这会产生问题，因为您无法返回固定大小的数组，但您可以返回 **。

我仍然不确定图表数组的用例是什么，但是哎呀，这通过了 valgrind。

Answer 3

我想我找到了我正在寻找的解决方案。我尽可能地使用 Valgrind 来测试读/写权限，并且没有错误。是的，存在内存泄漏，但这不是这个问题的重点（我知道这些，不用担心）。

这是创建简单图表的完整代码。很想听听这个实现可能存在的任何问题......

#include "stdio.h"
#include "stdlib.h"

#define MaxV 10
#define MaxE 5

typedef struct edge {
    int dest;
    int cost;

    struct edge *next;
} Edge, *Graph[MaxV];

Graph *initGraph() {
    Graph *g = (Graph*)malloc(sizeof(Graph));

    for(int i = 0; i < MaxV; i++)
        (*g)[i] = NULL;

    return g;
}

int insertEdge(Graph *g, int o, int d, int c) {
    if(!g) return -1;

    Edge *edge = (Edge*)malloc(sizeof(Edge));

    edge->dest = d;
    edge->cost = c;

    edge->next = (*g)[o];
    (*g)[o] = edge;

    return 0;
}

int main(void) {
    Graph *g1 = initGraph();
    Edge *aux = NULL;

    insertEdge(g1, 0, 1, 2);
    insertEdge(g1, 0, 2, 3);
    insertEdge(g1, 1, 4, 5);
    insertEdge(g1, 2, 4, 1);
    insertEdge(g1, 4, 8, 6);

    for(int i = 0; i < MaxV; i++) {
        printf("[%02d]\n", i);

        for(aux = (*g1)[i]; aux != NULL; aux = aux->next)
            printf(" [%d] » [%d] (%d)\n", i, aux->dest, aux->cost);
    }

    return 0;
}