代码之家 › 专栏 › 技术社区 › Gibser

交换链表中的节点?

linked-list struct list c

Gibser · 技术社区 · 7 年前

我编写这个函数是为了交换链表中的两个节点,但结果是分段错误。你能查一下吗?谢谢 (我为struct student*做了typedef,作为punt)

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 回复 | 直到 7 年前

mangusta 7 年前

我想这就足够了,基本上与代码的唯一区别是最后一条语句(为了简单起见,没有包含空检查):

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;

}

StereoBucket 7 年前

如果可能,只需交换两个节点的内容,就可以更轻松地交换它们。结果是一样的。如果代码中的其他地方有一个指向所交换节点之一的指针,并且仍然希望它是同一个节点,那么这会造成问题。

总之,回到你的代码。有几件事需要改进。首先,我们需要检查一下 node1 和 node2 不为null,如果不是,我们可以继续,否则退出函数,因为我们无法交换它。交换代码的前4行没有问题,但有两个问题:

之前的节点 点头1 (在交换之前)可能为空,因此访问它的 next 指向 点头2 将导致未定义的行为和可能的崩溃。检查它是否存在,然后执行分配。
您忘记检查之后是否存在节点 点头2 (交换前)如果是,指出 prev 指向 点头1

rustyx 7 年前

它通常有助于可视化双链接列表中的链接,只需将其绘制在一张纸上即可。您会注意到每个节点有4个链接:

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

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

以下方法行不通:

node1->next=node2->next;

这将覆盖旧值 node1-> next .您需要使用临时变量。比如:

#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);
}

注意——在线程环境中,需要某种形式的锁定。

推荐文章