Q&A
excange()が何をするものかを記せ。コメントもないコードを解釈する気にならん。
リストの構造体のデータをソートしているコードがあるんですが、
exchange()関数のところを図を使って書こうと思ったのですが、うまくいきません。
図で説明してもらえませんか。
exchange()関数のところでデータが同じ場合にはそのままreturnして
*p,*ｑをｒ、ｓで保存しているところまでは分かるのですが、そのあとが
さっぱりわかりません。
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
回答3件
0
ベストアンサー
こんにちは。
ちょっと難しいので、最初の質問だけ。
&((*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 13:49
総合スコア23272
ありがとうございます。たすかりました。図を書いてかくにんします。
ここがしっかり理解できないのに、そのつぎはないですね。
１つ１ついろんな方に説明をいただきながら、がんばります。
0
ノードの交換をやりたいのかな?
僕だったらアタマひねってポインタいぢくるより
name,address,tel,mail のﾅｶﾐを交換する。
[追記]
てかまず構造自体をいぢくりますね。扱いたいデータとそのつながりとは本来別モノなんだから。
C
1struct address { 2 名前やら住所やらモロモロ 3}; 4 5struct link { 6 struct address* data; 7 struct link* next; 8 struct link* prev; 9};
こうしておけばデータの交換が楽。
投稿2018/01/25 03:01
編集2018/01/25 03:09総合スコア16614
すみません。excange()関数の中で行っているポインタのやり取りがわからないのです。
たぶんデータの大小を確認して交換して、そのどこかで*headもかえているんとおもうのですが、
コメントを自分なりにつけていたのですが。今読み返すと何を言っているのか分からなくて、
図を書いて理解しようとしたのですが，それもできないので質問しています。
この書き変えは後で挑戦させていただきます。ありがとうございます。
もうねますので明日またやります。
> たぶんデータの大小を確認して交換して、そのどこかで*headもかえているんとおもうのですが、
違いますね。比較とheadの更新はexchangeの外でやってます。
exchangeはリンクの張り替えのみ。
はい。ありがとうございます。あしたゆっくり確認します。
void data_sort(struct address **head) の戻り値pはexchange(head, p);を使って
これがheadになるということですか。そのあとは順次headの付け替えをするということですか。
exchangeのリンクの張り替えのみのところを解説してもらえませんか。
ごめん、こんなクソめんどくさいコード書かないので僕はパス。申し訳ないが他の方の回答を待ってください。
# 「難しいプログラムは間違っている」が信条なのです
すみませんでした。
ぃぇぃぇ、質問に正面から答えていない僕の落ち度です。
ポインタのポインタを復習してから見てみます。
(解読の例)
●->next を ●の次
●->before を ●の手前
と読み替えてごらん。
if (s->next != 0){
s->next->before = r;
}
は、「sの次が存在するなら、そいつの手前をrにする」と読める。
つまり" r ← sの次 " ってゆー上り方向のリンクを張り替えたってこと。
ありがとうございます。ねます。
0
ソート済みのリンクリストを作りたいのなら、要素交換で行うのではなくて先頭からひとつづつ要素をとり出して別リストに挿入してゆくほうが楽だとおもいます。
というか、順序を気にするのならリスト構造をやめるか、あるいは最初データを読み込む時点でソートしながら読み取って、ソートコマンドなんてなくしてしまうとか。
if(p==q)も pとqが同じ構造体であることを調べたいのならif(*p==*q)？
あと、二重ポインタを引数に使わなくて済む関数仕様にした方が安全かなぁ。
投稿2018/01/25 04:03
総合スコア702
ありがとうございます。コード自体が悪いみたいです。
非常に面倒ですが、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が末尾の場合の特別扱いが出てくる。
もし僕がやるなら、番兵を置いて先頭と末尾の処理を不要にするかなぁ。
僕なら交換するんじゃなく、"指定位置の要素を引き抜く"と"指定位置に要素を挿入する"のふたつを書きますね。両者はどっちみち必要になるはずだし。
もちろんリストをもいっこ用意して "listA中最小の要素をlistBに移動"を繰り返すのがいっちゃん楽だが、
時間計算量O(N^2)ではガマンできんのならマージソートかなー...
このコードは正常に動いているので、そういうのを確認します。ありがとうございました。
何のためにソートするのか、ですね。検索を早くしたいのなら木構造とかハッシュとかでもいいわけだし。
あなたの回答
tips
プレビュー
