ソートを自作
一方向リストを使ってデータを記憶するプログラムに、ソート機能を持つ関数自作する。
機能は＜名前:辞書順、数字:小さい順＞に並び替える。
このとき以下のアルゴリズムしたがって作ります。
『与えられたリストをリストＡ、ソート済みのリストをリストＢと呼ぶことにする。処理の開始段階では、リストＢは空である。
1: リストＡの要素の中で、最大値をもつ要素Ｃを探す。
2: 要素ＣをリストＡから削除する。
3: 要素ＣをリストＢの先頭に挿入する。
4: リストＡが空であれば終了。空でなければ Step1 にもどる。 』
下のコードは自分で考えてみたものです。全部は長いので構造体、関数のみ載せます。
typedef struct member{
char name[40];
int number;
struct member *next;
} MEMBER;
int compar_name(const MEMBER *x, const MEMBER *y){
return strcmp(x->name, y->name);
}
int compar_number(const MEMBER *x, const MEMBER *y){
return (x->number - y->number);
}
void remove_max(MEMBER *list, MEMBER *max, int(*compar)(const void*, const void*)){ /* 最大値maxをlistから削除 */
MEMBER *p, *q;
p=list->next;
q=list;
if(p==NULL && compar(q,max)==0) { return; }
else if(compar(q,max)==0) { q=p; }
else{
while(compar(p,max)!=0) { q=p; p=p->next; }
q->next=p->next;
free(p);
}}
MEMBER *find_max(MEMBER *list, int(*compar)(const void*, const void*)){ /* 最大値maxを探す */
MEMBER *ptr, *max;
for (ptr=max=list; ptr!=NULL; ptr=ptr->next){
if (compar(max,ptr)<0){ max=ptr; }
} return max;
}
MEMBER *listsort(MEMBER *list, int(*compar)(const void*, const void*)){ /* ソート関数 */
MEMBER *sorted, *ret;
ret=list;
for (;ret->next; ret=ret->next){
MEMBER *tmp, *max=NULL;
max=find_max(list, (int(*)(const void*, const void*))compar);
remove_max(list, max, (int(*)(const void*, const void*))compar);
sorted=(MEMBER *)malloc(sizeof(MEMBER));
strcpy(sorted->name, max->name);
sorted->number=max->number;
sorted=tmp;
tmp=sorted;
} return sorted;
}
並べ替えるデータの例:
OKITA 1
HARADA 10
TOUDOU 8
INOUE 6
SAITOU 3
NAGAKURA 2
TAKEDA 5
TANI 7
MATUBARA 4
SUZUKI 9
長いですが、教えて下さい。<(_ _)>
補足
ありがとうございます。SortedList SLをList Lから作るとうい関数なのですが、これから作成されるSLが引数というのはなぜでしょうか？