C言語関係掲示板

過去ログ

No.３９９．自己参照構造体のソート

[戻る]　[ホームページ]
No.2742
自己参照構造体のソート
投稿者---かん(2002/09/19 14:43:27)


１５章でとりあげられている自己参照構造体なんですが、
参考書などで問題を解いていたら、「名前をアルファベット順にソートしなさい」など
ソートも一緒に書かれていました。

構造体ポインタの受け渡しのところがソートをしてきちんと
順番に渡すところができませんでした。

まだ初心者の私にはこのあたりのところがわかりづらいので
解説を載せて頂けるとうれしいのですが。
よろしくお願い致します。
No.2744
Re:自己参照構造体のソート
投稿者---かずま(2002/09/19 17:14:36)


> １５章でとりあげられている自己参照構造体なんですが、
> 参考書などで問題を解いていたら、「名前をアルファベット順にソートしなさい」など
> ソートも一緒に書かれていました。

15章のプログラムの add_list() を次のように書き直せばよいでしょう。
struct list *add_list(int key, char *name, struct list *head)
{
    struct list *prev, *cur;
    struct list *p = malloc(sizeof *p);
    
    if (p == NULL) { printf("out of memory\n"); exit(1); }
    p->key = key;
    strcpy(p->name, name);
    p->next = NULL;
    
    if (head == NULL || strcmp(name, head->name) < 0) {
        p->next = head;
        return p;
    }
    for (prev = cur = head; (cur = cur->next) != NULL; prev = cur) {
        if (strcmp(name, cur->name) < 0) {
            p->next = cur;
            break;
        }
    }
    prev->next = p;
    return head;
}

No.2747
Re:自己参照構造体のソート
投稿者---かずま(2002/09/19 18:19:46)


strcpy() の次の p->next = NULL; が冗長でした。
    strcpy(p->name, name);
    
    if (head == NULL || strcmp(name, head->name) < 0) {
        p->next = head;
        return p;
    }
    for (prev = cur = head; (cur = cur->next) != NULL; prev = cur)
        if (strcmp(name, cur->name) < 0) break;
    p->next = cur;
    prev->next = p;
    return head;

No.2754
Re:自己参照構造体のソート
投稿者---かん(2002/09/19 23:56:03)


>strcpy() の次の p->next = NULL; が冗長でした。
strcpy(p->name, name);

わざわざ訂正までして頂いてありがとうございます。
p->next = NULL; があっても正しい動作をしたのですが？
あった場合はなぜいけないのでしょうか？

＞ for (prev = cur = head; (cur = cur->next) != NULL; prev = cur)
if (strcmp(name, cur->name) < 0) break;

ここの、for文の最後のprev = curのところが、トレースしてみたのですが
わからなかったのですが。

すみませんが、よろしければもう１度解説お願いします。
No.2755
Re:自己参照構造体のソート
投稿者---かずま(2002/09/20 02:13:04)


>> strcpy() の次の p->next = NULL; が冗長でした。

> p->next = NULL; があっても正しい動作をしたのですが？
> あった場合はなぜいけないのでしょうか？

冗長というのは、あってもいいけど、無駄だということです。
(1) 最初の if 文で return するとき
    p->next = NULL;
    p->next = head;

(2) for 文で、break するとき、
    p->next = NULL;
    p->next = cur;

(3) for 文で、break しないとき、
    p->next = NULL;
(1)と(2)は冗長ですよね。書き直したほうでは、p->next への代入は一回です。

> for (prev = cur = head; (cur = cur->next) != NULL; prev = cur)
>     if (strcmp(name, cur->name) < 0) break;
>
> ここの、for文の最後のprev = curのところが、トレースしてみたのですが
> わからなかったのですが。
この for ループは、次のように書いたほうが分かりやすかったかもしれません。
    prev = head,  cur = head->next;
    for ( ; cur != NULL; prev = cur,  cur = cur->next)
        if (strcmp(name, cur->name) < 0) break;
cur で、リストの要素を次々と見ていくのですが、p の指す新しい要素を挿入する
場所が見つかったとき、その cur の前に挿入するには、一つ前の要素へのポインタ
が必要です。それが prev なのです。図を描いてたどってみてください。

もしも、ひとつのポインタでループを回りたければ、次のようにすれば出来ます。
    for (prev = head; prev->next != NULL; prev = prev->next)
        if (strcmp(name, prev->next->name) < 0) break;

    p->next = prev->next;
    prev->next = p;
    return head;

余談ですが、if (strcmp(name, cur>name) <= 0) break; としたほうが、早く
ループを抜ける可能性があります。
No.2762
Re:自己参照構造体のソート
投稿者---かん(2002/09/21 00:38:47)


>この for ループは、次のように書いたほうが分かりやすかったかもしれません。<pre>
prev = head, cur = head->next;
for ( ; cur != NULL; prev = cur, cur = cur->next)
if (strcmp(name, cur->name) < 0) break;
</pre>cur で、リストの要素を次々と見ていくのですが、p の指す新しい要素を挿入する
>場所が見つかったとき、その cur の前に挿入するには、一つ前の要素へのポインタ
>が必要です。それが prev なのです。図を描いてたどってみてください。
>
>もしも、ひとつのポインタでループを回りたければ、次のようにすれば出来ます。
><pre>
for (prev = head; prev->next != NULL; prev = prev->next)
if (strcmp(name, prev->next->name) < 0) break;

p->next = prev->next;
prev->next = p;
return head;
</pre>
>余談ですが、if (strcmp(name, cur>name) <= 0) break; としたほうが、早く
>ループを抜ける可能性があります。

詳しい解説とソースありがとうございました。
絵を書いてトレースしてみてよくわかりました！
ありがとうございました。