在链表中交换节点?

I wrote this function in order to swap 2 nodes in a linked list, but the result is a Segmentation Fault. Can you check it? Thanks. (I did typedef for struct student* as punt)

我编写这个函数是为了在链表中交换两个节点，但结果是一个分割错误。你能检查吗?谢谢。(我对struct student*做了typedef)

void swap_node(punt node1, punt node2)
{

 node1->next=node2->next;
 node2->next=node1;
 node2->prev=node1->prev;
 node1->prev=node2;
 (node2->prev)->next=node2;

}

3 个解决方案

#1

When possible, two nodes are more easily swapped by only swapping their contents. The result is identical. This would pose a problem if somewhere else in your code you held a pointer to one of the nodes you swapped and are still expecting it to be the same node.

在可能的情况下，两个节点更容易交换，只交换它们的内容。结果是相同的。如果您的代码中有一个指向您交换的节点的指针，并且仍然期望它是相同的节点，那么这个问题就会产生问题。

Anyway, back to your code. There are a few things that need refinement. Firstly, we need to check if node1 and node2 are not null and if they aren't we can proceed, otherwise exit the function as we can't swap this. The first 4 lines of your swapping code are alright, but here's two issues:

不管怎样，回到你的代码。有一些事情需要改进。首先，我们需要检查node1和node2是否为空，如果它们不是，我们可以继续，否则退出函数，因为我们不能交换这个。交换代码的前4行很好，但这里有两个问题:

Node that was before node1 (prior to swapping) might be null, and thus accessing it's next pointer to point at node2 would result in undefined behaviour and likely crash. Check if it exists and then perform the assignment.
节点在node1之前(交换之前)可能是null，因此访问它的下一个指针指向node2会导致未定义的行为和可能的崩溃。检查是否存在，然后执行任务。
You forgot to check if there exists a node after node2 (prior to swapping) and if so, point it's prev pointer at node1
您忘记检查node2(在交换之前)是否存在一个节点，如果是这样，那么在node1上指向它的prev指针。

#2

I guess this would be sufficient, basically the only difference from your code is the last statement (did not include null checks for simplicity):

我想这就足够了，基本上唯一的区别就是您的代码是最后一个语句(不包含简单的null检查):

void swap_node(punt node1, punt node2)
{

node1->next=node2->next;
node2->next=node1;
(node1->prev)->next=node2;
node2->prev=node1->prev;
node1->prev=node2;
(node1->next)->prev=node1;

}

#3

It usually helps to visualize the links in a doubly linked list, just draw it on a piece of paper. You'll notice 4 links per node:

它通常有助于在一个双向链表中可视化链接，就在一张纸上画出来。你会注意到每个节点有4个链接:

node->next
node->next->prev
node->prev
node->prev->next

So to swap two unrelated nodes you need to swap the 4 links.

因此，要交换两个不相关的节点，您需要交换4个链接。

The following will not work:

以下是行不通的:

node1->next=node2->next;

This overwrites the old value node1-> next. You need to use a temporary variable instead. Something like this:

这重写了旧的值node1->。您需要使用临时变量。是这样的:

#define SWAP_PTR(a,b) { void* tmp = b; b = a; a = tmp; }

void swap_node(punt node1, punt node2)
{
  SWAP_PTR(node1->next, node2->next);
  SWAP_PTR(node1->next->prev, node2->next->prev);
  SWAP_PTR(node1->prev, node2->prev);
  SWAP_PTR(node1->prev->next, node2->prev->next);
}

Note - in a threaded environment you'll need some form of locking.

注意:在线程环境中，您需要某种形式的锁定。

#1

Node that was before node1 (prior to swapping) might be null, and thus accessing it's next pointer to point at node2 would result in undefined behaviour and likely crash. Check if it exists and then perform the assignment.
节点在node1之前(交换之前)可能是null，因此访问它的下一个指针指向node2会导致未定义的行为和可能的崩溃。检查是否存在，然后执行任务。
You forgot to check if there exists a node after node2 (prior to swapping) and if so, point it's prev pointer at node1
您忘记检查node2(在交换之前)是否存在一个节点，如果是这样，那么在node1上指向它的prev指针。

#2