4

このスキップリストの実装を読んで、私はこのコードフラグメントに出くわしました：

typedef struct nodeStructure{
    keyType key;
    valueType value;
    node forward[1]; /* variable sized array of forward pointers */
    };

私には、それforward[1]は1つの要素の配列を示しているように見えます。そしてコメントはそれを可変サイズの配列と呼んでいます。

私は何かを誤解していますか、それともこれは私が読んでいる情報源の単なる間違いですか？

4

4 に答える 4

5

これは構造体ハックと呼ばれます。これは、C99で導入された柔軟な配列メンバーの古い形式です。

これは、過去に構造体の最後のメンバーの変数配列を模倣するために使用されていましたが、Cでは厳密に準拠した構造体ではありません。

于 2012-11-08T20:02:39.113 に答える
3

これはCのプログラムパラダイムであり、時々見られます。構造体を割り当てるときは、sizeof（struct nodeStructure + numNodes * sizeof（node））を割り当てます。

これにより、構造体が1つだけであると宣言されている場合でも、構造体に対して複数のフォワードノードを持つことができます。少し醜いハックですが、機能します。

通常、これを行うと、「count」などと呼ばれるファイルも作成されるため、ノードの後に​​追加のエントリがいくつあるかがわかります。

于 2012-11-08T20:04:33.923 に答える
2

これは、古いCコンパイラ（C99より前）の一般的なトリックです。コンパイラを使用すると、forward宣言された長さの終わりを超えた要素を、struct;の最後の要素であるときに逆参照できます。次に、次のように、追加の要素にmalloc十分なメモリを使用できます。node

nodeStructure *ptr = malloc(sizeof(nodeStructure)+4*sizeof(node));
for (int i = 0 ; i != 5 ; i++) { // The fifth element is part of the struct
    ptr->forward[i] = ...
}
free(ptr);

このトリックを使用すると、個別の動的割り当てなしで、可変サイズの配列を構造体に埋め込むことができます。別の解決策は宣言することですが、それとは別に宣言するnode *forward必要がありmalloc、 sの数が不必要に倍増し、メモリの断片化が増える可能性があります。freenodeStructuremalloc

上記のフラグメントがハックなしでどのように見えるかを次に示します。

typedef struct nodeStructure{
    keyType key;
    valueType value;
    node *forward;
};

nodeStructure *ptr = malloc(sizeof(nodeStructure));
ptr->forward = malloc(5*sizeof(node));
for (int i = 0 ; i != 5 ; i++) {
    ptr->forward[i] = ...
}
free(ptr->forward);
free(ptr);

編集（Adam Rosenfieldによるコメントへの応答）：C99では、次のようにサイズのない配列を定義できます。node forward[];これは柔軟な配列メンバーと呼ばれ、C99標準のセクション6.7.2.1.16で定義されています。

于 2012-11-08T20:03:11.720 に答える
2

データ構造の実装は、柔軟な配列メンバー（C99で追加）を持たないC90標準に対して作成されている可能性があります。当時は、構造体の最後に1または0サイズ（*）の配列を使用して、動的に変化する数の要素にアクセスできるようにするのが一般的でした。

コメントは、C99スタイルの可変長配列を意味するものとして解釈されるべきではありません。さらに、C99では、メンバーの慣用的で標準に準拠した定義はforwardですnode forward[];。struct nodeStructureこのようなメンバーを持つタイプは、不完全タイプと呼ばれます。それへのポインターを定義することはできますが、このタイプの変数を定義したり、そのサイズを取得したりすることはできません。これらの操作は、プログラマーの意図とほぼ一致しませんが、許可するnode forward[0]すべての操作です。node forward[1]

（*）0サイズの配列は標準で禁止されていますが、GCCはこれらを正確にこの用途の拡張として受け入れました。

于 2012-11-08T20:05:55.247 に答える