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

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になる

Comments

[dodox86]

何となく

> Link[0]〜Link[4]には、それぞれ第二の要素「Link[ ][0]」を含んでいる事は理解してますが、

誤解されているというか、前提が変な気もしますが、パターン②は、NODE自体のポインタ、"要素数5の配列を常に持った"構造体ですがそのあたりは想定したものでしょうか。Linkとして適当か？ということですが。こんな結果になります。
$ cat t2.c
#include <stdio.h>

#pragma pack(1)
typedef struct node {
int ID;
struct node *Link[5];
} NODE;

int main() {
NODE node;
NODE *pnode;
printf("sizeof NODE=%d, sizeof pnode=%d, sizeof ID=%d, sizeof Link=%d\n",
(int)sizeof(NODE), (int)sizeof(pnode), (int)sizeof(node.ID), (int)sizeof(node.Link));
}

$ gcc -Wall t2.c
$ ./a.out
sizeof NODE=44, sizeof pnode=8, sizeof ID=4, sizeof Link=40
$

[Egg-Man]

> パターン②は、NODE自体のポインタ、"要素数5の配列を常に持った"構造体ですがそのあたりは想定したものでしょうか

はい(^^)
要素数5のポインタ配列に、それぞれ

p->Link[ i ] = (NODE*)malloc(sizeof(NODE));

とすることで、5つのポインタ配列各々に「ポインタを格納する領域」ではなく「データ(値)を格納する領域」を確保したつもりです(*^_^*)

sizeof演算子の使い方、参考にさせて頂きます????
有難うございますm(._.)m

[dodox86]

> p->Link[ i ] = (NODE*)malloc(sizeof(NODE));

で確保した領域にも、struct node *Link[5];のポインタ配列がそれぞれありますけど、無駄な気がしますし何か変な気もしますがよいのですか？という確認でした。それでよいのであれば構いません。

[Egg-Man]

話が逸脱してしまうのですが、実は今,複数の子ノードを持つ木構造を作成中で、ポインタ配列Link[ ]に、各々の子ノードのポインタを格納しようと試みていて..
それを再起処理によって実現したく、
p->Link[ ] = malloc
と無駄に「値を格納する領域」メモリまで確保しないと、なぜかプログラムが上手く作動しなくて(;o;)

[actorbug]

1.最終的に、どのような構造を作りたいのでしょうか。
　各NODEの子供は、1次元の配列と2次元の配列のどちらでしょうか。
　それぞれの配列のサイズは固定でしょうか可変でしょうか。
　作りたいのが1次元配列の場合、なぜ2次元配列の話がでてくるのでしょうか。
2.②の何が不満なのでしょうか。
　Linkの配列の各要素に対してmallocしなければならないことでしょうか。
　①のような感じで、一回のmallocでLinkの配列の各要素の分までメモリを確保できる方法を知りたいのでしょうか。

[Egg-Man]

1.
いわゆる、ミニマックス法で用いるゲーム木です。場合分けが多くなるほど、子ノードの数も増えるため、配列は可変にします。

本当は、
p->Link[0] = 子ノード0、
p->Link[1] = 子ノード1、
p->Link[2] = 子コード2、
と直接代入したいのですが、子ノードの数も可変なので、新たな場合分けが生じた際に新しく子ノードを生成します。
つまり、
p->Link[ ] = malloc とした上で、
再起関数の引数に↑新しく生成した、子ノードを入れます。

2.
不満ではないのですが、腑に落ちない点がありまして...

例えば、
p->Link[0] = (NODE*)malloc(sizeof(NODE)*3)
とした場合、
ポインタ配列Link[0]は、
Link[0][0],Link[0][1],Link[0][2]
の3つの配列を持つことになるのかどうかが知りたくて。

[rubato6809]

> 3つの配列を持つことになるのかどうかが知りたくて

そういう疑問なら新たな質問を立てたほうが良いのでは。ひとつの質問からこまごまとした疑問に展開したい気持ちはわかるけど、答えるほうは困るし、貴方の整理も回り道になってるような気がする。
データ構造を設計する段階で、その下回りの技法を整理したいわけでしょ？

もう一つの問題。親ノードにつながる子ノードの個数をあらかじめ決められないらしいけど、それが一次元でN個欲しいのか（Nは可変）、二次元でN＊M個ほしいのか（NもMも可変？）もスッキリしない。

[Egg-Man]

『rubato6809』さん

> そういう疑問なら新たな質問を立てたほうが良いのでは

おっしゃる通りです。
すいません????
情報が散乱してますね(^_^*)