自己参照型構造体の動的配列における、メモリ確保の認識の違い

Question

###自己参照型をポインタ配列で表現した、2つのパターンです↓

######パターン①
```
typedef struct node {

 int ID;
 struct node*Link[0];

}NODE;

NODE*p = (NODE*)malloc(sizeof(NODE) + sizeof(NODE*)*5);

```

######パターン②
```
typedef struct node {

 int ID;
 struct node*Link[5];

}NODE;

NODE*p = (NODE*)malloc(sizeof(NODE));

for(int i = 0; i<5; ++i)
p->Link[ i ] = (NODE*)malloc(sizeof(NODE));

```
上記のパターン②において
`Link[0]〜Link[4] `には、それぞれ第二の要素`「Link[ ][0]」`を含んでいる事は理解してますが、パターン①の場合は二次元目の要素は存在しないのでしょうか？

※
「第二の要素」「二次元目の要素」は、
array[X][Y]の場合の、[Y]に相当する部分です。


###試してみたこと
sizeof演算子を使って自己参照型構造体のサイズを、パターン①と②それぞれで計算してみたが、sizeof演算子は「ポインタに格納されたデータ数」を算出せず、「ポインタの型のサイズ」のみ算出してしまいます。
```
>パターン①の場合

NODE*p = (NODE*)malloc(sizeof(NODE) + sizeof(NODE*)*5);

printf(“%d”,sizeof(p));     //結果が4になる
```

Accepted Answer

「第二の要素」「二次元目の要素」というのが何なのかはっきりしませんが、`p->Link[0から4]` に何か入っているのかという観点では、①も②も、`p`の初期化直後は何も代入していないのでデタラメな値が入っていて使えません。

②は`p->Link[]`に確保したメモリのポインタを代入しているから`NODE`を指すようになります。①も同じようにポインタを代入すれば同じように動きます。①と②は最初のmalloc()のパラメータが違うだけで、それ以外の使い方は同じです。

`sizeof` 演算子はコンパイル時に決まる型のサイズを返します。`sizeof`がこの質問に役に立つかどうかは怪しいです。

----

質問文へのコメントを読むと、本当に欲しいものは動的に子供ノードの数が変更できるツリーのようです。

```c
typedef struct node {
 int id;
 size_t children_size;
 struct node* children;
} NODE;
```

コンパイル時固定サイズの配列やメモリ確保時にサイズが決まる配列では子供ノードの数の変更ができないので、`malloc()`や`realloc()`で確保した1次元配列へのポインタをメンバに入れるとよいかもしれません。

Answer

Cの仕様としては、①は、文法エラーです。
まずは、ANSI C 89 でサイズ０の配列を作ることはできません。 
gcc がサイズ０の配列メンバを作る方法として採用していたので、
gcc の書式をトレースする処理系では拡張仕様としてコンパイルできます。

ANSI C99からは、
struct node *Link[];
の様にサイズを記入しない事によって、サイズ 0 の配列メンバが作れます。
これは、ANSI C89のころ サイズ０のメンバを作る方法で、
MSC が採用していた方法で、ANSI C99 からこれが採用されました。

どのように使うかは、malloc で、サイズ 0 のメンバから始まる
いくつかのデータを計算するなりして、malloc で、余分な領域を確保し、
その余分な領域にデータを置くようにします。

追加：
なお、struct node *Link[] も、struct node*Link[5];　も、２次元配列ではありません、ポインタ配列です。

Answer

関連するルールとしては

- `sizeof` は型の大きさを返す。 つまり、 (VLA が絡むときに例外はあるが) コンパイル時に確定する値である。
- `data[i]` という形でのアクセスは `*(data+i)` の構文糖である。
- 配列が式に現れたときはその配列の先頭要素を指すポインタへ暗黙に型変換される。
- ただし、配列型が現れるのが単項 `&`、もしくは `sizeof` のオペランドであるときには暗黙の型変換の例外である。

というものがあります。

たとえば `int foo[3][5];` という形で `foo` が宣言されているとき `foo[0]` とアクセスするとこの型は `int[5]` となり、暗黙の型変換のルールで `int*` の値になります。

そして `int *bar[3]` という形で `bar` が宣言されているとき `foo[0]` とアクセスすると要素の型は `int*` ですからそのまま `int*` の値が返ってきます。

二次元配列とジャグ配列が同じ文法で要素にアクセスできるのは暗黙の型変換の作用なのです。

しかし、 `sizeof` のオペランドとしては現れる場合には暗黙の型変換は働きませんから `sizeof(foo[0])` は `sizeof(int[5])` に等しく、 `sizeof(bar[0])` は `sizeof(int*)` に等しくなってしまいます。

ジャグ配列は要素にアクセスするときに二次元配列と同じ文法を使えますが、二次元配列ではない (少なくとも言語仕様上の用語法では) ので質問者は何か根本的なところで思い違いをしているように思います。

Answer

> パターン①の場合は二次元目の要素は存在しないのでしょうか？ 

二次元の要素ってのがいまいち不明ですが、Linkは初期化されてませんね

関連した質問