学校課題の二分探索木

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。

BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF

トピックのレビュー
   

展開ビュー トピックのレビュー: 学校課題の二分探索木

Re: 学校課題の二分探索木

#13

by Act » 8ヶ月前

ありがとうございます。おかげさまで何とか課題を終わらせることができました。
今授業が終わったのですが、模範解答の提示はなさそうです。

Re: 学校課題の二分探索木

#12

by かずま » 8ヶ月前

不適切な入力への対処としては、行単位で読む方法もあります。

コード:

		char buf[256];
		if (!fgets(buf, sizeof buf, stdin)) break;
		if (sscanf(buf, "%d", &sousa) != 1) sousa = -1;
こっちのほうが簡単ですね。

しかし、scanf("%d", &sousa); だけでいいと思います。

というのは、この課題は、二分探索木の操作をどう実装するかが
主眼であり、エラー処理は別の問題だからです。

実用性を気にするのなら、
・データの挿入時に名前が 30文字以上入力された場合どうするのか
・10万件のデータがあった場合、常に全部を表示するのは問題
・挿入や削除を行ってもデータの保存ができないのなら意味がない
など、多くの解決すべき問題があると思います。

課題なら提出後、模範解答が示さるかもしれません。
そのときは、どんなものか教えていただければ幸いです。

Re: 学校課題の二分探索木

#11

by Act » 8ヶ月前

#4のコードであらためて実行してみました。その結果確かに無限ループに陥っていることが確認できました。
#4のコードを書いているときに、入力してほしい文字以外の入力に対する対応について全く考えていませんでした。次からは気を付けようと思います。

Re: 学校課題の二分探索木

#10

by かずま » 8ヶ月前

ちょっと言葉が足りませんでした。
#4 のあなたのプログラムで数字以外を入れると、
とんでもないことになりませんか?
と言いたかったのです。

int sousa; // 初期されていないから何が入っているかわからない。
scanf("%d", &sousa); // 数字を読み取ることしか考えていない。

ここで、q Enter と入力すると、'q' は数字ではないので、
scanf は数値に変換できず、sousa には何も入れません。
'q' は標準入力バッファに押し戻されて、次の入力に使われます。

sousa にはゴミ(不定値)が入っていて、switch(sousa) で分岐
します。たいていは default: に行くでしょう。そして、while (1)
に戻り、また scanf("%d", &sousa); で'q' が読み込まれて、
さっきと同じ動作をします。すなわち、無限ループになるのです。

#5 の私のプログラムでは、この無限ループを防ぐために
if (scanf("%d", &sousa) != 1) return 1;
で、異常終了させています。'0' で終了させたときのように
「正常終了します。」は表示されません。

実用的なプログラムでは、無限ループも異常終了もよくありません。
対処方法は、次のようにして改行コードまで読み飛ばすことでしょうか。

コード:

		if (scanf("%d", &sousa) != 1) {
			int c;
			while ((c = getchar()) != EOF && c != '\n') ;
			if (c == EOF) return 1;
			sousa = -1;
		}
malloc のほうは、

コード:

	if (p == NULL) {
		p = (NODE *) malloc(sizeof(NODE));
		if (p) {
			strcpy(p->name, name);
			strcpy(p->telnumb, telnumb);
			p->left = p->right = NULL;
		} 
		else puts("メモリ不足のためデータを登録できません。");
	}
もちろん、これらのやり方が最善というわけではありません。

Re: 学校課題の二分探索木

#9

by Act » 8ヶ月前

実際に実行してみましたが、処理の入力においてアルファベットを1文字から複数文字入力してもエラーが起こっているような様子がなく、逆に0を入力したときにエラーが起こっている様子です。

メニューの入力については、数字で操作を指定しているので操作を読みこんだあと、数字に変換できればその操作を実行し、変換できなければエラーメッセージを表示する方法しか思いつきませんでした。

Re: 学校課題の二分探索木

#8

by かずま » 8ヶ月前

Act さんが書きました:
8ヶ月前
探索する関数に関しては、今いるノードが空だったらデータが見つからなかったということでNULLを返すという認識でよろしいのでしょうか?
その通りです。
Act さんが書きました:
8ヶ月前
その次の

コード:

	diff = strcmp(name, p->name);
	if (diff < 0) return search(p->left, name);
	if (diff > 0) return search(p->right, name);
	return p;
この部分は探索するnameの文字列がpの文字列と比べて探索したいデータのほうが先になるときはdiff<0の場合でまたsearchを呼び出して、探索したいデータのほうが後になるときはdiff>0の場合で同様にsearchを呼び出してpがなにもないところまでひたすら繰り返すということでしょうか。
name が見つかるか、または p が NULL になるまで繰り返します。
name が見つかったら p は NULL ではありません。
Act さんが書きました:
8ヶ月前
次の消去する関数については、最初にpが何もないときの処理を明確にしておき、探索のばあいと同様に対象のnameとノードのnameを比較し、等しくならないときに対象のnameが大きければ左下のノードに、小さければ右下のノードに移り、また繰り返していく。
これは探索の場合と同じです。
Act さんが書きました:
8ヶ月前
その次の

コード:

		else {
			if (p->left == NULL) p = p->right; 
			else {
				NODE *q = p;
				p = p->left;
				if (q->right) {
					NODE *r = q->left;
					while (r->right) r = r->right;
					r->right = q->right;
					free(q);
				}
			}
		}
この部分が、対象のnameと等しかった時の条件というのはわかるのですが、次にqを使うのには理由があるのでしょうか。おそらく理解が追い付いていないので、説明をしていただけるとありがたいです。
p が指している現在の NODE を削除しないといけないのですが、
free(p); を実行すると、p の更新で p = p->left; が実行
できないのです。なぜなら、p->left はもう使えないからです。
そこで、NODE *q = p; p = p->left; free(q); とします。
または、Node *q = p->left; free(p); p = q; でもよいでしょう。

ここでバグを見つけてしまいました。その削除のコードは
free し忘れでメモリーリークするので、次のように修正します。

コード:

NODE *del(NODE *p, char name[])
{
	if (p == NULL) { puts("  データが見つかりません。"); return NULL; }
	int diff = strcmp(name, p->name);
	if (diff < 0) p->left = del(p->left, name);
	else if (diff > 0) p->right = del(p->right, name);
	else {
		NODE *q = p;
		if (p->left == NULL) p = p->right;
		else {
			p = p->left;
			if (q->right) {
				NODE *r = q->left;
				while (r->right) r = r->right;
				r->right = q->right;
			}
		}
		free(q);
	}
	return p;
}
まず、p == NULL のとき、すぐに return することで、
次の行から後を else に入れなくてよいようにし、
ネストが一段深くなるのを防いでいます。

diff < 0 や diff > 0 で del の再帰呼出しをするのは
検索と同じことです。

strdmp の結果を diff に入れるのは、次のように
strcmp を 2回実行するのは無駄だからです。

コード:

	if (strcmp(name, p->name) < 0) ...
	else if (strcmp(name, p->name) > 0) ...
	else {
さて、削除したい NODE が見つかった時、
その NODE は free するのですが、子の left か
rightを親に繋ぎなおさなければなりません。
p->left が NULL のときは p->right を返せばよいので
p = p->right; です。
p->left が NULL でないときは p->left を返すので、
p = p->left; です。
このとき、p->right が NULL なら問題ないのですが、
そうでないとき、p->right を p->left の右側に
繋がないといけないので、NODE *r を使って、right が
NULL になっている NODE を探しに行き、そこに繋ぎます。
以上の処理を行うと free(q) で NODE を削除できます。
Act さんが書きました:
8ヶ月前
最後に、main()内のファイルを開く部分ですが、

コード:

	fp = fopen("namelist5.txt", "r");  /*ファイルを開く */
	if (!fp) return puts("fopen failed"), 1;
ここの2行目の書き方は、このような書き方もできるという認識でよろしいのでしょうか。
質問や疑問ばかりで申し訳ないのですが、よろしくお願いします。
次のように書くのと同じです。

コード:

	if (fp == NULL) { puts("fopen failed"); return 1; }
100,000件のデータを扱う実用的なものにするんだったら、
malloc が失敗した場合の処理も入れたほうが良いでしょう。
また、メニューで 0~4以外の数字を入れても大丈夫ですが、
数字以外の文字を間違って入力したとき、とんでもないことに
なります。その対処方法は分かりますか?

Re: 学校課題の二分探索木

#7

by Act » 8ヶ月前

探索する関数に関しては、今いるノードが空だったらデータが見つからなかったということでNULLを返すという認識でよろしいのでしょうか?
その次の

コード:

diff = strcmp(name, p->name);
	if (diff < 0) return search(p->left, name);
	if (diff > 0) return search(p->right, name);
	return p;
この部分は探索するnameの文字列がpの文字列と比べて探索したいデータのほうが先になるときはdiff<0の場合でまたsearchを呼び出して、探索したいデータのほうが後になるときはdiff>0の場合で同様にsearchを呼び出してpがなにもないところまでひたすら繰り返すということでしょうか。

次の消去する関数については、最初にpが何もないときの処理を明確にしておき、探索のばあいと同様に対象のnameとノードのnameを比較し、等しくならないときに対象のnameが大きければ左下のノードに、小さければ右下のノードに移り、また繰り返していく。
その次の

コード:

		else {
			if (p->left == NULL) p = p->right; 
			else {
				NODE *q = p;
				p = p->left;
				if (q->right) {
					NODE *r = q->left;
					while (r->right) r = r->right;
					r->right = q->right;
					free(q);
				}
			}
		}
この部分が、対象のnameと等しかった時の条件というのはわかるのですが、次にqを使うのには理由があるのでしょうか。おそらく理解が追い付いていないので、説明をしていただけるとありがたいです。

最後に、main()内のファイルを開く部分ですが、

コード:

	fp = fopen("namelist5.txt", "r");  /*ファイルを開く */
	if (!fp) return puts("fopen failed"), 1;
ここの2行目の書き方は、このような書き方もできるという認識でよろしいのでしょうか。
質問や疑問ばかりで申し訳ないのですが、よろしくお願いします。

Re: 学校課題の二分探索木

#6

by かずま » 8ヶ月前

すみません。NODE の telnumb[20] だけでなく、
main の telnumb[12] も telnumb[20] にしてください。

Re: 学校課題の二分探索木

#5

by かずま » 8ヶ月前

"093-725-6495" は 12文字ですが、
文字列終端の '\0' を含めて 13バイトです。
携帯の電話番号は "090-1234-5678" で 14バイトです。
国際電話用の国番号を加えるともっと増えます。

maketree は挿入に使えます。
削除はちょっと難しいですね。

説明が面倒なので、
あなたが次のコードを理解して解説してください。
不具合の指摘、疑問点の質問などは歓迎します。

コード:

#include <stdio.h>   // fopen, fclose, fscanf, printf, puts, putchar
#include <string.h>  // strcpy, strcmp
#include <stdlib.h>  // malloc, free

/*構造体*/
typedef struct NODE {  /*構造体 */
	char name[30];     /*名前 */
	char telnumb[20];  /*電話番号 */
	struct NODE *left;
	struct NODE *right;
} NODE;

NODE *maketree(NODE *p, char name[], char telnumb[]);
void Output(NODE *p);
void Free(NODE *p);
NODE *search(NODE *p, char name[]);
NODE *del(NODE *p, char name[]);

int main(void)
{
	char name[30], telnumb[12];
	NODE *root, *node;
	FILE *fp;
	int sousa;

	fp = fopen("namelist5.txt", "r");  /*ファイルを開く */
	if (!fp) return puts("fopen failed"), 1;

	root = NULL;
	while (fscanf(fp, "%s%s", name, telnumb) == 2)
		root = maketree(root, name, telnumb);
	fclose(fp);

	do {
		puts("処理する内容を選んでください。\n"
		     "0.終了 1.挿入 2.検索 3.削除 4.表示");
		if (scanf("%d", &sousa) != 1) return 1;

		switch (sousa) {
		case 0: break;  /* 終了 */

		case 1:   /*情報を追加する */
			puts("追加する名前をローマ字で名→姓の順で入力してください。");
			scanf("%s", name);
			puts("追加する電話番号を-も含めて入力してください。");
			scanf("%s", telnumb);
			root = maketree(root, name, telnumb);
			break;

		case 2:   /*情報を検索する */
			puts("検索したい名前を入力してください。");
			scanf("%s", name);
			node = search(root, name);
			if (node)
				printf("  %s %s\n", node->name, node->telnumb);
			else
				puts("  not found");
			break;

		case 3:   /*削除する */
			puts("削除したい名前を入力してください。");
			scanf("%s", name);
			root = del(root, name);
			break;

		case 4:   /*表示する */
			Output(root);
			break;

		default:  /* 0~4以外の数字が入力されたとき */
			puts("入力された数字は対応していません。もう一度入力して下さい。");
		}
		putchar('\n');
	} while (sousa != 0);

	Free(root);
	printf("正常終了します。\n");
	return 0;
}

/*構造体*/
NODE *maketree(NODE * p, char name[], char telnumb[])  /*再帰関数 */
{
	if (p == NULL) {  /*NULLに突き当たったところに新たなノードを入れる */
		p = (NODE *) malloc(sizeof(NODE));  /*メモリの確保 */
		/*データの格納 */
		strcpy(p->name, name);
		strcpy(p->telnumb, telnumb);
		p->left = p->right = NULL;  /*”葉”はNULLを指す */
	}
	else if (strcmp(name, p->name) < 0)  /*比較した文字が後にくる->左に */
		p->left = maketree(p->left, name, telnumb);
	else if (strcmp(name, p->name) > 0)   /*比較した文字が先にくる->右に */
		p->right = maketree(p->right, name, telnumb);
	else
		printf("同姓同名のデータは登録できません。\n");
	return p;  /*main関数にはrootのアドレスを返す */
}

void Output(NODE * p)  /*通り掛け順のなぞりというらしい */
{
	if (p == NULL) return;

	Output(p->left);   /*左へ */
	printf("%s %s\n", p->name, p->telnumb);  /*自分のデータ */
	Output(p->right);  /*右へ */
}

void Free(NODE * p)
{
	if (p == NULL) return;
	Free(p->left);   /*左の子を解放 */
	Free(p->right);  /*右の子を解放 */
	free(p);         /*自分を解放 */
}

NODE *search(NODE * p, char name[])
{
	int diff;
	if (p == NULL) return NULL;
	diff = strcmp(name, p->name);
	if (diff < 0) return search(p->left, name);
	if (diff > 0) return search(p->right, name);
	return p;
}

NODE *del(NODE *p, char name[])
{
	if (p == NULL) puts("  not found");
	else {
		int diff = strcmp(name, p->name);
		if (diff < 0) p->left = del(p->left, name);
		else if (diff > 0) p->right = del(p->right, name);
		else {
			if (p->left == NULL) p = p->right; 
			else {
				NODE *q = p;
				p = p->left;
				if (q->right) {
					NODE *r = q->left;
					while (r->right) r = r->right;
					r->right = q->right;
					free(q);
				}
			}
		}
	}
	return p;
}
質問を放置せず、必ず返信をお願いします。
理解できないところがあれば、どこの何がわからないのかを
具体的に質問してください。

Re: 学校課題の二分探索木

#4

by Act » 8ヶ月前

返信ありがとうございます。少し考えてみて、下のコードから考えていこうと思います。

コード:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

/*構造体*/
typedef struct NODE{/*構造体*/
  char name[30];/*名前*/
  char telnumb[12];/*電話番号*/
  struct NODE *left;
  struct NODE *right;
  struct NODETag *parent;
}NODE;

NODE *maketree(NODE *p,char a[], char b[]);
void Output(NODE *p);
void Free(NODE *p);

char scname[30],sctelnumb[12];
struct tnode *root, *node, *old, *new;

int main(void)
{
  char name[30],telnumb[12];
  char scname[30],sctelnumb[12];
  NODE *root, *node, *old, *new;
  NODE *tget;
  FILE *fp;
  int sousa;

  fp = fopen("namelist5.txt","r");/*ファイルを開く*/

  root = NULL;
  while(fscanf(fp,"%s%s",name,telnumb)!=EOF)root = maketree(root,name,telnum\
b);

  fclose(fp);

  while(1){
    printf("処理する内容を選んでください。\n");
    printf("1.挿入 2.検索 3.削除 4.表示\n");
    scanf("%d",&sousa);

    switch(sousa){
    case 1:/*情報を追加する*/
      printf("追加する名前をローマ字で名→姓の順で入力してください。\n");
      scanf("%s",scname);
      printf("追加する電話番号を-も含めて入力してください。\n");
      scanf("%s",sctelnumb);
      sounyuu(root,scname,sctelnumb);
      break;

    case 2:/*情報を検索する*/
      printf("検索したい名前を入力してください。\n");
      scanf("%s",scname);
      printf("検索したい名前の電話番号を入力してください。\n");
      scanf("%s",sctelnumb);
      search(scname,sctelnumb);
      break;

    case 3:/*削除する*/
      printf("削除したい名前を入力してください。\n");
      scanf("%s",scname);
      break;

    case 4:/*表示する*/
      Output(root);
      break;

    default:/*1~3以外の数字が入力されたとき*/
      printf("入力された数字は対応していません。もう一度入力して下さい。/n")\
;
    }
    printf("\n");
  }

  printf("正常終了します。\n");
  return 0;
}

/*構造体*/
NODE *maketree(NODE *p, char a[], char b[])/*再帰関数*/
{
  if(p == NULL){/*NULLに突き当たったところに新たなノードを入れる*/
    p = (NODE *)malloc(sizeof(NODE));/*メモリの確保*/
    /*データの格納*/
    strcpy(p->name, a);
    strcpy(p->telnumb, b);
    p->left = p->right = NULL;/*”葉”はNULLを指す*/
  }
  else if(strcmp(a,p->name)<0)/*比較した文字が後にくる->左に*/
    p->left = maketree(p->left,a,b);
  else if(strcmp(a,p->name)>0)/*比較した文字が先にくる->右に*/
    p->right = maketree(p->right,a,b);
  else printf("同姓同名のデータは登録できません。\n");

  return p;/*main関数にはrootのアドレスを返す*/
}

void Output(NODE *p)/*通り掛け順のなぞりというらしい*/
{
  if(p == NULL)
    return;

  Output(p->left);/*左へ*/
  printf("%s %s\n",p->name, p->telnumb);/*親のデータ*/
  Output(p->right);/*右へ*/
}

void Free(NODE *p)
{
  if(p == NULL)return;

  Free(p->left);/*左の子を解放*/
  Free(p->right);/*右の子を解放*/
  Free(p);/*親*/
}

int search(char scname[],char sctelnumb[]){

}

int sounyuu(char scname[],char sctelnumb[]){
  
}
上のコードではコンパイルは通ります。データのファイルの中身は以下の通りです。

コード:

masugata_kimiiti 017-670-4762
souseki_keiko 01-7935-5243
okunuki_sawako 011-175-5411
hukumi_tihuru 093-725-6495
kosagawa_gaiiti 011-765-5257
現段階では、表示のみがしっかり動き

コード:

hukumi_tihuru 093-725-6495
kosagawa_gaiiti 011-765-5257
masugata_kimiiti 017-670-4762
okunuki_sawako 011-175-5411
souseki_keiko 01-7935-5243
と表示されます。
まず、データを挿入する関数についてですが、maketreeを使ってやろうと思いましたが、前の課題でうまくいった

コード:

root=maketree(root,name,telnumb);
として作ろうとしましたが、
”互換性のないポインタ型から 1 番目の ‘maketree’ の引数に渡しています [デフォルトで有効]
root=maketree(root,scname,sctelnumb);”
というコンパイルエラーが出てしまいコンパイルできません。
また、課題として、入力した名前のデータを検索する関数、削除する関数を作るのですが、いろいろ調べて実際に書いてみたりしましたが内容が理解できなかったです。

Re: 学校課題の二分探索木

#3

by かずま » 8ヶ月前

Act さんが書きました:
8ヶ月前
ここまでは作ってみました。
なにか書き忘れもあると思うので、ご指摘ください。
コンパイルできるコードを提示してください。
エラーメッセージの意味が分からないのなら、
それを貼り付けてください。
メニューに、「4.表示 」を追加してください。
実行できるようになったら、データのファイルの件数を 5件にして、
実行結果を示し、どこが分からないのかを質問してください。

Re: 学校課題の二分探索木

#2

by Act » 8ヶ月前

いろいろ参考にして挿入と検索の関数を書いてみましたがうまくいきません。正直理解が追い付いていないところがあります。

コード:

int search(char scname[],char sctelnumb[]){
  NODE=root;
  while(1){
    if(strcmp(scname,NODE->name) == 0)
      break;
    if(strcmp(scname,NODE->name) < 0){
      if(NODE->left==NULL)
        break;
      NODE=NODE->left;
    }
    else{
      if(NODE->right==NULL)
        break;
      NODE=NODE->right;
    }
  }

  if(strcmp(scname,NODE->name) == 0){
    if(strcmp(sctelnumb,NODE->telnumb) == 0)
      printf("みつかりました\n");
    else
      printf("番号が違う可能性があります\n");
  }

  if(syrcmp(scname,NODE->name) != 0)
    printf("みつかりませんでした\n");

  return 0;
}

int sounyuu(char scname[],char sctelnumb[]){
  NODE=root;
  while(NODE != NULL){
    old=NODE;
    if(strcmp(scname,NODE->name) == 0){/*同じ名前があった時*/
      printf("同じ名前が存在しています。\n");
      break;
    }

    if(strcmp(scname,NODE->name) < 0){
      NODE=NODE->left;
    }else{
      NODE=NODE->right;
    }
  }

  NODE=(struct tnode *)malloc(sizeof(struct tnode));
  strcpy(NODE->name,scname);
  strcpy(NODE->telnumb,sctelnumb);
  NODE->left=NODE->right=NULL;

  if(strcmp(scname,NODE->name) < 0){
    old->left=NODE;
  }else{
    old->right=NODE;
  }

  return 0;
}
どなたかご助力をお願いします。

学校課題の二分探索木

#1

by Act » 8ヶ月前

学校の課題で、二分探索木においてデータの挿入、削除、および検索の各関数の作成をする問題が出ました。削除と検索の関数の作り方がわかりません。今は課題の提出を最優先にしたいため解答を求めていますが、アドバイスなどもうれしいです。

コード:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

/*構造体*/
typedef struct NODE{/*構造体*/
  char name[30];/*名前*/
  char telnumb[12];/*電話番号*/
  struct NODE *left;
  struct NODE *right;
}NODE;

NODE *maketree(NODE *p,char a[], char b[]);
void Output(NODE *p);
void Free(NODE *p);

int Sounyuu(){

}

int Del(){

}

int Search(NODE *p,int n){
  char scname[30];
  NODE *root;
  NODE *tget;
  FILE *fp;
  int sousa;

  fp = fopen("namelist100.txt","r");/*ファイルを開く*/

  root = NULL;
  while(fscanf(fp,"%s%s",name,telnumb)!=EOF)root = maketree(root,name,telnum\
b);

  fclose(fp);

  while(1){
    printf("処理する内容を選んでください。\n");
    printf("1.挿入 2.削除 3.検索\n");
    scanf("%d",&sousa);

    switch(sousa){
    case 1:/*情報を追加する*/
      printf("追加する名前をローマ字で名→姓の順で入力してください。\n");
      scanf("%s",name);
      printf("追加する電話番号を-も含めて入力してください。\n");
      scanf("%s",telnumb);
      maketree(name[],telnumb[]);
      break;

    case 2:/*情報を削除する*/
      printf("削除する名前を入力してください。\n");
      scanf("%s",scname);
      Del(scname);
      break;

    case 3:/*情報を検索する*/
      printf("検索したい名前を入力してください。\n");
      scanf("%s",name);
      Search()
      break;

    default:/*1~3以外の数字が入力されたとき*/
      printf("入力された数字は対応していません。もう一度入力して下さい。/n")\
;
    }
    printf("\n");
  }

  printf("正常終了します。\n");
  return 0;
}

/*構造体*/
NODE *maketree(NODE *p, char a[], char b[])/*再帰関数*/
{
  if(p == NULL){/*NULLに突き当たったところに新たなノードを入れる*/
    p = (NODE *)malloc(sizeof(NODE));/*メモリの確保*/
    /*データの格納*/
    strcpy(p->name, a);
    strcpy(p->telnumb, b);
    p->left = p->right = NULL;/*”葉”はNULLを指す*/
  }
  else if(strcmp(a,p->name)<0)/*比較した文字が後にくる->左に*/
    p->left = maketree(p->left,a,b);
  else if(strcmp(a,p->name)>0)/*比較した文字が先にくる->右に*/
    p->right = maketree(p->right,a,b);
  else printf("同姓同名のデータは登録できません。\n");

  return p;/*main関数にはrootのアドレスを返す*/
}

void Output(NODE *p)/*通り掛け順のなぞりというらしい*/
{
  if(p == NULL)
    return;

  Output(p->left);/*左へ*/
  printf("%s %s\n",p->name, p->telnumb);/*親のデータ*/
  Output(p->right);/*右へ*/
}

void Free(NODE *p)
{
  if(p == NULL)return;

  Free(p->left);/*左の子を解放*/
  Free(p->right);/*右の子を解放*/
  Free(p);/*親*/
}

}

ここまでは作ってみました。
なにか書き忘れもあると思うので、ご指摘ください。
お力をお借りしたいです。よろしくお願いします。
以下、問題文です。

1.4 [標準課題1] データの挿入,削除,および検索の各関数の作成
次に,あらかじめ作成した二分探索木に対して,新しいデータを挿入する関数,削除 する関数,および,データを検索する関数を作成する.作成したプログラムが正しく動 作していることを確認するために,テストデータとして 100,000 件のリストを保存した “namelist100k.txt” をプログラミング演習 II のページからダウンロードし,そのデータ から作成した二分探索木に対して新しいデータの入力,検索,削除を行う.まず,作成し た二分探索木に対する処理(入力,検索,削除)の選択を標準入力で行い,次に処理を行 うデータを入力する.具体的に挿入されたことを検索により確かめて正しく動作してい ることを確認する.また,データの削除についても検索を行ってデータが二分探索木か ら削除されたことを確認する.

ページトップ