1

我正在尝试编写一个函数来删除链表的前元素，并将头指针设置为删除后的下一个元素。

这是我的代码：

void LinkedList::delete_front(){
    if(head != NULL){
            if(head->next != NULL){
                    ListNode *tmp = head;
                    delete head;
                    head = tmp->next;
            }
            else {delete head; head = NULL;}
    }
    size--;
}

这是我的类定义：

class ListNode{

    public:
            Item data;
            ListNode *next;
};
class LinkedList{

    private:
            ListNode *head;
            int size;

    public:
            LinkedList();
            ~LinkedList(); 
            bool empty();
            void insert_front(Item i);
            void insert_back(Item i);
            void delete_front();
            void delete_back();
            void print();
};

Andddddd .....这是问题所在，在 valgrind 中运行时，在第一次 delete_front() 调用之前会弹出此错误：

==4738== Invalid read of size 8
==4738==    at 0x400B3C: LinkedList::delete_front() (in /home/jon/jball2_lab06/linkedlist)
==4738==    by 0x400E59: main (in /home/jon/jball2_lab06/linkedlist)
==4738==  Address 0x5a03f98 is 8 bytes inside a block of size 16 free'd
==4738==    at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4738==    by 0x400B37: LinkedList::delete_front() (in /home/jon/jball2_lab06/linkedlist)
==4738==    by 0x400E59: main (in /home/jon/jball2_lab06/linkedlist)
4

4 回答 4

3

这里的问题：

if(head->next != NULL){
    ListNode *tmp = head;
    delete head;
    head = tmp->next;
}

您将 temp 分配给 head，然后删除 head。然后尝试再次访问它。

于 2013-10-11T20:27:40.153 回答
2

您正在删除元素，然后尝试访问它。就是这几行：

ListNode *tmp = head;
delete head;
head = tmp->next; // tmp was initialized to head, but head was just deleted!

应该是：

ListNode *tmp = head->next;
delete head;
head = tmp;

更新：我刚刚意识到通过上述方法，整个方法可以变得更加容易：

void LinkedList::delete_front()
{
    if(head != NULL) {
        ListNode *tmp = head->next;
        delete head;
        head = tmp;
        --size;
    }
}

应该适用于所有情况。您不必检查，head->next == NULL因为上面也处理它。它还修复了代码中的错误，size即使列表为空，我--size在if(head != NULL)块内移动时也会减少。

请注意，这会保留您的原始语义，即“如果列表为空，则不执行任何操作”。这通常不是你想要的，考虑抛出一个异常：

void LinkedList::delete_front()
{
    if(head == NULL) {
        throw std::runtime_exception( "LinkedList::delete_front() "
                                      "called with empty list" );
    }

    ListNode *tmp = head->next;
    delete head;
    head = tmp;
    --size;
}
于 2013-10-11T20:27:27.083 回答
1

你的问题就在这里：

                ListNode *tmp = head;
                delete head;
                head = tmp->next;

您将 tmp 设置为 head，然后删除 head，然后使用 tmp。tmp 指向您刚刚删除的内存。

相反，将 tmp 设置为 head，将 head 设置为 head->next，然后删除 tmp。

于 2013-10-11T20:27:18.687 回答
1

如果您使用智能指针，它将减少为：

void LinkedList::delete_front() {
    if(head != NULL) {
        head = head->next;
        --size;
    }
}

在哪里：

class ListNode{
    public:
        Item data;
        unique_ptr<ListNode> next;
};

class LinkedList{
    private:
        unique_ptr<ListNode> head;
//.. etc

另外，我已经修复了大小减小的错误，即使head是NULL.

于 2013-10-11T20:39:39.453 回答