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));

割り当てるだけなsuccessors *ので、各successorsオブジェクトは（理論的には）より多くintのオブジェクトを指すように大まかに拡張できます。

于 2012-06-11T15:55:11.170 に答える