Q&A
木構造での辞書的検索のやり方
c言語で "木構造の中に入力した文字列が存在するかを確認するプログラム" を作りたいのですが、検索する関数内の条件をうまく書くことができないので、どのような条件と書き方で辞書的な検索ができるのかを教えて欲しいです。
木構造の中身はソースコード内で宣言してよいものとしています。
(一応書いたのですが、"すべて存在しない"と表示されてしまいます。)
該当のソースコード
c
1#include<stdio.h> 2#include<stdlib.h> 3#include<string.h> 4 5struct node{ 6 char animal[20]; 7 struct node *left; 8 struct node *right; 9}; 10typedef struct node node; 11 12int member_tree(char *namae , struct node *p){ 13 while(namae == p->animal){ 14 if(*namae == '\0') 15 return 1; 16 namae++; 17 p++; 18 } 19 if(strcmp(namae,p->animal) == 1) member_tree(namae,p->right); 20 if(strcmp(namae,p->animal) == -1) member_tree(namae,p->left); 21 return 0; 22} 23 24int main(void){ 25 char name[20]; 26 char *p; 27 node *root; 28 node *elephant,*cat,*dog,*rat,*hourse,*bat,*hamster; 29 char animals[][20] = {"elephant","cat","dog","rat","horse","bat","hamster"}; 30 root = (node*)malloc(sizeof(node)); 31 elephant = (node*)malloc(sizeof(node)); 32 cat = (node*)malloc(sizeof(node)); 33 dog = (node*)malloc(sizeof(node)); 34 rat = (node*)malloc(sizeof(node)); 35 hourse = (node*)malloc(sizeof(node)); 36 bat = (node*)malloc(sizeof(node)); 37 hamster = (node*)malloc(sizeof(node)); 38 strcpy(elephant->animal,animals[0]); 39 strcpy(cat->animal,animals[1]); 40 strcpy(dog->animal,animals[2]); 41 strcpy(rat->animal,animals[3]); 42 strcpy(hourse->animal,animals[4]); 43 strcpy(bat->animal,animals[5]); 44 strcpy(hamster->animal,animals[6]); 45 46 root = elephant; 47 root->left = cat; 48 root->left->left = bat; 49 root->left->right = dog; 50 root->right = rat; 51 root->right->left = hourse; 52 root->right->left->left = hamster; 53 54while(1){ 55 printf("動物名を英語で入力してください(00で終了)-->"); 56 scanf("%s" , name); 57 // p = (node*)malloc(sizeof(node)); 58 // strcpy(*p,name); 59 p = &(name[0]); 60 if(strcmp(name,"00") == 0){ 61 printf("終了します\n"); 62 break; 63 } 64 else{ 65 if(member_tree(p,root) == 0){ 66 printf("%sは存在しません.\n" , name); 67 } 68 else{ 69 printf("%sは存在します.\n" , name); 70 } 71 } 72 } 73 74 return 0; 75} 76
＜追記＞
gdbで実行した場合の表示
Program received signal SIGSEGV, Segmentation fault __strcmp_see42() at../sysdeps/x86_64/multiarch/strcmp.S:130 130 ../sysdeps/x86_64/multiarch/strcmp.S: そのようなファイルやディレクトリはありません. in ../sysdeps/x86_64/multiarch/strcmp.S
＜追記＞
セグメンテーション違反が発生したコード
#include<stdio.h> #include<stdlib.h> #include<string.h> struct node{ char animal[20]; struct node *left; struct node *right; }; typedef struct node node; int member_tree(char *namae , struct node *p){ int diff = strcmp(namae , p->animal); if(p == NULL) return 0; if(diff > 0) return member_tree(namae , p->right); if(diff < 0) return member_tree(namae , p->left); return 1; } int main(void){ char name[20]; char *p; node *root; node *elephant,*cat,*dog,*rat,*hourse,*bat,*hamster; char animals[][20] = {"elephant","cat","dog","rat","horse","bat","hamster"}; root = (node*)malloc(sizeof(node)); elephant = (node*)malloc(sizeof(node)); cat = (node*)malloc(sizeof(node)); dog = (node*)malloc(sizeof(node)); rat = (node*)malloc(sizeof(node)); hourse = (node*)malloc(sizeof(node)); bat = (node*)malloc(sizeof(node)); hamster = (node*)malloc(sizeof(node)); strcpy(elephant->animal,animals[0]); strcpy(cat->animal,animals[1]); strcpy(dog->animal,animals[2]); strcpy(rat->animal,animals[3]); strcpy(hourse->animal,animals[4]); strcpy(bat->animal,animals[5]); strcpy(hamster->animal,animals[6]); root = elephant; root->left = cat; root->left->left = bat; root->left->right = dog; root->right = rat; root->right->left = hourse; root->right->left->left = hamster; while(1){ printf("動物名を英語で入力してください(00で終了)-->"); scanf("%s" , name); // p = (node*)malloc(sizeof(node)); // strcpy(*p,name); p = &(name[0]); if(strcmp(name,"00") == 0){ printf("終了します\n"); break; } else{ if(member_tree(p,root) == 0){ printf("%sは存在しません.\n" , name); } else{ printf("%sは存在します.\n" , name); } } } return 0; }
回答1件
0
ベストアンサー
どんな木構造ができているのか図に書いて、例えば、
"dog" を入れたら、member_tree がどういう動きをするのか
丹念に追ってみましたか？
それをやってみて何が分かりますか？
member_tree を次のようにすれば動くはずです。
C
1int member_tree(char *namae, struct node *p) 2{ 3 if (p == NULL) return 0; 4 int diff = strcmp(namae, p->animal); 5 if (diff > 0) return member_tree(namae, p->right); 6 if (diff < 0) return member_tree(namae, p->left); 7 return 1; 8}
これが理解できますか？
動いたから解決ではなく、質問のコードがなぜダメか理解してください。
追記
質問のコードの member_tree を私のコードに置き換えたものです。
C
1#include<stdio.h> 2#include<stdlib.h> 3#include<string.h> 4 5struct node{ 6 char animal[20]; 7 struct node *left; 8 struct node *right; 9}; 10typedef struct node node; 11 12int member_tree(char *namae, struct node *p) 13{ 14 if (p == NULL) return 0; 15 int diff = strcmp(namae, p->animal); 16 if (diff > 0) return member_tree(namae, p->right); 17 if (diff < 0) return member_tree(namae, p->left); 18 return 1; 19} 20 21int main(void){ 22 char name[20]; 23 char *p; 24 node *root; 25 node *elephant,*cat,*dog,*rat,*hourse,*bat,*hamster; 26 char animals[][20] = {"elephant","cat","dog","rat","horse","bat","hamster"}; 27 root = (node*)malloc(sizeof(node)); 28 elephant = (node*)malloc(sizeof(node)); 29 cat = (node*)malloc(sizeof(node)); 30 dog = (node*)malloc(sizeof(node)); 31 rat = (node*)malloc(sizeof(node)); 32 hourse = (node*)malloc(sizeof(node)); 33 bat = (node*)malloc(sizeof(node)); 34 hamster = (node*)malloc(sizeof(node)); 35 strcpy(elephant->animal,animals[0]); 36 strcpy(cat->animal,animals[1]); 37 strcpy(dog->animal,animals[2]); 38 strcpy(rat->animal,animals[3]); 39 strcpy(hourse->animal,animals[4]); 40 strcpy(bat->animal,animals[5]); 41 strcpy(hamster->animal,animals[6]); 42 43 root = elephant; 44 root->left = cat; 45 root->left->left = bat; 46 root->left->right = dog; 47 root->right = rat; 48 root->right->left = hourse; 49 root->right->left->left = hamster; 50 51while(1){ 52 printf("動物名を英語で入力してください(00で終了)-->"); 53 scanf("%s" , name); 54 // p = (node*)malloc(sizeof(node)); 55 // strcpy(*p,name); 56 p = &(name[0]); 57 if(strcmp(name,"00") == 0){ 58 printf("終了します\n"); 59 break; 60 } 61 else{ 62 if(member_tree(p,root) == 0){ 63 printf("%sは存在しません.\n" , name); 64 } 65 else{ 66 printf("%sは存在します.\n" , name); 67 } 68 } 69 } 70 71 return 0; 72}
実行結果
text
1動物名を英語で入力してください(00で終了)-->dog 2dogは存在します. 3動物名を英語で入力してください(00で終了)-->cat 4catは存在します. 5動物名を英語で入力してください(00で終了)-->egg 6eggは存在しません. 7動物名を英語で入力してください(00で終了)-->00 8終了します
セグメンテーション違反になりません。
セグメンテーション違反になるというコードと入力データを質問に追記してください。
投稿2021/06/14 15:30
編集2021/06/15 10:39
総合スコア8224
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/06/15 10:12
2021/06/15 10:21
2021/06/15 11:54
2021/06/15 11:55
2021/06/15 11:58
2021/06/15 12:03
2021/06/15 12:29