c++ - 简单链表删除失败

Question

我正在学习 C++，我尝试实现简单的单链表，但删除节点部分失败。我不明白为什么这个基本的 delete_node 部分失败了。 delete_node 方法中的 prev->set_next 行似乎无法正常工作。我也尝试调试它，但未能发现错误。

using namespace std; //ignore it for simplicity

class Node {
    int data;
    Node *next;
public:
    Node() {}
    void set_data(int a_data)
    {
        data = a_data;
    }
    void set_next(Node *a_next)
    {
        next = a_next;
    }

    int get_data()
    {
        return data;
    }

    Node* get_next()
    {
        return next;
    }
};


class List {
    Node *head;
public:
    List()
    {
        head = NULL;
    }

    void print_list();
    void append_node(int data);
    void delete_node(int data);
};

void List::print_list()
{
    Node *temp = head;
    if(temp == NULL)
    {
        cout << "empty" << endl;
        return;
    }

    if(temp->get_next() == NULL)
    {
        cout << temp->get_data() << "--->";
        cout << "NULL" << endl;
    }
    else
    {
        do
        {
            cout << temp->get_data() << "+++>";
            temp = temp->get_next();
        } while(temp != NULL);
        cout << "NULL" << endl;
    }
}

void List::append_node(int data)
{
    Node *new_node = new Node();
    new_node->set_data(data);
    new_node->set_next(NULL);

    Node *temp = head;
    if(temp != NULL)
    {
        while(temp->get_next()!=NULL)
        {
            temp = temp->get_next();
        }
        temp->set_next(new_node);
    }
    else
    {
        head = new_node;
    }
}


void List::delete_node(int data)
{
    Node *temp = head;
    if(temp == NULL)
    {
        return;
    }
    else
    {
        Node *prev = NULL;
        do
        {
            prev = temp;
            if(temp->get_data() == data)
            {
                prev->set_next(temp->get_next());
                delete temp;
                break;
            }
            temp = temp->get_next();
        } while(temp!=NULL);
    }
}


int main()
{
    List list;
    list.append_node(10);
    list.append_node(20);
    list.append_node(30);
    list.append_node(40);
    list.append_node(50);
    list.append_node(60);

    list.delete_node(30); //

    list.print_list();
    return 0;
}

valgrind 给我以下错误。

==22232== Invalid read of size 8
==22232==    at 0x400D38: Node::get_next() (20_1.cpp:25)
==22232==    by 0x400A5E: List::print_list() (20_1.cpp:62)
==22232==    by 0x400C6C: main (20_1.cpp:127)
==22232==  Address 0x5abdd28 is 8 bytes inside a block of size 16 free'd
==22232==    at 0x4C2F24B: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==22232==    by 0x400BA8: List::delete_node(int) (20

Answer 1

让我们仔细看看 List::delete_node 函数中的这些行

prev = temp;
if(temp->get_data() == data)
{
    prev->set_next(temp->get_next());
    delete temp;
    break;
}

第一个使 prev 指向与 temp 指向的节点完全相同的节点。在此之后 prev == temp 为真。

所以当你这样做的时候

prev->set_next(temp->get_next());

和

一样

temp->set_next(temp->get_next());

也就是说，您使 temp->next 指向 temp->next，这根本不会改变它。您永远不会取消该节点与列表的链接，但您确实会删除它。这会使您打印的列表无效，因为您将取消引用已删除的节点。

作为一个简单的解决方案，您可以这样做:

if (head->get_data() == data)
{
    // Special case: Head node is the one we want to delete
    Node* old_head = head;

    // Make the head be the second node in the list, if any
    head = head->get_next();

    // Delete the old head
    delete old_head;
}
else
{
    // We know it's not the head node of the list, use the "next" to find it
    for (Node* node = head; node->get_next() != 0; node = node->get_next())
    {
        if (node->get_next()->get_data() == data)
        {
            // It's the "next" node we want to remove
            Node* old_next = node->get_next();

            // Unlink the node
            node->set_next(node->get_next()->get_next());

            delete old_next;

            break;
        }
    }
}