Почему мой двоичный поиск перегрузил оператор присваивания перемещений неправильно, основываясь на моем коде? - PullRequest
Новая
       18

Почему мой двоичный поиск перегрузил оператор присваивания перемещений неправильно, основываясь на моем коде?

0 голосов
/ 18 ноября 2018

перегруженный оператор присваивания BST.cpp: 

BST& BST::operator=(BST&& otherBST) {
    if (this != &otherBST) {
        if (root) {
            stack <Node*> nodeStack;
            nodeStack.push(root);

            Node *currentNode = nullptr;
            while (!nodeStack.empty()) {
                currentNode = nodeStack.top();
                nodeStack.pop();

                if (currentNode->rlink) {
                    nodeStack.push(currentNode->rlink);
                }
                if (currentNode->llink) {
                    nodeStack.push(currentNode->llink);
                }

                delete currentNode;
                currentNode = nullptr;
            }
            cout << root << endl; // This is where it seems like root is not being deleted correctly/nullptr'd.
        }

        root = move(otherBST.root);
        otherBST.root = nullptr;
    }
    else {
        cerr << "ERROR: Cannot assign to self." << endl;
    }

    return *this;
}

Посмотрите на часть cout << root << endl, которую я прокомментировал. Когда этот фрагмент кода запускается, он печатает адрес, отличный от 00000000. Не похоже, что они удаляются правильно. </p>

Это код, в котором BST вызывающего объекта удаляется (все ветви), а затем крадет дерево другого BST. Оператор назначения перемещения. Но почему он не печатает nullptr, а вместо этого печатает другой адрес? Не похоже, что он удаляется правильно.

Вот для справки:

Это скриншот запуска тестового драйвера: Нажмите здесь, чтобы увидеть.

main.cpp 

#include <iostream>
#include "Test.h"
using namespace std;

int main()
{
    runTest();

    cout << endl << endl;
    system("Pause");
    return 0;
}

test.h 

#include "BST.h"

void runTest() {
    cout << "--------------------------------------------------------------------" << endl;
    cout << "Binary Search Tree Test Driver" << endl;
    cout << "--------------------------------------------------------------------" << endl;
    // Initialization:
    BST bst1;
    // Traversal when there are no elements in the tree:
    cout << "BST traversal when there are no elements within the tree (bst1): " << endl;
    bst1.preorderTraversal();
    cout << endl;
    cout << "BST, inserting one element into the tree recursively and non-recursively (bst1): " << endl;
    bst1.insert(21);
    bst1.preorderTraversal();
    cout << endl;
    bst1.insert(69);
    bst1.preorderTraversal();
    cout << endl;
    cout << "BST, inserting duplicate elements into the tree recursively (bst1): " << endl;
    bst1.insert(32);
    bst1.insert(32);
    bst1.preorderTraversal();
    cout << endl;
    cout << "BST using the function destroyTree (bst1): " << endl;
    bst1.destroyTree();
    bst1.preorderTraversal();
    cout << endl;
    cout << "BST copy constructor by copy constructing bst1 (bst2): " << endl;
    bst1.insert(21);
    bst1.insert(69);
    BST bst2(bst1);
    bst2.preorderTraversal();
    cout << endl;
    cout << "BST move constructor by move constructing bst1 (bst3): " << endl;
    BST bst3 = move(bst1);
    bst3.preorderTraversal();
    cout << endl;
    cout << "BST move assignment operator by move assigning bst2 (bst1) when bst1 has no elements in its tree: " << endl;
    bst1.destroyTree();
    bst1 = move(bst2);
    bst1.preorderTraversal();
    cout << endl;
    bst1.destroyTree();
    bst2.destroyTree();
    cout << "BST move assignment operator by move assigning bst2 (bst1) when bst1 already has some elements in its tree: " << endl;
    bst1.insert(21);
    bst1.insert(105);
    bst1.insert(18);
    bst1.insert(16);
    bst1.insert(7);
    bst1.insert(19);
    bst1.insert(109);
    bst1.insert(125);
    bst1.insert(101);
    bst2.insert(691);
    bst1 = move(bst2);
    bst1.preorderTraversal();
    cout << endl;
}

BST.h 

#ifndef BST_H
#define BST_H

#include <string>       
#include <iostream>
#include <stack>

using namespace std;

class Node
{
    friend class BST;
public:
    Node() : data(0), rlink(nullptr), llink(nullptr) {}
    ~Node() {}
private:
    int data;
    Node *rlink, *llink;
};

class BST
{
public:
    BST();

    BST(const BST& otherBST); 

    BST(BST&& otherBST); 

    void insert(int item);

    void insertNonRecursive(int item);

    void preorderTraversal() const;

    // BST& operator=(const BST& otherBST); 

    BST& operator=(BST&& otherBST); 

    void destroyTree();

    ~BST();

private:
    Node * root; // Pointer to the root.

    void copyConstructor(const Node *p);

    void insert(Node* &p, Node *newNode);

    void preorderTraversal(const Node *p) const;

    void destroyTree(Node *&p);
};

#endif

BST.cpp 

#include "BST.h"

BST::BST() : root(nullptr) {}

BST::BST(const BST& otherBST) {
    copyConstructor(otherBST.root);
}

BST::BST(BST&& otherBST) {
    root = move(otherBST.root);

    otherBST.root = nullptr;
}

void BST::copyConstructor(const Node *p) {
    if (p != nullptr) {
        insert(p->data);
        copyConstructor(p->llink);
        copyConstructor(p->rlink);
    }
}


void BST::insert(int insertItem)
{
    Node  *newNode = new Node;
    newNode->data = insertItem;
    insert(root, newNode);
}

void BST::insert(Node* &p, Node *newNode)
{
    if (p == nullptr)
        p = newNode;
    else if (p->data > newNode->data)
        insert(p->llink, newNode);
    else
        insert(p->rlink, newNode);
}

void BST::insertNonRecursive(int item) {
    if (root == nullptr) {
        root = new Node();
        root->data = item;
    }
    else {
        Node *current = root;
        bool searching = true;

        while (searching) {
            if (item > current->data && current->rlink != nullptr) {
                current = current->rlink;
            }
            else if (item < current->data && current->llink != nullptr) {
                current = current->llink;
            }
            else if (item == current->data) {
                cerr << "The item to insert is already in the list, duplicates are not allowed." << endl;
                searching = false;
            }
            else {
                if (item > current->data) {
                    current->rlink = new Node();
                    current->rlink->data = item;
                }
                else {
                    current->llink = new Node();
                    current->llink->data = item;
                }

                searching = false;
            }
        }
    }
}

void BST::preorderTraversal() const {
    if (root == nullptr)
        cerr << "There is no tree.";
    else
    {
        preorderTraversal(root);
    }
}

void BST::preorderTraversal(const Node *p) const {
    if (p != nullptr) {
        cout << p->data << " ";
        preorderTraversal(p->llink);
        preorderTraversal(p->rlink);
    }
}

BST& BST::operator=(BST&& otherBST) {
    if (this != &otherBST) {
        if (root) {
            stack <Node*> nodeStack;
            nodeStack.push(root);

            Node *currentNode = nullptr;
            while (!nodeStack.empty()) {
                currentNode = nodeStack.top();
                nodeStack.pop();

                if (currentNode->rlink) {
                    nodeStack.push(currentNode->rlink);
                }
                if (currentNode->llink) {
                    nodeStack.push(currentNode->llink);
                }

                delete currentNode;
                currentNode = nullptr;
            }
            cout << root << endl; // This is where it seems like root is not being deleted correctly/nullptr'd.
        }

        root = move(otherBST.root);
        otherBST.root = nullptr;
    }
    else {
        cerr << "ERROR: Cannot assign to self." << endl;
    }

    return *this;
}

void BST::destroyTree(Node* &p)
{
    if (p != nullptr)
    {
        destroyTree(p->llink);
        destroyTree(p->rlink);
        delete p;
        p = nullptr;
    }
}

void  BST::destroyTree()
{
    destroyTree(root);
}

BST::~BST()
{
    destroyTree(root);
}

1 Ответ

0 голосов
/ 18 ноября 2018

Я думаю, что линия, которую вы упомянули, просто в порядке и ничего не пропускает.Просто указатель не присваивается NULL.Вы, вероятно, ожидаете, что pA будет NULL в приведенном ниже примере 

int *pA = new int;
int *pB = pA;
delete pB;
pB=NULL;

printf("pA=0x%p, pB=0x%p", pA,pAB);

Обратите внимание, что хотя pA указывает на что-то, что является висящим указателем, утечки нет.

Чтобы получить желаемоеПоведение, вы можете установить корень в NULL после того, как вы закончите вставку в стек.

...