Указатель члена перезаписывается при возврате функции? - PullRequest
Новая
       15

Указатель члена перезаписывается при возврате функции?

1 голос
/ 14 февраля 2012

Я практиковал свой C ++, так как он стал немного ржавым после колледжа, и у меня странная проблема, когда значение члена перезаписывается, как только моя функция возвращается. 

template <class T>
class BstNode
{
    public:
        T value;
        BstNode<T>* left;
        BstNode<T>* right;
        BstNode<T>* parent;

        BstNode()
        { left = right = parent = NULL; }
        BstNode(T value)
        { this->value=value; left=right=parent=NULL;}
        BstNode(T value, BstNode<T>* parent)
        { this->value=value; this->parent=parent; left=right=NULL;}
};

template <class T>
class BinarySearchTree 
{
    protected:
        BstNode<T>* root;

        void removeNode(BstNode<T>* node);
        void addChild(T value, BstNode<T>* node);
        BstNode<T>* find(T value, BstNode<T>* node);
    public:
        BinarySearchTree()
        { root = NULL; }
        ~BinarySearchTree()
        { removeNode(root); }

        BinarySearchTree<T> insert(T value);
        bool contains(T value);
        BinarySearchTree<T> remove(T value);

        void print();

        BstNode<T>* getRoot() {return root;}

};

template <class T>
BinarySearchTree<T> BinarySearchTree<T>::insert(T value)
{
    if (root == NULL)
    {
        root = new BstNode<T>(value);       
    }
    else
    {
        addChild(value, root);
    }
    cout << "VAL: " << root->value << endl << "LEFT: " << root->left << endl << "RIGHT: "<< root->right << endl << "ADDR: " << root <<endl;
    return *this;
}
template <class T>
void BinarySearchTree<T>::addChild(T value, BstNode<T>* node)
{

    if (value > node->value)
    {
        cout <<"\tgt"<<endl;
        if (node->right == NULL)
        {
            node->right = new BstNode<T>(value, node);
        }
        else
        {
            addChild(value, node->right);
        }
    }
    else
    {
        cout<<"\tlte"<<endl;
        if (node->left == NULL)
        {
            node->left = new BstNode<T>(value, node);
        }
        else
        {
            addChild(value, node->left);
        }
    }
}

// [other member functions]


int main()
{
    BinarySearchTree<int> tree;
    BstNode<int> *n;
    n = tree.getRoot();
    cout << "ADDR: " << n <<endl<<endl;
    tree.insert(5);
    n = tree.getRoot();

    cout << "VAL: " << n->value << endl << "LEFT: " << n->left << endl << "RIGHT: "<< n->right << endl << "ADDR: " << n << endl;
    return 1;
}

Вывод моей функции: 

$ ./bst
ADDR: 0

VAL: 5
LEFT: 0
RIGHT: 0
ADDR: 0xa917c8

VAL: 11085080
LEFT: 0xa917a8
RIGHT: 0
ADDR: 0xa917c8

Я не понимаю, почему значения в корневом узле изменились, но указатель все еще указывает на то же место. Единственное, о чем я могу подумать, это то, что корневой узел создается в стеке, а не выделяется в куче, но не new обеспечивает правильное распределение памяти в C ++?

1 Ответ

3 голосов
/ 14 февраля 2012

Думаю, проблема в том, что ваш метод вставки возвращает BinarySearchTree по значению, но у вас не определен конструктор копирования.В результате это создает поверхностную копию BinarySearchTree, возвращает ее и вызывает срабатывание деструктора копии.Затем он удаляет BstNode, хранящийся в качестве корня, но поскольку скопированный BinarySearchTree использует BstNodes совместно с исходным деревом, вы удаляете память в исходном дереве.Ошибка, которую вы получаете, связана с обращением к освобожденной памяти, когда вы пытаетесь снова получить доступ к узлу.

Чтобы исправить это, либо используйте функцию вставки, возвращающую ссылку на дерево (поэтому копия не создается), либо определяйтеконструктор копирования или оператор присваивания.В идеале делай и то и другое.: -)

Надеюсь, это поможет!

...