トップ Cに関する質問 if()文の条件を図にしています。矢印の方向がわかりません。

編集履歴

回答編集履歴

一文字強調

2018/02/15 03:58

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -98,7 +98,7 @@
-そもそも、next ポインタは構造体の先頭をポイントするのに対し、p, q の値は next ポインタ（構造体の途中）をポイントする（＝構造体の先頭をポイントしない）のだから、「nextに入っているアドレスがポインタｑのアドレスと等しい」とはなりません。
+そもそも、next ポインタは構造体の先頭をポイントするのに対し、p, q の値は next ポインタ（構造体の途中）をポイントする（＝構造体の先頭をポイントしない）のだから、「next**に**入っているアドレスがポインタｑのアドレスと等しい」とはなりません。

回答の肝心な部分を追加編集（再投稿）

2018/02/15 03:58

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -66,21 +66,53 @@
 さらに、その２つの next ポインタの値を代入した r と s が指している Y と Z が交換対象である。交換しようとしているのが Y と Z である事と、p, q が指している場所を、勘違いしないようにしましょう。
-つまり ``` if (&((*p)->next) == q) ``` の条件は**隣り合う２つを交換する場合**を意味します。ここ、問題ありませんよね？
+つまり ``` if (&((*p)->next) == q) ``` の条件は**隣り合う２つを交換する場合**を意味します。ここ、問題ありませんよね？・・・と書いたら問題ありまくり、というか**ここが質問のキモ**でしたね。ポインタ、*演算子、&演算子などが苦手な人はひっかかるでしょう。図１を見ながら解説を編集します。
-・・・と書いたら問題ありまくりな感じなので図１を見ながら少しだけ解説を加えます。
-そもそも** &((*p)->next) の値は　YN という番地**です。Y番地の構造体にある、nextポインタ自体のメモリアドレスです。**q ポインタの値も YN **です。だから一致するのです。たぶん質問者はそこがわかっていない。
+** &((*p)->next) の値は　YN という番地**です。Y番地の構造体にある、nextポインタ自体のメモリアドレスです。**q ポインタの値も YN **です。だから一致するのです。これに対し質問者は
+> &((*p)->next) の値は…XN番地ではないのですか。YN番地でいいのでしょうか。
+と問い返しました。図１に next ポインタはXN番地、YN番地、ZN番地の３つありますが、XN番地の next を ((*p)->next) だと勘違いしたのです。こういう時は気を落ち着けて ``` struct address ** p; ``` を、こんな風に整理すると良いと思います。
+- p の値は XN である（XN番地の next ポインタを指す）
+- *p の値は Y である（Y番地の構造体を指す）
+- **p の値(?)は Y番地にある構造体である
+p, *p, **p と、参照演算子「*」の数が増えるにつれて図１の中の注目点が移っていきます。*p == Y を確認できれば ``` (*p)->next ``` を ``` Y->next ``` と置き換えることができ、 ``` (*p)->next ``` は Y 番地の構造体の中の next ポインタだと理解できるはずです。
+質問の次の部分はツッコミどころでした。
 > (*p)->next)はポインタｐのnextでそのnextに入っているアドレスがポインタｑのアドレスと等しい
-よく見ると「(*p)->next)はポインタｐのnext」ではないし、「nextに入っているアドレスがポインタｑのアドレスと等しい」というのも混乱です。なるほど、ここが鬼門のようです。ポインタ、*演算子、&演算子などが苦手な人はひっかかるでしょうね。
+そもそも、next ポインタは構造体の先頭をポイントするのに対し、p, q の値は next ポインタ（構造体の途中）をポイントする（＝構造体の先頭をポイントしない）のだから、「nextに入っているアドレスがポインタｑのアドレスと等しい」とはなりません。
+よく見ると「(*p)->next)はポインタｐのnext」が上記の勘違いを示しているし、「nextに入っているアドレスがポインタｑのアドレスと等しい」にも混乱が見えます。私的には「ポインタｑのアドレスと等しい」という表現にダメ出しをしたい。ここは「ポインタ q の値」としなくてはならない。
+「いや、q のアドレスとは（qは値としてアドレスを持つポインタなのだから）q がポイントしている場所（== YN）という意味だ、だからqの値のことだ」という弁解が予想できますが、「qのアドレス」と言ったら変数 q 自身のメモリアドレスを意味します（複数の解釈ができるとしても、第一の意味はこれ）。図１には q 自身の番地を示していないが、もちろん q 自身にもアドレスはあります。ただ、コードを解釈するのに q のアドレスを考える必要がないので省略したまで、「qのアドレス」という表現は無用＝誤りだったのです。
+繰り返しますが、コードを読み書きする時、**変数の値なのか、変数のアドレスなのか、明確に区別することが大事**です。区別が曖昧だとあんな表現をしてしまいがち。そして、こんなにもメモリアドレスを意識しなければならないのは、アセンブリ言語を除けばC/C++ぐらいしか無く、ポインタが苦手な人が多い要因でもあるでしょう。その苦手を克服するには、変数領域のイメージを図にしてみる、変数の具体的なアドレスを確認する、を繰り返すことだと思います。メモリダンプできると、なお良いと思う。こうしたことがポインタ廻りの文法を自然に理解する近道であり、手間を惜しむな、と言いたい。質問者はコードを理解しようと膨大なコメントを書き込んでいましたが、言葉・文章よりも図のほうが雄弁です。それにこの間のやり取りは**図を使うと議論が明確になる**ことを実証したのじゃないですか（笑）。
@@ -202,9 +234,9 @@
         if (s->next != 0) s->next->before = r;
-            r->before = s;           // 順序逆
+        r->before = s;           // 順序逆
-            s->before = r->before;   // 順序逆
+        s->before = r->before;   // 順序逆
 ```

追加説明の修正、その4。さらに追伸２項目を追加

2018/02/15 02:55

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -80,13 +80,15 @@
-「nextに入っているアドレスがポインタｑのアドレスと等しい」というところに混乱がある。
+よく見ると「(*p)->next)はポインタｐのnext」ではないし、「nextに入っているアドレスがポインタｑのアドレスと等しい」というのも混乱です。なるほど、ここが鬼門のようです。ポインタ、*演算子、&演算子などが苦手な人はひっかかるでしょうね。
-X ⇒ Y ⇒ Z というつながりを、X ⇒ Z ⇒ Y というつながりに変えようとしています。各変数の値・各ポインタの値がそれぞれどうなればよいか、考えてみてください。
+さて、図１の関係が成り立つ時、X ⇒ Y ⇒ Z というつながりを、X ⇒ Z ⇒ Y というつながりに変えようとします。各変数の値・各ポインタの値がそれぞれどうなればよいか、考えてみてください。
+---
 次に、``` if (&((*p)->next) == q) ``` が成り立たない場合とは、**離れた構造体を交換する場合**です。
@@ -186,4 +188,322 @@
 ともかく全部で８本のポインタを書き換えるべきことが図から分かりますし、コード上にもポインタの値を書き換えるところが８行あります。質問者は自ら手を動かして、その８箇所について、図とコードの対応をとってみると良いと思う。
+---
+P.S.1
+[参考にしたコード](http://codepad.org/B83f1FSq)にあった決定的なバグは、次に示した最後２行の順番が逆になっていることです。
+```C
+    if (&((*p)->next) == q) {
+        if (s->next != 0) s->next->before = r;
+            r->before = s;           // 順序逆
+            s->before = r->before;   // 順序逆
+```
+ここから得られる教訓は、ポインタの付け替えは操作の順序が重要な箇所がある、ということ。誤りを犯しやすい所だし、リストの操作は扱うデータに関わらず一般性があるのだから、いちいちプログラマが直接書かなくても良くしよう・・・それが C++ の std::list コンテナでしょう。
+P.S.2
+[参考にしたコード](http://codepad.org/B83f1FSq)はリスト構造の特質を活かしているとは思えません。おそらく通常のソートプログラムで２つの要素を交換することが exchange() 関数の発想の元でしょう。でもそれがコードを不必要に難しくしている大きな要因になっています。
+どなたかが指摘していたようにリスト構造では、要素をリストに挿入する、要素をリストから削除する、といった簡単な操作を用意するものです。そのほうが処理が簡単になり見通しが良くなります。具体例を示すために、恥ずかしながら「いちいち書いた」同等のコードを示してみます。
+```C
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <assert.h>
+#define FILENAME "address.csv"
+#define LINESIZE 80 /* メモリ節約w */
+#define N 16        /* メモリ節約w */
+typedef struct address {
+    char name[N];
+    char address[N];
+    char tel[N];
+    char mail[N];
+    struct address *next;
+    struct address *prev;
-（まだ続く）
+} ADDR;
+void ins_addr(ADDR *new, ADDR *ap)    // (*ap) の直後に (*new) を挿入
+{
+    new->prev = ap;
+    new->next = ap->next;
+    if (new->next)
+        new->next->prev = new;
+    ap->next = new;
+}
+ADDR *rmv_addr(ADDR *ap)   // (*ap)をリストから外す:remove
+{
+    ap->prev->next = ap->next;
+    if (ap->next) {
+        ap->next->prev = ap->prev;
+    }
+    return ap;             // そのまま返す
+}
+ADDR *min_addr(ADDR *ap)   // ap以降の「最小」を探す
+{
+    ADDR *min = ap;        // 先頭を「最小」にして検索開始
+    while (ap->next) {     // 「次」があるなら
+        ap = ap->next;     // その「次」と「最小」を比較
+        if (strcmp(ap->name, min->name) < 0) {
+            min = ap;      // 「最小」を更新
+        }
+    }
+    return min;
+}
+void sort_list(ADDR *head)           // head以降をソート
+{
+    ADDR *min, *ap = head;
+    while (ap->next) {               // 「次」がある間、繰返す
+        min = min_addr(ap->next);    // 「次」以降の「最小」を見つけ
+        if (min) {
+            ins_addr(rmv_addr(min), ap);    // 抜出し、先頭の直後に移動する
+        }
+        ap = ap->next;               // 移動したばかりの所を先頭にして、繰返す
+    }
+}
+void free_list(ADDR *ap)    // メモリ返却
+{
+    while (ap) {
+        ADDR *n = ap->next;
+        free(ap);
+        ap = n;
+    }
+}
+void show_list(ADDR *ap)    // リスト一覧表示
+{
+    while (ap) {
+        printf("%-10s %p: next = %p, prev = %p\n",
+               ap->name, ap, ap->next, ap->prev);
+        ap = ap->next;
+    }
+    // printf("\n");
+}
+ADDR *line2addr(char line[])    // 読み込んだ一行を構造体に格納する
+{
+    ADDR *new;
+    const char *token = ",\n\r";    // カンマと改行文字で区切る
+    char *p;
+    new = malloc(sizeof(ADDR));    // メモリ獲得
+    assert(new != NULL);
+    p = strtok(line, token);
+    assert(p != NULL);        // "氏名の切り出しに失敗しました。"
+    strcpy(new->name, p);
+    p = strtok(NULL, token);
+    assert(p != NULL);        // "住所の切り出しに失敗しました。"
+    strcpy(new->address, p);
+    p = strtok(NULL, token);
+    assert(p != NULL);        // "電話番号の切り出しに失敗しました。"
+    strcpy(new->tel, p);
+    p = strtok(NULL, token);
+    assert(p != NULL);        // "メールアドレスの切り出しに失敗しました。"
+    strcpy(new->mail, p);
+    return new;
+}
+void make_list(const char *fname, ADDR *head)    // ファイルをリストに読込む
+{
+    FILE *fp;
+    char line[LINESIZE];
+    fp = fopen(fname, "r");
+    assert(fp != NULL);
+    while (fgets(line, LINESIZE, fp) != NULL) {
+        ADDR *n = line2addr(line);    // 一行をADDR構造体に変換し
+        ins_addr(n, head);            // headの直後（リスト先頭）に挿入する
+    }
+    fclose(fp);
+}
+int main(void)
+{
+    ADDR head = {
+        "head(dummy)", "", "", "", NULL, NULL
+    };
+    printf(" ... read file into list ...\n");
+    make_list(FILENAME, &head);
+    show_list(&head);    // 念の為 head から表示
+    printf(" ... sorting ...\n");
+    sort_list(&head);
+    show_list(head.next);
+    free_list(head.next);
+    return 0;
+}
+```
+リスト中の「最小」を見つけたら、交換するのではなく、削除して（リストから外して）挿入し直すだけ、隣り合うかどうかに関係なく処理できます。
+line2addr() 関数を除けば、各関数は10行程度、さほど難しくないはずです。再帰も不要。
+[参考にしたコード](http://codepad.org/B83f1FSq)はポインタ変数 struct address *head; を大元にしていますが、そこは工夫の余地があると思います。私はheadとして空の構造体を置いてみました。それもあって、ポインタのポインタはひとつも使わずに済んでいます。
+他に手抜きかもしれないが、エラー判定はassert()で済ませているし、chop()関数を使わず strtok() で改行文字を削除しています。お試しあれ。

追加説明の修正、その３

2018/02/11 07:55

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -80,7 +80,7 @@
-「ポインタｑのアドレスと等しい」というところに混乱がある。図にも表せていないようだ。
+「nextに入っているアドレスがポインタｑのアドレスと等しい」というところに混乱がある。

無駄な改行を削除

2018/02/11 04:54

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -76,9 +76,7 @@
-> (*p)->next)はポインタｐのnextでそのnextに入っているアドレスがポインタｑのアドレス
+> (*p)->next)はポインタｐのnextでそのnextに入っているアドレスがポインタｑのアドレスと等しい
-と等しい

説明追加、その２

2018/02/11 04:42

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -72,7 +72,17 @@
 ・・・と書いたら問題ありまくりな感じなので図１を見ながら少しだけ解説を加えます。
-そもそも** &((*p)->next) の値は　YN という番地**です。Y番地の構造体にある、nextポインタ自体のメモリアドレスです。q ポインタの値も YN です。だから一致するのです。たぶん質問者はそこがわかっていない。
+そもそも** &((*p)->next) の値は　YN という番地**です。Y番地の構造体にある、nextポインタ自体のメモリアドレスです。**q ポインタの値も YN **です。だから一致するのです。たぶん質問者はそこがわかっていない。
+> (*p)->next)はポインタｐのnextでそのnextに入っているアドレスがポインタｑのアドレス
+と等しい
+「ポインタｑのアドレスと等しい」というところに混乱がある。図にも表せていないようだ。

追加説明の字句をわずか修正

2018/02/11 04:38

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -72,7 +72,7 @@
 ・・・と書いたら問題ありまくりな感じなので図１を見ながら少しだけ解説を加えます。
-そもそも &((*p)->next) とは　YN という番地です。Y番地の構造体にある、nextポインタ自体のメモリアドレスです。q ポインタの値も YN です。だから一致するのです。たぶん質問者はそこがわかっていない。
+そもそも** &((*p)->next) の値は　YN という番地**です。Y番地の構造体にある、nextポインタ自体のメモリアドレスです。q ポインタの値も YN です。だから一致するのです。たぶん質問者はそこがわかっていない。

&((*p)->next) == q の説明追加

2018/02/11 04:26

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -67,6 +67,12 @@
 さらに、その２つの next ポインタの値を代入した r と s が指している Y と Z が交換対象である。交換しようとしているのが Y と Z である事と、p, q が指している場所を、勘違いしないようにしましょう。
 つまり ``` if (&((*p)->next) == q) ``` の条件は**隣り合う２つを交換する場合**を意味します。ここ、問題ありませんよね？
+・・・と書いたら問題ありまくりな感じなので図１を見ながら少しだけ解説を加えます。
+そもそも &((*p)->next) とは　YN という番地です。Y番地の構造体にある、nextポインタ自体のメモリアドレスです。q ポインタの値も YN です。だから一致するのです。たぶん質問者はそこがわかっていない。

質問者のコメントを回答に追加。

2018/02/11 04:16

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -46,7 +46,11 @@
-X番地、Y番地、Z番地にある３つの構造体が X ⇒ Y ⇒ Z というつながりになっている状態です。構造体の先頭アドレスに加えて、構造体中の next, before ポインタのアドレスを XN, XB, YN, YB ... としました。p ポインタの値は XN だけど、XN は（Xの）next ポインタのアドレスであって、next ポインタの値ではない事を念押しします。
+X番地、Y番地、Z番地にある３つの構造体が X ⇒ Y ⇒ Z というつながりになっている状態です。構造体の先頭アドレスに加えて、構造体中の next, before ポインタのアドレスを XN, XB, YN, YB ... としました。p ポインタの値は XN であり、XN は（Xの）next ポインタのアドレスであって、next ポインタの値ではない事を念押しします。
+**p の値は next ポインタのアドレスである、即ち next ポインタをポイントしている。**
 全てのデータはメモリ上にある＝**全てのデータにメモリアドレスがある**。ポインタが活躍するプログラムを読み書きする時、メモリの値なのか、メモリのアドレスなのか、きちんと把握することは大事です。だから図を描いてみると良いのです。

てにをは修正

2018/02/11 00:43

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -82,7 +82,9 @@
+B と E を交換したら、どうなるか。
-B と E を交換したら、どうなるか。 A ⇒ B ⇒ C ⇒ D ⇒ E ⇒ F は A ⇒ E ⇒ C ⇒ D ⇒ B ⇒ F というつながりにすることが目的ですが、リスト構造ではデータそのもの（構造体、その中の name[], address[]など）を動かさず、ポインタを付け替えて順番を変えるのです。次は交換後の図です。
+A ⇒ B ⇒ C ⇒ D ⇒ E ⇒ F を A ⇒ E ⇒ C ⇒ D ⇒ B ⇒ F というつながりにすることが目的ですが、リスト構造ではデータそのもの（構造体、その中の name[], address[]など）を動かさず、ポインタを付け替えて順番を変えるのです。次は交換後の図です。
 図３

回答追加。else以下の解説

2018/02/11 00:25

投稿

rubato6809

スコア1380

test CHANGED Viewed

@@ -62,10 +62,108 @@
 さらに、その２つの next ポインタの値を代入した r と s が指している Y と Z が交換対象である。交換しようとしているのが Y と Z である事と、p, q が指している場所を、勘違いしないようにしましょう。
+つまり ``` if (&((*p)->next) == q) ``` の条件は**隣り合う２つを交換する場合**を意味します。ここ、問題ありませんよね？
-``` if (&((*p)->next) == q) ``` の条件は**隣り合う２つを交換する場合**を意味します。ここ、問題ありませんよね？
-従って X ⇒ Y ⇒ Z というつながりを、X ⇒ Z ⇒ Y というつながりに変えようとしています。各変数の値・各ポインタの値がそれぞれどうなればよいか、考えてみてください。
+X ⇒ Y ⇒ Z というつながりを、X ⇒ Z ⇒ Y というつながりに変えようとしています。各変数の値・各ポインタの値がそれぞれどうなればよいか、考えてみてください。
+次に、``` if (&((*p)->next) == q) ``` が成り立たない場合とは、**離れた構造体を交換する場合**です。
+操作対象の構造体がひとつあると、その前後の構造体の next, before が変更を受けるので、都合３つの構造体に影響します。exchange()は２つを交換するから、最大で６個の構造体が影響を受けるという事。その６つを A ⇒ B ⇒ C ⇒ D ⇒ E ⇒ F とします。交換対象は B と E です。p, q, r, s の各ポインタがどこをポイントしているか、ご確認ください。
+図２
+![図２，６つの構造体](27415013992132696137fefbc5329894.jpeg)
+B と E を交換したら、どうなるか。 A ⇒ B ⇒ C ⇒ D ⇒ E ⇒ F は A ⇒ E ⇒ C ⇒ D ⇒ B ⇒ F というつながりにすることが目的ですが、リスト構造ではデータそのもの（構造体、その中の name[], address[]など）を動かさず、ポインタを付け替えて順番を変えるのです。次は交換後の図です。
+図３
+![図３、交換後](641b9ebeaaf37de52254ac44f98d8350.jpeg)
+例えば、A番地の構造体のnextポインタ（AN番地）が「B→E」とあるのは、この操作でnextポインタの値がBからEに変更される事を表します。
+この、ポインタの付け替えをしているのが else 以下のコードです。
+```C
+    r = *p; s = *q;
+    if (&((*p)->next) == q) {
+        // 隣り合う２つを交換する（省略）
+    } else {
+        // 離れた２つを交換する
+        if (s->next != 0) {
+            s->next->before = r;
+        }
+        if (r->next != 0) {
+            r->next->before = s;
+        }
+        // ２つの before ポインタを交換する
+        t = s->before;
+        s->before = r->before;
+        r->before = t;
+        // ２つの next ポインタを交換する
+        t = r->next;
+        r->next = s->next;
+        s->next = t;
+        *p = s;
+        *q = r;
+    }
+```
+t ポインタを使った３行のパターンが２つあります。これは X と Y を交換する時、一時変数 t を使って
+```C
+    t = X;
+    X = Y;
+    Y = t;
+```
+とするのと同じです。図３で言えば B と E の next, before ２つの交換です。他にも同じパターンで交換できる所がありそうですが、
+ともかく全部で８本のポインタを書き換えるべきことが図から分かりますし、コード上にもポインタの値を書き換えるところが８行あります。質問者は自ら手を動かして、その８箇所について、図とコードの対応をとってみると良いと思う。
-（続きは後で）
+（まだ続く）