ランダムなサイズの三分木を作成するプログラムを書いています。つまり、各ノードにランダムに 0 ～ 3 個のブランチを追加し、ツリーの大きさを確認します。目標は、これを数千回実行してから、サイズ、直径、深さなどの統計を行うことです。
基本的なツリー構造を使用してから、ノード (0、1、2、3) を作成時に基づいて順序付けできるように、tab_of_order と呼ばれるポインターのポインターを使用します。
ただし、現在のコードはランダムにクラッシュします (おそらく 5 回に 1 回)。下部に、クラッシュがどのように見えるかの例を示します。ArbreAlea() は正常に動作しているように見えますが、戻り時にクラッシュします。理由もわかりません。クラッシュが止まるまで、おそらく 1000 件のループを実行することはできません。
また、ランダム ツリーを作成する関数の最初に、「警告: 互換性のないポインター型からの代入 [デフォルトで有効]」というポインター警告が表示されます。これにより、機能がクラッシュする可能性がありますか? それを修正する方法はありますか？
貼り付けていない 2 つの関数は、確率が変化する乱数 (0、1、2、3、4) を作成する関数です。
どんな助けでも大歓迎です！
#include<stdlib.h>
#include<stdio.h>
// Structure of the tree. Position is the value of the node. The nodes are
// numbered 1 to n thus the number gives it's position
struct tree_el {
int position;
struct tree_el * first, * second, * third, * fourth;
};
typedef struct tree_el myNode;
//Structure of the data to be analysed
struct donnees {
int nb_vertices;
int nb_feuilles;
int profondeur;
int largeur;
int diametre;
};
//Simplified queue structure
struct queue {
int debut;
int fin;
};
//initialize functions
int get_rnd_value (int min, int max);
int rand_loi1 (int iteration);
void add_node (int nb_node_to_add, myNode **tab_of_order, struct queue *arbreQ);
struct donnees * ArbreAlea (void);
int main(void)
{
srand((unsigned)time(NULL)); //seed random number generator
int nb_node=0;
struct donnees *resultat;
resultat=(struct donnees*)malloc(sizeof(struct donnees)*1);
resultat = ArbreAlea();
printf("\n\nNombre Vertices : %d \n",resultat->nb_vertices);
return 0;
}
void add_node(int nb_node_to_add, myNode **tab_of_order, struct queue *arbreQ){
int i;
int next = arbreQ->debut;
for (i=1; i <= nb_node_to_add; i++){
myNode *tmp_node;
tmp_node = (myNode*) malloc(sizeof(myNode)*1);
tmp_node->position = arbreQ->fin + i;
if(i==1){
tab_of_order[next]->first = tmp_node;
}
else if(i==2) {
tab_of_order[next]->second = tmp_node;
}
else if(i==3) {
tab_of_order[next]->third = tmp_node;
}
else if(i==4) {
tab_of_order[next]->fourth = tmp_node;
}
tab_of_order[tmp_node->position] = tmp_node;
//printf("Tab_of_order[ %d ] %d connected to node %d\n", next , i, tab_of_order[tmp_node->position]->position);
}
//printf("add to node %d, %d node(s) is/are added\n", next , nb_node_to_add);
arbreQ->fin = arbreQ->fin + nb_node_to_add;
arbreQ->debut +=1;
tab_of_order[arbreQ->fin + 1] = NULL;
//printf("\nDebut %d Fin %d\n",arbreQ->debut,arbreQ->fin);
return;
}
struct donnees * ArbreAlea (void) {
struct donnees *data;
//Here i get "warning: assignment from incompatible pointer type [enabled by default]"
data = (struct donnnes *)malloc(sizeof(struct donnees)*1);
struct queue *arbreQ;
arbreQ = (struct queue *)malloc(sizeof(struct queue)*1);
arbreQ->debut=0;
arbreQ->fin=0;
int nb_node = 0; //nb_node is the number total of nodes in tree.
int nb_node_to_add; // nb_node_to_add is how many nodes you have to add for each node.
// this table keeps track of the order of nodes to quickly look up where to add the next node.
myNode ** tab_of_order;
tab_of_order = (myNode **) malloc(sizeof(myNode*) * nb_node);
// First we make the begninning of the tree. This is the only time it can have 4 branches.
// There is a 1/4 chance of having a tree of size one.
myNode *tree;
tree = (myNode*) malloc(sizeof(myNode) * 1 ) ;
tree->position = 0;
tab_of_order[0] = tree;
//next = 0;
nb_node_to_add = rand_loi1(arbreQ->debut);
if (nb_node_to_add == 0){
data->nb_vertices=1;
data->nb_feuilles=0;
data->profondeur=0;
data->largeur=0;
data->diametre=0;
printf("\nZero Tree");
return(data);
}
else {
do {
nb_node_to_add=rand_loi1(arbreQ->debut);
printf("\nAdding %d nodes, debut %d, fin %d",nb_node_to_add,arbreQ->debut,arbreQ->fin);
if (nb_node_to_add==0)
arbreQ->debut += 1;
else if (nb_node_to_add>=1)
add_node(nb_node_to_add, tab_of_order, arbreQ);
nb_node = nb_node + nb_node_to_add;
if (tab_of_order[arbreQ->debut]==NULL)
printf("\n Next is null : %d",arbreQ->debut);
}while (tab_of_order[arbreQ->debut]!=NULL);
}
data->nb_vertices=nb_node+1;
data->profondeur=0;
data->largeur=0;
printf("\nTree debut %d fin %d nodes %d",arbreQ->debut,arbreQ->fin,nb_node+1);
return (data);
}