自己参照型構造体とソート

質問

現在Ｃ言語の自己参照型について勉強をして入るのですが
mallocで確保した領域でソートを行うにはどのようにすれば
良いのでしょうか。
(qsort関数は使わず、独自の関数で行う)

*図
-database
|number
|name
|next----batabase
_____________|number
_____________|name
_____________|next------と続く

ソースコード
#include <stdio.h>

struct database{
int number;
char f_name;
struct *next;
};

int data_sort(){
/* ここのやり方がWebを見ても理解が出来ない状態です。 */
}

int main(){
struct database *d1,*d2;
d1 = (struct database *)malloc(sizeof(struct database*))
d2 = NULL;

while(cnt < 10){
scanf("%d",&d1->number);
scanf("%s",d1->name);

d1->next = d2;
d2 = d1;
cnt++;
}
data_sort();
}

回答No.3

asuncion · ベストアンサー

＞「ソートしてある状態を保ちながら、リストへ挿入する」
＞というのは、mainで配列を組んで配列内でソートしてから、
＞ソートした値をmallocで確保した領域に入れるという事なのでしょうか・・。

そうではありません。
配列は一切使いません。リスト構造を使っている意味がなくなりますので。

「ソートしてある状態を保ちながら、リストへ挿入する」とは、こういうことです。

リストの初期状態（空っぽであることです）を含めて、当該のリストは
何らかのキー（番号とか名前）でソート済です。
そのリストを先頭からサーチしていくと、いま着目しているデータを
リストのどこに挿入すればよいかがわかります。
挿入すべき場所が見つかったら、適切にポインタを張り替えます。
こうすることで、当該のリストは「いつでもソート済」の
状態にあることになります。

お礼

上記の事を元に自分自身で解決して見ます。
ありがとうございました。

補足

回答ありがとうございます。
何となくですが、少し見えてきたような気がします。
ポインタの張替え方法が、分からないので例えでいいので
教えていただけないでしょうか…。

回答No.2

toda hiro（@hiro_knigh）

汚いと文句が飛んできそうですが

typedef struct tagData{
int num;
char name[256];
struct tagData *next;
}DATA;

void data_sort(DATA **start);

int main()
{
DATA *d1,*d2,*d3;
char buf[256];
int num = 0;

d1 = NULL;

while(1){
printf("[%03d].num = ",num+1);
gets(buf);
if (atoi(buf)== -1)break;
d2 =(DATA *)malloc(sizeof(DATA));
d2->num =atoi(buf);
printf("[%03d].name = ",num+1);
gets(buf);
strcpy(d2->name,buf);
num++;
d2->next = NULL;
if (d1 == NULL) {
d1 = d2;
}else{
for (d3 = d1 ;; d3 = d3->next){
if(d3->next == NULL) {
d3->next = d2;
break;
}
}
}
}
data_sort(&d1);
}

void data_sort(DATA **start)
{
DATA *d1,*tmp,**d3;
int i,j,num = 0;

if (*start == NULL)return;

for (d1 = *start ;; d1 = d1->next){
num++;
if(d1->next == NULL)break;
}
if (num == 1)return;
d3 = (DATA **)malloc(sizeof(DATA *) * num);
num = 0;
for (d1 = *start ;; d1 = d1->next){
d3[num++] = d1;
if (d1->next == NULL)break;
}
for (i = 0; i < (num - 1); i++){
for (j = (num - 1); j > i; j--){
if (d3[j-1]->num > d3[j]->num){
tmp = d3[j-1];
d3[j-1] = d3[j];
d3[j] = tmp;
}
}
}

*start = NULL;
for (i = 0; i < num; i++){
d3[i]->next = NULL;
if (*start == NULL){
*start = d3[i];
}else{
for (tmp = *start ; ; tmp = tmp->next) {
if (tmp->next == NULL) {
tmp->next = d3[i];
break;
}
}
}
}
free(d3);
}

お礼

回答ありがとうございます。
やはり、領域を確保して値を入れた後の処理(ソート)は、
思ったより、難しいようですね・・・。
ソースを書いていただきありがとうございます。
このソースは参考にします。

回答No.1

asuncion

リスト構造でソートを行なうには、
「ソートしてある状態を保ちながら、リストへ挿入する」
という方法が楽だと思います。

もちろん、データの入力順にリスト構造を作って後からソートする、という方法も使えます。

ところで、リスト構造以前の話として、

＞#include <stdio.h>

malloc関数を使うのであれば、stdlib.hもインクルードしてあげましょう。

＞struct *next;

こういう定義はできません。今回使っているのは何型の構造体ですか？

＞char f_name;

f_nameには１バイト分しか領域を取っていないのに

＞scanf("%s",d1->name);

文字列の入力を求めています。正しくありません。メンバー名の食い違いもありますね。

お礼

回答ありがとうございます。
「ソートしてある状態を保ちながら、リストへ挿入する」
というのは、mainで配列を組んで配列内でソートしてから、
ソートした値をmallocで確保した領域に入れるという事なのでしょうか・・。
もし、上記のようなものなら少し目的が違うので、もう少し考えて見ます。
ありがとうございました。m(_ _)m