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

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

ただいまの
回答率

89.20%

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

解決済

回答 1

投稿

  • 評価
  • クリップ 1
  • VIEW 4,573

links

score 9

前提・実現したいこと

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

該当のソースコード

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

int end_of_file = 0;

struct word{

    char name[20];
    struct word *next;
    int count;

};
struct word *head;

struct word* new(){

    struct word *p;
    p = (struct word *)malloc(sizeof(struct word));
    p->next = NULL;
    return p;

}

struct word *search(struct word *p, char *buffer){
    struct word *temp = p;

    while(temp){
        if(strcmp(temp->name, buffer) == 0){
            return temp;
        }else{
            temp = temp->next;
        }
    }
    return NULL;
}

int read_word(FILE *file, char *buffer){

    char ch;
    int n = 0;
    buffer[0] = '\0';

    if(end_of_file == 1)
        return 0;

    while(1){
        ch = fgetc(file);
        switch(ch){
            case ',':
            case '.':
            case '\n':
            case ' ': 
                break;
            case EOF: 
                end_of_file = 1; 
                break;
            default:
                buffer[n] = ch;
                n++;
                buffer[n] = '\0';
                continue;
        }
    if(buffer[0] == '\0')
        return 1;
    else 
        return n;
    }
}

void delete(){
    struct word *temp, *del;
    if(head != '\0'){
        temp = head;
        while(temp){
            del = temp;
            temp = temp->next;
            free(del);
        }
    }
    head = NULL;
}

int main(void){

    struct word *w, *b, *root;
    char buf[20];
    int a = 0;
    FILE *fp;

    if((fp = fopen("anne.txt", "r")) == '\0'){
        printf("failed to open file\n");
        exit(1);
    }else{
        w = new();
        head = w;
        while(1){
            while(w->next != '\0')
                w = w->next;   
            a = read_word(fp, buf);
            b = search(head, buf);
            if(a == 0)
                break;
            if(a == 1){
                if(w->name[0] != '\0'){
                    if(b == NULL){
                        strcpy(w->name, buf);
                        w->count++;
                        w->next = new();
                    }else{
                        w = b;
                        w->count++;
                    }
                }else{
                    continue;
                }
            }else{
                    if(b == NULL){
                        strcpy(w->name, buf);
                        w->count++;
                        w->next = new();
                    }else{
                        w = b;
                        w->count++;
                    }
            }
        }
        root = head;
        while(root->next != '\0'){
            printf("%s    %d\n", root->name, root->count);
            root = root->next;
        }
        fclose(fp);
    }
    delete();
    return 0;
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+1

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

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

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

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

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

    a = read_word(fp, buf);
    ...
    if(a == 1){
          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 ポインタだけです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>    // or "typedef enum { false, true } bool;"
typedef struct word {
    struct word *next;
    int count;
    char name[20];
} WORD;
WORD head = {          // ポインタではなく、空の構造体にしてみた
    NULL, 0, { '\0' }
};

WORD *new(char *buf)
{
    WORD *p;

    p = malloc(sizeof(WORD));  // キャストは不要
    strcpy(p->name, buf);      // 文字列を格納、構造体を初期化
    p->next = NULL;
    p->count = 1;
    return p;
}

WORD *search(WORD *p, char *buffer)
{
    WORD *temp = p;

    while (temp) {
        if (strcmp(temp->name, buffer) == 0)
            return temp;

        temp = temp->next;
    }
    return NULL;
}

int read_word(FILE *file, char *buffer)
{
    static bool end_of_file = false;
    int len = 0;    // 文字列長を返す

    if (end_of_file == true)
        return EOF;

    while (1) {
        int ch = fgetc(file);

        switch (ch) {
        case EOF:
            end_of_file = true;
            /* NO_BREAK */
        case ',':
        case '.':
        case '\n':
        case ' ':
            buffer[len] = '\0';  // 文字列終端は、ここだけ
            return len;

        default:
            buffer[len++] = ch;  // 文字を格納
            break;
        }
    }
}

void delete(void)
{
    WORD *curr, *temp;

    for (curr = head.next; curr != NULL; curr = temp) {
        temp = curr->next;
        free(curr);
    }
}

void reading(void)
{
    WORD *tail, *b;
    char buf[20];
    int wlen;        // 文字列長
    FILE *fp;

    if ((fp = fopen("anne.txt", "r")) == NULL) {
        printf("failed to open file\n");
        exit(1);
    }

    tail = &head;     // 最初はリスト先頭が最後尾
    while (1) {
        wlen = read_word(fp, buf);
        if (wlen == EOF) {
            return;
        }
        if (wlen == 0) {
            continue;
        }

        b = search(head.next, buf);
        if (b == NULL) {
            // 初出現なので新規登録
            WORD *t = new(buf);  // new()の呼出はここだけ
            tail->next = t;       // 最後尾につなぐ
            tail = t;
        } else {
            b->count++;          // 出現回数を+1
        }
    }
    fclose(fp);
}

void sorting(void)
{
    WORD *top, *max, *prev, *curr, *succ;

    for (top = &head; top->next != NULL; top = top->next) {
        /* top->next から終わりまで「最大」エントリを探す */
        max = curr = top->next; // とりあえず先頭を最大とする
        prev = top;             // 最大の一つ前を覚えておく

        while ((succ = curr->next) != NULL) {
            if (strcmp(succ->name, max->name) < 0) { // 比較
                max = succ;     // 最大エントリを更新
                prev = curr;    // 一つ前も更新
            }
            curr = curr->next;  // 一歩前へ
        }

        /* 最大エントリmaxが見つかった。交換が必要か? */
        if (max != top->next) {
            prev->next = max->next;   // リストからmaxを抜き出し
            max->next = top->next;    // maxをtopの次に挿入する
            top->next = max;
        }
    }
}

void showList(void)
{
    WORD *w;

    for (w = head.next; w != NULL; w = w->next)
        printf("%4d %s\n", w->count, w->name);
}

int main(void)
{
    reading();    showList();
    printf("--- sorting ---\n");
    sorting();    showList();
    delete();
    return 0;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/10 22:53

    丁寧な回答ありがとうございます。
    NULLと'\0'の違いを理解していなかったので、その部分の解説をしてくださっていて助かりました。
    read_word関数の部分の解説がすごく勉強になりました。確かに、複雑になっていたので反省しました。
    typedefを使えばstructをいちいち書かなくて済むと気づいたのがほとんど終わってからだったので、書き換えるのを諦めてしまいました(汗)
    線形リスト扱う最初のうちは、紙に書くなどして可視化すると良いのだと感じました。

    一つ質問があります。
    「fgetc(), getchar()等で、一文字を読み、かつ、EOFの判定をするなら、char型変数で受け取るのではなく、int型で受け取ってください。」という部分で、どうしてchar型ではなくint型なのでしょうか。よろしければ解説をお願いします。

    キャンセル

  • 2017/07/10 23:50 編集

    #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。

    キャンセル

  • 2017/07/11 05:29

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

    キャンセル

  • 2017/07/11 14:54

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

    キャンセル

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

  • ただいまの回答率 89.20%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる