質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.58%

「ポインタのポインタ」のつなぎ替えをしている部分がわからない

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 2,113
退会済みユーザー

退会済みユーザー

リストの構造体のデータをソートしているコードがあるんですが、その中の
exchange()関数のところを図を使って書こうと思ったのですが、うまくいきません。
その前に書かれているコードの正確な理解が出来ていないと思います。

exchange()関数のところでご教授してもらいました説明を参考に、コメントをつけました。

if (s->next != 0){}の下の文r->before = s;からs->next = r;までは
if (s->next == 0){}という条件のことでしょうか。

if{},else{}文でしているのは、「ポインタのポインタ」のつなぎ替えと思うのですが、
if{}文で何をしているのか
条件は&((*p)->next) == q でqが(*p)->nextのアドレスをポイントしている。または
&((*q)->next) == pでpが(*q)->nextのアドレスをポイントしている場合。

ということは分かりました。

else{}文で何をしているのか
上のif{}文の条件でないときの作業だと思うのですが、

if (s->next != 0){}から下のコード(r->before = s;から)を

どなたか詳しく、やさしい説明をしてもらえませんか。
よろしくお願いいたします。

//codepad.org/B83f1FSq        
//正常動作(リスト構造)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h> //

#define N 256
#define FILENAME "address.csv"

struct address{
  char name[N];
  char address[N];
  char tel[N];     // 電話番号
  char mail[N];
  struct address *next;
  struct address *before; 
};

void data_show(struct address* head);
void data_sort(struct address** head);

void chop(char *p){
  for (; *p; p++)
    ;

  p--; 
  while (*p == '\r' || *p == '\n')
    *(p--) = 0;

}

void list_add(struct address **head,  char *name, char *address, char *tel, char *mail) 
{
      struct address *p;
      if ((p = malloc(sizeof(struct address))) != 0) {

          strcpy(p->name, name);    

        strcpy(p->address, address);

        strcpy(p->tel, tel);

        strcpy(p->mail, mail);        

        p->next = *head;
        if (p->next != 0)
              p->next->before = p;
        p->before = 0;
        *head = p;
      }
}


void data_show(struct address *head) {
  if (head != 0) {
    printf(" %s, %s, %s, %s\n", head->name, head->address, head->tel, head->mail);
    data_show(head->next);
  }
}

struct address **listmin(struct address **head) {
  struct address **p;

  if (*head == 0)
    return 0;
  if ((*head)->next == 0)
    return head;
    //

  if (strcmp((*head)->name, (*(p = listmin(&((*head)->next))))->name) < 0)
    return head;
  else
    return p;
}

//大小を入れ替える 
void exchange(struct address **p, struct address **q) 
{
  struct address *r, *s, *t;
  assert(*p != 0 && *q != 0);

  if (p == q)
    return;

  r = *p; s = *q;
  if (&((*p)->next) == q || &((*q)->next) == p) {

             if (s->next != 0){

              s->next->before = r;

        }
        s->before = r->before;

        r->before = s;

        *p = s;

        *q = s->next;

        s->next = r;

        return;
  } else {  
    if (s->next != 0)

      s->next->before = r;

    if (r->next != 0)

          r->next->before = s;

    t = s->before;

    s->before = r->before;

    r->before = t;

    t = r->next;

    r->next = s->next;

    s->next = t;

    *p = s;
    *q = r;
  }
}

void data_sort(struct address **head) 
{
      struct address **p;

      if (*head != 0) {
        for (;;) {
              p = listmin(head);
              //関数listmin(head)は、名前からリストの全ての要素をチェックして、
              //いちばん小さいnameを持つ要素を返していると思われます。
              //そうでないと正しくソートされません。 

              if (p == 0)break;

              exchange(head, p);
              //大小を入れ替える 

              head = &((*head)->next);
              //見つけたいちばん小さい要素を関数exchange(head, p)で先頭に移動しています。
        }
      }
}

void release(struct address **head) 
{
      if (*head != 0) {
        release( &((*head)->next) );
        free(*head);
        *head = 0;
      }
}

int main() 
{
      struct address *head;
      FILE* fp;
      static char buff[N], name[N], address[N], tel[N], mail[N];
      char *token=",";

      head = 0;

      if ((fp = fopen(FILENAME,"r")) != 0) {
          while(fgets(buff, N, fp) != 0){
          //本当の大元の文字列を書き換えないようにするために
          //bufを確保してコピーし、それをstrtok()の引数にしている。
            char *p;
            chop(buff);
            printf( "ファイルから読んだ文字列:%s\n", buff );

            p = strtok(buff, token);
            if ( p != NULL ) {
                  strcpy(name, p);
            } else {
                  printf( "氏名の切り出しに失敗しました。\n");
                  break;
            }
            p = strtok(NULL, token);

            if ( p != NULL ) {
                  strcpy(address, p);
            } else {
                  printf( "住所の切り出しに失敗しました。\n");
                  break;
            }
            p = strtok(NULL, token);

            if ( p != NULL ) {
                  strcpy(tel, p);
            } else {
                  printf( "電話番号の切り出しに失敗しました。\n");
                  break;
            }
            p = strtok(NULL, token);

            if ( p != NULL ) {
                  strcpy(mail, p);
            } else {
                  printf( "メールアドレスの切り出しに失敗しました。\n");
                  break;
            } 
            list_add(&head, name, address, tel, mail);
          }
          fclose(fp);
      }  
      data_sort(&head);
      data_show(head);

      release(&head);
      return 0;
}

/* 実行結果
naka@naka ~
$ cd kadai/kadai9-8

naka@naka ~/kadai/kadai9-8
$ gcc -o kad9-8b kad9-8b.c -Wall

naka@naka ~/kadai/kadai9-8
$ kad9-8b
ファイルから読んだ文字列:yamada,tone,090-1122,mail-9
ファイルから読んだ文字列:hosi,nagoya,5436,mail-7
ファイルから読んだ文字列:kato,kanagawa,080-8888,mail-2
ファイルから読んだ文字列:koko,yosida,090-2314,mail-6
ファイルから読んだ文字列:naka,kamikosaka,080-4444,mail-1
ファイルから読んだ文字列:nakada,nogata,090-6376,mail-8
ファイルから読んだ文字列:saito,yamanashi,080-6666,mail-3
ファイルから読んだ文字列:suzuki,saitama,090-2222,mail-5
 hosi, nagoya, 5436, mail-7
 kato, kanagawa, 080-8888, mail-2
 koko, yosida, 090-2314, mail-6
 naka, kamikosaka, 080-4444, mail-1
 nakada, nogata, 090-6376, mail-8
 saito, yamanashi, 080-6666, mail-3
 suzuki, saitama, 090-2222, mail-5
 yamada, tone, 090-1122, mail-9

naka@naka ~/kadai/kadai9-8
$
*/



/* 実行結果
naka@naka ~
$ cd kadai/kadai9-8

naka@naka ~/kadai/kadai9-8
$ gcc -o kad9-8b kad9-8b.c -Wall

naka@naka ~/kadai/kadai9-8
$ kad9-8b
ファイルから読んだ文字列:yamada,tone,090-1122,mail-9
ファイルから読んだ文字列:hosi,nagoya,5436,mail-7
ファイルから読んだ文字列:kato,kanagawa,080-8888,mail-2
ファイルから読んだ文字列:koko,yosida,090-2314,mail-6
ファイルから読んだ文字列:naka,kamikosaka,080-4444,mail-1
ファイルから読んだ文字列:nakada,nogata,090-6376,mail-8
ファイルから読んだ文字列:saito,yamanashi,080-6666,mail-3
ファイルから読んだ文字列:suzuki,saitama,090-2222,mail-5
 hosi, nagoya, 5436, mail-7
 kato, kanagawa, 080-8888, mail-2
 koko, yosida, 090-2314, mail-6
 naka, kamikosaka, 080-4444, mail-1
 nakada, nogata, 090-6376, mail-8
 saito, yamanashi, 080-6666, mail-3
 suzuki, saitama, 090-2222, mail-5
 yamada, tone, 090-1122, mail-9

naka@naka ~/kadai/kadai9-8
$
*/


/* 実行結果
naka@naka ~
$ cd kadai/kadai9-8

naka@naka ~/kadai/kadai9-8
$ gcc -o kad9-8b kad9-8b.c -Wall

naka@naka ~/kadai/kadai9-8
$ kad9-8b
ファイルから読んだ文字列:yamada,tone,090-1122,mail-9
ファイルから読んだ文字列:hosi,nagoya,5436,mail-7
ファイルから読んだ文字列:kato,kanagawa,080-8888,mail-2
ファイルから読んだ文字列:koko,yosida,090-2314,mail-6
ファイルから読んだ文字列:naka,kamikosaka,080-4444,mail-1
ファイルから読んだ文字列:nakada,nogata,090-6376,mail-8
ファイルから読んだ文字列:saito,yamanashi,080-6666,mail-3
ファイルから読んだ文字列:suzuki,saitama,090-2222,mail-5
 hosi, nagoya, 5436, mail-7
 kato, kanagawa, 080-8888, mail-2
 koko, yosida, 090-2314, mail-6
 naka, kamikosaka, 080-4444, mail-1
 nakada, nogata, 090-6376, mail-8
 saito, yamanashi, 080-6666, mail-3
 suzuki, saitama, 090-2222, mail-5
 yamada, tone, 090-1122, mail-9

naka@naka ~/kadai/kadai9-8
$
*/

/* 実行結果
naka@naka ~
$ cd kadai/kadai9-8

naka@naka ~/kadai/kadai9-8
$ gcc -o kad9-8b kad9-8b.c -Wall

naka@naka ~/kadai/kadai9-8
$ kad9-8b
ファイルから読んだ文字列:yamada,tone,090-1122,mail-9
ファイルから読んだ文字列:hosi,nagoya,5436,mail-7
ファイルから読んだ文字列:kato,kanagawa,080-8888,mail-2
ファイルから読んだ文字列:koko,yosida,090-2314,mail-6
ファイルから読んだ文字列:naka,kamikosaka,080-4444,mail-1
ファイルから読んだ文字列:nakada,nogata,090-6376,mail-8
ファイルから読んだ文字列:saito,yamanashi,080-6666,mail-3
ファイルから読んだ文字列:suzuki,saitama,090-2222,mail-5
 hosi, nagoya, 5436, mail-7
 kato, kanagawa, 080-8888, mail-2
 koko, yosida, 090-2314, mail-6
 naka, kamikosaka, 080-4444, mail-1
 nakada, nogata, 090-6376, mail-8
 saito, yamanashi, 080-6666, mail-3
 suzuki, saitama, 090-2222, mail-5
 yamada, tone, 090-1122, mail-9

naka@naka ~/kadai/kadai9-8
$
*/
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

checkベストアンサー

+1

ところで、ソートは自前で実装する必要はありません。標準ライブラリを使いましょう。

#include <stdlib.h>
#include <string.h>

int compare_address_name(struct address *l, struct address *l) {
    return strcmp(l->name, r->name);
}

void data_sort(struct address **head) {
    struct address *array[MAX_LIST_SIZE]; # サイズは決め打ち:-)
    struct address *h, **a;

    if (head == 0 || *head == 0) {
        return;
    }

    # リストの各要素のポインタを配列に代入する。
    h = *head;
    a = array;
    while (h != 0) {
        *a++ = h;
        h = h->next;
    }

    # 配列の各要素をソートする。
    qsort(array, sizeof(struct address *), a - array, compare_address_name);

    # 配列の各要素をリストに追加する。
    h = 0;
    while (--a >= array) {
        *a->next = h;
        *a->before = 0;
        h = *a;
    }

    *head = h;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/28 16:28

    URL codepad.org/B83f1FSq です。すみません。よろしくおねがいします。
    色々コメントをしていて、コードが違っている可能性があります。

    キャンセル

  • 2018/01/28 16:57

    コードを修正しました。正常動作します。

    キャンセル

  • 2018/01/30 10:27

    課題でやってるというのなら、ネットで探したプログラムの解読を、というのは下策でしょう。exchangeでソートってのは配列ではいいけどリストではそんなによくないし。てか、自力で解読できるのならそれもいいけど、解読を他人に頼るようならそれは勉強が足りないので、もっと前の段階から総復習したほうがいいのでは?と職業柄考えてしまいます。あと、解読して理解したうえで自力で書くのはいいですが、ネットで拾ったのを手直しして課題として提出するのは不正行為。

    キャンセル

+1

長いので少しずつ回答します。

p = listmin(head);
//(*head)->nameと(*head)->next)のnameとを比べて
//小さいほうのポインタのポインタを返却値にしている。

関数listmin(head)は、名前からリストの全ての要素をチェックして、いちばん小さいnameを持つ要素を返していると思われます。そうでないと正しくソートされません。

if (p == 0)
    break;

おそらく、リストが残り1つの場合、ソートが完了したとして、ループを抜けます。

exchange(head, p);
//大小を入れ替える

ここでは、見つけたいちばん小さい要素を関数exchange(head, p)で先頭に移動しています。

head = &((*head)->next);

ループの最後では、先頭の次の要素を新たな先頭にして、処理を繰り返します。

で、関数exchange(head, p)の中身ですが、以下の処理を行っています。

  1. リストheadから要素pを引っこ抜いて、抜けた部分を繋ぎ直す。
  2. リストheadの先頭に要素pを追加して、要素pを新しいリストの先頭にする。

if (&((*p)->next) == q || &((*q)->next) == p) {

尚、この条件ではリストの先頭要素と要素pが隣り合っているかどうかチェックしていますが、ポインタのつなぎ替えの順番を工夫すれば、1つにまとめることも可能です。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/28 17:14

    p==0はポインタのポインタがNULLで何も指していない状態ですよね。
    リストが残り1つの場合、はどうしてわかるんですか?

    キャンセル

  • 2018/01/28 18:41 編集

    listmin(head)のコードを貼ってくれたのですね。
    実際のコードは、「リストの先頭が空のとき、返り値が0になるので、ソートが完了したとして、ループを抜けます。」ですね。

    キャンセル

  • 2018/01/29 05:34

    ありがとうございます。今日お昼仕事です。
    帰ったらまた続きをやりたいと思います。
    これからもよろしくお願いします。

    キャンセル

+1

if(&((*p)->next) == q || &((*q)->next) == p)の条件式が何を意味しているかは理解していますか?
ifの条件式が真になる場合は図のようになりますが、elseの場合はどのようなケースが考えられますか?
イメージ説明

[追記]
提示されたexchange()関数を実行してみました。
仕様が不明なので何とも言えないのですが、正常に動作しているようには見えません。
exchange()関数実行後にリンクリストが壊れているように見えますが・・・。
正常動作はどのように確認しましたか?

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

#define N 256
#define FILENAME "address.csv"

struct address{
  char name[N];
  char address[N];
  char tel[N];     // 電話番号
  char mail[N];
  struct address *next;
  struct address *before; 
};

void exchange(struct address **p, struct address **q)
{
    struct address *r, *s, *t;
    assert(*p != 0 && *q != 0);

    if (p == q)
        return;

    r = *p;
    s = *q;
   if (&((*p)->next) == q || &((*q)->next) == p) {
        if (s->next != 0){
            s->next->before = r;
        }
        r->before = s;
        s->before = r->before;
        *p = s;
        *q = s->next;
        s->next = r;
        return;
    } else {
        if (s->next != 0){
            s->next->before = r;
        }
        t = s->before;
        s->before = r->before;
        if (r->next != 0){
            r->next->before = s;
        }
        r->before = t;
        t = r->next;
        r->next = s->next;
        s->next = t;
        *p = s;
        *q = r;
    }
}

void data_create( struct address **head )
{
    int i;
    struct address data[8] = {
        { "yamada","tone","090-1122","mail-9", NULL, NULL },
        { "hosi","nagoya","090-1122","mail-9", NULL, NULL },
        { "kato","kanagawa","090-1122","mail-9", NULL, NULL },
        { "koko","yosida","090-1122","mail-9", NULL, NULL },
        { "naka","kamikosaka","090-1122","mail-9", NULL, NULL },
        { "nakada","nogata","090-1122","mail-9", NULL, NULL },
        { "saito","yamanashi","090-1122","mail-9", NULL, NULL },
        { "suzuki","saitama","090-1122","mail-9", NULL, NULL }
    };
    struct address *p[9] = {NULL};

    for ( i = 0; i < 8; i++ ) {
        p[i] = malloc( sizeof(struct address));
        *p[i] = data[i];
    }

    for ( i = 0; i < 8; i++ ){
        if ( p[i] != NULL ) {
            p[i]->next = p[i+1];
            if ( i > 0 ) {
                p[i]->before = p[i-1];
            }
        }
    }

    *head = p[0];
}

int main()
{
    struct address *head = NULL;
    struct address *p = NULL;
    struct address *q = NULL;
    data_create( &head );

    printf( "オリジナルデータ表示\n");
    p = head;
    while ( p != NULL ) {
        printf("addr=%08x, next=%08x, before=%08x, %s\n", p, p->next, p->before, p->name );
        p = p->next;
    }
    printf("###################\n");
    printf( "exchange() 実行前\n");
    p = head->next;
    q = head->next->next;
    printf("p: addr=%08x, next=%08x, before=%08x, %s\n", p, p->next, p->before, p->name );
    printf("q: addr=%08x, next=%08x, before=%08x, %s\n", q, q->next, q->before, q->name );
    exchange( &p, &q );
    printf( "exchange() 実行後\n");
    printf("p: addr=%08x, next=%08x, before=%08x, %s\n", p, p->next, p->before, p->name );
    printf("q: addr=%08x, next=%08x, before=%08x, %s\n", q, q->next, q->before, q->name );

    printf("###################\n");
    printf( "変更後データ表示\n");
    p = head;
    while ( p != NULL ) {
        printf("addr=%08x, next=%08x, before=%08x, %s\n", p, p->next, p->before, p->name );
        p = p->next;
    }


    return 0;
}

実行結果
$gcc -o main *.c
$main
オリジナルデータ表示
addr=01675010, next=01675430, before=00000000, yamada
addr=01675430, next=01675850, before=01675010, hosi
addr=01675850, next=01675c70, before=01675430, kato
addr=01675c70, next=01676090, before=01675850, koko
addr=01676090, next=016764b0, before=01675c70, naka
addr=016764b0, next=016768d0, before=01676090, nakada
addr=016768d0, next=01676cf0, before=016764b0, saito
addr=01676cf0, next=00000000, before=016768d0, suzuki

#############

exchange() 実行前
p: addr=01675430, next=01675850, before=01675010, hosi
q: addr=01675850, next=01675c70, before=01675430, kato
exchange() 実行後
p: addr=01675850, next=01675850, before=01675850, kato
q: addr=01675430, next=01675c70, before=01675430, hosi

#############

変更後データ表示
addr=01675010, next=01675430, before=00000000, yamada
addr=01675430, next=01675c70, before=01675430, hosi
addr=01675c70, next=01676090, before=01675430, koko
addr=01676090, next=016764b0, before=01675c70, naka
addr=016764b0, next=016768d0, before=01676090, nakada
addr=016768d0, next=01676cf0, before=016764b0, saito
addr=01676cf0, next=00000000, before=016768d0, suzuki

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/30 13:38

    写真を撮ってフォルダに保存するところまできました。
    後はどこかに貼り付けてアップします。
    時間がかかりそうです。

    キャンセル

  • 2018/01/30 13:44

    写真はkadai9-8のフォルダに保存するところまできました。
    後はどこに貼り付けるのか、探してあっぷします。
    時間かかりそうです。

    キャンセル

  • 2018/01/30 13:44

    休憩します。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.58%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る