La fonction de membre de classe fonctionne normalement, mais reste bloquée dans une boucle infinie lorsqu'elle est appelée comme membre d'une autre classe

Question

J'ai écrit une structure arborescente et ai fait une recherche de base pour rechercher des nœuds dans l'arborescence. L'arbre lui-même utilise un nœud sentinelle pour marquer toutes les extrémités (parent de la racine, enfant des feuilles), et la recherche parcourt simplement les nœuds jusqu'à ce qu'il trouve une correspondance ou touche le nœud sentinelle. La fonction de recherche fonctionne correctement lorsque je l'appelle sur une instance d'une arborescence, mais elle reste bloquée lorsque l'arborescence est membre d'une autre classe. Dans le code suivant, "t.search (1)" fonctionne, mais "embedded_tree.t.search (1)" est bloqué dans une boucle infinie.

Je l'ai réduit au fait que lorsque l'appel à embedded_tree.t.search() est fait, le contenu de "& sentinel" pointe correctement vers le noeud sentinelle, mais semble être un nouveau pointeur, comme ce n'est pas équivalent au contenu de root, sentinel.parent et sentinel.child. De là, je suis coincé et je ne sais pas comment l'appeler afin que & sentinel correspond aux pointeurs qui ont été créés lors de la construction de l'arbre.

#include <iostream> 

struct NODE { 
    int key; 
    NODE* parent; 
    NODE* child; 
    NODE() : key(0), parent(NULL), child(NULL) {}; 
}; 

struct TREE { 
    NODE sentinel; 
    NODE* root; 

    TREE() 
    { 
     sentinel = *new NODE; 
     sentinel.parent = &sentinel; 
     sentinel.child = &sentinel; 
     root = &sentinel; 
    } 

    NODE* search(int k) 
    { 
     NODE* x = root; 
     while (x != &sentinel) 
     { 
      if (x->key == k) return x; 
      x = x->child; 
     } 
     return &sentinel; 
    } 
}; 

struct A { 
    TREE t; 

    A() : t(*new TREE()) {}; 
}; 

int main() 
{ 
    TREE t; 
    t.search(1); 

    A embedded_tree; 
    embedded_tree.t.search(1); 
} 

Answer 1

Vous confondez l'allocation de mémoire dynamique avec l'allocation de pile. Quand vous faites

sentinel = *new NODE 

mauvaises choses se produisent. La mémoire est allouée pour NODE sentinel sur la pile, puis pour NODE dans l'opérateur new, puis l'affectation est effectuée à la variable sentinel et la mémoire créée dans l'opérateur new est perdue. Vous devez réécrire votre code pour utiliser des pointeurs au lieu et ajouter Destructeurs, quelque chose comme ça

#include <iostream> 

struct NODE { 
    int key; 
    NODE* parent; 
    NODE* child; 
    NODE() : key(0), parent(NULL), child(NULL) {}; 
}; 

struct TREE { 
    NODE* sentinel; 
    NODE* root; 

    TREE() 
    { 
     sentinel = new NODE; 
     sentinel->parent = sentinel; 
     sentinel->child = sentinel; 
     root = sentinel; 
    } 

    ~TREE() { 
     if (NULL != sentinel) { 
      delete sentinel; 
      sentinel = NULL; 
      root = NULL; 
     } 
    } 

    NODE* search(int k) 
    { 
     NODE* x = root; 
     while (x != sentinel) 
     { 
      if (x->key == k) return x; 
      x = x->child; 
     } 
     return sentinel; 
    } 


}; 

struct A { 
    TREE* t; 

    A() : t(new TREE()) {}; 
    ~A() { 
     if (NULL != t) { 
      delete t; 
      t = NULL; 
     } 

    } 
}; 

int main() 
{ 
    TREE t; 
    t.search(1); 

    A embedded_tree; 
    embedded_tree.t->search(1); 
} 

Cependant, puisque nous parlons de C++, je vous suggère de regarder des pointeurs intelligents et les conteneurs après que vous vous familiariser avec gestion manuelle de la mémoire.