C言語 線形リストで辞書順でのソートが上手く行えない。

Question

前提・実現したいこと

C言語, teratail初心者です。
学校の課題で「テキストファイルから単語を読み取り、同じ単語が出現すれば回数を記録し、単語は辞書順にソートして線形リストを作る。」という課題です。このソートがうまくいきません。

初心者故にコードが汚い所があると思いますが、ご助力いただけると幸いです。
解決策でなくても、「ここが駄目」っていうポイントだけでもありがたいです。

発生している問題・エラーメッセージ

大体の単語はソート出来ているのですが、一部上手くソートされていません。
(Mrsという単語が、辞書順で最後尾の訳では無いのに、最後尾に行ってしまう
a行が上手くソートされない など。)

該当のソースコード

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

#define True 1
#define False 0

typedef struct word{
	char name[20];
	int count;
	struct word *next;
}Word;

/* ---プロトタイプ宣言--- */
int read_word(FILE*, char[]);
void print_nodes(Word*, FILE*);
Word *add_node(char[], Word*);
Word *create_word(char[]);
int check_word(char[], Word*);
Word *sort_node(char[], Word*);

/* ---main関数--- */
int main(void){
	FILE *fp;
	FILE *fp_print;
	Word *root = NULL;
	char buf[20];

	fp = fopen("anne_short.txt", "r");
	fp_print = fopen("output.txt", "a");

	if(fp == NULL){
		printf("Error!\n");
		exit(1);
	}else{
		printf("リスト作成中\n");
		
		while(read_word(fp, buf) > 0){
			root = add_node(buf, root);
		}

		printf("リスト作製終了\n");
		print_nodes(root, fp_print);
	}
	fclose(fp);
	fclose(fp_print);
	
	return 0;
}

/* ---anne_short.txtから単語の読み取り--- */
int read_word(FILE *fp, char buf[]){
	int ch;
	int index = 0;
	int i;
	
	while((ch = fgetc(fp)) != EOF){
		switch(ch){
			case ' ':
			case ',' :
			case '.':
			case '\n':
			case '\0':
				if(index == 0){ //読み飛ばす文字が続いた場合
					break;
				}else{
					buf[index++] = '\0';
					return index;
				}
			default:
				buf[index++] = ch;
				break;
		}
	}
}

/* ---nodeのnameを出力--- */
void print_nodes(Word *out, FILE *fp_print){
	if(out != NULL){
		printf("単語:%s 回数:%d回\n", out->name, out->count);
		fprintf(fp_print, "単語:%s 回数:%d回\n", out->name, out->count);
		print_nodes(out->next, fp_print);
	}
}

/* ---新規nodeの追加--- */
Word *add_node(char buf[], Word *root){
	Word *behind;// 挿入する直前のnodeのアドレス
	Word *front;// 挿入する直後のnodeのアドレス
	Word *tmp;
	
	// 初回実行時はrootに新規nodeを紐づけ
	if(root == NULL){
		root = create_word(buf);

	// 2回目以降
	}else{
		if((check_word(buf, root)) == True){// True = 新出の単語
			behind = sort_node(buf, root);
			front = behind->next;
			
			if(behind == root){// 先頭に追加する場合
				tmp = create_word(buf);
				root = tmp;
				tmp->next = behind;
				
			}else if(behind->next == NULL){// 最後尾に追加する場合
				behind->next = create_word(buf);
				
			}else{// リストの途中に追加する場合
				tmp = create_word(buf);
				behind->next = tmp;
				tmp->next = front;
			}
		}
	}
	return root;
}

/* ---新規nodeの作製--- */
Word *create_word(char buf[]){
	Word *node = (Word*)malloc(sizeof(Word));

	// 新規nodeの初期化
	node->next = NULL;
	node->count = 1;
	strcpy(node->name, buf);

	return node;
}

/* ---新出単語かどうかのチェック--- */
int check_word(char buf[], Word *root){
	Word *checker = root;

	// 新出ならTrue, 既出ならcountをインクリメントしてFalseを返す
	while(checker != NULL){
		if(stricmp(checker->name, buf) == 0){
			checker->count++;
			return False;
		}else{
			checker = checker->next;
		}
	}
	return True;
}

/* ---nodeを挿入する際に辞書順に--- */
Word *sort_node(char buf[], Word *root){
	Word *node = root;
	Word *behind = node; // 単語を挿入する直前のnodeのアドレス
	
	while(stricmp(buf, node->name) > 0){
		if(node->next != NULL){
			behind = node;
			node = node->next;
		}else{
			break;
		}
	}
	
	return behind;
}

試したこと

補足情報（FW/ツールのバージョンなど）

私の環境を記させて頂きます。足りない情報がございましたら教えていただけると幸いです。
Windows 8
テキストエディタ : サクラエディタ
コンパイラ mingw-w64

Answer 1

割とよく出来てるけど、惜しいなーと思いました。

read_word で EOF に到達したときの返り値

while ループから出た箇所に return index; が必要です。

sort_node の返り値で判断できないケースが有る

じっくり処理を追ってみるとわかると思うのですが、 root のみノードが存在して末尾の要素を追加する場合を考えてみましょう。

/* ---nodeを挿入する際に辞書順に--- */
Word *sort_node(char buf[], Word *root){
    Word *node = root;
    Word *behind = node; // 単語を挿入する直前のnodeのアドレス

    while(stricmp(buf, node->name) > 0){
        if(node->next != NULL){
            behind = node;
            node = node->next;
        }else{
            break;
        }
    }

    return behind;
}

stricmp(buf, node->name) > 0 かつ node->next == NULL なのでループが終了し、結果として behind は root と一致します。
したがって末尾に追加すべき( behind->next == NULL )か先頭に追加すべき( behind == root )か判断がつかない状態になってしまいます。

解決策としては、 behind の初期値を NULL にして先頭に挿入すべきケースを明確に分ける方法ですね。

/* ---nodeを挿入する際に辞書順に--- */
Word *sort_node(char buf[], Word *root){
    Word *node = root;
    Word *behind = NULL; // 単語を挿入する直前のnodeのアドレス

    while(stricmp(buf, node->name) > 0){
        behind = node; // 挿入すべき位置は node の位置より後
        if(node->next != NULL){
            node = node->next;
        }else{
            break;
        }
    }

    return behind;
}

これによって他の箇所も変更する必要があると思うので、よしなに。

Comments

[Malo]

回答ありがとうございました！
適切なアドバイス、自分で考えさせる余地が程よくあり、とても勉強になりました！

Answer 2

回答ではないですが、
Windowsを使っているなら、VisualStudioを使ってデバッグしてみてはどうでしょう
ソースコード上の任意の行にブレークポイントを設置し、実行をそこで止め、各変数の内容を参照することができます。
また、1行づつ実行し、変数の内容をモニタするようなこともできます

Comments

[y_waiwai]

しかし、Teratailのポイントシステムは単なる人気投票でしかないというのはわかってるつもりだけど、デバッグの方法を提示したらマイナスつくというのは驚愕やな。
なにをしたいんだろう

[YouheiSakurai]

デバッグ方法ではなくデバッグすれば出来ることを記載したからでしょう。VisualStudioでCにブレイクポイントを設定してデバッグしたことあります？私はないですし、多分出来るようになるまで少なくとも数日かかると思います。そんな人、もしくはこれをやった事がある人は、この回答をゴールへの道のりの長さに反して薄いと感じてるんじゃないかと思います。(私は感じてます。)

[y_waiwai]

デバッグできないと思われるような初心者だからデバッグ方法を教えちゃダメって話？
なんじゃそれ
質問くんにはもう進歩するなと言ってるのと一緒じゃないの？

Cのコードでブレークポイント設定してデバッグしないってことは、ひたすらコードとにらめっこ？
世の中というのはオレが思ってるほど進んでないのかな？

[YouheiSakurai]

そういう事、世の中との乖離だと思います。

[kazto]

横から失礼します。
さすがにデバッグを知らずにプログラミングするのは非効率極まると思います。
実際にプログラムが動く様子を観察して理解が深まることも多々あります。
y_waiwaiさんのご意見が世の中と乖離しているとは、思いません。

[YouheiSakurai]

まず、VisualStudioってみんなが使っているデファクトスタンダードの製品か、否、シェアは高めだがそうではないと感じています。次に、人はいつデバッガを使えるようになるものなのか、私はある程度プログラミングをやってて必要に迫られた時だと思っています。最後に、VisualStudioってそんなにとっつきやすいのか、私はMSの流儀を知らないと難しいんじゃないかと想像しています。何もデバッガの有用性を否定しているわけではありません。世の中はそんな感じで、特に職業プログラマではない学生に対して「Windowsを使っているなら、VisualStudioを使ってデバッグしてみてはどうでしょう」の一言で片付かないと主張しているまでです。

[pepperleaf]

デバッグそのものは否定しませんが、環境に mingw-w64 とあり、無視してませんか?　また、デバッガを使うにもエネルギーは必要だし、最初から、使えたら、苦労しない。
そして、回答そのものが、"努力が足りない、もっと頑張れ" みたいな感じで、全く回答になって無いと感じました。無い方がマシです。他の方に任せるべきです。

[can110]

質問者様の環境（サクラエディタ/mingw-w64)から全くの初心者とは思えません。
VSも比較的簡単に使いこなせると感じてます。ネットでの情報も豊富ですし。
また、質問コードの規模からもデバッガを使うのに良いタイミングでしょう。
よってVSでのデバッグを勧めるのは自然なことだと思います。
ま、シェアとか流儀とはおいといて、まずは使ってみて判断してもよいかと。

[pepperleaf]

can110さん、
> 質問者様の環境（サクラエディタ/mingw-w64)
サクラエディタは、あちこちで良く聞きます。初心者に薦めるところも多いようです。mingw-w-64 も gccのようなので、フリーのコンパイラとして使われる事が多いと思われます。(インストール済なら、 gcc xxx.c だけで使える)
そして、最初に"学校で..." とある事から、先生(or 学校)の推奨または、指定である可能性が高いです。VSが使えるか? と言うより、学校のPCに入れられるか?
もっと大きな問題は、それが質問者の期待する回答かと言う事ですね。
そういう意味では、ここで本来の質問と離れた議論をする事自体が大変、失礼なのですが。

[YouheiSakurai]

ここまでをまとめると私は主張が割れやすい箇所を突いているという事ですね。まぁ正解のない話なのでそれが分かれば私的にはOKです。

[kazto]

http://pypl.github.io/IDE.html
windowsの開発環境ではVisual Studioがトップである、という点のみ、ご指摘します。

[can110]

pepperleafさん、コメントありがとうございます。
学校指定のPCだとすでに環境は構築済みの可能性はありますね。見落としてました。
ただ「回答ではないですが」と断られてたうえでの回答でありますし
「デバッガ使うといいよ」という意見は基本的に正しいと思いましたので、それに賛同するためにコメントしました。
たしかに本質問には関係ないですね。失礼しました。