二分探索木のプログラムを実装したいです

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
matcha
記事: 5
登録日時: 2ヶ月前

二分探索木のプログラムを実装したいです

#1

投稿記事 by matcha » 2ヶ月前

はじめて質問をします
至らないところがありましたらご指摘お願いいたします
[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;
}
 [1.3] どのようなエラーやトラブルで困っているか(エラーメッセージが解る場合は記載)

「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言語を理解しているか
  C言語の基本は習いましたがまだまだ未熟者です

自分の理解が正しいのか不安なのでコメント多いです
見づらければ修正します

エラーがたくさん出ると思うのですが一つずつしか出てこないのでどこでやらかしているのか把握しきれていません
ご指摘お願いいたします。

matcha
記事: 5
登録日時: 2ヶ月前

Re: 二分探索木のプログラムを実装したいです

#2

投稿記事 by matcha » 2ヶ月前

投稿した質問を編集する方法もしりたいです

matcha
記事: 5
登録日時: 2ヶ月前

Re: 二分探索木のプログラムを実装したいです

#3

投稿記事 by matcha » 2ヶ月前

include <stdlib.h>
が消えていました。編集の方法を知りたいです、
通報?とかしかないです

アバター
usao
記事: 1635
登録日時: 7年前

Re: 二分探索木のプログラムを実装したいです

#4

投稿記事 by usao » 2ヶ月前

マルチポストしている暇があるなら
その時間で教科書を少しでも読んだ方が遥かに有用であろうと思わずにはいられません

https://teratail.com/questions/307464

アバター
usao
記事: 1635
登録日時: 7年前

Re: 二分探索木のプログラムを実装したいです

#5

投稿記事 by usao » 2ヶ月前

> int delete(int key)
> この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか

ここらへんとか,話の流れ(というか意味というか)がさっぱりわかりません.
戻り値をintとしてコードを書いたのはあなたなのであり,その戻り値の仕様すらコメントとして書いてすらいるではないか.
なのに「戻り値がない」と言う.何を言っているのか?

アバター
usao
記事: 1635
登録日時: 7年前

Re: 二分探索木のプログラムを実装したいです

#6

投稿記事 by usao » 2ヶ月前

> 関数の中身は「Cプログラマのアルゴリズムとデータ構造」という教科書を参考にしています

その教科書を読むだけではその教科書のコードが理解できないのであれば,
別途,何らかの情報ソースを探して,まずはCの基礎の基礎を学ぶべき.
手元に基礎を復習できる教材が無いなら,例えば「C 入門」とか何か適当にググって良さそうなところを2時間くらい見てきたらどうか?

(これは本当に真面目なアドバイス.こういう場所で他者に尋ねるよりもよほど早く解決するだろう.)

アバター
みけCAT
記事: 6390
登録日時: 10年前
住所: 千葉県
連絡を取る:

Re: 二分探索木のプログラムを実装したいです

#7

投稿記事 by みけCAT » 2ヶ月前

matcha さんが書きました:
2ヶ月前
投稿した質問を編集する方法もしりたいです
投稿した記事の右上にある鉛筆っぽいマークのボタンを押すことで編集できます。
ただし、投稿してから5分間しか編集できません。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6390
登録日時: 10年前
住所: 千葉県
連絡を取る:

Re: 二分探索木のプログラムを実装したいです

#8

投稿記事 by みけCAT » 2ヶ月前

matcha さんが書きました:
2ヶ月前
「32行目」で記述エラーを発見しました。
というのは再現できませんでしたが、
gccでコンパイルしたところ、以下のコンパイルエラーが出ました。
(gccの-Werrorオプションを用いて警告もエラー扱いにしました)
ロジックはチェックしていません。
  • 2行目:あってはいけない位置に全角スペースがある
    (消すべき)
  • 42行目:ifが無いのにelseがある
    (39~41行目を{}で囲むのを忘れた?)
  • 45行目・74行目:ifが無いのにelseがある
    (代わりに} else {とするべき?)
  • 74行目:ifが無いのにelseがある
    (代わりに} else {とするべき?)
  • 82行目:代入できないものに代入しようとしている
    (比較には=ではなく==を用いるべき)
  • 123行目:まだ宣言も定義もされていない関数deleteminが使われている
    (関数などの識別子は使う前に宣言または定義を置かないといけない)
  • 124行目・125行目:代入できないものに代入しようとしている
    (単項&で取得したアドレスには代入できないので、&を取るか、左に*を付けてデリファレンスするべき)
  • 153行目:インデントがおかしい
    (151目のwhileでループしたいように見えて紛らわしい)
  • 159行目・175行目・188行目:関数定義で返り値の型が書かれていない
    (値を返さないようなのでvoidを付けるべき)
  • 194行目:宣言も定義もされていない関数postorderrが使われている
    (postorderとするべき)
  • 203行目・204行目:使用されていない変数が宣言されている
    (消すかコメントアウトした方がいいかも)
  • 223行目・228行目・233行目:引数がある関数なのに引数を入れずに呼び出そうとしている
    (rootを引数として渡すべき?)
  • 245行目:あってはいけない位置に全角スペースがある
    (消すべき)
matcha さんが書きました:
2ヶ月前
まず、
NODE *search(int key)
教科書に書いてあったこの宣言の仕方がよく分かりません

型名なしの関数の宣言の仕方を調べると一つだけ解説しているサイトが見つかり、自動的にint型になると書  いてあったのですが正しいのでしょうか?
正しいですが、型名は省略しないべきです。
なお、この宣言は型名なしの関数の宣言ではなく、きちんと型名が書かれています。
matcha さんが書きました:
2ヶ月前
preorder(NODE *p)
postorder(NODE *p)
inorder(NODE *p)
これらの関数は引数があり、戻り値がない場合なのでvoid型、
そう思ったら、voidを書くべきです。
戻り値の型が明示されていないため、int型になります。
なお、これらの関数には値を指定したreturn文が無いため、
呼び出し元でこれらの関数から「返された」値を用いると未定義動作になります。
matcha さんが書きました:
2ヶ月前
int delete(int key)
この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか
引数も戻り値もある場合なのでvoid型ではないと思います。
この関数では、きちんと値を指定したreturn文が使用されています。
matcha さんが書きました:
2ヶ月前
NODE *search(int key)
NODE *insert(int key)
NODE *deletemin(NODE **p)
これらの関数は引数があり、戻り値がある場合はvoid型ではない、int型だと思います。
search関数とinsert関数の引数はint型ですが、
戻り値、deletemin関数の引数、そして関数自体はint型ではありません。
matcha さんが書きました:
2ヶ月前
if (key == p->data)
ここの部分で教科書では関数を使って比べていましたがむずかしいので不等号を使って比べることにしました
keyは値ですが、p->dataは番地ですよね
同じように値同士で扱うにはどのようにしたら良いのでしょうか
38行目ですね。
pは構造体nodeへのポインタなので、p->dataもint型の値です。
すでに値同士で扱っています。
matcha さんが書きました:
2ヶ月前
構造体の場合、アロー演算子は番地、ドットが実体だと習いましたがエラーが出てしまいます
A->Bは(*A).Bと同じ意味です。
何を書いて、どのようなエラーが出るのでしょうか?
matcha さんが書きました:
2ヶ月前
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;

ここの部分で出力する場合の値と指定した値の変数名はそれぞれ変えたほうが良いですよね?
「出力する場合の値」というのは意味がよくわかりませんが、
a, key1, key2は同じ「木のノードに格納する値を表すint型の変数」であり、
同時に複数の変数の値を使うことが無いので、同じ変数にしてもいいと思います。
matcha さんが書きました:
2ヶ月前
探索した値の番地を出力する際に、

/* もしキーと注目している節のデータとが等しければポインタを関数として返す */
printf("探索した値の番地です>>%d\n",p->data);
return p;

としていますが、めちゃくちゃな状態です
探索した値の番地を返す場合、 return pはどのように扱えば良いのか悩みます。
return pはkey == p->dataが成立する場合のみ実行するようにすると良いでしょう。
(39行目~41行目を{}で囲み、40行目だけでなく41行目も38行目の条件が成立した場合のみ実行するようにする)
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

matcha
記事: 5
登録日時: 2ヶ月前

Re: 二分探索木のプログラムを実装したいです

#9

投稿記事 by matcha » 2ヶ月前

usaoさん
ご指摘ありがとうございます
マルチポスト?ということになるのですね
Cの基礎の基礎を自分で勉強します
ありがとうございます

matcha
記事: 5
登録日時: 2ヶ月前

Re: 二分探索木のプログラムを実装したいです

#10

投稿記事 by matcha » 2ヶ月前

みけCATさん
質問とエラーが多いのに丁寧に説明してくださり助かります!!
一つずつエラーを消していこうと思います
参考にさせていただきます!ありがとうございます!

返信

“C言語何でも質問掲示板” へ戻る