質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.45%

  • Xcode

    5058questions

    Xcodeはソフトウェア開発のための、Appleの統合開発環境です。Mac OSXに付随するかたちで配布されています。

  • C

    4680questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

2分木のデータの追加

受付中

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 552

thanatos

score 2

前提・実現したいこと

■概要
0~n-1のn個のデータを、ツリー構造としてリスト化
(リスト化の方法)

操作:
0<=r<=1として、①②の場合分けによって右の子を見るか、左の子を見るか判断する。
①確率rで左の子を見る
⑴左の子が空であれば、左の子に接点を作成しデータを挿入
⑵左の子が空でなければ、左の子を見る
②確率1-rで右の子を見る
⑴右の子が空であれば、右の子に節点を作成しデータを挿入
⑵右の子が空でなければ、右の子を見る

※根が空であれば、根に節点を作成し、データを挿入する

その後、
・リストアップ後ツリーの深さ(根から最も深い葉までの辺の数)
・処理時間
をprintf関数によって出力する

発生している問題・エラーメッセージ

表出している問題としては、カウンタが適切に作動しないこと。
具体的に、出力が常に1となる。

分析したところ、insert_data関数が再帰的に呼び出されていないのではと考えています。

・仮に上記が原因であった場合、ソースコードのどこに問題があるのか。
・もしくは、他に原因がある場合それは何か。ソースコードのどこに問題があるのか。
を教授願います。

また、プログラミング初心者で、他にもコードとして不適切な部分が多々あるかと思います。その部分についても加えて指摘していただけるとありがたいです。(デバッグはすでに済ませております)

よろしくお願いいたします。

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

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

int insert_data(int d,int r,NODE *node){       /*d:データ,r:設定する確率,node:注目節点*/
    int count = 0;
    int k;
    NODE *newnode,*p;

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

    p -> left = NULL;
    p -> right = NULL;
    p -> data = d;                         /*新しいノードの生成と定義*/

        srand(time(NULL));
        k = rand() % 100;

        if(k<r){
            if(node->left==NULL){
               node->left = p;        /*node_leftを見て、空っぽであれば新しいnodeを作成*/
            }
            else{
              insert_data(d,r,node->left);
            }
        }

        else if(r<k+1){
            if(node->right==NULL){
                node->right = p;
            }
            else if(node->right!=NULL){
               insert_data(d,r,node->right);
            }
        }

    count++;

    return count;

}

int main(void){

    NODE *main_node;
    main_node->left=NULL;
    main_node->right=NULL;
    main_node->data=0;      /*リストの根(root)をあらかじめ生成*/

    int i=1, n;
    int main_count=1;
    int s,t;
    clock_t start,end;
    double req_time;

    printf("nの値は:\n");
    scanf("%d",&n);
    printf("sの値は?\n");
    scanf("%d",&s);                         /*1〜100の数字を作る→作成した乱数と比較する*/

    start = clock();                /*計測開始*/

    for(i=1;i<n;i++){

        t = insert_data(i,s,main_node);        /*データを次々に生成し、リストに挿入していく*/

        if(main_count<t){
            main_count = t;        /*最も深いところまで行っていたら(カウンタの数が現状で最大であれば)main_countに代入*/
        }
    }

    end = clock();                            /*計測終了*/

    req_time=(double)(end-start)/CLOCKS_PER_SEC;
    printf("処理に%.6f秒かかりました。\n",req_time);
    printf("木の深さは:%d\n",main_count);

    return 0;

}

試したこと

誤っているのではと考える部分としては、
・ノードの作成方法(malloc関数の使用法)
・そもそもリストが上記概要の条件に沿って、適切に作成されていない
と考えています。

補足情報(言語/FW/ツール等のバージョンなど)

・言語:C言語
・現在独学で、アルゴリズム・データ構造について学んでおります。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+3

プログラミングとはコードを書いて、動かして、意図した動作でない場合は「デバッグする」ことです。これらはワンセットになっているものです。コードを書いてデバッグしないならそれはプログラミングの半分しかしていないことになります。

デバッグはすでに済ませております

プログラムが正しく動かないうちはデバッグが済んでいるといういいかたはしません。

ご質問には「自分のコードを眺めて、どこがおかしいのかを推測した」意見は書かれています。それも机上デバッグというものなので「デバッグ」の一種ではあるのですが、机上デバッグだけでプログラムの誤りを全て見つけることは(ベテランのプログラマーなら可能かも知れませんが)初心者の場合は相当困難です。プログラミングの知識が不足しているからです。

それなりの経験を積んだプログラマーであっても、計算機で実際に動かしながらプログラムの動作や途中のデータを調べつつ、判明した事実に基づいて誤りを推測していかないと、なかなかバグを見つけられないことが多いです。

計算機を動かしてデバッグしてもなかなか原因がつかめないこともあるでしょう。そういうときは「これこれのデバッグをして、この行を実行した際にこの変数の値はこうなっていた」というような自分のデバッグ結果とともに質問してください。そうすれば「どういうふうにすれば答えに結び付くか」のアドバイスが得られやすくなります。


一つだけ計算機を動かしても見つけるのが困難な間違い(バグ)を指摘します。mallocで確保した領域は「使っている間はfreeしてはいけません」。free(newnode)の後でp->leftなどでmallocで確保した領域そのものにアクセスしています。アクセスする可能性があるならその領域は使っていることになります。よってfreeしてはいけません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

問題点は多々ありそうですが、パッと見ておかしいところを3点。

  1. mallocしたあとすぐにfreeしている
  2. count変数がinsert_data関数のローカル変数なので、単に1プラスして返却しているだけ
  3. insert_data関数内でinsert_data関数を再帰呼び出しているが、戻り値を受け取っていない

1は動的メモリの理解不足です。
2と3は、再帰呼び出しの理解不足です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

具体的に、出力が常に1となる

ちゃんとロジックは理解できていませんが、insert_data()はリカーシブルコールされていますので
呼ばれる毎にインスタンスが作成されcountに0が設定され、戻る際には+1されて戻り値となります。
ですので1となります。
これを避けるには、insert_data()にパラメータとして渡すか、グローバル変数とする方法が考え
られます。

また、mainのNODE *main_node;は、
NODE *main_node = (NODE *)malloc(sizeof(NODE));とされた方がよろしいかと。

似て非なるソースですが

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

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

int count;

int insert_data(int d, int r, NODE *node){       /*d:データ,r:設定する確率,node:注目節点*/
    int k;
        NODE *p;

    k = rand() % 100;

    if(k<r){
        if(node->left==NULL){
            p = (NODE *)malloc(sizeof(NODE));
            node->left = p;        /*node_leftを見て、空っぽであれば新しいnodeを作成*/
            p->left  = NULL;
            p->right = NULL;
            p->data  = d;
        }else{
           insert_data(d,r,node->left);
        }
    } else if(r<k+1){
        if(node->right==NULL){
            p = (NODE *)malloc(sizeof(NODE));
            node->right = p;
            p->left  = NULL;
            p->right = NULL;
            p->data  = d;
        }else{
            insert_data(d,r,node->right);
        }
    }

    count++;
    return count;

}

int print_data(NODE *node){
    count++;
    if(node->left  != NULL) print_data(node->left);
    if(node->right != NULL) print_data(node->right);
    printf("no.%d (%d)\n",node->data, count);
    count--;
}

int main(void){

    NODE *main_node = (NODE *)malloc(sizeof(NODE));
    main_node->left=NULL;
    main_node->right=NULL;
    main_node->data=0;      /*リストの根(root)をあらかじめ生成*/

    int i=1, n;
    int main_count=1;
    int s,t;
    clock_t start,end;
    double req_time;

    printf("nの値は:\n");
    scanf("%d",&n);
    printf("sの値は?\n");
    scanf("%d",&s);                         /*1〜100の数字を作る→作成した乱数と比較する*/

    start = clock();                /*計測開始*/

    for(i=1;i<n;i++){

        count = 1;
        insert_data(i,s,main_node);        /*データを次々に生成し、リストに挿入していく*/
        printf("c:%d\n",count);

        if(main_count<count){
            main_count = count;  /*最も深いところまで行っていたら(カウンタの数が現状で最大であれば)main_countに代入*/
        }
    }

    end = clock();                            /*計測終了*/

    req_time=(double)(end-start)/CLOCKS_PER_SEC;
    printf("処理に%.8f秒かかりました。\n",req_time);
    printf("木の深さは:%d\n",main_count);

    count = 0;
    print_data(main_node);

    return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.45%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • Xcode

    5058questions

    Xcodeはソフトウェア開発のための、Appleの統合開発環境です。Mac OSXに付随するかたちで配布されています。

  • C

    4680questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。