我被赋予了一项任务，即编写一个函数来反转双向链表。我编写了该函数并将其命名为reverse()。函数给出如下：
struct node* reverse(struct node** head_ref){
struct node *current=*head_ref;
struct node *tempNode=(struct node *)malloc(sizeof(struct node));
if(current->next == NULL){
return current;
}
while(current->next != NULL){
//tempNode=current;
tempNode->key=current->key;
tempNode->data=current->data;
tempNode->next=current->next;
tempNode->prev=current->prev;
current->next=current->prev;
current->prev=tempNode->next;
current=tempNode->next;
}
current->next=current->prev;
current->prev=NULL;
*head_ref =current;
return current;
}
其中，struct node** head_ref参数将头节点&head的引用作为参数。该功能工作正常。但我在这里的问题是而不是做
tempNode->key=current->key;
tempNode->data=current->data;
tempNode->next=current->next;
tempNode->prev=current->prev;
为什么我不能只做tempNode=current;？ 当我尝试这样做时，我的函数没有产生预期的结果。
tempnode = current分配指针，这意味着tempnode和currect都将指向内存中的同一地址。
tempnode = curr; // tempnode = 1036;
1020 1028 1036 1044
+------+------+------+------+
| | | curr | |
+------+------+------+------+
^
|
tempnode ---------
你只需要 tempnode 具有相同的值，所以你必须做deep copy，它到底在做什么。
tempNode->key=current->key;
tempNode->data=current->data;
tempNode->next=current->next; // You just copy the content of node
tempNode->prev=current->prev; // But they are in another part of memory
120 .... 1028 1036 1044
+------+------+------+------+------+
| temp | | curr | | |
+------+------+------+------+------+
它们具有相同的值，但它们指向另一个地址。
我可以看到你正在过度使用一些指针，你不应该这样做，因为你正在失去分配内存的地址 ->你不能再释放它了。
存储到某个临时变量，从节点中删除它后，您可以释放该内存。
请注意，您实际上不需要设置tempNode->key或tempNode->data;您可以将这些字段保留在当前节点中。但是，如果你做了结构赋值(*tempNode = *current;(而不是指针赋值(tempNode = current;(，你就没问题了。
请注意，每次反转列表时，代码都会泄漏节点;您不会释放分配的tempNode(可能是因为您用指针赋值覆盖了分配的空间(。最好不要将malloc()用于如此小的结构;只需使用struct node tempNode;，然后按tempNode.next等tempNode = *current;和引用成员。这样就没有必要释放它了。
事实上，鉴于实际上没有必要复制密钥和数据，我可能会使用struct node *old_next = current->next;和struct node *old_prev = current->prev;然后翻转链接：current->prev = old_next; current->next = old_prev; current = old_next;，如所示代码所示。 跟踪old_curr以便可以"返回"正确的值(通过head_ref分配给调用代码中的指针(是此代码中的另一个问题。 请注意，它设法避免将空列表和单条目列表特殊大小写。
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
struct node
{
int key;
int data;
struct node *prev;
struct node *next;
};
static struct node *reverse(struct node **head_ref)
{
struct node *current = *head_ref;
struct node *old_curr = 0;
while (current != 0)
{
struct node *old_next = current->next;
struct node *old_prev = current->prev;
current->prev = old_next;
current->next = old_prev;
old_curr = current;
current = old_next;
}
*head_ref = old_curr;
return current;
}
static struct node *create(int key, int data)
{
struct node *p = malloc(sizeof(*p));
if (p != 0)
{
p->key = key;
p->data = data;
p->next = 0;
p->prev = 0;
}
return p;
}
static struct node *insert_head(struct node *head, int key, int data)
{
struct node *n = create(key, data);
assert(n != 0);
if (head != 0)
head->prev = n;
n->next = head;
return n;
}
static void print_list(const char *tag, struct node *head)
{
printf("%s: [", tag);
const char *pad = "";
while (head != 0)
{
printf("%s(%d => %d)", pad, head->key, head->data);
pad = ",";
head = head->next;
}
printf("]n");
}
static void free_list(struct node *head)
{
while (head != 0)
{
struct node *next = head->next;
free(head);
head = next;
}
}
int main(void)
{
for (int size = 0; size < 10; size++)
{
struct node *list = 0;
for (int i = 0; i < size; i++)
list = insert_head(list, i, (7 * i + 4 + size) % 10);
print_list("New list", list);
reverse(&list);
print_list("Rev list", list);
free_list(list);
}
return 0;
}
运行时，程序生成输出：
New list: []
Rev list: []
New list: [(0 => 5)]
Rev list: [(0 => 5)]
New list: [(1 => 3),(0 => 6)]
Rev list: [(0 => 6),(1 => 3)]
New list: [(2 => 1),(1 => 4),(0 => 7)]
Rev list: [(0 => 7),(1 => 4),(2 => 1)]
New list: [(3 => 9),(2 => 2),(1 => 5),(0 => 8)]
Rev list: [(0 => 8),(1 => 5),(2 => 2),(3 => 9)]
New list: [(4 => 7),(3 => 0),(2 => 3),(1 => 6),(0 => 9)]
Rev list: [(0 => 9),(1 => 6),(2 => 3),(3 => 0),(4 => 7)]
New list: [(5 => 5),(4 => 8),(3 => 1),(2 => 4),(1 => 7),(0 => 0)]
Rev list: [(0 => 0),(1 => 7),(2 => 4),(3 => 1),(4 => 8),(5 => 5)]
New list: [(6 => 3),(5 => 6),(4 => 9),(3 => 2),(2 => 5),(1 => 8),(0 => 1)]
Rev list: [(0 => 1),(1 => 8),(2 => 5),(3 => 2),(4 => 9),(5 => 6),(6 => 3)]
New list: [(7 => 1),(6 => 4),(5 => 7),(4 => 0),(3 => 3),(2 => 6),(1 => 9),(0 => 2)]
Rev list: [(0 => 2),(1 => 9),(2 => 6),(3 => 3),(4 => 0),(5 => 7),(6 => 4),(7 => 1)]
New list: [(8 => 9),(7 => 2),(6 => 5),(5 => 8),(4 => 1),(3 => 4),(2 => 7),(1 => 0),(0 => 3)]
Rev list: [(0 => 3),(1 => 0),(2 => 7),(3 => 4),(4 => 1),(5 => 8),(6 => 5),(7 => 2),(8 => 9)]
请注意，我必须为 16 行函数创建 34 行支持代码。 当然，这并不是那么难，但是MCVE(最小，完整，可验证的示例(可以提供该基础架构，因此我不必这样做。 请记住在将来创建MCVE。