リス;ト構造のポインタ

質問

struct list{
int data;
struct list *next;
};
struct list *cons(int x,struct list *n){
struct list *ans;
ans=(struct list*)malloc(sizeof(struct list));
if(ans!=null)
ans->date=x;
ans->next=n;
}
return ans;}

void main(){
int x;
struct list *top=NULL;
struct list **tail=⊤
while(scanf("%d",&x)==1){
*tail=cons(x,NULL);　
tail=&((*tail)->next):　　　　　　　　
}　

入力した順にリストに追加されるプログラムらしいのですが、void main(){}の中のプログラムの動きが
よく分かりません。このプログラムの動作の流れを簡単に教えてください。漠然とした質問カと思いますが
よろしくお願いします。

回答No.6

lailai2580

mainで行われていることを簡単な図にしてみました。
1,2,3,…という順で入力したと仮定します。
topとtailの位置は現在指している所です。

NULL
top

NULL
top
tail

1回目のループ

(1) ⇒ NULL
top
tail

(1) ⇒ NULL
top　　tail

2回目のループ

(1) ⇒ (2) ⇒ NULL
top　　tail

(1) ⇒ (2) ⇒ NULL
top　　　　　 　tail

3回目のループ

(1) ⇒ (2) ⇒ (3) ⇒ NULL
top　　　　 　tail

(1) ⇒ (2) ⇒ (3) ⇒ NULL
top　　　　　　　　　　tail

以降同じように続くと思います。

お礼

わかりやすい説明有難うございました

回答No.5

ency

まず、cons() で何をやっているのかはお分かりですか？

1. リンク構造体を生成。
2. 引数で渡された数値でメンバ変数 data を初期化。
3. 引数で渡されたリンク構造体を指すポインタでメンバ変数 next を初期化。
4. 初期化済みリンク構造体を指すポインタを返す。

と、こんな感じでしょうか。

で、main() の方でやっている処理ですが、こんな感じでしょうか。

1. キーボードから数字を入力。
2. cons() でリンク構造体を生成。
　ここでキーボードから入力した数字と NULL ポインタを初期値として与える。
　cons() の戻り値を *tail に格納する。
　# tail ではなく、*tail であることに注意。
3. tail を置き換える。
　# この置換えで、リンクが次々続いていきます。
4. 数値以外が入力されるまで 1～3 を繰り返す。

と、ここまではよろしいでしょうか。

では、実際の変数の動きを見ていきます。

--------------------------------------------------------
1. tail = ⊤

2. *tail = cons(x,NULL);
⇒ top = cons(x,NULL); と等価。
　　つまり、cons() で生成したリスト構造体を指すポインタが top に入る。
　ちなみに、この時点では top->next == NULL。

3. tail = &((*tail)->next);
　⇒ tail = &(top->next); と等価。
　　つまり、「2 で生成したリスト構造体 (を指すポインタ==top ですよね？)」の next を指すポインタが tail に入る。

4. *tail = cons(x,NULL);
　⇒ top->next = cons(x,NULL); と等価。
　ちなみに、この時点で (top->next)->next == NULL。

5. tail = &((*tail)->next);
　⇒ tail = &((top->next)->next); と等価。
　　つまり、「4 で生成したリスト構造体 (を指すポインタ==top->next ですよね？)」の next を指すポインタが tail に入る。

6. *tail = cons(x,NULL);
　⇒ (top->next)->next = cons(x,NULL); と等価。
　ちなみに、この時点で ((top->next)->next)->next == NULL。

…… (以下省略。。。)

--------------------------------------------------------

こんな感じで処理が進んでいくわけです。
つまり、リンクされていく段階で最後のリスト構造体の next は常に NULL で初期化されているわけです。

で、値を順次参照していく場合には、

top->data
(top->next)->data
((top->next)->next)->data
……
とリスト構造体の next == NULL になるまで続ければ良いわけで、ということはどうすれば良いかはお分かりですね。

こんな感じでいかがでしょうか。

お礼

レスが遅れて申し訳ありませんでした
分かりやすい説明有難うございました

回答No.4

hankyo

連結されていないと思いましたが、されてる見たいですね。。。
tailが一つ前の構造体のnextの参照位置を示しているのが、ポイントですね。

スレ汚し失礼しました。

回答No.3

hankyo

連結されていないと思いますが。。。

while文の中で一個前のstruct listへのポインターを持つ変数と、初めの一個目の構造体はwhile()の外で作る必要があると思います。

回答No.2

xcrOSgS2wY

なかなかいい線を来ています。考え方はしっかり合っています。

(*1)　　*tail=cons(x,NULL);
(*2)　　tail=&((*tail)->next):

のところが分かりづらいですよね。これは例題の出来が悪いせいですから、気に病む必要はありません。

さて肝心のリスト構造（順番に連結された構造）を作成している場所ですが、ちゃんと(*1)と(*2)で連結しています。（cons関数に渡しているNULLは単なる目くらましで、データを連結する役には立っていません。）

(*1)と(*2)で行っていることは、こういうことです。

(*1): cons関数が返す「構造体へのポインタ」（cons関数がmallocで取得したメモリへのポインタ）を「tailが指す変数」に格納する。

(*2): 「tailが指す変数の値」（すなわち、(*1)でcons関数が返した「構造体へのポインタ」）が指す構造体のメンバ変数next、へのポインタを変数tailに格納する。

「tailが指す変数」は最初はtopですが、2回目以降は「リスト構造の最後の構造体の中にあるメンバ変数next」であることに注意してください。

また、ループを回るごとにリストに構造体がどんどん追加されるので、「リスト構造の最後の構造体」はループを回るごとに変化します。

すごーく分かりづらいと思いますが、何となく意味が掴めるでしょうか。

補足

やっぱりtail=&((*tail)->next)が良く分からないんので、連結が良くわからないんですけど、ポインタのポインタ構造体tailっていうのはポインタの構造体topに対応させると
**tail=*top　、*tail=&topに対応するんでしょうか？
それならtail=&((*tail)->next)のtailが何を示して
いるのか良く分からないんです。又、=&((*tail)->next)はループが一回目の場合(*tail)->nextの指している物(=null？）のアドレスってことでしょうか？
最後にもう一つ、このプログラムを表示させる場合は
for(struct list *p=top;p!=null;p=p->next)
printf("%D",p->date);
でokなんでしょうか？

ゴチャゴチャしてて読みにくいと思いますが、よろしくお願いします。

回答No.1

xcrOSgS2wY

どこまで分かっているのか書いてもらえれば、説明するのが楽になるので助かるのですが。

まず変数の内容を紙に書き出して、1行ずつ順を追って動作を確認してみてください。3回くらいループしてみてください。

その上で、分かったことと分からないことを箇条書きに書いてみてください。そうしてもらえれば答えやすいです。

補足

全体的に間違ってそうなんですけど
一回目のループの場合は
>struct list *top=NULL;
構造体のポインタtopのアドレスをNULLにする

>struct list **tail=⊤
　構造体のポインタのポインタtailのアドレスをtopの
　アドレス=NULLにする

>while(scanf("%d",&x)==1){
　入力された値が一つならループする

>*tail=cons(x,NULL);
　構造体のポインタのポインタtailにxの値と、
　次の場所(=NULL)を入れる。またtopのアドレスが
　かわる？
>tail=&((*tail)->next):
　ここの記述が良く分かりません、一応書いてみると
　構造体のポインタのポインタtailの次のデータの
　場所=NULLをtailのアドレスとする？　　　　　　
}　

３回ほどループして見たんですけど、入力される値のつながりがない(リストになっていない）ような気がします。