自己参照型構造体の配列

Question

###自己参照型構造体の配列は可能か？

自身と同じ型を持つ構造体同士を
繋ぎ合わせるために必要なのが
自己参照型構造体ですが、
それを宣言する際についての質問です。

該当のソースコード

typedef struct node {

  int ID;
  struct node*Link[ ];

}NODE;

????上記のように、自己参照型構造体を**「配列」**として宣言するのは規格に反するのでしょうか？

試したこと

とりあえず上記のように宣言した上で
作業を進め、コンパイルを実行すると何も起きずそのままプログラムが終了します。(エラーメッセージなし)

Comments

[int32_t]

コンパイルエラーの場合はエラーメッセージを必ず書いてください。

[Egg-Man]

承知致しました。

Answer 1

[]の中に配列の要素数を書けば問題ないです。

構造体の末尾のメンバーの場合は、要素数を書かない[]のままでも文法的にはOKですが、可変配列メンバーとなり、NODEへのポインターを宣言してmallocで必要サイズを割り当てるという使い方になります。

Comments

[Egg-Man]

ご回答ありがとうございます。

「構造体の末尾のメンバーの場合は、要素数を書かない[]のままでも文法的にはOK」

↑については、
初めて知ることができました。
構造体、奥が深いですね(　ﾟдﾟ)

Answer 2

要素数不定(0)の配列が構造体メンバの最後にひとつだけであれば(ちゃんと書けば)無問題。

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int ID;
  int size;
  struct node* Link[0];
} NODE;

NODE* allocate(int id, int size) {
  NODE* ptr = (NODE*)malloc(sizeof(NODE)+sizeof(NODE*)*size);
  if ( ptr ) {
    ptr->ID = id;
    ptr->size = size;
    for ( int i = 0; i < size; ++i ) ptr->Link[i] = NULL;
  }
  return ptr;
}

void print(const NODE* node) {
  printf("ID:%d Link:", node->ID);
  for ( int i = 0; i < node->size; ++i ) {
    printf("%p ", node->Link[i]);
  }
  printf("\n");
}

int main() {
  NODE* p = allocate(123, 4);
  print(p);
  free(p);
  return 0;
}

Comments

[Egg-Man]

コードまで丁寧に書いて頂き、
有り難うございます。

NODE* ptr = (NODE*)malloc(sizeof(NODE)+sizeof(NODE*)*size);

????このように、sizeof演算子を連続で使う方法は思いも及びませんでした。
驚きと発見で感無量です( ´ ▽ ` )

[episteme]

要は構造体の総サイズを求めてるだけですから。

[Egg-Man]

すいません、少し腑に落ちない点がありまして....

例えば、

NODE* ptr = (NODE*)malloc(sizeof(NODE)+sizeof(NODE*)*3);

とした場合は

ptr->Link[0],
ptr->Link[1],
ptr->Link[2],

の3つなのか、それとも

ptr->Link[0]->Link[0],
ptr->Link[0]->Link[1],
ptr->Link[0]->Link[2],

のようなイメージでいいのか、どちらが正しい認識なのでしょうか？

[episteme]

typedef struct node {
int ID;
int size;
struct node* Link[3];
} NODE;

と同義です。

Answer 3

配列サイズが固定ではないなら、構造体の定義ではサイズが決まらないといけないので、0サイズの配列として定義するか、ポインタの配列を動的に確保します。

配列サイズのメンバーを足す必要もあるでしょうね。

typedef struct node {
  int ID;
  struct node* Link[0];
} NODE;

// 配列がN要素のときの確保
NODE* p = (NODE*)malloc(sizeof(NODE) + sizeof(NODE*) * N);

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

// 配列がN要素のときの確保
NODE* p = (NODE*)malloc(sizeof(NODE));
p->Link = (NODE**)malloc(sizeof(NODE*) * N);

Comments

[Egg-Man]

なるほどです。
凄く分かりやすく、有難うございます。

ちなみになんですが、
1つ目の回答における

malloc(sizeof(NODE) + sizeof(NODE*) * N);

の箇所を初めて見ました。
この場合の「sizeof(NODE*)*N」
の部分は、構造体メンバ変数のint型ID
のサイズは確保しない、との認識で正しいでしょうか？

[int32_t]

そうですね。IDは前半の sizeof(NODE) に含まれていて、後半の sizeof(NODE*) * N は Link のぶんだけです。

[Egg-Man]

そういうメモリの確保法があったなんて凄い！！感動です。
有難うございます。

[Egg-Man]

すいません、まだ少し腑に落ちない点がありまして....

例えば、

NODE* p = (NODE*)malloc(sizeof(NODE)+sizeof(NODE*)*3);

とした場合、

p->Link[0],
p->Link[1],
p->Link[2],

の3つなのか、それとも

p->Link[0]->Link[0],
p->Link[0]->Link[1],
p->Link[0]->Link[2],

のようなイメージでいいのか、
どちらが正しい認識なのでしょうか？

Answer 4

自己回答ではなく、回答予想になっていたため削除しました。

Comments

[int32_t]

これは回答ではないので、質問文に追記してください。