質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

1回答

1621閲覧

線形リストでの単語の並べ替えがうまくいきません。

links

総合スコア9

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

1クリップ

投稿2017/07/09 10:58

###前提・実現したいこと
単語の線形リストを作成し、同じ単語には1つのstruct word構造体を用い、単語の出現回数を数える。そして、出現単語を辞書順に並べ替える。
合っているかはわからないですが、一応単語の出現回数を数えるところまではできました。しかし、辞書順に並べ替えるときにうまくいかないので助言をいただきたく質問しました。まだ、始めたばかりですのでソースコードが見にくいかもしれませんが、宜しくお願いします。
あと、こうした方が良い、などの助言もしていただけるとありがたいです。

###該当のソースコード

c

1#include <stdio.h> 2#include <stdlib.h> 3#include <string.h> 4 5int end_of_file = 0; 6 7struct word{ 8 9 char name[20]; 10 struct word *next; 11 int count; 12 13}; 14struct word *head; 15 16struct word* new(){ 17 18 struct word *p; 19 p = (struct word *)malloc(sizeof(struct word)); 20 p->next = NULL; 21 return p; 22 23} 24 25struct word *search(struct word *p, char *buffer){ 26 struct word *temp = p; 27 28 while(temp){ 29 if(strcmp(temp->name, buffer) == 0){ 30 return temp; 31 }else{ 32 temp = temp->next; 33 } 34 } 35 return NULL; 36} 37 38int read_word(FILE *file, char *buffer){ 39 40 char ch; 41 int n = 0; 42 buffer[0] = '\0'; 43 44 if(end_of_file == 1) 45 return 0; 46 47 while(1){ 48 ch = fgetc(file); 49 switch(ch){ 50 case ',': 51 case '.': 52 case '\n': 53 case ' ': 54 break; 55 case EOF: 56 end_of_file = 1; 57 break; 58 default: 59 buffer[n] = ch; 60 n++; 61 buffer[n] = '\0'; 62 continue; 63 } 64 if(buffer[0] == '\0') 65 return 1; 66 else 67 return n; 68 } 69} 70 71void delete(){ 72 struct word *temp, *del; 73 if(head != '\0'){ 74 temp = head; 75 while(temp){ 76 del = temp; 77 temp = temp->next; 78 free(del); 79 } 80 } 81 head = NULL; 82} 83 84int main(void){ 85 86 struct word *w, *b, *root; 87 char buf[20]; 88 int a = 0; 89 FILE *fp; 90 91 if((fp = fopen("anne.txt", "r")) == '\0'){ 92 printf("failed to open file\n"); 93 exit(1); 94 }else{ 95 w = new(); 96 head = w; 97 while(1){ 98 while(w->next != '\0') 99 w = w->next; 100 a = read_word(fp, buf); 101 b = search(head, buf); 102 if(a == 0) 103 break; 104 if(a == 1){ 105 if(w->name[0] != '\0'){ 106 if(b == NULL){ 107 strcpy(w->name, buf); 108 w->count++; 109 w->next = new(); 110 }else{ 111 w = b; 112 w->count++; 113 } 114 }else{ 115 continue; 116 } 117 }else{ 118 if(b == NULL){ 119 strcpy(w->name, buf); 120 w->count++; 121 w->next = new(); 122 }else{ 123 w = b; 124 w->count++; 125 } 126 } 127 } 128 root = head; 129 while(root->next != '\0'){ 130 printf("%s %d\n", root->name, root->count); 131 root = root->next; 132 } 133 fclose(fp); 134 } 135 delete(); 136 return 0; 137} 138

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

コーディングスタイルは私と違いますが、コードに律儀な性格が表れているように感じられ、好ましく思いました。同時に経験不足なども感じました。

私は、先輩のコードを読み解いてリストの操作を理解しました。理解しましたが、いざ書こうとすると、リスト構造の絵を描いて、これをここに挿入するには、このポインタを、こっちに代入して・・・と、いちいち絵を描いています(苦笑)。そういうものだ、という事を含めて、参考にしていただけると幸いです。

気づいた事をいくつか挙げます。

NULL と書くべき所に '\0' を使っています。数値としてはどちらも0ですが、'\0' はヌル文字の値であり、文字変数に対して使うべき。一方、NULLはヌルポインタの値です。ポインタに対する比較・代入はNULLを使いましょう。

read_word()が返す値 0, 1, n の意味は、
0 -- 既にEOFに到達した
1 -- buf[] に格納しない文字(',', '.', '\n', ' ')が続いた場合
n -- 入力した文字列の長さ
かと思いました。文字列長が1の場合("I", "a")があるので、おそらくそれを考慮して

C

1 a = read_word(fp, buf); 2 ... 3 if(a == 1){ 4 if(w->name[0] != '\0'){

としたのでしょうが、余計に複雑にしています。私なら、
-1 -- 既にEOFに到達した(普通EOFは -1 に定義されている)
0 -- buf[] に格納しない文字(',', '.', '\n', ' ')
1以上 -- 単語の文字列長
とします。EOFをそのまま返せますし、(0の場合も含めて)文字列長をそのまま返せるので、コードがシンプルになります。

フラグとして使っているend_of_file変数は、値として0と1を代入していますが、0と1でさえもマジックナンバになる事があります。<stdbool.h> があれば、bool型が定義済みですし、trueとfalseを値として使えます。その方が意味が伝わりやすくなります。

そのend_of_file変数をグローバル変数にしていますが、必要なのは read_word() 関数だけですから、関数内のstatic変数にできるし、したほうが良いです。

fgetc(), getchar()等で、一文字を読み、かつ、EOFの判定をするなら、char型変数で受け取るのではなく、int型で受け取ってください。

if〜else〜の中でreturn/break/continueする場合、組み方を変えればインデントを浅くでき、可読性が上がります。

構造体の型名はtypedefしてしまえば、いちいちstructと書かずに済みます(笑)。新しく作った型名は、マクロ名と同様、大文字で書く(少なくとも先頭は大文字にする)ことで、変数名等との混同を避けることができます。

さて、ソートを考えた時、線形リストというデータ構造はあまり得策ではないと思います。こんなページを発見しました。
連結リストのソート

「ややこしくて途中で挫折した」他にコメントもあまり芳しくありません。ですが、こんな手順が浮かびました。
リストに10個データがあるとします。リストを最後まで辿れば、10個の中からリストの先頭に来るべき要素が見つかります。その要素をリストから削除(抜き出)し、リストの先頭に挿入し、これで先頭が決まります。
その次は、残り9個の要素に対して、同様の処理を行い、これで2番目が決まります。
その次は、残り8個(以下省略)、という具合い。
下のコードをご覧ください。手元で簡単なテストはパスしました。

要素を削除する・要素を挿入する、はリスト構造の得意とするところ…とは言え、上述の通り、絵を描かないと処理を間違えますし、変数がいくつ必要なのかさえ迷います(苦笑)。

もうひとつ、head変数をポインタにするのは、一見素直なようでいて、手順が複雑になる要因だと思いました。ソートの手順と合わせて考えた結果、ポインタではなく、空の構造体変数にしてみました(これは人によってやり方が違うかもしれない)。実際に使っているのは head.next ポインタだけです。

C

1#include <stdio.h> 2#include <stdlib.h> 3#include <string.h> 4#include <stdbool.h> // or "typedef enum { false, true } bool;" 5typedef struct word { 6 struct word *next; 7 int count; 8 char name[20]; 9} WORD; 10WORD head = { // ポインタではなく、空の構造体にしてみた 11 NULL, 0, { '\0' } 12}; 13 14WORD *new(char *buf) 15{ 16 WORD *p; 17 18 p = malloc(sizeof(WORD)); // キャストは不要 19 strcpy(p->name, buf); // 文字列を格納、構造体を初期化 20 p->next = NULL; 21 p->count = 1; 22 return p; 23} 24 25WORD *search(WORD *p, char *buffer) 26{ 27 WORD *temp = p; 28 29 while (temp) { 30 if (strcmp(temp->name, buffer) == 0) 31 return temp; 32 33 temp = temp->next; 34 } 35 return NULL; 36} 37 38int read_word(FILE *file, char *buffer) 39{ 40 static bool end_of_file = false; 41 int len = 0; // 文字列長を返す 42 43 if (end_of_file == true) 44 return EOF; 45 46 while (1) { 47 int ch = fgetc(file); 48 49 switch (ch) { 50 case EOF: 51 end_of_file = true; 52 /* NO_BREAK */ 53 case ',': 54 case '.': 55 case '\n': 56 case ' ': 57 buffer[len] = '\0'; // 文字列終端は、ここだけ 58 return len; 59 60 default: 61 buffer[len++] = ch; // 文字を格納 62 break; 63 } 64 } 65} 66 67void delete(void) 68{ 69 WORD *curr, *temp; 70 71 for (curr = head.next; curr != NULL; curr = temp) { 72 temp = curr->next; 73 free(curr); 74 } 75} 76 77void reading(void) 78{ 79 WORD *tail, *b; 80 char buf[20]; 81 int wlen; // 文字列長 82 FILE *fp; 83 84 if ((fp = fopen("anne.txt", "r")) == NULL) { 85 printf("failed to open file\n"); 86 exit(1); 87 } 88 89 tail = &head; // 最初はリスト先頭が最後尾 90 while (1) { 91 wlen = read_word(fp, buf); 92 if (wlen == EOF) { 93 return; 94 } 95 if (wlen == 0) { 96 continue; 97 } 98 99 b = search(head.next, buf); 100 if (b == NULL) { 101 // 初出現なので新規登録 102 WORD *t = new(buf); // new()の呼出はここだけ 103 tail->next = t; // 最後尾につなぐ 104 tail = t; 105 } else { 106 b->count++; // 出現回数を+1 107 } 108 } 109 fclose(fp); 110} 111 112void sorting(void) 113{ 114 WORD *top, *max, *prev, *curr, *succ; 115 116 for (top = &head; top->next != NULL; top = top->next) { 117 /* top->next から終わりまで「最大」エントリを探す */ 118 max = curr = top->next; // とりあえず先頭を最大とする 119 prev = top; // 最大の一つ前を覚えておく 120 121 while ((succ = curr->next) != NULL) { 122 if (strcmp(succ->name, max->name) < 0) { // 比較 123 max = succ; // 最大エントリを更新 124 prev = curr; // 一つ前も更新 125 } 126 curr = curr->next; // 一歩前へ 127 } 128 129 /* 最大エントリmaxが見つかった。交換が必要か? */ 130 if (max != top->next) { 131 prev->next = max->next; // リストからmaxを抜き出し 132 max->next = top->next; // maxをtopの次に挿入する 133 top->next = max; 134 } 135 } 136} 137 138void showList(void) 139{ 140 WORD *w; 141 142 for (w = head.next; w != NULL; w = w->next) 143 printf("%4d %s\n", w->count, w->name); 144} 145 146int main(void) 147{ 148 reading(); showList(); 149 printf("--- sorting ---\n"); 150 sorting(); showList(); 151 delete(); 152 return 0; 153}

投稿2017/07/10 12:53

編集2017/07/10 15:02
rubato6809

総合スコア1380

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

links

2017/07/10 13:53

丁寧な回答ありがとうございます。 NULLと'\0'の違いを理解していなかったので、その部分の解説をしてくださっていて助かりました。 read_word関数の部分の解説がすごく勉強になりました。確かに、複雑になっていたので反省しました。 typedefを使えばstructをいちいち書かなくて済むと気づいたのがほとんど終わってからだったので、書き換えるのを諦めてしまいました(汗) 線形リスト扱う最初のうちは、紙に書くなどして可視化すると良いのだと感じました。 一つ質問があります。 「fgetc(), getchar()等で、一文字を読み、かつ、EOFの判定をするなら、char型変数で受け取るのではなく、int型で受け取ってください。」という部分で、どうしてchar型ではなくint型なのでしょうか。よろしければ解説をお願いします。
rubato6809

2017/07/10 14:57 編集

#define EOF (-1) -1 を2進数で表すと、全てのビットが1です。intが32bitなら、EOF == -1 == 0xffffffff です。 読もうとしているファイルの中に、データとして 0xff というバイトデータがある場合を考えてください。 int ch = getchar(); とした場合、getchar() は 0xff というデータを 0x000000ff として返します。よって if (ch == EOF) という条件は成立しません。 ところが、 char ch = getchar(); の場合、ch には下位8bitの 0xff だけが代入され、それが符号拡張されると0xffffffffとなり、if (ch == EOF) という条件が成立してしまいます。 結果として、0xffがある所で EOF に到達した事になり、そこから先のデータを読むことができません。 あ、でもasciiコードで書かれたテキストファイルに 0xff というデータは含まれないはずだから、問題は起きないはずですねw。
rubato6809

2017/07/10 20:29

fclose(fp); を実行しないバグ orz
links

2017/07/11 05:54

そうなのですね。すごく勉強になります。ありがとうございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問