ソートを自作

質問

一方向リストを使ってデータを記憶するプログラムに、ソート機能を持つ関数自作する。
機能は＜名前:辞書順、数字:小さい順＞に並び替える。
このとき以下のアルゴリズムしたがって作ります。

『与えられたリストをリストＡ、ソート済みのリストをリストＢと呼ぶことにする。処理の開始段階では、リストＢは空である。

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

長いですが、教えて下さい。<(_ _)>

回答No.5

sakusaker7 · ベストアンサー

> いろいろやってみたのですが、もう少しheadについて、教えてもらえないでしょうか？

特にこの辺を、というのがあると説明しやすいのですが
参考になるのは

単方向リスト(Singly Linked List)
http://homepage1.nifty.com/daccho/program/algo/slinklst.htm

とか。
このページの例ではダブルポインタを使ってますね。

んで、さっくりサンプルを書いてみました。
手抜きしているところがいくつかあるので、
その辺は注意してください
#mallocの戻り値をチェックしてないとか

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

typedef int DATA_TYPE;

struct CELL {
DATA_TYPE val;
struct CELL* next;
};
typedef struct CELL CELL;

CELL*
list_append(CELL* headp, DATA_TYPE val)
{
CELL* newcell;

newcell = (CELL *)malloc(sizeof (CELL));
newcell->val = val;
newcell->next = headp->next;
headp->next = newcell;

return headp;
}

CELL*
list_delete(CELL* headp, DATA_TYPE val)
{
CELL* prev = headp;
CELL* p = prev->next;

for (; p; prev=p, p=p->next)
if (val == p->val)
prev->next = p->next;

return p;
}

CELL*
list_find(CELL* headp, DATA_TYPE val)
{
CELL* p = headp->next;

for (; p; p=p->next)
if (val == p->val)
return p;

return NULL;
}

void
list_print(CELL* headp)
{
CELL *p = headp->next;
int count;

for (count=0 ;p; p=p->next)
printf("%d: %d\n", count++, p->val);
}

DATA_TYPE sampledata[] = {6, 3, 7, 2, 1, 9};

int
main()
{
CELL theHead = {0, NULL};
int i;

for (i=0; i<(sizeof sampledata / sizeof sampledata[0]); i++) {
list_append(&theHead, sampledata[i]);
}

list_print(&theHead);
list_delete(&theHead, 2);
printf("%s\n", "#####");
list_print(&theHead);
list_delete(&theHead, 9);
printf("%s\n", "#####");
list_print(&theHead);

return 0;
}

実行例:
0: 9
1: 1
2: 2
3: 7
4: 3
5: 6
#####
0: 9
1: 1
2: 7
3: 3
4: 6
#####
0: 1
1: 7
2: 3
3: 6

コメントをつけてるひまはなかったので、ここがわからん
というのがあれば例によって遠慮なくどうぞ。

参考URLの追加
データ構造
http://www5c.biglobe.ne.jp/~ecb/c/14_04.html

それから
C言語による最新アルゴリズム事典
http://amazon.jp/dp/4874084141
のような本を一冊手元に持っておくといいですよ。
この本はちょっと古いですけど、結構つかえます。
他にもこの手の本はいろいろありますので
本屋なりで探してみるのもよいと思います。

回答No.4

sakusaker7

> 方法として、先頭を削除するとき削除する前のノードがないとできないのはわかるので、
> 削除するノードのまえに空ノードを作ろうと考えたのですが、そのやり方がわかりません。
> 何度もすいません。もう一度アドバイスください。

ん、いいとこついていますね。
いろいろやり方はありますけど、たとえば
MEMBER head; //ポインタ変数ではない
という変数を宣言しておいて、

head.next は最初(つまりリストが空の場合)はNULLを入れておいて、
リストに要素を追加するときは
p = ノード作成関数();
p->next = head.next;
head.next = p;
のようにして追加していきます。こうすることで、head.nextは
常にリストの先頭を指すようになります。

で、リストを扱う関数の引数には &head とそのアドレスを渡してやると。
リストを終端まで手繰る部分がちょっと変わりますが基本的には同じです。

もし複数のリストを一度に扱いたいのでheadのように固定的な宣言をした変数ではいやだというのなら、
headの役目をする変数も MEMBER *headp のようにしておいて、さらに
関数にはそのアドレス、つまり
list_function(MEMBER **head, ...)
のようにダブルポインタを渡すというやり方もあります。

もっと詳しく説明してほしいということなら遠慮なく補足で要求してください。
今は寝る直前なのでプログラム片で例を示すことはできませんでした。
ごめんして。

補足

いろいろやってみたのですが、もう少しheadについて、教えてもらえないでしょうか？

参考URLでもいいのでお願いします<(_ _)>

回答No.3

sakusaker7

これくらいの長さならまだ読めなくもないから良いですよ。
変数名のつけ方とかがめちゃくちゃだと
読む気にもなりませんけど(笑)

んじゃあまず、

void remove_max(MEMBER *list, MEMBER *max, int(*compar)(const void*, const void*)){ /* 最大値maxをlistから削除 */

に、最大値が先頭要素であるリストとか、
要素が一つだけのリストを渡したときにどのように
動作するか、デバッガでステップ実行してみてください。

そうしたらどこがおかしいかわかるんじゃないかな。

もうひとつ、
remove_max(list, max, (int(*)(const void*, const void*))compar);
sorted = (MEMBER *)malloc(sizeof(MEMBER));
strcpy(sorted->name, max->name);
sorted->number = max->number;

は、remove_max で最大値を持つ要素は取り除かれている
(freeされている)から、そのあとで
max->name, max->numberにアクセスするのはまずいです。

補足

アドバイスをみて、やってみました。
MEMBER *listsort(MEMBER *list, int(*compar)(const void*, const void*)){ /* ソート関数 */
の　remove_max(list, max, (int(*)(const void*, const void*))compar);
の位置が変だということわかりました。

void remove_max(MEMBER *list, MEMBER *max, int(*compar)(const void*, const void*)){ /* 最大値maxをlistから削除 */
に『先頭を削除する』ときに先頭が消せないという問題があるのは気付けたのですが、うまくできません。
方法として、先頭を削除するとき削除する前のノードがないとできないのはわかるので、削除するノードのまえに空ノードを作ろうと考えたのですが、そのやり方がわかりません。

何度もすいません。もう一度アドバイスください。

回答No.2

sakusaker7

> 長いですが、教えて下さい。<(_ _)>
何を?

とりあえず

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;

sorted=tmp の次の行で tmp=sorted ってのは
何を狙っているかわかりません。
それにこのループでは

> 3: 要素ＣをリストＢの先頭に挿入する。

をやろうとしているように感じられなくはありませんが
できてませんね。

疑問に思っていること、質問したいことを
もう少し具体的にしてみてください。
#正直手を入れたいところはたくさんありますが
#我慢しておきます

補足

質問者のsy5399912です。
投稿してすぐ回答してもらってありがとうございます。
初投稿で、いろいろわかってなくてすいませんでしたm(_ _)m
短くしたつもりですが、やっぱり長すぎますよね～。

教えてほしいのは、listsort( , )で返すsortedをprintfしたとき、バグってしまいます。例えば、数の小さい順にしたとき、前に挙げたデータ例をソートすると、
『OKITA: 1.
　OKITA: 1.
　OKITA: 1.
　<� a<� a: 2.
<� a<� a: 3.
　<� a<� a: 4.
　<� a<� a: 5.
　<� a<� a: 6.
　<� a<� a: 7.
　<� a<� a: 8.
　<� a<� a: 9.
　<� a<� a: 10.
　%s: 0.　　　　　』
『名前が出てない、memberの数が変』みたいなことになってしまいます。
そこで、sortedがちゃんとprintfするにはどうすればいいか教えて下さい。

前に挙げたコード少し変えたのでその部分だけ載せます。また長くなっていますが、お願いします。

MEMBER *listsort(MEMBER *list, int(*compar)(const void*, const void*)){
MEMBER *sorted, *ret, *res, *tmp, *max;
res=list, ret=list;
int s=0;
for(;res != NULL ;res = res->next){ s++; } /* listに入っているデータの数を数える。 */
for (; s!=0; ret=ret->next){ /* 3:要素ＣをリストＢの先頭に挿入する。 */
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->next = tmp;
tmp = sorted;
s--;
} /* 4:リストＡが空であれば終了。空でなければ Step1 にもどる。 */
return sorted;
}

MEMBER *find_max(MEMBER *list, int(*compar)(const void*, const void*)){ /* 1:リストＡの要素の中で、最大値をもつ要素Ｃを探す。 */

void remove_max(MEMBER *list, MEMBER *max, int(*compar)(const void*, const void*)){ /* 2:要素ＣをリストＡから削除する。 */

回答No.1

noname#96023

全部読んでる暇は無いので回答は出来ませんが、
全体的にコメントが少ないです。

他人のプログラムを読むほど、時間がかかり苦労するものは無いと認識したほうが良いですよ。