指针和指向单链表中指针的指针，帮助我理解C++

Question

我仍在努力理解指针、绘制节点和所有东西，但有些东西似乎无法理解。

例如，这里有一个函数，它应该从列表中删除具有偶数值的节点

void delete_even()
{

node* ptr = head;
while (ptr)
{
if (ptr->data % 2 == 0)
{
nod* aux = ptr;
ptr = ptr->next;
delete aux;
}
else
{
ptr = ptr->next;
}
}
}

据我所知，名为ptr的指针指向head，head是链表中的第一个节点。1我的逻辑是什么样子的因此while ptr=!null检查头中的数据是否是偶数。不是1所以ptr = ptr->next;这意味着(好吧，让ptr指向ptr的下一个元素所指向的任何一个)，这就让指针ptr指向列表中的第二个节点，对吧？2作为这样的

既然ptr指向第二个节点，而data元素是偶数，那么创建一个名为aux的新指针，并指向ptr当前指向的同一节点！现在，使ptr指向下一个节点，即列表中的第三个节点，并删除包含第二个节点地址的aux；3像这个

现在我再看一遍，它可能不起作用，因为第一个节点和第三个节点之间的链接断了。。。正确的

一个很酷的家伙来了，告诉我用指针对指针，因为这更容易。并帮我处理了这个代码：

void delete_even()
{
node **p= &head;
while (*p)
{
if ((*p)->data % 2 == 0)
{
node *nextptr=*p;
*p=(*p)->next;
delete nextptr;
}
else
{
p= &(*p)->next;
}
}
}

据我所知，p指向名为head的指针，该指针指向第一个节点。

p表示查看p所指向的对象，在这种情况下，它应该是指针head*p的意思是看p所指的东西，在这个例子中，指针head，然后再看head所指的事情，所以这应该是第一个节点，对吧？

我想我说得对。

现在，当*p!=NULL(当第一个节点指向除NULL以外的任何值时)验证第一个节点的data是否为偶数。不是，是1。因此，使p(head指针)具有第二节点的地址。5个这样现在我们看到数据是2，所以我们制作了一个名为nextptr的指针，并使该指针指向*p所指向的同一个对象，即第二个节点，对吗？之后，我们查看*p所指向的东西(第二个节点)，并将其移动到下一个节点，然后删除nextptr指针。6最后一个

从纸面上看，它对我来说是一样的，也许我的绘画和理解是不对的。但我花了好几天的时间试图理解它，但它根本没有。。。我的意思是，第二个代码运行良好，但我只是不明白为什么逻辑看起来和第一个一样。有人知道如何更好地解释吗？

Answer 1

因此，使p(head指针)具有第二个节点的地址。

此语句存在两个问题。

首先，p不是head指针。相反，p指向head指针(在过程的这一点上)。当p发生变化时，head保持不变。(另一方面，如果*p发生变化，则会影响head。)

其次，新值不是第二节点((*p)->next)的地址。相反，它是第一节点(&(*p)->next)中的next指针的地址。注意&。

因此，图像5应该如下所示：

head    p 
|     |
V     |
--------+----   ------------   ------------   ------------
|       V   |   |          |   |          |   |          |
|    -------|   |   -------|   |   -------|   |   -------|
| 1  | next-+-->| 2 | next-+-->| 3 | next-+-->| 4 | NULL |
|    -------|   |   -------|   |   -------|   |   -------|
-------------   ------------   ------------   ------------

看看你能不能从这里拿走。(在这一步之前，你一直做得很好，所以我认为你可以。)如果你或其他人陷入困境，或者只是想检查第六个图像应该是什么，下面是删除节点2:之前的情况

head p||V|--------+-------------------------------|V||||||-------||-------||1|下一个-+------------------->|3|下一个-+->|4|NULL||-------|-------|-------||-------|-------------||---------------------------|--------|^下一步--->|2|下一个-+-----||-------|------------

对照循环的另一次迭代检查结果可能也很有帮助。这就是图像七：

head p||V|---------------------+-----------------|||V||||-------||-------||1|下一个-+------------------->|3|下一个-+->|4|NULL||-------||-------|----------------------------

评论：尾随指针比这种指针对指针的方法更容易理解

Answer 2

这两种实现实际上都是错误的。他们有几个问题。

1. 有一个边缘案例没有得到处理。当第一个元素，即head所指向的元素被删除时，头指针需要用下一个值更新。显然，这个逻辑需要是递归的，这样它就可以在删除前一个头之后处理新的头。

2. 还缺少将最后一个指针链接到当前指针上的逻辑。为此，您需要维护一个last指针，并用ptr->next更新last->next指针以保持列表的连接。如果last指针为空，那么您知道head需要更新。

3. 同时还混合了太多的决策，这使得算法变得不必要地复杂。我喜欢算法在采取任何操作之前保存下一个指针的习惯用法。这解放了心理逻辑，让它思考实际需要对数据做什么，而不是试图在头脑中同时处理这两个流。

4. 在检查指针的有效性时的一个小的修辞修正。最好对照nullptr进行检查，而不是假设空指针为零。

我会这样重写：

void delete_even()
{
// Initialize the iterator
node* ptr = head;
node* last = nullptr;
// loop while the current pointer is not null
while (ptr!=nullptr)
{
// Save the pointer to next node 
node* next = ptr->next;
// If the data is even, delete and reconnect everything
if (ptr->data % 2 == 0) {
// Delete the data
delete ptr;
// Reconnect the previous pointer so the list is intact
// This is the head node
if ( last==nullptr ) head = next;
// There is a previous valid node
else last->next = next;
} else {
// Update last to the last valid node
last = ptr;
}
// Proceed to the next node
ptr = next;
}
}