Cで隣接リストを持つ配列に基づいてグラフを初期化する際の問題

Question

私は以前Graphでプレイしていましたが、StackOverflowの助けを借りてそれを正しく管理しましたが、以下のような構造は使用しませんでした。私は(*g[i])->next = NULL;の最初の反復にセグメンテーションフォールトを取得し、私は理由を理解することはできません

#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; 
} 

...私はここで間違ってやっているのか理解できないようです。私は無数のものを試しましたが、私はそのような構造でグラフの初期化を管理することはできません。また、私は宣言し、グラフへのポインタを返す方法は、この構造のための正しい方法を行っている？

私はinit関数の中にたくさんのポインタを入れたり、何を複雑にしていますか？

P.S：異なる構造定義を提案しないでください。私は上記のものを変更することはできません。それが本当の問題です。グラフを使って自分の構造を動かす方法を知っていますが、上記のものを使う必要があります。

Answer 1

私が探していた解決策が見つかりました。私は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 2

私は*Graph[MaxV]の2番目のtypedefを実際に理解していません。私はどうなるのか

は、次のように別の構造体を宣言している：

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 3

何らかの形でtypedefを変更しないというOPの要求に応じて、完全な改訂版です。

私はこれに変更助言する：

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]と等価であり、ただし、外側の配列サイズが固定されていることは明らかである。それはあなたがcan't return a fixed size arrayだから問題を生みますが、**を返すことができます。

グラフの配列のユースケースが何であるかはまだ分かりませんが、これはvalgrindを渡します。