Segmentation nœuds d'arbre de copie de défaut dans un tableau

Question

j'utilise cette structure pour mon arbre:

typedef struct product{ 
     char name[50]; 
     char id[5]; 
     double price; 
     int amount; 
     struct product *left_p, *right_p; 
    }product_t; 

Alors, je dois convertir l'arbre dans un tableau. J'ai écrit cela pour la dimension de l'arbre:

int tree_dim(product_t *node_p){ 
    int i = 1 ; 
    if (node_p == NULL) 
     i = 0; 
    else{ 
     i += tree_dim(node_p->left_p); 
     i += tree_dim(node_p->right_p); 
    } 
    return i; 
} 

Mon arbre est peuplé en lisant les enregistrements d'un fichier txt. Les enregistrements sont 21 et la valeur retournée par tree_dim est correcte. La valeur est stockée dans arr_dim.

Puis-je créer un product_t *products_a; Wich sera le « tableau » et affecter en mémoire à l'aide products_a = malloc (arr_dim*sizeof (product_t));

Maintenant, c'est la fonction de remplir le tableau avec les nœuds d'arbres:

void fill_array(int *index, product_t *node_p, product_t *products_a){ 

    if (node_p != NULL){ 
     fill_array(index, node_p->left_p, products_a); 
     products_a[*index++] = *node_p; 
     fill_array(index, node_p->right_p, products_a); 

    } 
} 

Mais ça me donne une erreur de segmentation donc j'ai aussi essayé cette 2ème solution:

int fill_array(product_t *node_p, product_t *products_a){ 

    int i = 1 ; 
    if (node_p == NULL){ 
     i=0; 
    } 
    else 
    { 
     i += fill_array(node_p->left_p, products_a); 
     products_a[i-1] = *node_p; 
     i += fill_array(node_p->right_p, products_a); 

    } 
    return i; 
} 

Ce qui ne donne pas de défaut de segmentation mais quand je pr Dans le tableau, il y a des positions vides. J'ai besoin de conseils pour savoir où je me trompe. Peut-être un problème avec l'index et les appels récursifs mais je ne peux pas le comprendre.

Answer 1

Regardez le precedence de ces deux opérateurs

*index++ 

++ Incrémentation a une priorité supérieure * déréférencer droit? Par conséquent, si vous vous déplacez en mémoire pour la première fois par sizeof(int), vous ne pourrez plus utiliser la mémoire qui vous est allouée et le déréférencement entraînera UB.

Il est toujours préférable d'utiliser les parenthèses () si vous n'êtes pas sûr de la précédence.

(*index)++ // This is right 

Answer 2

Filip a déjà signalé le problème avec votre première fonction.

Le problème avec votre deuxième fonction est que cela ne fonctionne que lorsque vous remplissez à partir de la branche gauche. Après avoir fait cela et copié le produit actuel, il y a quelques éléments dans le tableau, mais la copie à partir de la bonne branche recommencera à l'index 0, donc elle écrasera les données existantes et laissera les données à la fin non initialisées.

Vous pouvez résoudre ce problème en passant l'index actuel i à votre fonction, mais je trouve la syntaxe i = func(..., i); un peu redondante.

En C, vous pouvez passer dans un sous-tableau de array à partir de l'élément i avec &array[i] ou simplement array + i. (Rappelez-vous qu'un tableau dans un appel de fonction « désintègre » en un pointeur vers le premier élément, &array[0].)

donc ça marchera:

int fill_array(product_t *node_p, product_t *products_a) 
{   
    int i = 0; 

    if (node_p == NULL) return 0; 

    i += fill_array(node_p->left_p, products_a); 
    products_a[i++] = *node_p; 
    i += fill_array(node_p->right_p, &products_a[i]); 

    return i; 
}