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

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

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

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

Q&A

解決済

2回答

410閲覧

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

Malo

総合スコア19

C

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

0グッド

1クリップ

投稿2018/07/03 07:21

前提・実現したいこと

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

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

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

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

該当のソースコード

C

1#include <stdio.h> 2#include <stdlib.h> 3#include <string.h> 4 5#define True 1 6#define False 0 7 8typedef struct word{ 9 char name[20]; 10 int count; 11 struct word *right; 12 struct word *left; 13}Word; 14 15/* ---プロトタイプ宣言--- */ 16int read_word(FILE*, char[]); 17Word *add_word_binarytree(Word*, char[]); 18int check_word(Word*, char[]); 19Word **branch_node(Word*, char[]); 20Word *create_node(char[]); 21void print_node(Word*); 22 23 24/* ---main関数--- */ 25int main(void){ 26 FILE *fp; 27 Word *root = NULL; 28 char buf[20]; 29 30 fp = fopen("anne.txt", "r"); 31 if(fp == NULL){// anne. txtが存在しない場合 32 printf("Error!\n"); 33 exit(1); 34 }else{// anne.txtが存在する場合 35 while(read_word(fp, buf) > 0){ 36 37 root = add_word_binarytree(root, buf); 38 } 39 print_node(root); 40 } 41 42 fclose(fp); 43 return 0; 44} 45 46/* ---anne.txtから単語の読み取り--- */ 47int read_word(FILE *fp, char buf[]){ 48 int ch; 49 int index = 0; 50 int i; 51 52 while((ch = fgetc(fp)) != EOF){ 53 switch(ch){ 54 case ' ': 55 case ',' : 56 case '.': 57 case '\n': 58 case '\0': 59 if(index == 0){ //読み飛ばす文字が続いた場合 60 break; 61 }else{ 62 buf[index++] = '\0'; 63 return index; 64 } 65 default: 66 buf[index++] = ch; 67 break; 68 } 69 } 70 return index; 71} 72 73/* ---2分木での単語の追加--- */ 74Word *add_word_binarytree(Word *root, char buf[]){ 75 Word **wedge;// 新出単語が挿入される親のアドレス 76 77 if(root == NULL){// 1個目の単語 78 root = create_node(buf); 79 }else{// 2個目以降 80 if(check_word(root, buf) == True){// True = 新出単語 81 wedge = branch_node(root, buf); 82 *wedge = create_node(buf); 83 } 84 } 85 return root; 86} 87 88/* ---新出単語かどうかの判定--- */ 89int check_word(Word *root, char buf[]){ 90 Word *checker = root; 91 int judge = 0;// 右の木を辿るか左の木を辿るか 92 93 while(checker != NULL){ 94 if((judge = stricmp(buf, checker->name)) == 0){// 既出の単語の場合 95 checker->count++; 96 return False; 97 }else if(judge > 0){// bufの方が大きい場合 98 checker = checker->left; 99 }else if(judge < 0){// bufの方が小さい場合 100 checker = checker->right; 101 } 102 } 103 104 return True; 105} 106 107/* ---辞書順で分岐させる--- */ 108Word **branch_node(Word *root, char buf[]){ 109 Word **parent = NULL;// 新出単語の親となるnodeのアドレス 110 Word *checker = root; 111 int judge;// 右の木を辿るか左の木を辿るか 112 113 while(checker != NULL){ 114 if((judge = stricmp(buf, checker->name)) > 0){ 115 parent = &checker->left; 116 checker = checker->left; 117 }else if(judge < 0){ 118 parent = &checker; 119 checker = checker->right; 120 } 121 } 122 return parent; 123} 124 125/* ---新規nodeの作成--- */ 126Word *create_node(char buf[]){ 127 Word *node = (Word*)malloc(sizeof(Word)); 128 129 printf("buf = %s\n", buf); 130 131 strcpy(node->name, buf); 132 node->count = 1; 133 node->right = NULL; 134 node->left = NULL; 135 136 return node; 137} 138 139/* ---nodeを出力--- */ 140void print_node(Word *node){ 141 142 if(node->right != NULL){ 143 print_node(node->right); 144 } 145 printf("単語%-20s: 回数:%d\n", node->name, node->count); 146 if(node->left != NULL){ 147 print_node(node->left); 148 } 149}

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

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

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

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

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

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

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

guest

回答2

0

ベストアンサー

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

投稿2018/07/03 08:41

asm

総合スコア15147

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

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

pepperleaf

2018/07/03 14:14

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

2018/07/04 04:24

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

0

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

投稿2018/07/03 08:12

y_waiwai

総合スコア87774

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

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

Malo

2018/07/04 04:27

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.48%

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

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

質問する

関連した質問