Klassenmitgliedsfunktion funktioniert normal, aber bleibt in einer Endlosschleife stecken, wenn sie als Datenelement einer anderen Klasse aufgerufen wird

Question

Ich schrieb eine Baumstruktur und machte eine einfache Suchfunktion, um nach Knoten im Baum zu suchen. Der Baum selbst verwendet einen Sentinel-Knoten, um alle Enden zu markieren (Eltern der Wurzel, Kind der Blätter), und die Suche iteriert einfach durch die Knoten, bis sie entweder eine Übereinstimmung findet oder den Sentinel-Knoten trifft. Die Suchfunktion funktioniert einwandfrei, wenn ich sie für eine Instanz eines Baumes aufruft, sie bleibt jedoch hängen, wenn der Baum ein Datenelement einer anderen Klasse ist. Im folgenden Code funktioniert "t.search (1)", aber "embedded_tree.t.search (1)" bleibt in einer Endlosschleife stecken.

Ich habe es auf die Tatsache eingegrenzt, dass, wenn der Aufruf von embedded_tree.t.search() gemacht wird, der Inhalt von "& sentinel" korrekt auf den Sentinel-Knoten zeigt, aber ein neuer Zeiger zu sein scheint, als Es entspricht nicht den Inhalten von root, sentinel.parent und sentinel.child. Von hier aus bin ich fest und bin mir nicht sicher, wie ich es nennen soll, so dass & Sentinel mit den Zeigern übereinstimmt, die erstellt wurden, als der Baum erstellt wurde.

#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

Sie verwechseln dynamische Speicherzuordnung mit Stapelzuordnung. Wenn Sie tun

sentinel = *new NODE 

schlimme Dinge passieren. Speicher wird für NODE sentinel auf dem Stapel zugeordnet, dann für NODE in new-Operator, dann wird Zuweisung zu sentinel Variable vorgenommen, und Speicher erstellt in new Operator ist verloren. Sie sollten Ihren Code neu schreiben Zeiger zu verwenden, anstatt, und Destruktoren hinzufügen, so etwas wie dieses

#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); 
} 

Da aber wir reden über C++, würde ich Ihnen vorschlagen, intelligente Zeiger und Container zu suchen, nachdem Sie vertraut mit manueller Speicherverwaltung.