Cのソートについて

[hide]

Cのソートについて質問です。

struct Data
{
int code; // 社員コード
char name[32]; // 氏名
int birth; // 誕生日
struct Data *next // 次のデータを指すポインタ
}

上のような構造体を宣言したとします。

*nextの部分にstruct Data分の領域をmallocし、次のデータとして、データを増やしていきます。
この時、社員コード，又は指名の昇順にソートしたいのですが、データを入れ替えるのではなく、*nextの値だけを書き換えて昇順に参照できるようにしたいのですが、どうしてもやり方がわかりません・・

struct Data shain
{
{3,"murata",19830215,社員コード = 2のデータが格納されている構造体の先頭アドレス}, // 先頭アドレス
{2,"nakata",19870421,社員コード = 1のデータが格納されている構造体の先頭アドレス},
{1,"kubota",19790615,NULL},
};

上のようにデータが入っているとして、"murata"のデータがshainの先頭アドレスとします。

それを以下のようにソートしたいのです。

struct Data shain
{
{3,"murata",19830215,NULL},
{2,"nakata",19870421,社員コード = 3のデータが格納されている構造体の先頭アドレス},
{1,"kubota",19790615,社員コード = 2のデータが格納されている構造体の先頭アドレス}, // 先頭アドレス
};

そして、shainの先頭アドレスを"kubota"に設定したいのです。

このやり方をどなたか、教えてもらえないでしょうか？

よろしくお願いします。

[組木紙織]

双方向リストじゃなくて単方向リストですか？
単方向ならマージソートするのがやりやすいんじゃないでしょうか？

[ookami]

曲解かもしれませんが
struct Data *next // 次のデータを指すポインタ
の代わりに
struct Data *codenext // 次の社員コードのデータを指すポインタ
struct Data *namenext // 次の名前のデータを指すポインタ
を持たせて二重管理するのはどうでしょうか。挿入・削除の時だけ気をつければソートの必要そのものがなくなるのではと考えたので。

[組木紙織]

>ookamiさん
二重管理は手法としてはありだと思いますが、今回の場合どうなんでしょうか。
実際に使うためだとしたら、いいですが、
課題に使うのだとしたら、だめですよね。


リンクリストのマージソートの方法です。
http://www.geocities.jp/ky_webid/algorithm/021.html

[たいちう]

私が実装するとしたら、(struct Data *)の配列を用意します。

1) リストの各要素へのポインタを配列に代入。
2) ポインタの先を参照しながら配列をソート。
3) 配列を見ながら、リストのnextを順に設定。