プログラマ専用SNS ミクプラ

コード:

#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)と表示されます。どの部分がが悪いのかが分からず困っているので教えてください。

３分木の具体的な内容は、
「引数として与えられた整数データ 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) に戻る．」
です。

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

こちらではSegmentation Faultを再現できませんでした。
・コンパイルや実行をしているのが本当にこのコードかを確認してください。
　・最新のコードを保存しましたか？
　・作業ディレクトリは正しいですか？
　・最新のコードをコンパイルしましたか？
・デバッガやprintfデバッグなどで、具体的にどこで落ちているかを確認してください。

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

コード:

    tall = height(root);

なぜこの値を確認しようとしていないのか。

コード:

        srand(time(NULL));

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

コード:

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

何で型が微妙に異なっているのか。どうせならdoubleに統一する方がいいんじゃないのか。

コード:

    p = (NODE *)malloc(sizeof(NODE));

事実上全くといっていいほど起きないが、もし万が一仮に
mallocに失敗したときの処理は本当に不要なのか。
くらいですかね。

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

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

こちらの環境で下記のコードを実行してみる（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;
}

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

プログラマ専用SNS ミクプラ

3分木の実装について

3分木の実装について

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

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

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

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

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

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