C結構圖，幫助理解結構

Question

我想在C中創建一個數據結構來表示圖。我發現這是非常有用的鏈接：

http://pine.cs.yale.edu/pinewiki/C/Graphs

在我看來，一個非常好的起點。但是我對理解數據結構有些問題。

struct graph { 
    int n;    /* number of vertices */ 
    int m;    /* number of edges */ 
    struct successors { 
     int d;   /* number of successors */ 
     int len;  /* number of slots in array */ 
     char is_sorted; /* true if list is already sorted */ 
     int list[1]; /* actual list of successors */ 
    } *alist[1]; 
}; 

我不明白爲什麼結構繼任聲明，因爲它是不以這樣的方式

struct graph { 
    int n;    /* number of vertices */ 
    int m;    /* number of edges */ 
    struct successors { 
     int d;   /* number of successors */ 
     int len;  /* number of slots in array */ 
     char is_sorted; /* true if list is already sorted */ 
     int *list; /* actual list of successors */ 
    } *alist; 
}; 

正如我在相繼式功能看到創建圖形：

Graph 
graph_create(int n) 
{ 
    Graph g; 
    int i; 

    g = malloc(sizeof(struct graph) + sizeof(struct successors *) * (n-1)); 
    assert(g); 

    g->n = n; 
    g->m = 0; 

    for(i = 0; i < n; i++) { 
     g->alist[i] = malloc(sizeof(struct successors)); 
     assert(g->alist[i]); 

     g->alist[i]->d = 0; 
     g->alist[i]->len = 1; 
     g->alist[i]->is_sorted= 1; 
    } 

    return g; 
} 

它爲alist分配更多空間，我不明白爲什麼要聲明它爲alist [1]。 你能解釋我是如何工作的嗎？

我希望問題很清楚，因爲我自己很困惑。

Answer 1

struct successors { 
    /* 
    */ 
    int list[1]; /* actual list of successors */ 
} *alist[1]; 

使用雙間接（每一指針OP */&和下標操作[]是一個間接層，並且需要額外的存儲器訪問）alist構件上，以使每個索引是malloc「d。

struct successors { 
    /* 
    */ 
    int *list; /* actual list of successors */ 
} *alist; 

不。

此外，從你的鏈接：

/* basic directed graph type */ 
typedef struct graph *Graph; 

該鏈接有相當大量的代碼。

我並不完全瞭解->list的使用方式，但您的方法只爲int *保留空間，而原始保留指針和目標int。

的

g = malloc(sizeof(struct graph) + sizeof(struct successors *) * (n-1)); 

分配唯一allocs successors *所以每個successors對象可以（在理論上）粗略地擴展到指向更int的。