二分木を使ってソートを行うプログラムが動作を停止してしまいます

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

二分木を使ってソートを行うプログラムが動作を停止してしまいます

#1

投稿記事 by FFF » 9年前

node->dataはnode->leftの部分木に含まれている全てのデータ以上かつ
node->dataはnode->rightの部分木ぶ含まれている全てのデータ以下
という2つの条件を満たした部分木をファイルからデータを読み込み作成し、それをprint_tree関数を使って表示させるというプログラムを作りました。
データは
max 100 n 100
54
16



2
11
といったような形式で書かれたファイルを読み込みます。
完成したプログラムを実行したところ、動作を停止してしまいます。再帰のどこかで無限ループが起きているのだと思いますが、その原因が見つかりません。
誰かおしえてくださると助かります。

コード:

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

typedef struct treenode{
  int data;
  int r;
  struct treenode *left;
  struct treenode *right;
  struct treenode *prev;
}treenode;

void print_tree(struct treenode *node){//二分木を左の部分木を優先し再帰で表示する
  if(node == NULL)
    return;
  if(node->left != NULL)
    print_tree(node->left);
  printf("%d\n",node->data);
  if(node->right != NULL)
    print_tree(node->right);
 
}

void add_tree(struct treenode *node, struct treenode *add){//与えられたノードを木の適切な位置に挿入する
  if(node == NULL){
  	if(add->r == 1){
  		(add->prev)->right = add;
  	}else{
  		(add->prev)->left = add;
  	}
  	return;
  }
  else if(node->data >= add->data){
  	add->r = 0;
  	add->prev = node;
    add_tree(node->left, add);
  }
  else{
  	add->r = 1;
  	add->prev = node;
    add_tree(node->right, add);
  }
}

int main(int argc, char **argv){
	struct treenode *tree = NULL;
	tree->left = NULL;
	tree->right = NULL;
	long max, n, i;
	long *num;
	FILE *inp;
	int c = 0;		
	if (argc != 2){
      printf("Usage: %s <ファイル名>\n", argv[0]);
      return 1;
    }

	inp = fopen(argv[1], "r");
	if (!inp)
    {
      printf("入力ファイルエラー\n");
      return 1;
    }

	fscanf(inp, "max %ld n %ld\n", &max, &n);

	num = malloc(sizeof(long) * n);
	
	while(fscanf(inp, "%ld\n", num+c) != EOF){
    c++;
	}
	fclose(inp);
	if(c == n){
  	tree->data = num[0];
    for(i = 1; i < n; i++){
      treenode *add = (treenode *)malloc(sizeof(treenode));
      add->data = num[i];
      add->right = NULL;
      add->left = NULL;
      add->prev = NULL;
      add->r = 0;
      add_tree(tree, add);
    }
    print_tree(tree);
    free(num);
  }
  else{
    printf("入力ファイルエラー\n");
  }
  return 0;
}

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

Re: 二分木を使ってソートを行うプログラムが動作を停止してしまいます

#2

投稿記事 by みけCAT » 9年前

FFF さんが書きました:

コード:

int main(int argc, char **argv){
	struct treenode *tree = NULL;
	tree->left = NULL;
	tree->right = NULL;
NULLをデリファレンスしてはいけません。
このコードは自殺に等しく、無限ループとか以前に論外ですね。
オフトピック
xv6などの特殊な環境なら0番地にアクセスしても死なないかもしれませんが、それはまた別のお話。
まあ、そもそもNULLのビットは全て0とは限らないし、NULLはどの関数やオブジェクトへのポインタとも等しくないと決まっているので、自殺以外で明示的にNULLをデリファレンスするのはよくないでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

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

Re: 二分木を使ってソートを行うプログラムが動作を停止してしまいます

#3

投稿記事 by みけCAT » 9年前

FFF さんが書きました:完成したプログラムを実行したところ、動作を停止してしまいます。再帰のどこかで無限ループが起きているのだと思いますが、その原因が見つかりません。
デバッガは使いましたか?
縛りプレイ、宗教上の理由、課題で禁止されている、使おうとするとパスワードを要求される、職場で使おうとすると「手抜き」とみなされて怒られる、などの使えない理由が無いのであれば、デバッガを使うといいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

box
記事: 2002
登録日時: 14年前

Re: 二分木を使ってソートを行うプログラムが動作を停止してしまいます

#4

投稿記事 by box » 9年前

みけCAT さんが書きました: 縛りプレイ、宗教上の理由、課題で禁止されている、使おうとするとパスワードを要求される、職場で使おうとすると「手抜き」とみなされて怒られる
何もそこまで言わんでも…。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

FFF
記事: 3
登録日時: 9年前

Re: 二分木を使ってソートを行うプログラムが動作を停止してしまいます

#5

投稿記事 by FFF » 9年前

解決しました。
何も指していないポインタの指す内容を参照しようなんておかしなことをしていたのが原因でした。
回答してくださった方ありがとうございました。

FFF
記事: 3
登録日時: 9年前

Re: 二分木を使ってソートを行うプログラムが動作を停止してしまいます

#6

投稿記事 by FFF » 9年前

解決ボタンをおすのを忘れてましたすいません

閉鎖

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