3分木の実装について

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

3分木の実装について

#1

投稿記事 by Ayumu.K » 1年前

コード:

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

typedef struct _node{
	int data;
	struct _node *left;
	struct _node *center;
	struct _node *right;
} NODE;

NODE *root;

void insert_data(int d, double t);

double GetRandom();

int height(NODE *c);

NODE *create_node(int d);

int main(void){

	int n,tall;
	
	for(n=0;n<100;n++){
		insert_data(1,0.1);
	}

	tall = height(root);

	return 0;

}

void insert_data(int d, double t){
	if(root==NULL){
		root = create_node(d);
	}else{
		NODE *p;
		p = root;
		int b = 0;
		while(b==0){
			srand(time(NULL));
			double r = GetRandom();
			if(r<t){
				if(p->left==NULL){
					p->left = create_node(d);
					b++;
				}else{
					p=p->left;
				}
			}
			if(r>(1-t)){
				if(p->right==NULL){
					p->right = create_node(d);
					b++;
				}else{
					p=p->right;
				}
			}if((r>=t)&&(r<=(1-t))){
				if(p->center==NULL){
					p->center = create_node(d);
					b++;
				}else{
					p=p->center;
				}
			}
		}
	}
}

double GetRandom(){
	return ((float)rand()/RAND_MAX);
}

int height(NODE *c){
	int d,e,f;
	if(c==NULL){
		return -1;
	}

	d=height(c->left);
	e=height(c->right);
	f=height(c->center);

	if((d>=e)&&(d>=f)){
		return d+1;
	}
	if((e>=d)&&(e>=f)){
		return e+1;
	}
	if((f>=d)&&(f>=e)){
		return f+1;
	}
}

NODE *create_node(int d) {
	NODE *p;
	p = (NODE *)malloc(sizeof(NODE));
	p->data = d;
	p->left = NULL;
	p->center = NULL;
	p->right = NULL;
	return p;
} 
質問です。
大学の課題で3分木を作り、高さを求めるコードを書きました。コンパイルは成功するものの、実行するとsegmentation fault (core dumped)と表示されます。どの部分がが悪いのかが分からず困っているので教えてください。

3分木の具体的な内容は、
「引数として与えられた整数データ d を 3 分木に挿入するための関数 void insert data(int d, double t)を作成せよ.但し,挿入処理に際して,以下の手順に従ってデータを挿入するものとする.なお,引数 t は,0 < t < 0.5 の値をとり,3 分木の左を見るか右を見るか真ん中を見るかを決定するための閾値として利用する(以下のステップ (3) を参照).

(1) 3 分木が空(すなわち,root が NULL)ならば,新たな節点を生成し,これにデータ d を代入するとともに,生成した節点のアドレスの値を root に代入して,処理を終える.

(2) 3 分木が空でないならば,根を注目節点として以降の処理を行う.すなわち,NODE へのポインタ型の変数p を用意して p に root の値を代入し,以下に進む.

(3) p(=注目節点)の左の子を見るか右の子を見るか真ん中の子を見るかについて,0 ∼ 1 の乱数 r を発生さ
せ,r < t であれば左の子を,r > 1 − t であれば右の子を,それ以外であれば真ん中の子を見るように決
定する.

(4) 上記で決定した子が空であれば(すなわち,子の位置に節点が存在しなければ),新たな節点を生成し,これにデータ d を代入するとともに,生成した節点を注目節点(p が指す節点)の子(左右真ん中のいずれであるかはステップ (3) で決定済)の位置にぶら下げ,処理を終える.

(5) (3) で決定した位置に子が存在すれば,その子を新たな注目節点とし(すなわち,p にその子のアドレスを代入し),ステップ (3) に戻る.」
です。

長くなってしまい申し訳ないです。プログラミングは得意ではないです。回答お待ちしております。

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

Re: 3分木の実装について

#2

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

こちらではSegmentation Faultを再現できませんでした。
・コンパイルや実行をしているのが本当にこのコードかを確認してください。
 ・最新のコードを保存しましたか?
 ・作業ディレクトリは正しいですか?
 ・最新のコードをコンパイルしましたか?
・デバッガやprintfデバッグなどで、具体的にどこで落ちているかを確認してください。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

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

Re: 3分木の実装について

#3

投稿記事 by box » 1年前

えっと、こっちでもsegmentation faultは起きませんでした。
気になることといえば、

コード:

    tall = height(root);
なぜこの値を確認しようとしていないのか。

コード:

        srand(time(NULL));
乱数の種を初期化する場所は本当にここでいいのか。
本来、そういうことはmain()の「先頭で1回だけ」すればいいんじゃないのか。

コード:

double GetRandom(){
    return ((float)rand()/RAND_MAX);
何で型が微妙に異なっているのか。どうせならdoubleに統一する方がいいんじゃないのか。

コード:

    p = (NODE *)malloc(sizeof(NODE));
事実上全くといっていいほど起きないが、もし万が一仮に
mallocに失敗したときの処理は本当に不要なのか。
くらいですかね。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

Ayumu.K

Re: 3分木の実装について

#4

投稿記事 by Ayumu.K » 1年前

改めて実行したところ、何も出力されずに終了してしまいました。
insert_data()関数に問題があるようなんですが改善策が分かりませんでした。

Ayumu.K

Re: 3分木の実装について

#5

投稿記事 by Ayumu.K » 1年前

すみません。tallをprintfで表示するのを忘れていました。
実行したところ高さがずっと0になってしまいます…

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

Re: 3分木の実装について

#6

投稿記事 by box » 1年前

こちらの環境で下記のコードを実行してみる(20回以上)と、
12~16のいずれかの値を出力します。
想定どおりかどうかはわかりません。

コード:

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

typedef struct _node{
    int data;
    struct _node *left;
    struct _node *center;
    struct _node *right;
} NODE;

NODE *root;

void insert_data(int d, double t);
double GetRandom(void);
int height(NODE *c);
NODE *create_node(int d);

int main(void)
{
    int n;

    srand(time(NULL));
    for (n = 0; n < 100; n++) {
        insert_data(1, 0.1);
    }
    printf("%d\n", height(root));
    return 0;
}

void insert_data(int d, double t)
{
    if (root == NULL) {
        root = create_node(d);
    } else {
        NODE *p = root;
        int b = 0;

        while (b == 0) {
            double r = GetRandom();

            if (r < t) {
                if (p->left == NULL) {
                    p->left = create_node(d);
                    b++;
                } else{
                    p = p->left;
                }
            }
            if (r > 1 - t) {
                if (p->right == NULL) {
                    p->right = create_node(d);
                    b++;
                } else {
                    p = p->right;
                }
            }
            if (r >= t && r <= 1 - t) {
                if (p->center == NULL) {
                    p->center = create_node(d);
                    b++;
                } else {
                    p = p->center;
                }
            }
        }
    }
}

double GetRandom(void)
{
    return ((double) rand() / RAND_MAX);
}

int height(NODE *c)
{
    int d, e, f;

    if (c == NULL) {
        return -1;
    }
    d = height(c->left);
    e = height(c->right);
    f = height(c->center);
    if (d >= e && d >= f) {
        return d + 1;
    }
    if (e >= d && e >= f) {
        return e + 1;
    }
    if (f >= d && f >= e) {
        return f + 1;
    }
}

NODE *create_node(int d){
    NODE *p = (NODE *) malloc(sizeof(NODE));

    if (!p) {
        fprintf(stderr, "malloc error\n");
        exit(EXIT_FAILURE);
    }
    p->data = d;
    p->left = NULL;
    p->center = NULL;
    p->right = NULL;
    return p;
}
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

Ayumu.K

Re: 3分木の実装について

#7

投稿記事 by Ayumu.K » 1年前

ありがとうございます。
自分が単純に多くの凡ミスをしていることに気づきました。
期待通りに動きました。

返信

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