我是否正确地为 C 中的双向链表实现了此删除节点函数?

Question

我正在学习双向链表。我已经实现了一个正常工作的删除节点功能，并且旨在工作，无论要删除的节点是第一个节点、最后一个节点还是介于两者之间的任何节点。但是，我想知道我的逻辑是否正确(我应该说是有效的(。我在确定正确执行此功能的明确示例时遇到了一些麻烦。 此链表不会跟踪尾巴作为仅供参考。任何反馈将不胜感激。

Node *removeNode(Node *head, int d)
{
Node *curr = head;
while (curr != NULL){
if (curr->data == d){
if (curr->prev == NULL && curr->next == NULL){
free(curr);
head = NULL;
return head;
} else if (curr->prev == NULL){
curr->next->prev = NULL;
head = curr->next;
free(curr);
return head;
} else if (curr->next == NULL){
curr->prev->next = NULL;
free(curr);
return head;
} else if (curr->prev != NULL && curr->next != NULL){
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
free(curr);
return head;
}
} else if (curr->data != d){
curr = curr->next;
}           
}
return head;
}

Answer 1

您当前的代码工作正常;这很好。 Valgrind 给了它一个干净的健康账单，至少在使用我创建的支持代码运行时是这样。 但是，它可以简化。

这就是我想出的：

#include <stdlib.h>
#include <stdio.h>
typedef struct Node Node;
struct Node
{
int data;
Node *prev;
Node *next;
};
static Node *removeNode(Node *head, int d)
{
Node *curr = head;
while (curr != NULL)
{
if (curr->data != d)
curr = curr->next;
else
{
if (curr->prev != NULL)
curr->prev->next = curr->next;
else
head = curr->next;
if (curr->next != NULL)
curr->next->prev = curr->prev;
free(curr);
return head;
}
}
return head;
}
static Node *addNodeAtHead(Node *head, int d)
{
Node *item = malloc(sizeof(*item));
if (item != 0)
{
item->next = head;
item->prev = NULL;
if (head != 0)
head->prev = item;
item->data = d;
}
return item;
}
static void dumpList(const char *tag, Node *head)
{
printf("%s:", tag);
while (head != 0)
{
printf(" %d", head->data);
head = head->next;
}
putchar('n');
}
int main(void)
{
Node *head = 0;
head = addNodeAtHead(head, 23);
head = addNodeAtHead(head, 43);
head = addNodeAtHead(head, 73);
head = addNodeAtHead(head, 13);
head = addNodeAtHead(head, 33);
dumpList("Full", head);
head = removeNode(head, 33);
dumpList("Lost 33", head);
head = removeNode(head, 23);
dumpList("Lost 23", head);
head = removeNode(head, 13);
dumpList("Lost 13", head);
head = removeNode(head, 34);
dumpList("Lost 34", head);
head = removeNode(head, 43);
dumpList("Lost 43", head);
head = removeNode(head, 73);
dumpList("Lost 73", head);
head = removeNode(head, 37);
dumpList("Lost 37", head);
return 0;
}

根本区别在于，上面的代码在最大可行的情况下避免了专门处理特殊情况。

如果上一个节点不为空

• ，则调整前一个节点的下一个指针指向下一个节点(下一个节点是否为空并不重要(;
• 否则，头部必须更改为指向下一个节点(下一个节点是否为 null 仍然无关紧要(。
• 如果下一个节点不为 null，则调整下一个节点的上一个指针以指向上一个节点(并且上一个节点是否为 null 并不重要(。
• 然后释放当前节点并返回头节点。

在运行 macOS Sierra 10.12.5 的 Mac 上运行时的示例输出：

$ make dl61 && valgrind --suppressions=etc/suppressions-macos-10.12.5 -- ./dl61
gcc -O3 -g -std=c11 -Wall -Wextra -Werror -Wmissing-prototypes -Wstrict-prototypes dl61.c -o dl61 
==3505== Memcheck, a memory error detector
==3505== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3505== Using Valgrind-3.13.0.SVN and LibVEX; rerun with -h for copyright info
==3505== Command: ./dl61
==3505== 
Full: 33 13 73 43 23
Lost 33: 13 73 43 23
Lost 23: 13 73 43
Lost 13: 73 43
Lost 34: 73 43
Lost 43: 73
Lost 73:
Lost 37:
==3505== 
==3505== HEAP SUMMARY:
==3505==     in use at exit: 22,308 bytes in 163 blocks
==3505==   total heap usage: 184 allocs, 21 frees, 28,572 bytes allocated
==3505== 
==3505== LEAK SUMMARY:
==3505==    definitely lost: 0 bytes in 0 blocks
==3505==    indirectly lost: 0 bytes in 0 blocks
==3505==      possibly lost: 0 bytes in 0 blocks
==3505==    still reachable: 0 bytes in 0 blocks
==3505==         suppressed: 22,308 bytes in 163 blocks
==3505== 
==3505== For counts of detected and suppressed errors, rerun with: -v
==3505== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 5 from 5)
$

代码很少好到无法改进。 我认为removeNode()的这种变体更整洁一些。 它的循环只担心遍历列表以查找要删除的(第一个(节点。 然后，如果找到一个节点，它会在循环主体之外删除它。 此代码也需要编写的<assert.h>标头(但尚未触发(。

static Node *removeNode(Node *head, int d)
{
Node *curr = head;
while (curr != NULL && curr->data != d)
curr = curr->next;
if (curr != NULL)
{
assert(curr->data == d);
if (curr->prev != NULL)
curr->prev->next = curr->next;
else
head = curr->next;
if (curr->next != NULL)
curr->next->prev = curr->prev;
free(curr);
}
return head;
}

结果和以前一样。