チェーンの解釈について

parapara · #1

独学で勉強してる者ですが、又分からない事が出てきており、困っております。
下記の状態なんですが,ご助言お願いします一方向チェーンなんですが。

#include<stdio.h>         //一方向チェーン
#include<stdlib.h>
#include<string.h>
typedef struct person{
	char name[20];
	int age;
	struct person *next;
}Person;
int main(void){
	Person dmy={"",0,NULL};
	Person *start=&dmy;
	Person *wkdtp;
	Person *ip;
	char name[20],age_ss[6];
	while(1){
		printf("名前=");gets(name);
		if(strcmp(name,"")==0)break;
		printf("年齢=");gets(age_ss);
		wkdtp=(Person *)malloc(sizeof(Person));
		if(wkdtp==NULL){
			printf("メモリ確保できません\n");
			exit(EXIT_FAILURE);
		}
		strcpy(wkdtp->name,name);
		wkdtp->age=atoi(age_ss);
		for(ip=start;ip->next!=NULL;ip=ip->next){
			if(wkdtp->age < ip->next->age){
				wkdtp->next=ip->next;
				ip->next=wkdtp;//*********ここ***********//
				break;
			}
		}
		if(ip->next==NULL){
			ip->next=wkdtp;
			wkdtp->next=NULL;
		}
	}
	for(ip=start->next;ip!=NULL;ip=ip->next){
		printf("%10s %3d\n",ip->name,ip->age);
	}
	return(EXIT_SUCCESS);
}

ip->next=wkdtp;だと前と次の間に新たにチェーンを埋め込もうとしてるのは分かるんですが、
でもこれだと、ip->nextだけじゃなく、ip->nextが表しているポインタも変わってしまうのではないかと思うのですが、
つまりwkdtpという先頭アドレスをもつ構造体(入ってきたのと次の二つ)が２個できてしまう。うまく説明できなくてすいません。

box · #2

こんな絵でご理解いただけるでしょうか。

【リンクの付け替え前】

    ip                               ip->next
+--------+                          +--------+
|        | -----------------------> |        |
+--------+                          +--------+

                    wkdtp
                  +--------+
                  |        |
                  +--------+



【リンクの付け替え操作（その１）】
wkdtp->next=ip->next; の実行

    ip                               ip->next
+--------+                          +--------+
|        | -----------------------> |        |
+--------+                     +--> +--------+
                               |
                    wkdtp      |
                  +--------+   |
                  |        | --+
                  +--------+



【リンクの付け替え操作（その２）】
ip->next=wkdtp; の実行

    ip
+--------+                          +--------+
|        | --+                 +--> |        |
+--------+   |                 |    +--------+
             |                 |
             |      wkdtp      |
             |    +--------+   |
             +--> |        | --+
                  +--------+

parapara · #3

返信ありがとうございます。
(その１)で一番右の奴がip->nextじゃないですか、
それもwkdtpには変わらないんでしょうか？
つまり下の図のように。それともアドレスはmallocにより固定的に
決まるから、変更不可能で変更しようとしても、何も起きないということでしょうか？
凄いお馬鹿な質問だったらごめんなさい。

【リンクの付け替え操作（その２）】
ip->next=wkdtp; の実行

    ip                                wkdtp
+--------+                          +--------+
|        | --+                 +--> |        |
+--------+   |                 |    +--------+
             |                 |
             |      wkdtp      |
             |    +--------+   |
             +--> |        | --+
                  +--------+

box · #4

> (その１)で一番右の奴がip->nextじゃないですか、
> それもwkdtpには変わらないんでしょうか？

変わらないです。
wkdtpという、今回リスト構造に加えたい領域に対しては、
１）wkdtpから出て行くリンク
２）wkdtpに入ってくるリンク
の２本を適切につなぐ必要があります。

１）今回は、もともとの ip と ip->next との間に wkdtp をつなぎたいので、
wkdtp の次（つまり wkdtp->next）は、（もともとの）ip->next となります。
これが、
wkdtp->next = ip->next;
という文と対応します。

２）今回は、もともとの ip と ip->next との間に wkdtp をつなぎたいので、
ip の次（つまり、新しい ip->next）は、wkdtp となります。
これが、
ip->next = wkdtp;
という文と対応します。

なお、今回の図のような内容を貼り付ける際は、
図の前後を＜pre＞と＜/pre＞タグ（カッコは半角）ではさんで、
レイアウトが崩れないようにしてください。
これらのタグではさまなかった場合、ブラウザは複数の空白を１つの空白と
みなしてしまい、レイアウトが崩れます。

parapara · #5

変わらない理由が知りたいんですが、駄目でしょうか？

box · #6

> 変わらない理由が知りたいんですが、駄目でしょうか？

リンクの付け替え操作は２段階に分かれています。
１段階目：今回リスト構造に挿入したい wkdtp から出て行くリンクを設定する
２段階目：wkdtp に入ってくるリンクを設定する

ここまではいいですか？

parapara · #7

はい、それは分かるんですが、余分な動作ip->nextで
示される構造体のポインタが変わらない理由がしりたいんですが。
訂正したんですが、念のためもう一度書きます。しつこくてすいません。
 Re:チェーンの解釈について      
 返信ありがとうございます。
(その１)で一番右の奴がip->nextじゃないですか、
それもwkdtpには変わらないんでしょうか？
つまり下の図のように。それともアドレスはmallocにより固定的に
決まるから、変更不可能で変更しようとしても、何も起きないということでしょうか？

【リンクの付け替え操作（その２）】
ip->next=wkdtp; の実行

    ip                                wkdtp
+--------+                          +--------+
|        | --+                 +--> |        |
+--------+   |                 |    +--------+
             |                 |
             |      wkdtp      |
             |    +--------+   |
             +--> |        | --+
                  +--------+

Hermit · #8

box さんの図を、ちょっと変更させてもらって、書いてみる。

【リンクの付け替え前】

ip ipNext
+-----------------+ +---------+
|ip->next = ipNext| --------------------------> | |
+-----------------+ +---------+

wkdtp
+--------------------+
|wkdtp->next = 未設定|
+--------------------+

【リンクの付け替え操作（その１）】
wkdtp->next=ipNext; の実行

ip ipNext
+-----------------+ +---------+
|ip->next = ipNext| --------------------------> | |
+-----------------+ +--> +---------+
|
wkdtp |
+--------------------+ |
|wkdtp->next = ipNext|---+
+--------------------+

【リンクの付け替え操作（その２）】
ip->next=wkdtp; の実行

ip ipNext
+----------------+ +--------+
|ip->next = wkdtp|--+ +--> | |
+----------------+ | | +--------+
| |
| wkdtp |
| +--------------------+ |
+-->|wkdtp->next = ipNext|--+
+--------------------+

box · #9

> はい、それは分かるんですが、余分な動作ip->nextで
> 示される構造体のポインタが変わらない理由がしりたいんですが。

余分な動作は、何もありません。リンクを張り替えるために必要かつ不可欠な動作です。
先ほど書いた１段階目から、もう一度説明します。

１段階目：今回リスト構造に挿入したい wkdtp から出て行くリンクを設定する 

    ip                               ip->next
+--------+                          +--------+
|        | -----------------------> |        |
+--------+                     +--> +--------+
                               |
                    wkdtp      |
                  +--------+   |
                  |        | --+
                  +--------+

１段階目が終わった時点では、上図のようになります。
つまり、「そのときの」ip->nextが、wkdtpの「次」に来るようにしなければなりません。
そこで、ip->nextの値を、wkdtp->nextに代入します。
式で書くと、
wkdtp->next = ip->next;
です。
１段階目は、これで終わりです。ここまでは、いいでしょうか？

Hermit · #10

変になってる・・・削除が効かない

管理人さん・・・削除して(;_;)

parapara · #11

はい、ここまでは大丈夫です。ここの時点で一番右の奴がip->nextなのに、
次の操作でwkdtpに変わらないのが疑問なんです。
すいません、迷惑をおかけして。

box · #12

> はい、ここまでは大丈夫です。ここの時点で一番右の奴がip->nextなのに、
> 次の操作でwkdtpに変わらないのが疑問なんです。

リンクの張り替えの２段階目です。
２段階目：今回リスト構造に挿入したい wkdtp に入ってくるリンクを設定する

１段階目が終わった時点では、そのときの ip->next に向かっているリンクが２本あります。
ip から出ているリンクと wkdtp から出ているリンクです。
リンク張り替えの２段階目では、２本のリンクのうち、ip から出ているリンクだけを
張り替える必要があります。もう１本の、wkdtp から出ているリンクは、
１段階目で処理済のため２段階目で意識してはいけません。

張り替えた結果、１段階目終了時点の ip->next に成り代わって、wkdtp が
「新しく」「ipの次」になります。
「新しく」ということは、代入することを意味します。
「ipの次」は、文字通り ip->next のことです。
よって、２段階目の操作は、
ip->next = wkdtp;
となります。

box · #13

少し補足します。

   A              B
+-----+        +-----+
|     |        |     |
+-----+        +-----+

上図のように、リンクを張っていない状態から

   A              B
+-----+        +-----+
|     | -----> |     |
+-----+        +-----+

このようにリンクを張るということは、
Aの次をBにする、ということです。

ここで、いったんリンクのことを離れてみます。
「nを10にする」をC言語で表現すると、
n = 10;
となります。これはご理解いただけるでしょう。

リンクの話に戻ります。
「Aの次をBにする」をC言語で表現するということは、
「Aの次」にBを代入することです。
つまり、
A->next = B;
です。

parapara · #14

工夫を凝らした解答(その時点でのリンクの詳細)のお陰で、
なんとか分かりました。私の素朴な疑問にお付き合いさせてしまって、
ご迷惑をおかけして、すみませんでした。
またの機会がありましたら、よろしくお願いします。
長い時間ありがとうございました。

		8月 2025
日	月	火	水	木	金	土
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31