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

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

ただいまの
回答率

91.03%

  • C

    3067questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

listのコードでデータのソートのところのポインタのつなぎ替えが分からない

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 196

sanchu52

score 121

リストの構造体のデータをソートしているコードがあるんですが、
exchange()関数のところを図を使って書こうと思ったのですが、うまくいきません。
図で説明してもらえませんか。
exchange()関数のところでデータが同じ場合にはそのままreturnして
*p,*qをr、sで保存しているところまでは分かるのですが、そのあとが
さっぱりわかりません。

if (&((*p)->next) == q || &((*q)->next) == p)のところで
&((*p)->next) == q、&((*q)->next) == pは具体的にどういうことなんでしょうか。

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

if (s->next != 0){
s->next->before = r;
//「sの次が存在するなら、そいつの手前をrにする」と読める。
//つまり" r ← sの次 " ってゆー上り方向のリンクを張り替えたってこと。
のようなわかり易い説明をしてもらいました。

ポインタのポインタは復習してみました。
コメントを付けていますが、自分でもよくわかりません。
いつも同じような質問で申し訳ありませんが、どなたか説明をしてもらえませんか。
よろしくお願いいたします。

// 電話帳プログラム

#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; 
};

//(*head)->nameと(*head)->next)のnameとを比べて
//小さいほうのポインタのポインタを返却値にしている。
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)
  // #include <string.h>
  //  int strcmp( const char *str1 , const char *str2 );
  // str1<str2ならば負の値を返す。
    return head;
  else
    return p;
}

void exchange(struct address **p, struct address **q) 
{
      struct address *r, *s, *t;
       assert(*p != 0 && *q != 0);
      //assertマクロは関数形式マクロで、引数に偽(すなわち0)が指定されると、
    //ソースファイル名や行番号等の情報を標準エラー出力に出力し、
    //プログラムを終了させます。
      if (p == q)
        return;

      r = *p; s = *q;
      if (&((*p)->next) == q || &((*q)->next) == p) {
       // (*p)はポインタで,(*p)->nextも次のポインタである。
       //  q(ポインタのポインタ)と(*p)->nextを比較するには&((*p)->next)とする。

        if (s->next != 0){
            s->next->before = r;
              //「sの次が存在するなら、そいつの手前をrにする」と読める。
        //つまり" r ← sの次 " ってゆー上り方向のリンクを張り替えたってこと。
    }   
        r->before = s;
        //rは*pであるから,*p->before = sである。s==*qなので
        //*p->beforeに*q(これはポインタ)を代入する。

        s->before = r->before;
        // s->beforeに*q(これはポインタ)を代入する。

        *p = s;
        //sは*qだから*pに*q(これはポインタ)を代入する。

        *q = s->next;
        //s->nextは(*q)->nextであるから*qに(*q)->next(これはポインタ)を代入する。

        s->next = r;
        //rは*pであるから,(*q)->nextに*p(これはポインタ)を代入する。

        return;
      } else {
        if (s->next != 0){
        // (*q)->nextが0でないとき

              s->next->before = r;
              // (s->next)->before=*p
          }
        t = s->before;
        // s->before==(*q)->before
        // t=(*q)->before

        s->before = r->before;
        // s->beforeにr->before==(*p)->before(これはポインタ)を代入する。    

        if (r->next != 0){
        // (*p)->nextが0でないとき

              r->next->before = s;
              // (r->next)->before=*q
          }
        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);
              //(*head)->nameと(*head)->next)のnameとを比べて
            //小さいほうのポインタのポインタを返却値にしている。
            //帰ってきたhead(小さいほうのポインタのポインタ),または
            //p(小さいほうのポインタのポインタ)

              if (p == 0)
                break;

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

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

データ
address.csv
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
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • episteme

    2018/01/25 11:52

    excange()が何をするものかを記せ。コメントもないコードを解釈する気にならん。

    キャンセル

回答 3

checkベストアンサー

+1

こんにちは。

ちょっと難しいので、最初の質問だけ。

&((*p)->next) == q

において、**pはaddress構造体型ですから、*pはaddress構造体へのポインタです。
従って、(*p)もaddress構造体へのポインタです。
であれば、(*p)->nextはaddress構造体のnextメンバですね。
ならば、&((*p)->next)はそのアドレスですから、nextメンバのアドレスとなります。
それと q が等しいという条件ですから、qはadress構造体のnextメンバをポイントしているのだろうと思います。
つまり、*pが指すaddress構造体のnextメンバをqがポイントしているならば、この条件が成立します。

これが何を意味するかはごめんなさい。長めのソースですので読む気力が足りません。
後は頑張って下さい。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/01/27 23:07

    ありがとうございます。たすかりました。図を書いてかくにんします。
    ここがしっかり理解できないのに、そのつぎはないですね。
    1つ1ついろんな方に説明をいただきながら、がんばります。

    キャンセル

+1

ノードの交換をやりたいのかな?
僕だったらアタマひねってポインタいぢくるより
name,address,tel,mail のナカミを交換する。

[追記]
てかまず構造自体をいぢくりますね。扱いたいデータとそのつながりとは本来別モノなんだから。

struct address {
  名前やら住所やらモロモロ
};

struct link {
  struct address* data;
  struct link* next;
  struct link* prev;
};

こうしておけばデータの交換が楽。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/01/25 12:24

    すみません。excange()関数の中で行っているポインタのやり取りがわからないのです。
    たぶんデータの大小を確認して交換して、そのどこかで*headもかえているんとおもうのですが、
    コメントを自分なりにつけていたのですが。今読み返すと何を言っているのか分からなくて、
    図を書いて理解しようとしたのですが,それもできないので質問しています。

    キャンセル

  • 2018/01/25 12:25

    この書き変えは後で挑戦させていただきます。ありがとうございます。

    キャンセル

  • 2018/01/25 12:27

    もうねますので明日またやります。

    キャンセル

  • 2018/01/25 12:32

    > たぶんデータの大小を確認して交換して、そのどこかで*headもかえているんとおもうのですが、

    違いますね。比較とheadの更新はexchangeの外でやってます。
    exchangeはリンクの張り替えのみ。

    キャンセル

  • 2018/01/25 12:34

    はい。ありがとうございます。あしたゆっくり確認します。

    キャンセル

  • 2018/01/25 12:46

    void data_sort(struct address **head) の戻り値pはexchange(head, p);を使って
    これがheadになるということですか。そのあとは順次headの付け替えをするということですか。
    exchangeのリンクの張り替えのみのところを解説してもらえませんか。

    キャンセル

  • 2018/01/25 12:49

    ごめん、こんなクソめんどくさいコード書かないので僕はパス。申し訳ないが他の方の回答を待ってください。
    # 「難しいプログラムは間違っている」が信条なのです

    キャンセル

  • 2018/01/25 12:50

    すみませんでした。

    キャンセル

  • 2018/01/25 12:54

    ぃぇぃぇ、質問に正面から答えていない僕の落ち度です。

    キャンセル

  • 2018/01/25 12:56

    ポインタのポインタを復習してから見てみます。

    キャンセル

  • 2018/01/25 13:09

    (解読の例)
    ●->next を ●の次
    ●->before を ●の手前
    と読み替えてごらん。

    if (s->next != 0){
    s->next->before = r;
    }
    は、「sの次が存在するなら、そいつの手前をrにする」と読める。
    つまり" r ← sの次 " ってゆー上り方向のリンクを張り替えたってこと。

    キャンセル

  • 2018/01/25 13:39

    ありがとうございます。ねます。

    キャンセル

0

ソート済みのリンクリストを作りたいのなら、要素交換で行うのではなくて先頭からひとつづつ要素をとり出して別リストに挿入してゆくほうが楽だとおもいます。
というか、順序を気にするのならリスト構造をやめるか、あるいは最初データを読み込む時点でソートしながら読み取って、ソートコマンドなんてなくしてしまうとか。

if(p==q)も pとqが同じ構造体であることを調べたいのならif(*p==*q)?

あと、二重ポインタを引数に使わなくて済む関数仕様にした方が安全かなぁ。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/01/25 13:06

    ありがとうございます。コード自体が悪いみたいです。

    キャンセル

  • 2018/01/25 13:26

    非常に面倒ですが、void exchange(struct address **p, struct address **q) のままで頑張れば書けますけどね。

    **pと**qを入れ替えるには
    (*p)->before->next
    (*p)->next->before
    (*p)->before
    (*p)->next
    (*q)->before->next
    (*q)->next->before
    (*q)->before
    (*q)->next
    これだけのポインタのつなぎ替えが必要ですよね。
    ato,
    **pが先頭、**pが末尾、**qが先頭、**qが末尾の場合の特別扱いが出てくる。

    もし僕がやるなら、番兵を置いて先頭と末尾の処理を不要にするかなぁ。

    キャンセル

  • 2018/01/25 13:38 編集

    僕なら交換するんじゃなく、"指定位置の要素を引き抜く"と"指定位置に要素を挿入する"のふたつを書きますね。両者はどっちみち必要になるはずだし。
    もちろんリストをもいっこ用意して "listA中最小の要素をlistBに移動"を繰り返すのがいっちゃん楽だが、
    時間計算量O(N^2)ではガマンできんのならマージソートかなー...

    キャンセル

  • 2018/01/25 13:41

    このコードは正常に動いているので、そういうのを確認します。ありがとうございました。

    キャンセル

  • 2018/01/25 15:04

    何のためにソートするのか、ですね。検索を早くしたいのなら木構造とかハッシュとかでもいいわけだし。

    キャンセル

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

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

関連した質問

  • 解決済

    スタックの応用

    スタックを利用して入力された文字列の回文を作るプログラムを作成したら、出力されません。 例えば、「abcd」と入力したら、「abcddcba」と主著力される。 発生して

  • 解決済

    c言語 リスト構造の検索

    アドレス帳の検索機能だけのプログラムを作っています。 作りたいプログラムは、  1,検索したい人の名前を入力する  2,事前に登録された情報の中から部分一致検索する 

  • 解決済

    オーバーフローします...

    前提・実現したいこと アルファベット順に表示したいです どうやったらアルファベット順に表示できますか? もし,このままでいいならオーバーフローを直して欲しいです... アル

  • 解決済

    C言語のエラー修正について

    コード #include <stdio.h> #define New (element) RealNew( & element ) #define InputInt( number

  • 解決済

    プログラムでポインタのポインタがはっきりわかりません。

    以下のプログラムでポインタのポインタがはっきりわかりません。 私なりのコメントをいれています。間違いがありましたらご指摘おねがいします。p->next = *ap;    で  *

  • 受付中

    リスト構造と待ち行列

    リスト構造と待ち行列をしたいのですが、よくわかりません。 おすすめのサイトや説明おねがいします。 #include <stdio.h> #include <stdlib.h>

  • 受付中

    C言語 リスト 新しいノードをリストの最後に追加

    C言語 リストについて ↓のプログラムでは入力した数字を逆順に表示 /* list.c */ #include <stdio.h> #include <stdlib.h> st

  • 解決済

    コードのどこで実行結果の「ファイルから読んだ文字列:hosi,nagoya,5436,mail-7」...

    コードのどこで実行結果の「ファイルから読んだ文字列:hosi,nagoya,5436,mail-7」 を表示しているんですか。 それと何度も教えてもらっているのですが、関数void

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

  • C

    3067questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。