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

[kentra21]

”名前”誕生年,誕生月,誕生日
の順で並んでいる誕生日リストをファイルから読み込んで構造体を用いて誕生日順に線形リストを作成するという問題で、自己参照型構造体を利用して構造体を用いてファイルから誕生日リストを読み込むことまではできたのですが、作成した構造体を誕生日順に並び替える方法が分かりません。配列型構造体を使えば簡単に解決することは分かるのですが、どうにかして自己参照型構造体を用いて解決したいです。
どのようにしたらソートすることが出来るのでしょうか。幾ら考えても分かりません、どうかお願いします。
環境 　
　OS ： Windows
　VC++ 2015

コード:

 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
	int year, month, day;
} DATE;
typedef struct person {
	char name[20];
	DATE birthday;
	struct person *next;
} PERSON;

int main() {
	FILE *fp;	//ファイルポインタ宣言
	int i, j;
	int check;
	int name[32];
	int year = 0, month = 0 , day = 0;
	int count = 0;

	PERSON *head = NULL, *p, *buf[2];

	fp = fopen("birthday_list.txt", "r");
	
	if (fp != NULL) {

		while ((check= fscanf(fp, "%[^,],%d,%d,%d", name, &year, &month, &day))!=EOF) {
			p = calloc(1, sizeof(PERSON));
			p->next = head;
			head = p;
			strcpy(p->name, name);
			p->birthday.year = year;
			p->birthday.month = month;
			p->birthday.day = day;
			count++;
		}
//ここでソートをしようとして失敗してます
		for (i = 0; i <= count; i++) {
			p = head;
			for (j = count; i < j; j--) {
				buf[0] = p;
				buf[1] = p->next;
				if (buf[0]->birthday.year < buf[1]->birthday.year) {
					p = buf[1];
					p->next = buf[0];
					
				}
				else if (buf[0]->birthday.year == buf[1]->birthday.year && buf[0]->birthday.month < buf[1]->birthday.month){
					p = buf[1];
					p->next = buf[0];
					
				}
				else if (buf[0]->birthday.month == buf[1]->birthday.month && buf[0]->birthday.day < buf[1]->birthday.day) {
					p = buf[1];
					p->next = buf[0];
					
				}
				
				p = p->next;
			}
		}
//ここまで
		p = head;
		while (p) {
			printf("%s,%d,%d,%d\n", p->name, p->birthday.year, p->birthday.month, p->birthday.day);
			p = p->next;
		}
		
		fclose(fp);
	}
	else {
		printf("file open error\n");
	}

	return 0;

}
 

[みけCAT]

あなたのプログラムでは、pを書き換えてもpに格納されているオブジェクトを指している他の構造体に入っているポインタは書き換わらないので、失敗します。
リストのソートには、マージソートを使うのがいいでしょう。

また、あなたのプログラムでは、printfの文字の配列の最初の要素へのポインタを要求する%[にint*のデータを渡しているので、未定義動作を起こします。
main関数のローカル変数nameの型はchar[32]とした方がいいでしょう。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
	int year, month, day;
} DATE;
typedef struct person {
	char name[20];
	DATE birthday;
	struct person *next;
} PERSON;

/* d2よりd1が大きければ正の数、小さければ負の数、等しければ0を返す */
int compare(const DATE* d1, const DATE* d2) {
	if (d1->year != d2->year) {
		return d1->year > d2->year ? 1 : -1;
	}
	if (d1->month != d2->month) {
		return d1->month > d2->month ? 1 : -1;
	}
	if (d1->day != d2->day) {
		return d1->day > d2->day ? 1 : -1;
	}
	return 0;
}

PERSON* sort(PERSON* head) {
	PERSON *list1, *list2, **next;
	/* 0個または1個の場合、自明 */
	if (head == NULL || head->next == NULL) return head;
	/* リストを中央で2個に分割する */
	list1 = list2 = head;
	for (;;) {
		list2 = list2->next;
		if (list2 != NULL) list2 = list2->next;
		if (list2 == NULL) {
			/* list1の2倍進むlist2が最後まで行ったので、list1が真ん中にいるはず */
			list2 = list1->next; /* 後半部分の位置を保存する */
			list1->next = NULL; /* リストを切断する */
			list1 = head; /* 前半部分の位置を保存する */
			break;
		} else {
			list1 = list1->next;
		}
	}
	/* それぞれをソートする */
	list1 = sort(list1);
	list2 = sort(list2);
	/* マージする */
	head = NULL;
	next = &head;
	while (list1 != NULL || list2 != NULL) {
		if (list2 == NULL) {
			/* list2が空になったので、list1の残りの部分を連結する */
			*next = list1;
			break;
		} else if (list1 == NULL) {
			/* list1が空になったので、list2の残りの部分を連結する */
			*next = list2;
			break;
		} else {
			/* 昇順にソートするので、小さい方を取り出す */
			if (compare(&list1->birthday, &list2->birthday) <= 0) {
				*next = list1;
				list1 = list1->next;
			} else {
				*next = list2;
				list2 = list2->next;
			}
			next = &(*next)->next;
			*next = NULL;
		}
	}
	return head;
}


int main(void) {
	FILE *fp;	//ファイルポインタ宣言
	int check;
	char name[32];
	int year = 0, month = 0 , day = 0;
	int count = 0;

	PERSON *head = NULL, *p;

	fp = fopen("birthday_list.txt", "r");
	
	if (fp != NULL) {

		while ((check= fscanf(fp, "%[^,],%d,%d,%d", name, &year, &month, &day))!=EOF) {
			p = calloc(1, sizeof(PERSON));
			p->next = head;
			head = p;
			strcpy(p->name, name);
			p->birthday.year = year;
			p->birthday.month = month;
			p->birthday.day = day;
			count++;
		}

		p = sort(head);

		while (p) {
			printf("%s,%d,%d,%d\n", p->name, p->birthday.year, p->birthday.month, p->birthday.day);
			p = p->next;
		}
		
		fclose(fp);
	}
	else {
		printf("file open error\n");
	}

	return 0;

}

オフトピック

1行に1個のデータが書かれているファイルを用いると2行目以降に書かれている名前に改行が含まれてしまいますが、

構造体を用いてファイルから誕生日リストを読み込むことまではできた

と書かれているので、これは仕様でしょう。

[metaphor]

デバッガーでみるとリスト構造がこわれて
//ここまで
p = head;
while (p) {
p = p->next;
}
で無限ループになります。（36行のcount++;が1回多い気がします。）
「過去ログより」
”一般的にリスト構造では、並び替えるのではなく、リスト構造を作るときに、昇順、または降順につなぎながら作成します。
今やろうとしているのは一度できているリスト構造をつなぎ替えようとしているように見えますがそうですか？
そうしなさいという課題なのでしょうか？。
もし、読み込むのは今行われているように、常に先頭に追加する方法で行い、そのあと並び替えなければいけないなら、
今あるリストから１こずつ取り出し、別のリスト構造を作っていくという方法をとります。
どの方法でいきますか？”

[かずま]

挿入ソートにしてみました。

コード:

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

typedef struct {
    int year, month, day;
} DATE;

typedef struct person {
    char name[20];
    DATE birthday;
    struct person *next;
} PERSON;

int lt(const DATE *a, const DATE *b)
{
    return a->year < b->year || a->year == b->year &&
        (a->month < b->month || a->month == b->month && a->day < b->day);
}
 
int main(void)
{
    char name[20];
    int year, month, day;
    PERSON *head = NULL, *p, *n = NULL, **q;
    FILE *fp = fopen("birthday_list.txt", "r");
    if (fp == NULL) { printf("file open error\n"); return 1; }

    while (fscanf(fp, " %19[^,],%d,%d,%d", name, &year, &month, &day) == 4) {
        p = malloc(sizeof(PERSON));
        p->next = head;
        head = p;
        strcpy(p->name, name);
        p->birthday.year = year;
        p->birthday.month = month;
        p->birthday.day = day;
    }
    fclose(fp);

    for (; p = head; p->next = *q, *q = p) {  // 挿入ソート
        head = p->next;
        for (q = &n; *q && lt(&(*q)->birthday, &p->birthday); q = &(*q)->next) ;
    }
    head = n;

    for (p = head; p; p = p->next) printf("%s,%d,%d,%d\n",
            p->name, p->birthday.year, p->birthday.month, p->birthday.day);

    for (p = head; p; p = n) {  // malloc したものを free
        n = p->next;
        free(p);
    }
    return 0;
}

[metaphor]

あ、正解がでますね。失礼いたしました。

[kentra21]

どうやら、リストの作り方が悪かったようですね。
もう一度勉強しなおしてきます。回答ありがとうございました。

[かずま]

どうやら、リストの作り方が悪かったようですね。

リストの作り方は悪くありません。
バブルソートをしようとしていますが、それが間違っています。

通常のバブルソートは、末尾から順に、隣り合う 2つの要素を比較していって、
先頭のほうに一番小さいものが来るんですが、リストの場合、
末尾から順に見ていくことができないので、先頭から順に見ていき、
一番大きいものが末尾に来るようにすればよいでしょう。

コード:

#include <stdio.h>  // fopen, fclose, fscanf, printf
#include <stdlib.h> // malloc, free
 
typedef struct {
    int year, month, day;
} DATE;
 
typedef struct person {
    char name[20];
    DATE birthday;
    struct person *next;
} PERSON;
 
int lt(const DATE *a, const DATE *b)
{
    return a->year < b->year || a->year == b->year &&
        (a->month < b->month || a->month == b->month && a->day < b->day);
}
 
int main(void)
{
    char name[20];
    int year, month, day;
    int i, count = 0;
    PERSON *head = NULL, *p, *n, **q;
    FILE *fp = fopen("birthday_list.txt", "r");
    if (fp == NULL) { printf("file open error\n"); return 1; }
 
    while (fscanf(fp, " %19[^,],%d,%d,%d", name, &year, &month, &day) == 4) {
        p = malloc(sizeof(PERSON));
        p->next = head;
        head = p;
        strcpy(p->name, name);
        p->birthday.year = year;
        p->birthday.month = month;
        p->birthday.day = day;
        count++;
    }
    fclose(fp);
 
    while (--count > 0)  // バブルソート
        for (q = &head, i = 0; i < count; i++, q = &(*q)->next) {
            n = (*q)->next;                          // 次のノードと
            if (!lt(&(*q)->birthday, &n->birthday))  // 比較して逆順だったら
                (*q)->next = n->next, n->next = *q, *q = n;  // 交換
        }

    for (p = head; p; p = p->next) printf("%s,%d,%d,%d\n",
            p->name, p->birthday.year, p->birthday.month, p->birthday.day);
 
    for (; p = head; free(p)) head = p->next;  // malloc したものを free
    return 0;
}