C言語関係掲示板

過去ログ

No.272.構造体のソート

[戻る] [ホームページ]


No.1628

構造体のソートをおしえてください!!
投稿者---さっちゃん(2002/05/31 15:27:35)


今とってもこまってます・・・。構造体
typedef struct list{
char name[MAX]; //名前
int score; //得点
struct list *before; //前のlistの構造体へのポインタ
struct list *next; //次のlist構造体へのポインタ
}LIST;
があったとして、
scoreの昇順に並べたいのです。実体のいれかえだと簡単に出来るのですが、

if(kari->score < nextp->score)
{
   strcpy(name_w,kari->name);//名前・得点を入れ替える
   score_w = kari->score;
   strcpy(kari->name,nextp->name);            kari->score = nextp->score;
   strcpy(nextp->name,name_w);
   nextp->score = score_w;
}
なかんじで・・・・。でも、
私としては、構造体の中で宣言したポインタを使っていれかえたいのです。
誰かお力をおかしください!!!




No.1629

Re:構造体のソートをおしえてください!!
投稿者---shelly(2002/05/31 15:43:56)


例えばリンクリストが、A-B-C-Dとつながっていて、BとCを入れ替えたい場合、
次の6つの値を更新する必要があります。
 A.next
 B.next
 B.before
 C.next
 C.before
 D.before

ではそれぞれの値をどう更新すればいいか考えてみてはどうでしょう。
swap(LIST *B, LIST *C)
てな感じの関数に出来そうですね。


No.1630

shellyさんへ
投稿者---さっちゃん(2002/05/31 15:58:47)


shellyさんアドバイスありがとうございました。
もう一度考えてみようとおもいます。


No.1631

やっぱりわかりません!!!!!!
投稿者---さっちゃん(2002/05/31 17:43:46)


すいません・・・。やっぱり分かりません・・・。shellyさんから例えばリンクリストが、A-B-C-Dとつながっていて、BとCを入れ替えたい場合、
次の6つの値を更新する必要があります。
 A.next
 B.next
 B.before
 C.next
 C.before
 D.before

ではそれぞれの値をどう更新すればいいか考えてみてはどうでしょう。
swap(LIST *B, LIST *C)
てな感じの関数に出来そうですね
ってな具合にアドバイスをもらったのですが・・・。
上のような関数をつくり、nextの場合、beforeがNULLの場合、両方違う場合
でわけた処理を考えてみたのですが、
二度目の交処理でおかしくなってしまいます。
・・・どうしたらよいのでしょうか。


No.1632

Re:やっぱりわかりません!!!!!!
投稿者---shelly(2002/05/31 18:09:39)


>上のような関数をつくり、nextの場合、beforeがNULLの場合、両方違う場合
>でわけた処理を考えてみたのですが、

ここまで気が回っているのなら完成は近そうですね。
せっかく自分で作ってみたんですから、ソースを載せてみてはどうですか?

>二度目の交処理でおかしくなってしまいます。
>・・・どうしたらよいのでしょうか。

期待する結果と違う結果が得られた場合、1行ずつ追いかけて
どこで裏切られているか調べていくのが(面倒ですが)確実です。
1度目は成功して2度目で失敗するなら、1度目と2度目で必ず何かが違うはず
です。
自分のソースは根気よく見てあげましょう。


No.1633

Re:構造体の(リストの)ソートをおしえてください!!
投稿者---kikk(2002/05/31 21:02:33)


ども。


リストのソートは、選択法か、挿入法か、マージソートが
よろしいかと。これらの場合、リストだとスワップは不要で、
要素の移動ですみます(前の2つの方法は1回の反復で移動1回)。
移動は、削除して(とっておいて)、挿入、という手順で
リンクをつなぎかえればOKです。


>私としては、構造体の中で宣言したポインタを使っていれかえたいのです。

という意見に水を差すようですが、せっかくリストを使ってるんだから、
と思った次第。気が向いたら検討してみてください。。


では。

No.1642

Re:構造体のソートをおしえてください!!
投稿者---かずま(2002/06/02 03:28:07)


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

typedef struct Score Score;
struct Score {
    char name[20]; 
    int  score;
    Score *prev, *next;
};

void initialize(Score *sp)
{
    sp->prev = sp->next = sp;
}

void cleanup(Score *sp)
{
    Score *p = sp->next;
    while (p != sp) {

        Score *t = p;
        p = p->next;
        free(t);
    }
    sp->prev = sp->next = sp;
}

void add(Score *sp, const Score *s)
{
    Score *p = malloc(sizeof(Score));
    if (p == NULL) fputs("out of memory\n", stderr), exit(1);
    strcpy(p->name, s->name);
    p->score = s->score;
    p->prev = sp->prev;
    p->next = sp;
    sp->prev->next = p;
    sp->prev = p;
}

void sort(Score *sp)
{
    Score *p1, *p2, *p3;

    if (sp->next == sp)
        return;
    for (p1 = sp->next->next; p1 != sp; ) {
        int score = p1->score;
        p2 = p1;
        p1 = p1->next;
        for (p3 = p2->prev; p3 != sp && p3->score < score; p3 = p3->prev)
            ;
        p2->prev->next = p2->next;
        p2->next->prev = p2->prev;
        p2->prev = p3;
        p2->next = p3->next;
        p3->next->prev = p2;
        p3->next = p2;
    }
}

int main()
{
    Score data, *sp;

    initialize(&data);

    while (scanf("%19s%d", data.name, &data.score) == 2)
        add(&data, &data);

    sort(&data);

    for (sp = data.next; sp != &data; sp = sp->next)
        printf("%-10s %4d\n", sp->name, sp->score);

    cleanup(&data);
    return 0;
}

[入力データ]
Ando    80
Kato   100
Sato    40
Tanaka  75
Nagano  60

[出力データ]
Kato        100
Ando         80
Tanaka       75
Nagano       60
Sato         40


No.1650

Re:構造体のソートをおしえてください!!
投稿者---さっちゃん(2002/06/03 10:00:55)


かずまさんのmainの部分の
add(&data, &data);
の()内部の意味が理解できません。
ホントに初心者なもので・・・。
よろしければ教えてやってください。



No.1653

Re:構造体のソートをおしえてください!!
投稿者---かずま(2002/06/03 19:12:02)


> add(&data, &data); の()内部の意味が理解できません。

initialize(&data), sort(&data), cleanup(&data) の &data は分かるけれども、
add(&data, &data) の &data は分からないということでしょうか。
それとも、同じ引数を 2つとっていることでしょうか。

何を説明したらいいのかよく分かりませんが、とにかく、紙と鉛筆を用意してください。

initialize(&data) を実行したあとの data の図を書いてみてください。
次に、add(&data, &data) を実行した後の図を書いてみてください。
さらに、add(&data, &data) を 3回ぐらい実行した図を書いてみてください。

書けましたか。

data.next は、リストの先頭へのポインタです。
data.prev は、リストの末尾へのポインタです。

data.name と data.score は、単に入力用のバッファとして使っているだけです。

Score temp;
while (scanf("%19s%d", temp.name, &temp.score) == 2)
  add(&data, &temp);

と書いてもかまいません。
第1引数は、initialize()、sort()、cleanup()と同様に、リストを扱うためのものです。
第2引数は、リストの末尾に追加したいデータを与えるものです。
だから、add には 2つの引数があるのです。

temp を用意してもよいのですが、でも、data.name と data.score が余っているので、
それを使っているだけのことです。

リストの先頭の prev は、NULL ではなく、data を指しています。
リストの末尾の next は、NULL ではなく、data を指しています。

NULL がないので、リストの要素の追加や削除のとき、端の処理を特別扱いする必要が
ありません。

以上の説明で分からなかったら、また質問してください。
ただし、どこが分からないのか、何が分からないのかを具体的に書いてください。

この説明で分かったのなら、なぜ最初に分からなかったを教えてください。
図は書いてみましたか。