c++ - 从函数返回指针如何工作？

Question

考虑以下代码片段:

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

我希望 find() 返回的 p 是 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*&:(请原谅我的肮脏 hack 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;
}

Answer 1

在 main 中，当您删除 p 时，您实际上是在删除 t 对象中的 root 指针!不要那样做，否则您将出现未定义的行为，这就是您在这里遇到的情况。

当你返回一个指针时，你返回了一个指针的拷贝，两个指针将指向同一个对象。如果您随后删除其中一个指针，另一个指针现在将指向已删除的对象。