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

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

ただいまの
回答率

90.34%

  • C

    3981questions

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

C言語 2分木の構築が上手く行えない

解決済

回答 2

投稿

  • 評価
  • クリップ 1
  • VIEW 210

Malo

score 2

 前提・実現したいこと

あるテキストファイル(英単語が約103000語)から、英単語を読み取り
同じ単語であれば構造体の中のcountという変数をインクリメントし、
新出単語は、右の木に辞書順で小さいものを、左の木に辞書順で大きいもの、と分けて2分木を構築していきたいのですが、うまく実行できません。

解決策でなくとも、「ここがおかしい」というポイントだけでも構いません。
ご助力いただけると幸いです。

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

新出単語かどうかを判定する関数が上手く動いていない場合がある
最後に全ての単語を出力する際に、一部しか出力されない。

 該当のソースコード

#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 *right;
    struct word *left;
}Word;

/* ---プロトタイプ宣言--- */
int read_word(FILE*, char[]);
Word *add_word_binarytree(Word*, char[]);
int check_word(Word*, char[]);
Word **branch_node(Word*, char[]);
Word *create_node(char[]);
void print_node(Word*);


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

    fp = fopen("anne.txt", "r");
    if(fp == NULL){// anne. txtが存在しない場合
        printf("Error!\n");
        exit(1);
    }else{// anne.txtが存在する場合
        while(read_word(fp, buf) > 0){

            root = add_word_binarytree(root, buf);
        }
        print_node(root);
    }

    fclose(fp);
    return 0;
}

/* ---anne.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;
        }
    }
    return index;
}

/* ---2分木での単語の追加--- */
Word *add_word_binarytree(Word *root, char buf[]){
    Word **wedge;// 新出単語が挿入される親のアドレス

    if(root == NULL){// 1個目の単語
        root = create_node(buf);
    }else{// 2個目以降
        if(check_word(root, buf) == True){// True = 新出単語
            wedge = branch_node(root, buf);
            *wedge = create_node(buf);
        }
    }
    return root;
}

/* ---新出単語かどうかの判定--- */
int check_word(Word *root, char buf[]){
    Word *checker = root;
    int judge = 0;// 右の木を辿るか左の木を辿るか

    while(checker != NULL){
        if((judge = stricmp(buf, checker->name)) == 0){// 既出の単語の場合
            checker->count++;
            return False;
        }else if(judge > 0){// bufの方が大きい場合
            checker = checker->left;
        }else if(judge < 0){// bufの方が小さい場合
            checker = checker->right;
        }
    }

    return True;
}

/* ---辞書順で分岐させる--- */
Word **branch_node(Word *root, char buf[]){
    Word **parent = NULL;// 新出単語の親となるnodeのアドレス
    Word *checker = root;
    int judge;// 右の木を辿るか左の木を辿るか

    while(checker != NULL){
        if((judge = stricmp(buf, checker->name)) > 0){
            parent = &checker->left;
            checker = checker->left;
        }else if(judge < 0){
            parent = &checker;
            checker = checker->right;
        }
    }
    return parent;
}

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

    printf("buf = %s\n", buf);

    strcpy(node->name, buf);
    node->count = 1;
    node->right = NULL;
    node->left = NULL;

    return node;
}

/* ---nodeを出力--- */
void print_node(Word *node){

    if(node->right != NULL){
        print_node(node->right);
    }
    printf("単語%-20s: 回数:%d\n", node->name, node->count);
    if(node->left != NULL){
        print_node(node->left);
    }
}

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

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

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 2

checkベストアンサー

+2

branch_nodeの
parent = &checker;
parent = &checker->right;の間違いくさい

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/07/03 23:14

    あと、趣味的には、 check_word() と branch_node()を一つにしたい。

    キャンセル

  • 2018/07/04 13:24

    回答ありがとうございます!
    試行錯誤している間に抜けてしまっていたようです...
    助かりました!

    キャンセル

+2

まずいところをいくつか。
read_word関数、入力文字数のチェックが行われてないので、19文字以上の単語が来たら破綻する
create_node関数、strcpy関数で文字列コピーしているが、これまた19文字以上の単語が来たら破綻する

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/07/04 13:27

    回答ありがとうございます!
    課題内容で、「20文字以下である」という保障があったもので忘れてしまっていました...
    本来は実装すべきなので、指摘頂きありがとうございます!

    キャンセル

同じタグがついた質問を見る

  • C

    3981questions

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