質問編集履歴

1 ソースコードの修正

thanatos

thanatos score 2

2017/05/14 17:53  投稿

2分木のデータの追加
###前提・実現したいこと
■概要
0~n-1のn個のデータを、ツリー構造としてリスト化
(リスト化の方法)
操作:
0<=r<=1として、①②の場合分けによって右の子を見るか、左の子を見るか判断する。
①確率rで左の子を見る
⑴左の子が空であれば、左の子に接点を作成しデータを挿入
⑵左の子が空でなければ、左の子を見る
②確率1-rで右の子を見る
⑴右の子が空であれば、右の子に節点を作成しデータを挿入
⑵右の子が空でなければ、右の子を見る
※根が空であれば、根に節点を作成し、データを挿入する
その後、
・リストアップ後ツリーの深さ(根から最も深い葉までの辺の数)
・処理時間
をprintf関数によって出力する
###発生している問題・エラーメッセージ
表出している問題としては、カウンタが適切に作動しないこと。
具体的に、出力が常に1となる。
分析したところ、insert_data関数が再帰的に呼び出されていないのではと考えています。
・仮に上記が原因であった場合、ソースコードのどこに問題があるのか。
・もしくは、他に原因がある場合それは何か。ソースコードのどこに問題があるのか。
を教授願います。
また、プログラミング初心者で、他にもコードとして不適切な部分が多々あるかと思います。その部分についても加えて指摘していただけるとありがたいです。(デバッグはすでに済ませております)
よろしくお願いいたします。
```ここに言語を入力
#include<stdio.h>
#include<stdlib.h>
#include<time.
#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を作成*/
              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;        /*node_leftを見て、空っぽであれば新しいnodeを代入する*/
               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)をあらかじめ生成*/
   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();              /*計測開始*/
   start = clock();              /*計測開始*/
   
   for(i=1;i<n;i++){
   
       t = insert_data(i,s,main_node);     /*データを次々に生成し、リストに挿入していく*/
       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言語
・現在独学で、アルゴリズム・データ構造について学んでおります。
  • C

    4831 questions

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

  • Xcode

    5162 questions

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

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る