Проблемы инициализации графа на основе массива со списками смежности в C

Question

Я раньше играл с Графиками и справился с этим с помощью 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; и не могу понять, почему. Я пробовал множество вещей, но я не могу управлять инициализацией Графа с такой структурой. Кроме того, способ, которым я объявляю и возвращаю указатель на График, сделан правильно для этой структуры?

Я усложняю вещи множеством указателей в функции init или как?

P.S .: Пожалуйста, не предлагайте другие определения структуры, я не могу ничего изменить в приведенном выше. Это реальная проблема. Я знаю, как работать с графиками, катящимися по моей собственной структуре, но мне нужно использовать ту, что выше.

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

Я думаю, что нашел решение, которое искал.Я использовал 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;
}

Answer 3

Завершить пересмотр ответа с учетом требования ОП никоим образом не изменять 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.