リスト構造のソートで悩んでます。。。

質問

リスト構造のソートで悩んでます。プログラムの内容はファイルからデータをリスト構造の構造体に読み込み、名前順にソートし結果を表示する。というものです。データの追加や削除はできるのですがソートとなると頭が混乱してしまいお手上げ状態になってしまいました。。。。。
読み込み用のデータとプログラムソースを以下に記載するのでどなたか良きアドバイスをお願いしますm(_ _)m

○データ

Sakuragi
16
Rukawa
16
Miyagi
17
Akagi
18
Mitsui
18

○ソース
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MENBER 5

typedef struct data{
char name[BUFSIZ];
int age;
struct data *next;
}LIST;

LIST *newLIST(void);
LIST *sort(LIST *);

int main(int argc,char *argv[]){

FILE *fp;
LIST *p;
LIST *np;
LIST *npb;
LIST *head;

char namae[BUFSIZ];
int toshi,i;

if((fp=fopen(argv[1],"r"))==NULL){
printf("no file\n");
exit(1);
}

head = newLIST();
npb =head;

for(i=0;i<MENBER;i++){
np = newLIST();
fscanf(fp,"%s %d",namae,&toshi);
strcpy(np->name,namae);
np->age = toshi;

npb->next =np;
npb = np;
}

sort(head);

for(p=head->next;p != NULL;p=p->next){
printf("%s\t%d\n",p->name,p->age);
}

for(p=head->next;p != NULL;p=np){
np = p->next;
free(p);
}

fclose(fp);
return(0);
}

LIST *newLIST(){
LIST *p;
p = (LIST *)malloc(sizeof(LIST));
p->next = NULL;
return(p);
}

LIST *sort(LIST *head){
}

回答No.2

chie65536 · ベストアンサー

ソートするには「リストの順を入れ替える」か「リストの順は変えずにデータを入れ替える」と言う処理が必要です。

第１案　リストの順を入れ替える

リストの順を入れ替えるには、各項目のnextメンバを入れ替えます。

例えば
Ａ→Ｂ→Ｃ→Ｄ→Ｅ
の状態でＢとＤを入れ替えるには
「Ｂを指す、Ａ->next」と「Ｄを指すＣ->next」を入れ替え
「Ｂの次を指す、Ｂ->next」と「Ｄの次を指す、Ｄ->next」を入れ替え
と言う２つの「入れ替え」を行わなければなりません。

「Ｂ」を参照している時に「Ｂを指す、Ａ->next」を知るには「Ｂの前は何か？」を知る必要があります。

リストの項目が少ないならば、先頭から順にサーチしていけば良いですが、項目が増えればサーチに時間が掛かり、現実的ではありません。

また、nextメンバの入れ替えが煩雑になり、あまり適切とは言えません。

第２案　データの実体を入れ替える

入れ替えの際にnextメンバを変更せず、nameメンバの内容、ageメンバの内容を入れ替えます。

この場合、ソート後に一番末尾になる項目が先頭にある、と言う場合、データの実体の入れ替えが何回も発生します。

もし「データの実体サイズ」が大きいと、メモリアクセスが膨大に発生し、実用にならない速度になります。

第３案　リストの順、データの実体は入れ替えず、リストからデータへの参照のみ入れ替える。

データ構造体とリスト構造体を分離します。

typedef struct data_t {
char name[BUFSIZ];
int age;
} DATA;

typedef struct list_t {
DATA *data;
LIST *next;
} LIST;

void swapLIST(LIST *p1,LIST *p2)
{
DATA *tp;
tp = p1->data;
p1->data = p2->data;
p2->data = p1->tp;
}

LIST *newLIST(){
LIST *lp;
DATA *dp;
lp = (LIST *)malloc(sizeof(LIST));
if(lp==NULL) return(NULL);
dp = (DATA *)malloc(sizeof(DATA));
if(dp==NULL) {free(lp); return(NULL);}
lp->data = dp;
lp->next = NULL;
return(lp);
}

void sort(LIST *top){
LIST *p1;
LSTT *p2;
for(p1=top;p1->next!=NULL;p1=p1->next){
for(p2=p1->next;p2!=NULL;p2=p2->next){
if(strcmp(p1->data->name,p2->data->name) > 0) swapLIST(p1,p2);
}
}
}

int main(int argc,char *argv[]){

FILE *fp;
LIST *p;
LIST *np;
LIST *head;

char namae[BUFSIZ];
int toshi,i;

if((fp=fopen(argv[1],"r"))==NULL){
printf("no file\n");
exit(1);
}

head = NULL;
np = NULL;

for(i=0;i<MENBER;i++){
p = newLIST();
if(p==NULL) break;/*メモリ不足*/
if(head==NULL) head=p;/*最初の１個目*/
if(np!=NULL) np->next =p;/*１つ前があるなら、１つ前のnextをpに繋げる*/
fscanf(fp,"%s %d",namae,&toshi);
strcpy(p->data->name,namae);
p->data->age = toshi;
np=p;
}

sort(head);

for(p=head;p != NULL;p=p->next){
printf("%s\t%d\n",p->data->name,p->data->age);
}

for(p=head;p != NULL;p=np){
free(p->data);
np = p->next;
free(p);
}

スワップ・ソートを行う場合、２つのリストのdataメンバのみ入れ替えれば良いので、かなり処理が軽く、この方法が一番現実的です。

なお、最初に確保するデータが無駄になっているので改良してあります。

お礼

３つもアドバイスを頂いて感謝します。
私は３番目のアドバイスを参考にさせてもらいました。
構造体を入れ替えるのではなく中身のメンバを入れ替える部分に
感動を覚えました！！なるほど！！みたいな。

回答No.4

solidnoise

線形リストのソートならマージソートを使ってはどうでしょうか。
ちょうどピッタリのページがありましたのでご紹介いたします。

参考URL：

http://www.geocities.jp/ky_webid/algorithm/021.html

お礼

ありがとうございます。
プログラムの勉強は最近はじめたばかりでマージシートという言葉も初めて耳にしました。まだ難しくて分かりませんが少しずつ勉強して理解できるようがんばります（＾＾）

回答No.3

___noboru___

これだとLISTのメンバが多くなればなるほど重くなりそうですが…。

static int listcmp(const void *a, const void *b)
{
　LIST *p, *q;
　int d;

　p = (LIST *) a;
　q = (LIST *) b;

　if ((d = p->age - q->name) == 0)
　　d = strcmp(p->name, q->name);

　return d;
}

LIST *sort(LIST *head)
{
　LIST *p, *buf;
　int n, i;

　/* 0個または1個は並べ替える必要がないのですぐ帰る */
　if (head == NULL || head->next == NULL)
　　return head;

　/* リストの要素数を数える。 */
　for (p = head, n = 0; p; p = p->next, n++);

　/* その分のメモリを確保する。 */
　if ((buf = (LIST *) calloc(n, sizeof(LIST))) == NULL) {
　　perror("calloc()");
　　exit(1);
　}

　/* 中身を buf の方に移す。 */
　for (i = 0, p = head; i < n; i++, p = p->next)
　　buf[i] = *p;

　/* クイックソートする。 */
　qsort(buf, n, sizeof(*buf), listcmp);

　/* 中身を元に戻す。 */
　for (i = 0, p = head; i < n; i++, p = p->next) {
　　strncpy(p->name, buf[i].name, sizeof(p->name));
　　p->age = buf[i].age;
　}

　/* bufはもう不要なのでメモリ開放 */
　free(buf);
}

お礼

アドバイスありがとうございます。
私はプログラムの知識が少ないのでcallocやp = (LIST *) a;などの
使い方がよく理解できてません。でもアドバイスを有効に活用できるよ
うにがんばって勉強します！！

回答No.1

osamuy

LIST型ポインタの配列をmallocし、そこにリストの要素のポインタを代入して、配列をqsortして、ソートした結果からリストを再リンクすれば良いかと。

お礼

簡潔かつ明確なアドバイス感謝です。
上でも書きましたが私はまだプログラムの勉強量が少ないので
理解できていない関数が多々あります。qsortもそのひとつで
いまいち理解できておりません。。。これからもがんばって勉強して
アドバイスを活用できるようになりたいです。