0

考虑以下代码片段：

#include <iostream>
#include <queue>

struct node {
    int key;
    node *l;
    node *r;

    node(int key)
        :key(key), l(nullptr), r(nullptr) {
    }
};

struct bst {
    node *root;

    bst() :root(nullptr) {

    }

    node* find(int key) {
        return find(root, key); 
    }

    node* find(node *root, int key) {
        if (!root) {
            return nullptr;
        } else {
            if (root->key < key) {
                return find(root->l, key);
            }
            else if (root->key > key) {
                return find(root->r, key);
            } else {
                return root;
            }
        }
    }

    void insert(int key) {
        insert(root, key);
    }

    void insert(node *&root, int key) {
        if (!root) {
            root = new node(key);
        } else {
            if (root->key < key) {
                insert(root->r, key);
            } else if (root->key > key) {
                insert(root->l, key);
            } else {
                return;
            }
        }
    }

    void print_by_level(std::ostream &o) {
        if (!root) {
            o << "(empty)";
            return;
        }
        std::queue<node*> q;
        int curr_lv = 1;
        int next_lv = 0;
        q.push(root);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            curr_lv--;
            o << p->key << ' ';
            if (p->l) {
                q.push(p->l);
                next_lv++;
            }
            if (p->r) {
                q.push(p->r);
                next_lv++;
            }
            if (curr_lv == 0) {
                o << '\n';
                curr_lv = next_lv;
                next_lv = 0;
            }
        }
        o << '\n';
    }

};

int main() {
    bst t;
    t.insert(5);
    t.insert(10);
    t.insert(15);
    t.print_by_level(std::cout);

    // return pointer to 5 which is root
    node *p = t.find(5);
    // modify it, ok
    p->key = 100;
    t.print_by_level(std::cout);

    // now try to delete or change where p is pointing to
    delete p;
    p = nullptr;
    // then it's not happy :(
    t.print_by_level(std::cout);

    return 0;
}

我希望p从find()is返回root，但事实并非如此！似乎它只返回了该指针的副本。然而p->key = 100实际上改变了 的值root。谁能帮我解释一下？

另一方面，如果我t.root手动删除，那么它会按预期工作。

int main() {
    bst t;
    t.insert(5);
    t.insert(10);
    t.insert(15);
    t.print_by_level(std::cout);

    // return pointer to 5 which is root
    node *p = t.find(5);
    // modify it, ok
    p->key = 100;
    t.print_by_level(std::cout);

    delete t.root;
    t.root = nullptr;
    // ok happy now
    t.print_by_level(std::cout);
    return 0;
}

现在尝试更改p指向并返回的位置node*&:(请原谅我的肮脏黑客nullp:()。

#include <iostream>
#include <queue>

struct node {
    int key;
    node *l;
    node *r;

    node(int key)
        :key(key), l(nullptr), r(nullptr) {
    }
};

struct bst {
    node *root;
    node *nullp;

    bst() :root(nullptr), nullp(nullptr) {

    }

    node*& find(int key) {
        return find(root, key); 
    }

    node*& find(node *root, int key) {
        if (!root) {
            return nullp;
        } else {
            if (root->key < key) {
                return find(root->l, key);
            }
            else if (root->key > key) {
                return find(root->r, key);
            } else {
                return root;
            }
        }
    }

    void insert(int key) {
        insert(root, key);
    }

    void insert(node *&root, int key) {
        if (!root) {
            root = new node(key);
        } else {
            if (root->key < key) {
                insert(root->r, key);
            } else if (root->key > key) {
                insert(root->l, key);
            } else {
                return;
            }
        }
    }

    /**
     *          p               q
     *         / \             / \
     *        q   x3     =>  x1   p
     *      /  \                 / \
     *     x1   x2              x2  x3
     */
    void rotate_w_left_child(node *&p) {
        node *q = p->l;
        p->l = q->r;
        q->r = p;
        p = q;
    }

    void print_by_level(std::ostream &o) {
        if (!root) {
            o << "(empty)";
            return;
        }
        std::queue<node*> q;
        int curr_lv = 1;
        int next_lv = 0;
        q.push(root);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            curr_lv--;
            o << p->key << ' ';
            if (p->l) {
                q.push(p->l);
                next_lv++;
            }
            if (p->r) {
                q.push(p->r);
                next_lv++;
            }
            if (curr_lv == 0) {
                o << '\n';
                curr_lv = next_lv;
                next_lv = 0;
            }
        }
        o << '\n';
    }

};

int main() {
    bst t;
    t.insert(5);
    t.insert(4);
    t.insert(1);
    t.print_by_level(std::cout);
    node *p = t.find(5);
    // using root, happy
    // t.rotate_w_left_child(t.root);
    // t.print_by_level(std::cout);

    // using p, not happy :(
    t.rotate_w_left_child(p);
    t.print_by_level(std::cout);
    return 0;
}
4

2 回答 2

1

当main您delete p实际删除对象root中的指针时t！不要那样做，否则你会有未定义的行为，这就是你在这里所经历的。

当你返回一个指针时，你返回了一个指针的副本，两个指针都指向同一个对象。如果您再delete使用其中一个指针，则另一个指针现在将指向已删除的对象。

于 2013-09-13T05:52:58.883 回答
0

[这不一定是答案，而是带有代码的评论]

您的代码可能受到变量阴影的影响，成员“root”显然与函数参数“root”发生冲突。

帮助避免此类问题的常见做法是为成员和其他特殊情况添加前缀，例如“m_”表示“member”，“s_”表示静态，“g_”表示“global”。不要把它和可怕的匈牙利语混为一谈——至少不是系统。

struct bst {
    node *m_root;
    node *m_nullp;

    bst() : m_root(nullptr), m_nullp(nullptr) {
    }

    node*& find(int key) {
        return find(m_root, key); 
    }

    node*& find(node *root, int key) {
        if (!root) { // definitely means the parameter
            return nullp;
        } else {
            if (root->key < key) {
                return find(root->l, key);
            }
            else if (root->key > key) {
                return find(root->r, key);
            } else {
                return root;
            }
        }
    }

    void insert(int key) {
        insert(m_root, key);
    }
于 2013-09-13T06:42:32.557 回答