Speicherzugriffsverletzung Struktur in Baumstruktur einfügen C++

Question

Ich versuche, einen Strukturbaum zu erstellen und meine Daten für die Baumknoten in die Struktur einzufügen, die zwei Datenbehälter enthält. Meine Baum/Datenstrukturen aussehen als solche:

class BinarySearchTree 
{ 
private: 

struct IndexEntry 
{ 
    int acctID; // (key) Account identifier 
    long recNum; // Record number 
}; 

struct tree_node 
{ 
    IndexEntry* entry; 
    tree_node* left; 
    tree_node* right; 
}; 
tree_node* root; 

public: 
BinarySearchTree() 
{ 
    root = NULL; 
} 

bool isEmpty() const { return root == NULL; } 
void insert(int, int); 
int search(int); 
int treeSearch(tree_node*, int); 
}; 

Ich bin an diesem Punkt in meiner Insert-Funktion eine Speicherzugriffsverletzung erhalten, und um ehrlich zu sein, ist dies das erste Mal ist, dass ich einen Baum von Strukturen versuchen, so Ich habe keine Ahnung, ob es überhaupt eine korrekte Insert-Funktion ist. Aber hier ist es:

void BinarySearchTree::insert(int rNum, int aNum) 
{ 
tree_node* t = new tree_node; 
tree_node* parent; 
t -> entry -> recNum = rNum; //right here I get a violation 
t -> entry -> acctID = aNum; //but if I remove the assignments 
t -> left = NULL;   //it gives me a violation further down 
t -> right = NULL; 
parent = NULL; 

if (isEmpty()) 
    root = t; 
else 
{ 
    tree_node* current; 
    current = root; 
    // Find the Node's parent 
    while (current) 
    { 
     parent = current; //This whole block will give me a memory violation 
     if (t -> entry -> recNum > current -> entry -> recNum) 
      current = current -> right; 
     else current = current -> left; 
    } 

    if (t -> entry -> recNum < parent -> entry -> recNum) 
     parent -> left = t; 
    else 
     parent -> right = t; 
} 
} 

Bitte beachten Sie meine Kommentare im zweiten Block des Codes für die Standorte der Speicherzugriffsverletzungen. Ich denke, es gibt etwas nicht initialisiertes innerhalb des Codes, aber ich weiß nicht wirklich, wo es sein würde oder wie es zu initialisieren ist.

Jede Hilfe oder Richtung würde geschätzt werden!

Answer 1

Du dereferencing nicht initialisiert Zeiger initialisieren. Wenn Sie dies tun:

dann Compiler wird Standardkonstruktor ausführen, die tatsächlich nichts tut. t->entry ist kein Wert zugewiesen und enthält Müll.

So später, wenn Sie dereferenzieren mit:

t -> entry -> recNum = rNum; //right here I get a violation 

(t -> entry -> ist dereferenzieren Betrieb), sind Sie nicht definiertes Verhalten, die in Ihrem Fall führt zu Absturz zu bekommen.

Die Lösung ist t -> entry vor der Dereferenzierung zu initialisieren.

Answer 2

müssen Sie t->entry

tree_node *t = new tree_node; 
t->entry = new IndexEntry; 

Answer 3

Der Zeiger entry in tree_node ist nicht richtig initialisiert, es ist ein Zeiger und es zeigt nicht auf ein gültiges Objekt. Sie können es im Konstruktor initialisieren, und vergessen Sie nicht, es im Destruktor zu löschen.

struct tree_node 
{ 
    IndexEntry *entry; 
    tree_node *left; 
    tree_node *right; 

    tree_node() : 
     entry(new IndexEntry), // create a new entry object 
     left(NULL), right(NULL) 
    {} 

    ~tree_node() 
    { 
     delete entry; // release the memory when we're done 
    } 
}; 

In der Tat sehe ich nicht, warum Sie IndexEntry auf der Halde in erster Linie erstellen müssen. Es scheint entry Teil tree_node ist, so können Sie einfach „einbetten“ es in tree_node:

struct tree_node 
{ 
    IndexEntry entry; // not a pointer, but an object 
    tree_node *left; 
    tree_node *right; 
}; 

Natürlich müssen Sie . verwenden, wenn die Mitglieder des entry Zugriff:

tree_node *t = new tree_node; 
t->entry.recNum = rNum; 
t->entry.acctID = aNum; 
t->left = NULL; 
t->right = NULL;