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

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

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

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

標準入力

標準入力(stdin)は、プログラムが標準的に用いるデータ入力元。リダイレクトしない限り、プログラムを起動した端末のキーボードが標準入力になります。UNIX系OSやC言語に実装されて普及した概念ですが、他のOSや言語も含めた総称としても使われます。

標準出力

標準出力(stdout)は、プログラムが標準的に用いるデータ出力元。標準出力に書き込み要求を発行しすることにより、ディスプレイ装置にデータを表示することができます。UNIX系OSやC言語に実装されて普及した概念ですが、他のOSや言語も含めた総称としても使われます。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

Q&A

解決済

2回答

2480閲覧

二分探索木を使って英単語と日本語のペアを辞書順にソートしたいのですが、出力が出ません

aardvark

総合スコア17

C

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

標準入力

標準入力(stdin)は、プログラムが標準的に用いるデータ入力元。リダイレクトしない限り、プログラムを起動した端末のキーボードが標準入力になります。UNIX系OSやC言語に実装されて普及した概念ですが、他のOSや言語も含めた総称としても使われます。

標準出力

標準出力(stdout)は、プログラムが標準的に用いるデータ出力元。標準出力に書き込み要求を発行しすることにより、ディスプレイ装置にデータを表示することができます。UNIX系OSやC言語に実装されて普及した概念ですが、他のOSや言語も含めた総称としても使われます。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

0グッド

0クリップ

投稿2020/07/26 04:34

実現したいこと・発生している問題

標準入力された複数の英単語・日本語のペアを二分探索木を使って辞書順にソートてから標準出力するプログラムをCで実現したいのですが、出力が何も表示されません。

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

root@LAPTOP-DJMEGTF2:~# valgrind ./a.out ==38== Memcheck, a memory error detector ==38== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==38== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info ==38== Command: ./a.out ==38== ==38== error calling PR_SET_PTRACER, vgdb might block sugar 砂糖 egg 卵 coffee コーヒー milk 牛乳 tea 紅茶 //入力の終了はこの場合Ctrl+Dで 知らせます ==38== ==38== HEAP SUMMARY: ==38== in use at exit: 264 bytes in 15 blocks ==38== total heap usage: 17 allocs, 2 frees, 4,368 bytes allocated ==38== ==38== LEAK SUMMARY: ==38== definitely lost: 200 bytes in 5 blocks ==38== indirectly lost: 64 bytes in 10 blocks ==38== possibly lost: 0 bytes in 0 blocks ==38== still reachable: 0 bytes in 0 blocks ==38== suppressed: 0 bytes in 0 blocks ==38== Rerun with --leak-check=full to see details of leaked memory ==38== ==38== For counts of detected and suppressed errors, rerun with: -v ==38== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) root@LAPTOP-DJMEGTF2:~#

Valgrindで確認してみたところ、このように入力をノードとしてメモリに格納すること自体はちゃんとできているようなのですが、printfによる出力が何も出ない上に、freeでメモリ解放したはずが出来ていません。

該当のソースコード

C

1#include <stdio.h> 2#include <string.h> 3#include <stdlib.h> 4#include <math.h> 5 6typedef char* String; //後で使いやすくできるよう、ここでStringタイプを定義しちゃいます。 7 8typedef struct node_{ 9 struct node_* left; //左の子へのポインタ 10 struct node_* right; //右の子へのポインタ 11 struct node_* parent; //親へのポインタ 12 String key; //探索に使うキー(この場合は英単語の見出し) 13 String value; //付属値(この場合は対応する日本語) 14}* node; //二分探索木のノードです。 15 16typedef struct{ 17 node root; //根節点のポインタ 18}* tree; //二分探索木の構造体を定義します 19 20#define left(x) (x->left) 21#define right(x) (x->right) 22#define parent(x) (x->parent) 23#define key(x) (x->key) 24#define value(x) (x->value) 25#define root(T) (T->root) 26#define NEW(p, n){p = malloc((n)*sizeof(p[0]));} 27 28int key_cmp(String p, String q){ 29 int c1, c2; 30 int i=0; 31 while(1){ 32 c1=p[i]; c2=q[i]; 33 if(c1<c2) return -1; 34 if(c1>c2) return 1; 35 if(c1==0) break; 36 i++; 37 } 38 return 0; 39} //英単語の見出しを比較する関数 40 41node node_new(String eng, String jpn){ 42 node x; 43 NEW(x, 1); 44 left(x)=NULL; 45 right(x)=NULL; 46 parent(x)=NULL; 47 key(x)=eng; 48 value(x)=jpn; 49 return x; 50} //新しいノードを作成 51 52tree tree_new(void){ 53 tree T; 54 NEW(T, 1); 55 root(T) = NULL; 56 return T; 57} //新しい二分探索木を作成 58 59void tree_insert(tree T, node z){ //二分探索木Tにzを挿入する 60 node x, y; 61 y=NULL; 62 x=root(T); 63 if(x==NULL) {x=z; return;} //Tが空ならzを根節点にして終わり 64 while(right(x) != NULL && left(x) != NULL){ 65 if (key_cmp(key(z), key(x)) < 0) {x=left(x);} 66 else {x=right(x);} 67 } //zを挿入する場所xを決める 68 if(right(x) == NULL && left(x) == NULL) {y=x;} 69 else if(right(x) == NULL && left(x) != NULL) {x=left(x); y=parent(x);} 70 else {x=right(x); y=parent(x);} //yはxの親 71 72 parent(z)=y; //zの親をyにする 73 if (key(z) < key(y)) {left(y) = z;} //yの子をzにする 74 else {right(y) = z;} 75 printf("%s %s\n", key(y), value(y)); //デバッグ用。ここでも出力が出ません。。。 76} 77 78void inorder_tree_walk(node x){ //木の根からたどることにより全てのキーをソートされた順序で出力 79 if (x != NULL){ 80 inorder_tree_walk(left(x)); 81 printf("%s %s\n", key(x), value(x)); 82 inorder_tree_walk(right(x)); 83 } 84} 85 86void free_nodes(node x){ 87 if (x != NULL){ 88 free_nodes(left(x)); 89 free_nodes(right(x)); 90 free(key(x)); 91 free(value(x)); 92 free(x); 93 } 94} 95 96void free_tree(tree T){ 97 free_nodes(root(T)); 98 free(T); 99} 100 101int main(int argc, char *argv[]){ 102 tree T; 103 node x; 104 char buf1[1000], buf2[1000]; 105 char* eng; //英単語の見出しに相当 106 char* jpn; //日本語訳に相当 107 T=tree_new(); 108 while(1){ 109 if (scanf("%s %s", buf1, buf2)<2) break; 110 eng=strdup(buf1); 111 jpn=strdup(buf2); 112 x=node_new(eng, jpn); 113 printf("%s %s\n", key(x), value(x)); //デバッグ用。ここはちゃんと出力が出ます。 114 tree_insert(T, x); 115 } 116 inorder_tree_walk(root(T)); 117 free_tree(T); 118 return 0; 119}

試したこと

デバッグのためにprintfをtree_insertで使ってみたのですが、そこでも何も出力は出ないようです。となるとtree_insertで二分探索木に挿入するコードがどこかおかしいのかと思いま。

ちなみにnode_new(eng, jpn);の直後のprintfはちゃんと出力がでるので、ノードはちゃんと作れていると思います。

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

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

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

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

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

guest

回答2

0

ベストアンサー

次の修正でどうなりますか?

Diff

1 node x, y; 2 y=NULL; 3 x=root(T); 4- if(x==NULL) {x=z; return;} //Tが空ならzを根節点にして終わり 5- while(right(x) != NULL && left(x) != NULL){ 6- if (key_cmp(key(z), key(x)) < 0) {x=left(x);} 7- else {x=right(x);} 8- } //zを挿入する場所xを決める 9- if(right(x) == NULL && left(x) == NULL) {y=x;} 10- else if(right(x) == NULL && left(x) != NULL) {x=left(x); y=parent(x);} 11- else {x=right(x); y=parent(x);} //yはxの親 12- 13- parent(z)=y; //zの親をyにする 14- if (key(z) < key(y)) {left(y) = z;} //yの子をzにする 15- else {right(y) = z;} 16- printf("%s %s\n", key(y), value(y)); //デバッグ用。ここでも出力が出ません。。。 17+ if (x == NULL) { root(T)=z; return; } //Tが空ならzを根節点にして終わり 18+ 19+ while (1) { 20+ if (key_cmp(key(z), key(x)) < 0) { 21+ if (left(x)) x = left(x); 22+ else { left(x) = z; parent(z) = x; return; } 23+ } 24+ else { 25+ if (right(x)) x = right(x); 26+ else { right(x) = z; parent(z) = x; return; } 27+ } 28+ } 29 }

投稿2020/07/26 14:42

kazuma-s

総合スコア8224

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

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

aardvark

2020/07/27 03:27

ありがとうございます!できました。
guest

0

C

1void tree_insert(tree T, node z){ //二分探索木Tにzを挿入する 2 node x, y; 3 y=NULL; 4 x=root(T); 5 if(x==NULL) {x=z; return;} //Tが空ならzを根節点にして終わり 6// ^^^ ここで T->root が書き換えられていないのでは? T->root = z じゃないと 7 ...

投稿2020/07/26 05:12

episteme

総合スコア16614

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

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

aardvark

2020/07/27 03:26

コメントありがとうございます。 確かに、そこは見落としておりました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問