C++ 删除链表中最前面的元素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19326662/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Deleting the front element in a linked list
提问by Riptyde4
I'm trying to write a function that deletes the front element of my linked list and sets the head pointer to the next element after the deleted one.
我正在尝试编写一个函数来删除链表的前元素，并将头指针设置为被删除元素之后的下一个元素。
Here is my code:
这是我的代码：
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--;
}
And here are my class definitions:
这是我的类定义：
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();
};
Annddddd.....this is the problem, when running in valgrind this error pops up right before the first delete_front() call:
Anddddd.....这就是问题所在，在 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)
回答by Daniel Frey
You are deleting the element and afterwards, you try to access it. It's these lines:
您正在删除该元素，然后尝试访问它。这是这些行：
ListNode *tmp = head;
delete head;
head = tmp->next; // tmp was initialized to head, but head was just deleted!
which should read:
应该是：
ListNode *tmp = head->next;
delete head;
head = tmp;
Update: I just realized that with the above, the whole method could become much easier:
更新：我刚刚意识到，有了上述，整个方法可以变得更容易：
void LinkedList::delete_front()
{
if(head != NULL) {
ListNode *tmp = head->next;
delete head;
head = tmp;
--size;
}
}
should work for all cases. You don't have to check for head->next == NULLas the above handles it as well. It also fixes the bug in your code where you decrease sizeeven if the list was empty my moving --sizeinside the if(head != NULL)block.
应该适用于所有情况。您不必检查，head->next == NULL因为上面也处理它。它还修复了代码中的错误，size即使列表为空，我--size在if(head != NULL)块内移动时也会减少。
Note that this keeps your original semantics which is "if the list is empty, do nothing". This is usually not what you want, consider throwing an exception:
请注意，这会保留您的原始语义，即“如果列表为空，则什么都不做”。这通常不是你想要的，考虑抛出异常：
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;
}
回答by Byron Lo
Problem here:
问题在这里：
if(head->next != NULL){
ListNode *tmp = head;
delete head;
head = tmp->next;
}
You assign temp to head, then delete head. Then try to access it again.
您将 temp 分配给 head，然后删除 head。然后尝试再次访问它。
回答by Peter Wood
If you use a smart pointer it will reduce to:
如果您使用智能指针，它将减少为：
void LinkedList::delete_front() {
if(head != NULL) {
head = head->next;
--size;
}
}
Where:
在哪里：
class ListNode{
public:
Item data;
unique_ptr<ListNode> next;
};
class LinkedList{
private:
unique_ptr<ListNode> head;
//.. etc
Also, I've fixed the bug where the size was decreasing even if headwas NULL.
另外，我已经修复了即使head是NULL.
回答by Zan Lynx
Your problem is right here:
你的问题就在这里：
ListNode *tmp = head;
delete head;
head = tmp->next;
You set tmp to head, then delete head, then you use tmp. tmp is pointing to memory that you just deleted.
您将 tmp 设置为 head，然后删除 head，然后使用 tmp。tmp 指向您刚刚删除的内存。
Instead, set tmp to head, set head to head->next, THEN delete tmp.
相反，将 tmp 设置为 head，将 head 设置为 head->next，然后删除 tmp。
