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

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

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

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

解決済

c言語で二分探索木を実装したいです

kyapi
kyapi

総合スコア5

C

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

5回答

0リアクション

1クリップ

5343閲覧

投稿2020/12/01 03:12

編集2020/12/02 08:18
コード `#include <stdio.h> #include <stdlib.h> /* 木の節の定義 */ typedef struct node{ int data; /* 探索のキーになるデータ型 */ struct node *left; /* 左の子 */ struct node *right; /* 右の子 */ }NODE; /* メンバright,leftにNULLポインタがセットされているときは該当する子がいないことを表す */ /* 初期状態では二分探索木は空の状態。 グローバル変数rootが二分探索木の根へのポインタを保持しているものとする */ /* グローバル変数rootをNULLで初期化 */ NODE *root = NULL; /* エラーメッセージをプリントしてexitする関数*/ /* ポインタ(アドレス)の先のデータを読み取り専用にする */ void fatal_error(const char *s) { /* fprintf関数を使ってstderrで標準エラーを出力する*/ fprintf(stderr,"%s", s); exit(1); /* 異常終了 */ } /* 二分探索木から最小の要素を削除する関数 */ /* 削除した節へのポインタを返す p:二分探索木へのポインタへのポインタ (つまり*pが木へのポインタとなる) NODE型へのポインターが戻り値 */ NODE *deletemin(NODE **p) { NODE *x; while ((*p)->left != NULL) p=&(*p)->left; x=*p; *p=(*p)->right; return x; } /* 二分探索木を探索する関数 */ /* パラメータkeyを受け取ってポインタを返す関数として定義 key:探索すべきキーの値 探索に成功した場合そのデータの節へのポインタを返す NODE型へのポインターが戻り値 */ NODE *search(int key) { NODE *p; /* 現在注目している節 */ p=root; /* まず根に注目する */ /* 進むべき子が存在する限り繰り返す */ while (p != NULL) { /* キーと注目している節のデータが等しいか比較 */ if (key == p->data){ /* もしキーと注目している節のデータとが等しければポインタを関数として返す */ printf("探索した値の番地です>>%p\n",p); return p; }else if (key < p->data){ /* キーの方が小さければ左部分木に進む */ p = p->left; }else{ /* キーの方が大きければ右部分木に進む*/ p = p->right; } /* ループを抜け出たということは見付からなかったというと NULL返して失敗したことを知らせる */ printf("NotExist\n"); return NULL; } } /* 二分探索木から要素を追加する関数*/ /* 探索と同じ要領で木を辿り、辿るべき部分木がなければそこに挿入する */ /* 挿入した要素が置かれる節へのポインタを返す すでに要素が登録されているのなら、何もしないでNULLを返す key:挿入するデータ NODE型へのポインターが戻り値 */ NODE *insert(int key) { NODE **p,*new; /* 変数pが変数rootを指すように初期化する */ p=&root; /* 挿入すべき場所が見つかるまで繰り返す */ while (*p != NULL) { /* キーと注目している節のデータが等しいか比較 */ if (key == (*p)->data){ /* すでに登録されている */ printf("AlreadyExsits\n"); return NULL; }else if (key < (*p)->data){ /* キーの方が小さければ左部分木に進む */ p =&(*p)->left; }else{ /* キーの方が大きければ右部分木に進む */ p =&(*p)->right; } } /* 挿入されるべき場所が見つかったら */ /* 挿入される節をつくる */ /* strct型のメモリを確保した分だけnewに入れる。もしNULLだったらエラー */ if((new=malloc(sizeof(NODE)))==NULL) fatal_error("out of memory!!"); /* 新しい節には子がないのでNULLにしておく */ new->left =NULL; new->right=NULL; /* 要素の値をセットする */ new->data=key; /* 正しい場所に挿入する */ /* ポインタpは挿入される節へのポインタが入っている場所を指している */ *p=new; return new; } /* 二分探索木から要素を削除する関数 */ /* 削除に成功したら1、要素が存在しなければ0を返す key:削除するデータ */ int delete(int key) { /* 親へのポインタを使う */ NODE **p, *x; /* 変数pが変数rootを指すように初期化する */ p = &root; /* 削除対象となる要素を探す */ while (*p != NULL) { /* 見つかった 変数pは削除される節の親のメンバleft,right 変数xは削除される節そのものを指している */ if (key == (*p)->data) { x = *p; /* 1つも子を持っていない、葉である場合 */ if (x->left == NULL && x->right == NULL){ *p = NULL; /* 右の子のみをもつ */ }else if (x->left == NULL){ *p = x->right; /* 左の子のみをもつ */ }else if (x->right == NULL){ *p = x->left; /* 左右2つの子を持つ */ }else{ /* 部分木から最小の要素を取り去る */ *p = deletemin(&x->right); (*p)->right = x->right; (*p)->left = x->left; } /* 取り除いた節を解放させる */ free(x); printf("Done\n"); return 1; }else if (key < (*p)->data){ /* 左部分木に進む */ p = &(*p)->left; }else{ /* 右部分木に進む */ p = &(*p)->right; } } /* 削除対象が見つからなかった */ printf("NotExist\n"); return 0; } /* 二分木を行きがけ順でなぞる */ void preorder(NODE *p) { /* 木が空なら何もしない */ if(p==NULL) return; else{ printf("%d ",p->data); /* 自身の値を出力 */ preorder(p->left); /* 左ノードへ移動 */ preorder(p->right); /* 右ノードへ移動 */ } } /* 二分木を通りがけ順でなぞる */ /* 全要素を昇順に表示する関数 二分探索木の全要素を小→大の順で表示する */ /* 全体の流れ ある要素の左枝先を全部調べ終えたら、自身の値を出力し、 次にその要素の右枝先の要素を全部調べる 左枝を調べる 調べ終えたら戻ってくる 値を出力する 右枝を調べる 調べ終えたら戻ってくる 関数を終了して、自身を呼び出した関数の元へと戻る */ void inorder(NODE *p) { /* 木が空なら何もしない */ if(p==NULL) return; else{ /* 引数に左へのポインタを渡すことで、再帰を繰り返して延々と左枝へ移動し 一番左、一番小さい値にたどり着く 子ノードはないため、引数の値はNULLに当たって戻ってくる 一番下位の要素なので、左枝と同様に右枝もない。 なので終点である NULL に行き当たり、また return で戻ってくる。 そして「一番左を操作する関数」は処理を終える。 この関数に戻り値はない。「画面に出力」して、それで終了*/ inorder(p->left); /* 左ノードへ移動 */ printf("%d ",p->data); /* 自身の値を出力 */ inorder(p->right); /* 右ノードへ移動 */ } /* 関数を終了して、自身を呼び出した関数のもとへ戻る */ } /* 二分木を帰りがけ順でなぞる */ void postorder(NODE *p) { /* 木が空なら何もしない */ if(p==NULL) return; else{ postorder(p->left); /* 左ノードへ移動 */ postorder(p->right); /* 右ノードへ移動 */ printf("%d ",p->data); /* 自身の値を出力 */ } } int main(void) { int a,key; int mn=0; printf("二分探索木をします\n"); do{ printf("\nメニューを選んでください\n1=追加 2=行きがけ順 3=通りがけ順 4=帰りがけ順 5=指定した値の番地 6=削除 9=終了\n"); scanf("%d",&mn); switch(mn){ case 1: printf("追加する数字を入力してください\n"); scanf("%d",&a); insert(a); break; case 2: printf("行きがけ順です\n"); preorder(root); break; case 3: printf("通りがけ順です\n"); inorder(root); break; case 4: printf("帰りがけ順です\n"); postorder(root); break; case 5: printf("指定した値の番地を出力します\n"); scanf("%d",&key); search(key); break; case 6: printf("指定した値を削除します\n"); scanf("%d",&key); delete(key); break; case 9: printf("終了します\n"); break; default: printf("エラー:メニューの中の数字を入力してください\n"); } }while (mn !=9); return 0; } `` ```### 前提・実現したいこと`````` 二分探索木のプログラムを実装したいです 仕様は 数字を入力して 1=追加 2=行きがけ順で表示 3=通りがけ順で表示 4=帰りがけ順で表示 5=指定した値の番地で表示 6=削除 9=終了 ができるようにしたいです アドバイスお願いいたします!! ### 発生している問題・エラーメッセージ 「34行目」で記述エラーを発見しました。 「identifier」を付け忘れています。 と出てしまいます

該当のソースコード

ここに言語を入力 ``` コード ``` ### 悩んでいること ① まず、 NODE *search(int key) 教科書に書いてあったこの宣言の仕方がよく分かりません 型名なしの関数の宣言の仕方を調べると一つだけ解説しているサイトが見つかり、自動的にint型になると書  いてあったのですが正しいのでしょうか? 引数があり、戻り値がある場合はvoid型ではない、 引数があり、戻り値がない場合はvoid型、 引数がなし、戻り値がある場合もvoid型、 引数がなし、戻り値がない場合もvoid型 と学びました preorder(NODE *p) postorder(NODE *p) inorder(NODE *p) これらの関数は引数があり、戻り値がない場合なのでvoid型、 int delete(int key) この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか NODE *search(int key) NODE *insert(int key) NODE *deletemin(NODE **p) これらの関数は引数があり、戻り値がある場合はvoid型ではない、int型だと思います。 ②keyの扱い方についてです if (key == p->data) ここの部分で教科書では関数を使って比べていましたがむずかしいので不等号を使って比べることにしました keyは値ですが、p->dataは番地ですよね 同じように値同士で扱うにはどのようにしたら良いのでしょうか 構造体の場合、アロー演算子は番地、ドットが実体だと習いましたがエラーが出てしまいます ③関数の値渡しについてです case 1: printf("追加する数字を入力してください\n"); scanf("%d",&a); insert(a); break; case 5: printf("指定した値の番地を出力します\n"); scanf("%d",&key1); search(key1); break; case 6: printf("指定した値を削除します\n"); scanf("%d",&key2); delete(key2); break; ここの部分で出力する場合の値と指定した値の変数名はそれぞれ変えたほうが良いですよね? ④探索した値の番地を出力する際に、 /* もしキーと注目している節のデータとが等しければポインタを関数として返す */ printf("探索した値の番地です>>%d\n",p->data); return p; としていますが、めちゃくちゃな状態です 探索した値の番地を返す場合、 return pはどのように扱えば良いのか悩みます。 ### 補足情報(FW/ツールのバージョンなど 初心者で使い方がよく分かっていません 自分の理解が正しいのか不安なのでコメント多いです 見づらければ修正します ご指摘ください

以下のような質問にはリアクションをつけましょう

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

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

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

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

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

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

適切な質問に修正を依頼しましょう。

y_waiwai

2020/12/01 03:15

このままではコードが読みづらいので、質問を編集し、<code>ボタンを押し、出てくる’’’の枠の中にコードを貼り付けてください
Zuishin

2020/12/01 03:19

> 「34行目」で記述エラーを発見しました。 > 「identifier」を付け忘れています。 > と出てしまいます それどころじゃなく、数えきれないほどの warning と error が出ました。
kyapi

2020/12/01 03:31

y_waiwaiさん、 コードの挿入をしました!
Zuishin

2020/12/01 03:34

> 他にも凡ミスがあるかもしれません 凡ミスというのは、本来できるはずのことをミスした時に使う言葉です。 20 行目や 30 行目などを見ても、まったく何もわからない人が書いたものにしか見えません。 あなたにはこの課題は早すぎます。この手の質問を見るたびに思うんですが、なぜ学習してから取り組まないのでしょう? テスト勉強せずにテストしなければならないルールでもあるんでしょうか?
fana

2020/12/01 06:49

> ドットにしたり、他の変数にに代入して値にしてもダメだった 行き当たりばったりにいじくってても仕方ないのでは. (確率的にたまたま正解と同じになることもあるハズ!という可能性に賭けた取り組み方なのか?) 課題が教科書に沿う内容であれば,教科書を読み返すのが最も手っ取り早い「頑張り」方なのでは.

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
86.12%

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

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

質問する

関連した質問

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

C

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