在 C 中通过引用传递删除列表中的节点
Delete node in a list with passing by reference in C
给定以下删除双向链表中元素的代码：
struct list
{
int info;
struct list *prev;
struct list *next;
};
struct list *insert(struct list *top,int k)
{
struct list *tmp=NULL;
if(!top)
{
tmp=(struct list *)malloc(sizeof(struct list));
if(tmp)
{
tmp->info=k;
tmp->next=NULL;
tmp->prev=NULL;
top=tmp;
}
else
printf("error\n");
}
else
{
top->next=insert(top->next,k);
if(top->next)
top->next->prev=top;
}
return top;
}
void delete(struct list **top,int k)
{
struct list *tmp=NULL;
if(*top)
{
if((*top)->info==k)
{
tmp=*top;
if((*top)->next)
{
(*top)->next->prev=(*top)->prev;
}
if((*top)->prev)
{
(*top)->prev->next=(*top)->next;
}
*top=(*top)->next;
free(tmp);
}
else
delete(&((*top)->next),k);
}
}
/* correct function
void delete(struct list **top,int k)
{
struct list *tmp=NULL;
if(*top)
{
if((*top)->info==k)
{
tmp=*top;
if((*top)->next)
{
(*top)->next->prev=(*top)->prev;
}
if((*top)->prev)
{
(*top)->prev->next=(*top)->next;
}
else
*top=(*top)->next;
free(tmp);
}
else
delete(&((*top)->next),k);
}
}*/
int main()
{
int i,k;
struct list *top=NULL;
for(i=1;i<11;i++)
top=insert(top,i);
printf("insert a key\n");
scanf("%d",&k);
delete(&top,k);
// ...
}
问题是删除节点k时，k的前一个节点的next字段不是指向k的后继者，而是指向k的后继者的后继者。
例如：
给定以下序列：1 2 3 4 5 6 7 8 9 10.
删除节点5；
结果：1 2 3 4 7 8 9 10。
为什么会这样？
EDIT：我在注释中添加了 delete 函数，其中只有当 *top 是头部时指针才会前进，现在它可以工作了。但是问题总是悬而未决，为什么改变 *top 的值也会修改 (*top)->prev->next=(*top)->next 之前改变的值。
工作代码
我没有检查 chat room，但这是我使用的测试代码的工作解决方案。它使用迭代而不是递归方法。我没有更改 insert() 代码（尽管我将它移到了 delete() 函数之后），但如果它变成 'my' 代码，我会删除递归。
#include <stdio.h>
#include <stdlib.h>
struct list
{
int info;
struct list *prev;
struct list *next;
};
static
void delete(struct list **top, int k)
{
struct list *node = *top;
while (node)
{
if (node->info == k)
{
if (node->next)
node->next->prev = node->prev;
if (node->prev)
node->prev->next = node->next;
if (node == *top)
*top = node->next;
free(node);
return;
}
node = node->next;
}
}
static
struct list *insert(struct list *top, int k)
{
struct list *tmp = NULL;
if (!top)
{
tmp = (struct list *)malloc(sizeof(struct list));
if (tmp)
{
tmp->info = k;
tmp->next = NULL;
tmp->prev = NULL;
top = tmp;
}
else
printf("error\n");
}
else
{
top->next = insert(top->next, k);
if (top->next)
top->next->prev = top;
}
return top;
}
static void dump_list_fwd(const char *tag, struct list *top)
{
printf("List %p: %s\n", (void *)top, tag);
while (top != 0)
{
printf(" Item %p: %2d (next %p, prev %p)\n", (void *)top,
top->info, (void *)top->next, (void *)top->prev);
top = top->next;
}
}
static void free_list(struct list *top)
{
while (top != 0)
{
struct list *next = top->next;
free(top);
top = next;
}
}
int main(void)
{
struct list *top = NULL;
for (int i = 1; i < 11; i++)
top = insert(top, i);
dump_list_fwd("After insert", top);
for (int i = 1; i < 11; i++)
{
int k = (i * 3 + 5) % 10 + 1;
printf("Delete %d\n", k);
delete(&top, k);
dump_list_fwd("After delete", top);
}
free_list(top);
return 0;
}
使用命令行可以干净地编译：
gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
-Wold-style-definition -Werror dellink.c -o dellink
除了main()之外的功能是static以满足-Wmissing-prototypes选项。如果要在这个源文件之外使用这些函数，它们将在 header 中声明 — 但没有其他源文件，也没有 header，所以我将它们设为 [=21] =].
delete()函数重写为迭代函数。关键观察结果 (fix) 是存储在传递给函数的指针中的地址应该只在删除节点时发生变化。当代码是递归时，这更难处理。我还通过将 (*top) 复制到局部变量中来避免在任何地方使用它；稍微简化了代码。
打印和释放函数是 straight-forward 位代码。我几乎总是将 tag 字符串传递给打印函数，以便可以简单地识别调用它的不同位置。如果我彻底完成这项工作，我会使用 uintptr_t 和 <inttypes.h> 中的 PRIXPTR 宏来避免为空指针打印 0x0 （我会使用 "0x%.12" PRIXPTR 来打印地址，完全意识到指针可能需要 16 个字节，但并不经常 运行 将其作为一个问题）。
main() 代码连续添加条目 1..10。删除循环以不同的顺序处理条目（9、2、5、8、1、4、7、10、3、6），因此 'remove from start' 和 'remove from end' 都被执行为以及 'remove from middle'.
样本运行
List 0x7f9460c03180: After insert
Item 0x7f9460c03180: 1 (next 0x7f9460c031a0, prev 0x0)
Item 0x7f9460c031a0: 2 (next 0x7f9460c031c0, prev 0x7f9460c03180)
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x7f9460c031a0)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
Item 0x7f9460c03200: 5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c03200)
Item 0x7f9460c03240: 7 (next 0x7f9460c03260, prev 0x7f9460c03220)
Item 0x7f9460c03260: 8 (next 0x7f9460c03280, prev 0x7f9460c03240)
Item 0x7f9460c03280: 9 (next 0x7f9460c032a0, prev 0x7f9460c03260)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03280)
Delete 9
List 0x7f9460c03180: After delete
Item 0x7f9460c03180: 1 (next 0x7f9460c031a0, prev 0x0)
Item 0x7f9460c031a0: 2 (next 0x7f9460c031c0, prev 0x7f9460c03180)
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x7f9460c031a0)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
Item 0x7f9460c03200: 5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c03200)
Item 0x7f9460c03240: 7 (next 0x7f9460c03260, prev 0x7f9460c03220)
Item 0x7f9460c03260: 8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 2
List 0x7f9460c03180: After delete
Item 0x7f9460c03180: 1 (next 0x7f9460c031c0, prev 0x0)
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
Item 0x7f9460c03200: 5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c03200)
Item 0x7f9460c03240: 7 (next 0x7f9460c03260, prev 0x7f9460c03220)
Item 0x7f9460c03260: 8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 5
List 0x7f9460c03180: After delete
Item 0x7f9460c03180: 1 (next 0x7f9460c031c0, prev 0x0)
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
Item 0x7f9460c03240: 7 (next 0x7f9460c03260, prev 0x7f9460c03220)
Item 0x7f9460c03260: 8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 8
List 0x7f9460c03180: After delete
Item 0x7f9460c03180: 1 (next 0x7f9460c031c0, prev 0x0)
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
Item 0x7f9460c03240: 7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 1
List 0x7f9460c031c0: After delete
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x0)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
Item 0x7f9460c03240: 7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 4
List 0x7f9460c031c0: After delete
Item 0x7f9460c031c0: 3 (next 0x7f9460c03220, prev 0x0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c031c0)
Item 0x7f9460c03240: 7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 7
List 0x7f9460c031c0: After delete
Item 0x7f9460c031c0: 3 (next 0x7f9460c03220, prev 0x0)
Item 0x7f9460c03220: 6 (next 0x7f9460c032a0, prev 0x7f9460c031c0)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03220)
Delete 10
List 0x7f9460c031c0: After delete
Item 0x7f9460c031c0: 3 (next 0x7f9460c03220, prev 0x0)
Item 0x7f9460c03220: 6 (next 0x0, prev 0x7f9460c031c0)
Delete 3
List 0x7f9460c03220: After delete
Item 0x7f9460c03220: 6 (next 0x0, prev 0x0)
Delete 6
List 0x0: After delete
valgrind 为代码提供了一份干净的健康证明 — 没有访问错误，也没有未释放的内存。
为什么原代码会跳过一个节点？
让我们画一幅画 — ASCII 艺术脱颖而出！
删除节点 2 之前：
+-----+
| top |
+-----+
|
v
+--------+ +--------+ +--------+ +--------+
| |---->| |---->| |---->| |
| Node 1 | | Node 2 | | Node 3 | | Node 4 |
| |<----| |<----| |<----| |
+--------+ +--------+ +--------+ +--------+
递归调用：
递归调用中的top实际存放在'Node 1'->next!
+-----+
| top |
+-----+
|
v
+--------+ +--------+ +--------+ +--------+
| |---->| |---->| |---->| |
| Node 1 | | Node 2 | | Node 3 | | Node 4 |
| |<----| |<----| |<----| |
+--------+ +--------+ +--------+ +--------+
Non-null (*top)->next:
分配：(*top)->next->prev=(*top)->prev;
+-----+
| top |
+-----+
|
v
+--------+ +--------+ +--------+ +--------+
| |---->| |---->| |---->| |
| Node 1 | | Node 2 | | Node 3 | | Node 4 |
| |<-------------------| |<----| |
+--------+ +--------+ +--------+ +--------+
Non-null (*top)->prev:
分配：(*top)->prev->next=(*top)->next;
注意因为top实际上是指向'Node 1'->next的指针，
作业 (*top)->prev->next = (*top)->next 也发生了变化
(*top).
+-----+
| top |
+-----+
|
v
+--------+ +--------+ +--------+ +--------+
| |------------------->| |---->| |
| Node 1 | | Node 2 | | Node 3 | | Node 4 |
| |<-------------------| |<----| |
+--------+ +--------+ +--------+ +--------+
分配 *top 并释放
分配(*top) = (*top)->next;
因为*top也是'Node 1'->next，赋值给*top
也会更改 'Node 1'->next 指向的位置，跳过 'Node 3'。
请注意，向后遍历仍会经过 'Node 3'.
+-----+
| top |
+-----+
|
v
+--------+ +--------+ +--------+
| |---------------------------------->| |
| Node 1 | | Node 3 | | Node 4 |
| |<-------------------| |<----| |
+--------+ +--------+ +--------+
现在解释了损坏的原因。
给定以下删除双向链表中元素的代码：
struct list
{
int info;
struct list *prev;
struct list *next;
};
struct list *insert(struct list *top,int k)
{
struct list *tmp=NULL;
if(!top)
{
tmp=(struct list *)malloc(sizeof(struct list));
if(tmp)
{
tmp->info=k;
tmp->next=NULL;
tmp->prev=NULL;
top=tmp;
}
else
printf("error\n");
}
else
{
top->next=insert(top->next,k);
if(top->next)
top->next->prev=top;
}
return top;
}
void delete(struct list **top,int k)
{
struct list *tmp=NULL;
if(*top)
{
if((*top)->info==k)
{
tmp=*top;
if((*top)->next)
{
(*top)->next->prev=(*top)->prev;
}
if((*top)->prev)
{
(*top)->prev->next=(*top)->next;
}
*top=(*top)->next;
free(tmp);
}
else
delete(&((*top)->next),k);
}
}
/* correct function
void delete(struct list **top,int k)
{
struct list *tmp=NULL;
if(*top)
{
if((*top)->info==k)
{
tmp=*top;
if((*top)->next)
{
(*top)->next->prev=(*top)->prev;
}
if((*top)->prev)
{
(*top)->prev->next=(*top)->next;
}
else
*top=(*top)->next;
free(tmp);
}
else
delete(&((*top)->next),k);
}
}*/
int main()
{
int i,k;
struct list *top=NULL;
for(i=1;i<11;i++)
top=insert(top,i);
printf("insert a key\n");
scanf("%d",&k);
delete(&top,k);
// ...
}
问题是删除节点k时，k的前一个节点的next字段不是指向k的后继者，而是指向k的后继者的后继者。
例如：
给定以下序列：1 2 3 4 5 6 7 8 9 10.
删除节点5；
结果：1 2 3 4 7 8 9 10。
为什么会这样？
EDIT：我在注释中添加了 delete 函数，其中只有当 *top 是头部时指针才会前进，现在它可以工作了。但是问题总是悬而未决，为什么改变 *top 的值也会修改 (*top)->prev->next=(*top)->next 之前改变的值。
工作代码
我没有检查 chat room，但这是我使用的测试代码的工作解决方案。它使用迭代而不是递归方法。我没有更改 insert() 代码（尽管我将它移到了 delete() 函数之后），但如果它变成 'my' 代码，我会删除递归。
#include <stdio.h>
#include <stdlib.h>
struct list
{
int info;
struct list *prev;
struct list *next;
};
static
void delete(struct list **top, int k)
{
struct list *node = *top;
while (node)
{
if (node->info == k)
{
if (node->next)
node->next->prev = node->prev;
if (node->prev)
node->prev->next = node->next;
if (node == *top)
*top = node->next;
free(node);
return;
}
node = node->next;
}
}
static
struct list *insert(struct list *top, int k)
{
struct list *tmp = NULL;
if (!top)
{
tmp = (struct list *)malloc(sizeof(struct list));
if (tmp)
{
tmp->info = k;
tmp->next = NULL;
tmp->prev = NULL;
top = tmp;
}
else
printf("error\n");
}
else
{
top->next = insert(top->next, k);
if (top->next)
top->next->prev = top;
}
return top;
}
static void dump_list_fwd(const char *tag, struct list *top)
{
printf("List %p: %s\n", (void *)top, tag);
while (top != 0)
{
printf(" Item %p: %2d (next %p, prev %p)\n", (void *)top,
top->info, (void *)top->next, (void *)top->prev);
top = top->next;
}
}
static void free_list(struct list *top)
{
while (top != 0)
{
struct list *next = top->next;
free(top);
top = next;
}
}
int main(void)
{
struct list *top = NULL;
for (int i = 1; i < 11; i++)
top = insert(top, i);
dump_list_fwd("After insert", top);
for (int i = 1; i < 11; i++)
{
int k = (i * 3 + 5) % 10 + 1;
printf("Delete %d\n", k);
delete(&top, k);
dump_list_fwd("After delete", top);
}
free_list(top);
return 0;
}
使用命令行可以干净地编译：
gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
-Wold-style-definition -Werror dellink.c -o dellink
除了main()之外的功能是static以满足-Wmissing-prototypes选项。如果要在这个源文件之外使用这些函数，它们将在 header 中声明 — 但没有其他源文件，也没有 header，所以我将它们设为 [=21] =].
delete()函数重写为迭代函数。关键观察结果 (fix) 是存储在传递给函数的指针中的地址应该只在删除节点时发生变化。当代码是递归时，这更难处理。我还通过将 (*top) 复制到局部变量中来避免在任何地方使用它；稍微简化了代码。
打印和释放函数是 straight-forward 位代码。我几乎总是将 tag 字符串传递给打印函数，以便可以简单地识别调用它的不同位置。如果我彻底完成这项工作，我会使用 uintptr_t 和 <inttypes.h> 中的 PRIXPTR 宏来避免为空指针打印 0x0 （我会使用 "0x%.12" PRIXPTR 来打印地址，完全意识到指针可能需要 16 个字节，但并不经常 运行 将其作为一个问题）。
main() 代码连续添加条目 1..10。删除循环以不同的顺序处理条目（9、2、5、8、1、4、7、10、3、6），因此 'remove from start' 和 'remove from end' 都被执行为以及 'remove from middle'.
样本运行
List 0x7f9460c03180: After insert
Item 0x7f9460c03180: 1 (next 0x7f9460c031a0, prev 0x0)
Item 0x7f9460c031a0: 2 (next 0x7f9460c031c0, prev 0x7f9460c03180)
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x7f9460c031a0)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
Item 0x7f9460c03200: 5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c03200)
Item 0x7f9460c03240: 7 (next 0x7f9460c03260, prev 0x7f9460c03220)
Item 0x7f9460c03260: 8 (next 0x7f9460c03280, prev 0x7f9460c03240)
Item 0x7f9460c03280: 9 (next 0x7f9460c032a0, prev 0x7f9460c03260)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03280)
Delete 9
List 0x7f9460c03180: After delete
Item 0x7f9460c03180: 1 (next 0x7f9460c031a0, prev 0x0)
Item 0x7f9460c031a0: 2 (next 0x7f9460c031c0, prev 0x7f9460c03180)
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x7f9460c031a0)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
Item 0x7f9460c03200: 5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c03200)
Item 0x7f9460c03240: 7 (next 0x7f9460c03260, prev 0x7f9460c03220)
Item 0x7f9460c03260: 8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 2
List 0x7f9460c03180: After delete
Item 0x7f9460c03180: 1 (next 0x7f9460c031c0, prev 0x0)
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
Item 0x7f9460c03200: 5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c03200)
Item 0x7f9460c03240: 7 (next 0x7f9460c03260, prev 0x7f9460c03220)
Item 0x7f9460c03260: 8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 5
List 0x7f9460c03180: After delete
Item 0x7f9460c03180: 1 (next 0x7f9460c031c0, prev 0x0)
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
Item 0x7f9460c03240: 7 (next 0x7f9460c03260, prev 0x7f9460c03220)
Item 0x7f9460c03260: 8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 8
List 0x7f9460c03180: After delete
Item 0x7f9460c03180: 1 (next 0x7f9460c031c0, prev 0x0)
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
Item 0x7f9460c03240: 7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 1
List 0x7f9460c031c0: After delete
Item 0x7f9460c031c0: 3 (next 0x7f9460c031e0, prev 0x0)
Item 0x7f9460c031e0: 4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
Item 0x7f9460c03240: 7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 4
List 0x7f9460c031c0: After delete
Item 0x7f9460c031c0: 3 (next 0x7f9460c03220, prev 0x0)
Item 0x7f9460c03220: 6 (next 0x7f9460c03240, prev 0x7f9460c031c0)
Item 0x7f9460c03240: 7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 7
List 0x7f9460c031c0: After delete
Item 0x7f9460c031c0: 3 (next 0x7f9460c03220, prev 0x0)
Item 0x7f9460c03220: 6 (next 0x7f9460c032a0, prev 0x7f9460c031c0)
Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03220)
Delete 10
List 0x7f9460c031c0: After delete
Item 0x7f9460c031c0: 3 (next 0x7f9460c03220, prev 0x0)
Item 0x7f9460c03220: 6 (next 0x0, prev 0x7f9460c031c0)
Delete 3
List 0x7f9460c03220: After delete
Item 0x7f9460c03220: 6 (next 0x0, prev 0x0)
Delete 6
List 0x0: After delete
valgrind 为代码提供了一份干净的健康证明 — 没有访问错误，也没有未释放的内存。
为什么原代码会跳过一个节点？
让我们画一幅画 — ASCII 艺术脱颖而出！
删除节点 2 之前：
+-----+
| top |
+-----+
|
v
+--------+ +--------+ +--------+ +--------+
| |---->| |---->| |---->| |
| Node 1 | | Node 2 | | Node 3 | | Node 4 |
| |<----| |<----| |<----| |
+--------+ +--------+ +--------+ +--------+
递归调用：
递归调用中的top实际存放在'Node 1'->next!
+-----+
| top |
+-----+
|
v
+--------+ +--------+ +--------+ +--------+
| |---->| |---->| |---->| |
| Node 1 | | Node 2 | | Node 3 | | Node 4 |
| |<----| |<----| |<----| |
+--------+ +--------+ +--------+ +--------+
Non-null (*top)->next:
分配：(*top)->next->prev=(*top)->prev;
+-----+
| top |
+-----+
|
v
+--------+ +--------+ +--------+ +--------+
| |---->| |---->| |---->| |
| Node 1 | | Node 2 | | Node 3 | | Node 4 |
| |<-------------------| |<----| |
+--------+ +--------+ +--------+ +--------+
Non-null (*top)->prev:
分配：(*top)->prev->next=(*top)->next;
注意因为top实际上是指向'Node 1'->next的指针，
作业 (*top)->prev->next = (*top)->next 也发生了变化
(*top).
+-----+
| top |
+-----+
|
v
+--------+ +--------+ +--------+ +--------+
| |------------------->| |---->| |
| Node 1 | | Node 2 | | Node 3 | | Node 4 |
| |<-------------------| |<----| |
+--------+ +--------+ +--------+ +--------+
分配 *top 并释放
分配(*top) = (*top)->next;
因为*top也是'Node 1'->next，赋值给*top
也会更改 'Node 1'->next 指向的位置，跳过 'Node 3'。
请注意，向后遍历仍会经过 'Node 3'.
+-----+
| top |
+-----+
|
v
+--------+ +--------+ +--------+
| |---------------------------------->| |
| Node 1 | | Node 3 | | Node 4 |
| |<-------------------| |<----| |
+--------+ +--------+ +--------+
现在解释了损坏的原因。