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

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』さん

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

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

Answer 1

Cの仕様としては、①は、文法エラーです。
まずは、ANSI C 89 でサイズ０の配列を作ることはできません。
gcc がサイズ０の配列メンバを作る方法として採用していたので、
gcc の書式をトレースする処理系では拡張仕様としてコンパイルできます。

ANSI C99からは、
struct node *Link[];
の様にサイズを記入しない事によって、サイズ 0 の配列メンバが作れます。
これは、ANSI C89のころ サイズ０のメンバを作る方法で、
MSC が採用していた方法で、ANSI C99 からこれが採用されました。

どのように使うかは、malloc で、サイズ 0 のメンバから始まる
いくつかのデータを計算するなりして、malloc で、余分な領域を確保し、
その余分な領域にデータを置くようにします。

追加：
なお、struct node Link[] も、struct nodeLink[5];　も、２次元配列ではありません、ポインタ配列です。

Comments

[Egg-Man]

詳しい解説ありがとうございます。

> なお、struct node *Link[] も、struct node*Link[5];　も、２次元配列ではありません、ポインタ配列です。

そのことに関しては理解しているのですが、例えば以下のように↓

for(int i = 0; i<5; ++i) {
p->Link[ i ] = (NODE*)malloc(sizeof(NODE)*3);
}

と、ポインタ配列の各要素においてmallocを使用し領域を確保した場合、

Link[0][0],Link[0][1],Link[0][2],
Link[1][0],Link[1][1],Link[1][2],
•••••••

のように、二次元配列を持つのかどうかが、いまいち分からなくて(^_^*)

Answer 2

関連するルールとしては

• 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 3

「第二の要素」「二次元目の要素」というのが何なのかはっきりしませんが、p->Link[0から4] に何か入っているのかという観点では、①も②も、pの初期化直後は何も代入していないのでデタラメな値が入っていて使えません。

②はp->Link[]に確保したメモリのポインタを代入しているからNODEを指すようになります。①も同じようにポインタを代入すれば同じように動きます。①と②は最初のmalloc()のパラメータが違うだけで、それ以外の使い方は同じです。

sizeof 演算子はコンパイル時に決まる型のサイズを返します。sizeofがこの質問に役に立つかどうかは怪しいです。

---

質問文へのコメントを読むと、本当に欲しいものは動的に子供ノードの数が変更できるツリーのようです。

typedef struct node {
 int id;
 size_t children_size;
 struct node* children;
} NODE;

コンパイル時固定サイズの配列やメモリ確保時にサイズが決まる配列では子供ノードの数の変更ができないので、malloc()やrealloc()で確保した1次元配列へのポインタをメンバに入れるとよいかもしれません。

Comments

[Egg-Man]

> 「第二の要素」「二次元目の要素」というのが何なのかはっきりしませんが、

二次元配列[X][Y]においての、[Y]に相当する部分です。

> ①も同じようにポインタを代入すれば同じように動きます

①のままでは、p->Link[ ][ ]のように二次元配列として扱えないのでしょうか？

[int32_t]

NODE型は、通常はツリー構造を表現するでしょう。
2次元配列相当の使い方はできないこともないですが、そうとう変です。

[int32_t]

> ①のままでは、p->Link[ ][ ]のように二次元配列として扱えないのでしょうか？

①も②も p->Link[n][m] のようには使えないですよ。①も②も p->Link[n]->Link[m] のように使えます。①と②は最初のmalloc()のパラメータが違うだけで、それ以外の使い方は同じです。

[Egg-Man]

例えば、

int*data[5];

for(int i = 0; i<5;++i)
data[ i ] = (int*)malloc(sizeof(int)*3);

とした場合は、
data[0][0],data[0][1],data[0][2],
data[1][0],data[1][1],data[1][2],
•••••

のように、変数dataは二次元配列として扱えるとの情報を以下のサイトで拝見したんですが、構造体の自己参照型においては、上記のような話とは別なのでしょうか？
https://daeudaeu.com/2d_data/

[int32_t]

まあ確かに p->Link[i] に sizeof(Node) * 3 の領域を入れれば p->Link[i][1] みたいに使えますが、「2次元に広がっていく木」なんて複雑な構造が本当に必要なのですか?

現状の質問文に対する回答は「①と②は最初のmalloc()のパラメータが違うだけで、それ以外の使い方は同じです。」で終わりだと思います。

質問文へのコメントから想像すると、1つの親ノードの子ノードの数も動的に変わるようなので、

typedef struct node {
int ID;
struct node* children;
} NODE;

にして、children には malloc() や realloc() で確保した1次元配列を入れる、でいいんじゃないでしょうか。

[Egg-Man]

なるほどですっ！！！????(*ﾟ▽ﾟ*)
今ようやく、核心を得ました！
自己参照型をポインタ配列にしていたことから混乱していたんだと気付きましたw
心から深く感謝致します。????‍♂️

あ、あと最後に1つ質問宜しいでしょうか。先程のコメント↓

> ①も②も p->Link[n][m] のようには使えないですよ。①も②も p->Link[n]->Link[m] のように使えます

という部分で疑問に感じたんですが、
p->Link[n][m]、
p->Link[n]->Link[m]、
これら2つは同等ではないのでしょうか？

[int32_t]

> これら2つは同等ではないのでしょうか？

違いますね。p->Link[n] に NODE m個以上の領域が代入されているとすると、
p->Link[n][m] は、pの2次元の子供の1つで、座標が (m, n)
p->Link[n]->Link[m] は、p->Link[n][0].Link[m] と同値で、pの孫へのポインタです。

[Egg-Man]

分かりやすい説明有難うございます。
っということは、

for(int i = 0; i<5;++i)
p->Link[n] = (NODE*)malloc(sizeof(NODE)*m);

の場合、

> ①も②も p->Link[n][m] のようには使えないですよ。①も②も p->Link[n]->Link[m] のように使えます。

> まあ確かに p->Link[i] に sizeof(Node) * 3 の領域を入れれば p->Link[i][1] みたいに使えますが

↑以前のコメントを参考にさせて頂くと、
p->Link[n][m]、
p->Link[n]->Link[m]、
の2つ両方が存在しているとの認識で正しいですよね(^｡^)

Answer 4

パターン①の場合は二次元目の要素は存在しないのでしょうか？

二次元の要素ってのがいまいち不明ですが、Linkは初期化されてませんね

Comments

[Egg-Man]

>二次元目の要素
二次元配列[x][y]の場合の、[y]に該当する部分です。

分かりづらい説明ですいません。

[y_waiwai]

どこにもそのような配列宣言している箇所は見当たりませんが

[Egg-Man]

例えば、

int*data[5];

for(int i = 0; i<5;++i)
data[ i ] = (int*)malloc(sizeof(int)*3);

として定義すれば、data変数は二次元配列として扱えられるそうです♪ (メモリ領域の確保の仕方は違いますが)

参考までに↓
https://daeudaeu.com/2d_data/

[y_waiwai]

①とはまったくちがうんですがそれは。
あなたがそうおもうならそういうことなんでしょうね、としか言いようがないですね。

[Egg-Man]

おっしゃる通りです。
先程の例は、②のことです。

しかし、①のp->Link[ ]においても、②と同様に二次元配列として扱えるのだろうか...というのが質問の意図です。