c++ - 如何删除节点指针

Question

这是作业。我还没有看到任何真正直接回答这个问题的东西，所以我很难修复它。我必须创建最大堆的链接节点实现，并且在删除值后删除节点时遇到困难。

我的代码:

template<class ItemType>
BinaryHeapNode<ItemType>* LinkedMaxHeap<ItemType>::getLastNode()
{
    BinaryHeapNode<ItemType>* lastNode = rootPtr->getRightSiblingPtr();
    BinaryHeapNode<ItemType>* prevLastNode = rootPtr;
    while(lastNode != nullptr)
{
    prevLastNode = lastNode;
    lastNode = lastNode->getRightSiblingPtr();      
}
return prevLastNode;
}

template<class ItemType>
bool LinkedMaxHeap<ItemType>::removeValue(ItemType value)
{
    BinaryHeapNode<ItemType>* tempNode = rootPtr;
    for (int i = 0; i < itemCount; i++)
    {
        if(tempNode->getItem() == value)
        {
            tempNode->setItem(getLastNode()->getItem());//set item
            delete getLastNode();                       //delete last node
            getLastNode() = nullptr;                    //set last node null
            getLastNode()->setRightSiblingPtr(nullptr); //last node should be different
            itemCount--;                                //set it's sibling to null
            heapRebuild(tempNode);
        }

        tempNode = tempNode->getRightSiblingPtr();
    }

    return true;
}

我的问题是 getLastNode() = nullptr。 VS 告诉我 getLastNode() 不是左值。这对我来说没有意义，因为 getLastNode 正在返回一个指向 BinaryHeapNode 的指针，但它不能将该指针设置为 nullptr？

我认为这可能是我的指针逻辑(充其量是不稳定的)的问题，所以我认为将 getLastNode() 更改为仅返回一个节点会有所帮助。那没有。所以我尝试弄乱 & 运算符并返回最后一个节点的地址。不用说我还没有找到解决方案。如果有人可以提供某种方向，将不胜感激。我只是不完全确定为什么它不起作用。

编辑:

根据 arynaq 提到的内容编辑了代码。错误消失了，但现在我有一堆链接器错误，我必须在测试之前修复它。这段代码会做我想做的事吗？我觉得它只是要删除 nodeToDelete 而不是删除堆中的节点。

template<class ItemType>
bool LinkedMaxHeap<ItemType>::removeValue(ItemType value)
{
    BinaryHeapNode<ItemType>* tempNode = rootPtr;
    BinaryHeapNode<ItemType>* nodeToDelete = getLastNode();
    for (int i = 0; i < itemCount; i++)
    {
        if(tempNode->getItem() == value)
        {
            tempNode->setItem(nodeToDelete->getItem());
            delete &nodeToDelete;
            nodeToDelete = nullptr;
            getLastNode()->setRightSiblingPtr(nullptr);
            itemCount--;
            heapRebuild(tempNode);
        }

        tempNode = tempNode->getRightSiblingPtr();
    }

    return true;
}

Answer 1

好的，我会尝试通过解释一些关于指针的事情来提供帮助。希望这会澄清一些误解并帮助您完成作业。

当您像这样获得指针的拷贝时:mypointer* p = get_pointer(); 然后删除它，您是 删除内存。但是，当您将 nullptr 分配给此局部变量时，它不会影响指针的“源”。

这是一个详细的示例，展示了哪里可能出错。如果您从未将 v[0] 设置为 nullptr。

#include <iostream>
#include <vector>

struct Object {
    ~Object() {
        std::cout << "Object destructor." << std::endl;
    }
    int val = 42;
};

struct OtherObj {
    int val = 322;
};

void print_vec(const std::vector<Object*>& v) {
    for (const auto& x : v) {
        std::cout << x << std::endl;
    }
}

int main(int, char**) {
    // Init vector and print addresses.
    std::vector<Object*> v(2);
    print_vec(v);

    // Init objects in vector and printit.
    for (auto& x : v) {
        x = new Object();
    }
    print_vec(v);

    // Get a copy of a pointer and delete that. All good so far.
    Object* pointer_to_delete = v[0];
    delete pointer_to_delete;

    // Assign nullptr to the temporary local pointer.
    // Does nothing to the pointer in the vector.
    pointer_to_delete = nullptr;

    // Print the vector to prove it.
    print_vec(v);

    // On a non debug build, the memory will still have the last value.
    // Careful! Cause of headaches here. This should be set to nullptr.
    std::cout << v[0]->val << std::endl; // "No problem", certainly not nullptr.

    // Now that we allocate a new object, v[0] will be overwritten.
    OtherObj* bad_bad_boy = new OtherObj();
    // Print the address of the new object, to show it was created at
    // the old v[0] address.
    std::cout << bad_bad_boy << std::endl;

    // Bad things ensue...
    std::cout << v[0]->val << std::endl;

    return 0;
}

clang 的输出是:

0x0
0x0
0x7ffa21c026c0
0x7ffa21c026d0
Object destructor.
0x7ffa21c026c0
0x7ffa21c026d0
42
0x7ffa21c026c0
322

如您所见，将本地指针设置为 nullptr 是不够的!我希望这能为您解决一些问题 :)

Online version