1

我正在尝试在 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]。你能解释一下这是如何工作的吗？

我希望这个问题很清楚，因为我自己也很困惑。

4

1 回答 1

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对象（理论上）可以粗略地扩展为指向 more int。

于 2012-06-11T15:55:11.170 回答