C言語の構造体についてなんですが。

質問

struct LIST {
　　　　struct Num* number;
　　　　struct LIST* next;/* 次の要素へのポインタ */
}*root;

struct Num{
　　　　int a;
　　　　struct Num* next; /* 次の要素へのポインタ */
}*numroot;

と構造体を定義したときに、

main(){
　　　　struct LIST *p;
　　　　for(p = root; p != NULL; p = p->next) ;
}

とすれば、pの先頭からNULLまでを参照していくことは分かるんですが、pのnumberの先頭からNULLまでの参照方法(プログラムのfor文の記述方法)がイマイチわかりません。つまり、構造体の構造体をどのように参照するかということです。

これを実現したい理由は、構造体内での数の格納を配列(固定長)ではなく可変長で格納したいからです。

分かる方は解答をお願いします。

回答No.2

hanabutako · ベストアンサー

こういうことを聞いていますか？
int
main(void)
{
　　　　struct LIST *p;
　　　　struct Num *q;

　　　　/* make the list structure some how */

　　　　for (p = root; p != NULL; p = p->next)
　　　　　　　　for (q = p->number; q != NULL; q = q->next) {
　　　　　　　　　　　　/* do something */
　　　　　　　　}

　　　　return 0;
}

余談ですが、「構造体内での数の格納を可変長で格納したい」という要求だけなら配列を動的に割り当てるという実装もあります。数を格納するためのオーバヘッドはこちらの方が少ないですし、ポインタの操作をあまりゴリゴリしないでいい分だけバグを作りにくいというメリットがあります。その反面、格納している配列を縮小したいときに再度メモリーを割り当てて移し変えるという面倒くさいことをしないといけなくなるという欠点もあります。また、リストを使う典型的な理由として要素の順序を自由に入れ替えたいというのもあると思いますが、配列を使うとこの点も不利ですね。

お礼

まさにそうです。スミマセン分かりにくい説明で。回答を読んで解決できました。

迅速かつ親切な回答ありがとうございました。

そういえば余談を見て、昔授業で配列の動的割り当てについてやったのを今思い出しました(＾＾;)

回答No.5

正親町（@Ohgimachi）

＃３です。
コピーミスです。

if((p=(LIST *)malloc(…))=NULL) return NULL;
root.last->next = p;
root->last = p;
return p;
は
if((p=(LIST *)malloc(…))=NULL) return NULL;
root.last->next = p;
root->last = p;
p->next = &root.LIST;//追加
return p;

リング構造にするとよい場合が多いのは、リストを検索する場合
終端をNULLにするとループ内での条件判定が２回になります。

for(p = root->next;p != NULL;p=p->next)
if(検索条件と一致) break;
return p;

リング構造にすると、ループ内での条件判定が１回で済みます。

rootを検索条件と一致するように書き換える。
for(p = root.next;検索条件と一致しない;p=p->next)
;
return root ? NULL : p;

リストの数が多い場合に、実行速度に差がでます。

Tacosanへ
構造体の中にポインタとして宣言した場合と配列と宣言した場合では、
C言語の書き方は同じでも、実行速度が異なります。
以下のようにaの11番目のデータにアクセスする場合、
ポインタでも配列でも同様に以下のように書けますが
p->a[10]

(1)配列と宣言した場合。
他の構造体のメンバーと同様に、
p+[オフセット]
でアクセス可能。32bitのCPUの場合
p+[8+40]

(2)ポインタで宣言した場合
同様に32bitとすると
aの値を読み込む
a=p+[8]
次に
a+[40]
とアクセスする。

ということで、ポインタにすると
メモリアクセスが一回増える
ということです。

回答No.4

Tacosan

今の C なら
struct List {
struct List *next;
int size;
int a[];
};
として
struct List *p = malloc(sizeof *p + sizeof *p->a * size);　p->size = size;
のようにするのがより適切でしょう＞#3. 構造体の最後のメンバに限り「大きさを明示しない」ことが可能になっています.

回答No.3

正親町（@Ohgimachi）

配列を使った大きさの異なる構造体を動的に割り付ける方法は
以下の２つの構造体を統合して

struct LIST {
struct Num* number;
struct LIST* next;/* 次の要素へのポインタ */
}*root;

struct Num{
int a;
struct Num* next; /* 次の要素へのポインタ */
}*numroot;

このようにします。
struct LIST {
struct LIST* next;/* 次の要素へのポインタ */
int cont; /*配列の要素の数*/
int a[1]; /*配列の実態*/
};

配列のサイズをnとすると
LIST *list;
list->next=malloc(sizeof(*list->next)+sizeof(list->a[0])*(n-1));
list->cont = n;
のように動的にメモリ領域を確保します。
リンクリストの構造体の大きさがことなるパターンは
頻繁に存在します。

また、rootを次のように設定してリング構造にすると
static struct {
LIST list;
List *last; /*終端へのポインタ*/
} root = {{&root.list, -1, 0}, &root.list};

もっとも頻繁に実行されるリストの追加が高速化できます。
LIST *p;
if((p=(LIST *)malloc(…))=NULL) return NULL;
root.last->next = p;
root->last = p;
return p;

終端のリストかどうかの判定は
if(list->next.cont < 0)
//リストの終端

削除は、lastの処理が増えます。
削除や移動を頻繁に行うのであれば
双方向リンクが圧倒的に高速です。
LIST *list; //削除するリスト
LIST *p;
if((p = root.next) == &root) return -1;//リンクが空かどうかの判定
while(p->next != list) //自分自身を参照しているリストを探す
p = p->next;

p->next = list->next;
if(root.last == list) root.last = p->next;
free(list);
return 0;

回答No.1

Tacosan

「pのnumberの先頭からNULLまでの参照」とはどういうことでしょうか?
リンクリストをたどるだけなら, 何も困ることはないと思うんだけど. p->number でリストの先頭要素がわかるよね.

補足

はい、そこはわかるんですが、p->numberの先頭要素からNULLまでのfor文の条件をどのように書くのかって部分でちょっと困ってます。

main(){
　　　　struct LIST *p;
　　　　for(p = root; p != NULL; p = p->next){
　　　　　　for(?){
　　　　　　　　printf("%d\n",p->number->a);
　　　　　　}
　　　　}
}

というように書いたときに、「？」部分をどのように書けばいいのかで困ってます。