4

我正在创建类似于结构列表的东西。在 main 的开头，我声明了一个空指针。然后我调用 insert() 函数几次，传递对该指针的引用，以添加新元素。

然而，似乎有些不对劲。我无法显示列表的元素，std::cout只是破坏了程序，即使它在没有警告的情况下编译。

#include <iostream>

struct node {
    node *p, *left, *right;
    int key;
};

void insert(node *&root, const int key)
{
    node newElement = {};
    newElement.key = key;

    node *y = NULL;
    std::cout << root->key; // this line
    while(root)
    {
        if(key == root->key) exit(EXIT_FAILURE);
        y = root;
        root = (key < root->key) ? root->left : root->right;
    }

    newElement.p = y;

    if(!y) root = &newElement;
    else if(key < y->key) y->left = &newElement;
    else y->right = &newElement;
}

int main()
{
    node *root = NULL;
    insert(root, 5);
        std::cout << root->key; // works perfectly if I delete cout in insert()
    insert(root, 2);
        std::cout << root->key; // program breaks before this line
    return 0;
}

如您所见，我在插入函数中创建了新的结构元素并将其保存在根指针中。在第一次调用中，甚至没有启动 while 循环，因此它可以工作，并且我能够在主函数中显示 root 的元素。

但是在第二次调用中，while 循环已经起作用，我得到了我描述的问题。

语法有问题，root->key因为即使我将它放在第一次调用中它也不起作用。

出了什么问题，原因是什么？

此外，我总是看到通过这样的指针插入新列表的元素：

node newElement = new node();
newElement->key = 5;
root->next = newElement;

此代码是否等于：

node newElement = {};
newElement.key = 5;
root->next = &newElement;

? 它会更干净一些，并且不需要删除内存。

4

4 回答 4

2

问题是因为您将指针传递给函数外的局部变量。取消引用此类指针是未定义的行为。你应该分配newElement.new

这段代码

node newElement = {};

创建一个局部变量newElement。一旦函数结束，范围就newElement结束了，它的内存被破坏了。但是，您将指向该被破坏内存的指针传递到函数外部。一旦函数退出，对该内存的所有引用都将变为无效。

另一方面，这段代码

node *newElement = new node(); // Don't forget the asterisk

在空闲存储区分配一个对象。delete这些对象在您明确显示之前一直可用。这就是为什么您可以在创建它们的函数退出后使用它们的原因。当然既然newElement是指针，就需要使用->它来访问它的成员。

于 2013-04-20T10:35:50.033 回答
1

您需要在这里学习的关键是堆栈分配对象和堆分配对象之间的区别。在您的插入函数中，您node newElement = {}是堆栈分配的，这意味着它的生命周期由封闭范围决定。在这种情况下，这意味着当函数退出时，您的对象将被销毁。那不是你想要的。您希望树的根存储在您的node *root指针中。为此，您需要从堆中分配内存。在 C++ 中，通常使用 new 运算符完成。这允许您将指针从一个函数传递到另一个函数，而其生命周期不取决于它所在的范围。这也意味着您需要小心管理堆分配对象的生命周期。

于 2013-04-20T10:50:06.887 回答
0

好吧，您的Also评论有一个问题。第二个可能更干净，但它是错误的。你必须新的记忆并删除它。否则，您最终会得到指向不再存在的对象的指针。这正是 new 解决的问题。

另一个问题

void insert(node *&root, const int key)
{
    node newElement = {};
    newElement.key = key;

    node *y = NULL;
    std::cout << root->key; // this line

在第一次插入时，root 仍然是 NULL，所以这段代码会使程序崩溃。

于 2013-04-20T10:35:34.550 回答
0

已经解释过您必须动态分配对象（使用new），但是这样做充满危险（内存泄漏）。

有两种（简单）解决方案：

  1. 有一个所有权计划。
  2. 使用竞技场来放置您的节点，并保留对它们的引用。

1 所有权方案

在 C 和 C++ 中，获取存储对象的内存有两种形式：自动存储和动态存储。例如，当您在函数中声明变量时使用自动，但是这些对象仅在函数的持续时间内存在（因此在之后使用它们时会遇到问题，因为内存可能被其他东西覆盖）。因此，您经常必须使用动态内存分配。

动态内存分配的问题是你必须明确地把它还给系统，以免它泄漏。在 C 中，这非常困难并且需要严格。在 C++ 中，虽然使用智能指针更容易。所以让我们使用这些！

struct Node {
    Node(Node* p, int k): parent(p), key(k) {}

    Node* parent;
    std::unique_ptr<Node> left, right;
    int key;
};

// Note: I added a *constructor* to the type to initialize `parent` and `key`
// without proper initialization they would have some garbage value.

注意 和 的不同parent声明left？父级拥有其子级 ( unique_ptr)，而子级仅指其父级。

void insert(std::unique_ptr<Node>& root, const int key)
{
    if (root.get() == nullptr) {
        root.reset(new Node{nullptr, key});
        return;
    }

    Node* parent = root.get();
    Node* y = nullptr;

    while(parent)
    {
        if(key == parent->key) exit(EXIT_FAILURE);
        y = parent;
        parent = (key < parent->key) ? parent->left.get() : parent->right.get();
    }

    if (key < y->key) { y->left.reset(new Node{y, key}); }
    else              { y->right.reset(new Node{y, key}); }
}

如果您不知道是什么unique_ptr，get()它只包含一个分配的对象，new并且该get()方法返回一个指向该对象的指针。您还可以reset使用它的内容（在这种情况下，它会正确处理它已经包含的对象，如果有的话）。

我会注意到我不太确定你的算法，但是嘿，这是你的:)

2 竞技场

如果这种处理记忆的方法让你一头雾水，那一开始是很正常的，这就是为什么有时竞技场可能更容易使用的原因。使用竞技场的想法很笼统。而不是逐个地打扰内存所有权，而是使用“某物”来保留内存，然后只操作对这些片段的引用（或指针）。您只需要记住，只要竞技场存在，这些引用/指针就一直存在。

struct Node {
    Node(): parent(nullptr), left(nullptr), right(nullptr), key(0) {}

    Node* parent;
    Node* left;
    Node* right;
    int key;
};

void insert(std::list<Node>& arena, Node *&root, const int key)
{
    arena.push_back(Node{});         // add a new node
    Node& newElement = arena.back(); // get a reference to it.
    newElement.key = key;

    Node *y = NULL;
    while(root)
    {
        if(key == root->key) exit(EXIT_FAILURE);
        y = root;
        root = (key < root->key) ? root->left : root->right;
    }

    newElement.p = y;

    if(!y) root = &newElement;
    else if(key < y->key) y->left = &newElement;
    else y->right = &newElement;
}

只要记住两件事：

  • 一旦你的竞技场死了，你所有的引用/指针都指向以太，如果你尝试使用它们，就会发生坏事
  • 如果您只将东西推入arena，它会增长，直到耗尽所有可用内存并且您的程序崩溃；在某些时候你需要清理！
于 2013-04-20T15:57:13.437 回答