至らないところがありましたらご指摘お願いいたします
[1] 質問文
[1.1] 自分が今行いたい事は何か
二分探索木のプログラムを実装したいです
仕様は
数字を入力して
switch文で
1=追加
2=行きがけ順で表示
3=通りがけ順で表示
4=帰りがけ順で表示
5=指定した値を番地で表示
6=削除
9=終了
ができるようにしたいです
アドバイスお願いいたします！！
関数の中身は「Cプログラマのアルゴリズムとデータ構造」という教科書を参考にしています
[1.2] どのように取り組んだか(プログラムコードがある場合記載)
#include <stdio.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); /* 異常終了 */
}
/* 二分探索木を探索する関数 */
/* パラメータkeyを受け取ってポインタを返す関数として定義
key：探索すべきキーの値
探索に成功した場合そのデータの節へのポインタを返す */
NODE *search(int key)
{
NODE *p; /* 現在注目している節 */
p=root; /* まず根に注目する */
/* 進むべき子が存在する限り繰り返す */
while (p != NULL) {
/* キーと注目している節のデータが等しいか比較 */
if (key == p->data)
/* もしキーと注目している節のデータとが等しければポインタを関数として返す */
printf("探索した値の番地です>>%d\n",p->data);
return p;
else if (key < p->data) {
/* キーの方が小さければ左部分木に進む */
p = p->left;
else
/* キーの方が大きければ右部分木に進む*/
p = p->right;
}
/* ループを抜け出たということは見付からなかったというと
NULL返して失敗したことを知らせる */
printf("NotExist\n");
return NULL;
}
/* 二分探索木から要素を追加する関数*/
/* 探索と同じ要領で木を辿り、辿るべき部分木がなければそこに挿入する */
/* 挿入した要素が置かれる節へのポインタを返す
すでに要素が登録されているのなら、何もしないでNULLを返す
key：挿入するデータ */
NODE *insert(int key)
{
NODE **p,*new;
/* 変数pが変数rootを指すように初期化する */
p=&root;
/* 挿入すべき場所が見つかるまで繰り返す */
while (*p != NULL) {
/* キーと注目している節のデータが等しいか比較 */
if (key == (*p)->data)
/* すでに登録されている */
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;
}
/* 二分探索木から最小の要素を削除する関数 */
/* 削除した節へのポインタを返す
p:二分探索木へのポインタへのポインタ
(つまり＊pが木へのポインタとなる) */
NODE *deletemin(NODE **p)
{
NODE *x;
while ((*p)->left != NULL)
p=&(*p)->left;
x=*p;
*p=(*p)->right;
return x;
}
/* 二分木を行きがけ順でなぞる */
preorder(NODE *p)
{
/* 木が空なら何もしない */
if(p==NULL)
return;
else{
printf("%d",p->data); /* 自身の値を出力 */
preorder(p->left); /* 左ノードへ移動 */
preorder(p->right); /* 右ノードへ移動 */
}
}
/* 二分木を通りがけ順でなぞる */
/* 全要素を昇順に表示する関数
二分探索木の全要素を小→大の順で表示する */
inorder(NODE *p)
{
/* 木が空なら何もしない */
if(p==NULL)
return;
else{
inorder(p->left); /* 左ノードへ移動 */
printf("%d",p->data); /* 自身の値を出力 */
inorder(p->right); /* 右ノードへ移動 */
}
}
/* 二分木を帰りがけ順でなぞる */
postorder(NODE *p)
{
/* 木が空なら何もしない */
if(p==NULL)
return;
else{
postorderr(p->left); /* 左ノードへ移動 */
postorder(p->right); /* 右ノードへ移動 */
printf("%d",p->data); /* 自身の値を出力 */
}
}
int main(void)
{
int i;
int n;
int a,key1,key2;
int mn=0;
printf("二分探索木をします\n");
do{
printf("メニューを選んでください\n\n1=追加\n2=行きがけ順\n3=通りがけ順\n4=帰りがけ順\n5=指定した値の番地\n6=削除\n9=終了\n");
scanf("%d",&mn);
switch(mn){
case 1:
printf("追加する数字を入力してください\n");
scanf("%d",&a);
insert(a);
break;
case 2:
printf("行きがけ順です\n");
preorder();
break;
case 3:
printf("通りがけ順です\n");
inorder();
break;
case 4:
printf("帰りがけ順です\n");
postorder();
break;
case 5:
printf("指定した値の番地を出力します\n");
scanf("%d",&key1);
search(key1);
break;
case 6:
printf("指定した値を削除します\n");
scanf("%d",&key2);
delete(key2);
break;
case 9:
printf("終了します\n");
break;
default:
printf("エラー：メニューの中の数字を入力してください\n");
}
}while (mn !=9);
return 0;
}
「32行目」で記述エラーを発見しました。
「identifier」を付け忘れています。
というエラーが出ます
他にもたくさんエラーがあると思われますがとりあえずここで苦戦しています。
[1.4] 今何がわからないのか、知りたいのか
① まず、
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はどのように扱えば良いのか悩みます。
[2] 環境
[2.1] OS ： Windows, Linux等々
EasyIDECを使っています
[2.2] コンパイラ名 ： VC++ 2008EE, Borand C++, gcc等々
c言語です
[3] その他
・どの程度Ｃ言語を理解しているか
C言語の基本は習いましたがまだまだ未熟者です
自分の理解が正しいのか不安なのでコメント多いです
見づらければ修正します
エラーがたくさん出ると思うのですが一つずつしか出てこないのでどこでやらかしているのか把握しきれていません
ご指摘お願いいたします。
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター