thanatos score 2
2017/05/14 17:53 投稿
| 2分木のデータの追加 |
| ###前提・実現したいこと |
| ■概要 |
| 0~n-1のn個のデータを、ツリー構造としてリスト化 |
| （リスト化の方法） |
| 操作： |
| 0<=r<=1として、①②の場合分けによって右の子を見るか、左の子を見るか判断する。 |
| ①確率rで左の子を見る |
| ⑴左の子が空であれば、左の子に接点を作成しデータを挿入 |
| ⑵左の子が空でなければ、左の子を見る |
| ②確率1-rで右の子を見る |
| ⑴右の子が空であれば、右の子に節点を作成しデータを挿入 |
| ⑵右の子が空でなければ、右の子を見る |
| ※根が空であれば、根に節点を作成し、データを挿入する |
| その後、 |
| ・リストアップ後ツリーの深さ(根から最も深い葉までの辺の数） |
| ・処理時間 |
| をprintf関数によって出力する |
| ###発生している問題・エラーメッセージ |
| 表出している問題としては、カウンタが適切に作動しないこと。 |
| 具体的に、出力が常に１となる。 |
| 分析したところ、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 = p; /*node_leftを見て、空っぽであれば新しいnodeを作成*/ |
| } |
| else{ |
| insert_data(d,r,node->left); |
| } |
| } |
| else if(r<k+1){ |
| if(node->right==NULL){ |
| node->right = p; |
| 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; |
| 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); /*１〜１００の数字を作る→作成した乱数と比較する*/ |
| 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言語 |
| ・現在独学で、アルゴリズム・データ構造について学んでおります。 |
