我正在尝试实现一个交换双链表的两个节点的函数，以便对当前目录的内容进行排序。但是我的函数似乎“删除”了我列表中的一些元素，这是代码：
void node_swap(struct s_node *left, struct s_node *right)
{
struct s_node *tmp;
tmp = left->prev;
if (tmp)
{
tmp->next = right;
right->prev = tmp;
}
else
right->prev = NULL;
left->prev = right;
left->next = right->next;
right->next = left;
right->next->prev = left->prev;
}
我看不出这有什么问题？
如果你写下你想做什么，你可以实现一个非常简单直接的解决方案。
[[工作代码在答案末尾]]
例如，如果您有两个要交换的节点（例如 A 和 B），则根据节点的位置有两种可能性。它们可以相邻也可以不相邻。
在相邻的情况下，您可以编写：
[X] - [A] - [B] - [Y]
A->prev = X;
A->next = B;
B->prev = A;
B->next = Y;
如果你用 B 交换 A，你会得到这样的结果：
[X] - [B] - [A] - [Y]
A->prev = B;
A->next = Y;
B->prev = X;
B->next = A;
这就是你想要得到的。您必须重新排列指针以交换两个节点 A 和 B。
如果您使用矩阵形式，规则会更直观：
A B A B
prev X A => prev B X
next B Y next Y A
或者只写矩阵：
X A --\ B X
B Y --/ Y A
请注意，交换矩阵顺时针旋转 90 度。如果对矩阵中的元素进行索引，就可以组成一个关联表：
0 1 --\ 2 0
2 3 --/ 3 1
因此，如果将指针存储在数组中，则可以轻松地重新排列它们：
0,1,2,3 -> 2,0,3,1
您也可以为不相邻的情况制定类似的规则：
[W] - [A] - [X] - ... - [Y] - [B] - [Z]
A->prev = W;
A->next = X;
B->prev = Y;
B->next = Z;
用 B 交换 A：
[W] - [B] - [X] - ... - [Y] - [A] - [Z]
A->prev = Y;
A->next = Z;
B->prev = W;
B->next = X;
A B A B
prev W Y => prev Y W
next X Z next Z X
W Y --\ Y W
X Z --/ Z X
0 1 --\ 1 0
2 3 --/ 3 2
0,1,2,3 -> 1,0,3,2
因为我们正在处理链表，所以改变特定节点中的指针是不够的。我们必须更新指向我们想要交换的节点的指针。该指针位于可交换对象的附近。
请注意，位于我们的指针指向的节点中的指针始终指向我们自己。
A->prev->next = A
A->next->prev = A
所以当你按照关联规则更新指针后，你只需要将外部指针指向给定的节点，就大功告成了！只要确保邻居当然存在。
您还需要检查节点 A 是否在节点 B 之前链接。如果没有，则需要交换两个参数。感谢kralyk 的提醒。
这些信息足以编写进行交换的必要函数。
int areTheyNeighbours(Node A,Node B) {
return ( A->next == B && B->prev == A ) || ( A->prev == B && B->next == A );
}
void refreshOuterPointers(Node A) {
if (A->prev != NULL)
A->prev->next = A;
if (A->next != NULL)
A->next->prev = A;
}
void swap(Node A,Node B) {
Node swapperVector[4];
Node temp;
if (A == B) return;
if (B->next == A) {
temp = A;
A = B;
B = temp;
}
swapperVector[0] = A->prev;
swapperVector[1] = B->prev;
swapperVector[2] = A->next;
swapperVector[3] = B->next;
if (areTheyNeighbours(A,B)) {
A->prev = swapperVector[2];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[1];
} else {
A->prev = swapperVector[1];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[2];
}
refreshOuterPointers(A);
refreshOuterPointers(B);
}
以下程序的选项：
Initial state: [1]-[2]-[3]-[4]
--------------------------------
[1] <-> [2]: [2]-[1]-[3]-[4]
[1] <-> [2]: [1]-[2]-[3]-[4]
[2] <-> [1]: [2]-[1]-[3]-[4]
[2] <-> [1]: [1]-[2]-[3]-[4]
--------------------------------
[1] <-> [3]: [3]-[2]-[1]-[4]
[1] <-> [3]: [1]-[2]-[3]-[4]
[3] <-> [1]: [3]-[2]-[1]-[4]
[3] <-> [1]: [1]-[2]-[3]-[4]
--------------------------------
[1] <-> [4]: [4]-[2]-[3]-[1]
[1] <-> [4]: [1]-[2]-[3]-[4]
[4] <-> [1]: [4]-[2]-[3]-[1]
[4] <-> [1]: [1]-[2]-[3]-[4]
--------------------------------
[2] <-> [3]: [1]-[3]-[2]-[4]
[2] <-> [3]: [1]-[2]-[3]-[4]
[3] <-> [2]: [1]-[3]-[2]-[4]
[3] <-> [2]: [1]-[2]-[3]-[4]
--------------------------------
[2] <-> [4]: [1]-[4]-[3]-[2]
[2] <-> [4]: [1]-[2]-[3]-[4]
[4] <-> [2]: [1]-[4]-[3]-[2]
[4] <-> [2]: [1]-[2]-[3]-[4]
--------------------------------
[3] <-> [4]: [1]-[2]-[4]-[3]
[3] <-> [4]: [1]-[2]-[3]-[4]
[4] <-> [3]: [1]-[2]-[4]-[3]
[4] <-> [3]: [1]-[2]-[3]-[4]
您可以通过以下链接立即运行代码：http :
//codepad.org/UHcmmag1
使用更正的交换功能更新链接：http : //codepad.org/LbRYjvPr
#include <stdio.h>
#include <stdlib.h>
typedef struct node_v {
int id;
struct node_v* prev;
struct node_v* next;
} Node_v;
typedef Node_v* Node;
void print(Node node) {
while (node->prev != NULL)
node = node->prev;
printf(" [%d]",node->id);
while (node->next != NULL) {
node = node->next;
printf("-[%d]",node->id);
}
printf("\n");
}
void connect(Node first,Node second) {
first->next = second;
second->prev = first;
}
Node createNode(int id) {
Node node = (Node)malloc(sizeof(Node_v));
node->id = id;
node->prev = NULL;
node->next = NULL;
return node;
}
int areTheyNeighbours(Node A,Node B) {
return ( A->next == B && B->prev == A ) || ( A->prev == B && B->next == A );
}
void refreshOuterPointers(Node A) {
if (A->prev != NULL)
A->prev->next = A;
if (A->next != NULL)
A->next->prev = A;
}
void swap(Node A,Node B) {
Node swapperVector[4];
Node temp;
if (A == B) return;
if (B->next == A) {
temp = A;
A = B;
B = temp;
}
swapperVector[0] = A->prev;
swapperVector[1] = B->prev;
swapperVector[2] = A->next;
swapperVector[3] = B->next;
if (areTheyNeighbours(A,B)) {
A->prev = swapperVector[2];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[1];
} else {
A->prev = swapperVector[1];
B->prev = swapperVector[0];
A->next = swapperVector[3];
B->next = swapperVector[2];
}
refreshOuterPointers(A);
refreshOuterPointers(B);
}
int main() {
Node n1 = createNode(1);
Node n2 = createNode(2);
Node n3 = createNode(3);
Node n4 = createNode(4);
connect(n1,n2);
connect(n2,n3);
connect(n3,n4);
printf("\nInitial state:");
print(n2);
printf("--------------------------------\n");
printf("[1] <-> [2]: ");
swap(n1, n2);
print(n1);
printf("[1] <-> [2]: ");
swap(n1, n2);
print(n1);
printf("[2] <-> [1]: ");
swap(n2, n1);
print(n1);
printf("[2] <-> [1]: ");
swap(n2, n1);
print(n1);
printf("--------------------------------\n");
printf("[1] <-> [3]: ");
swap(n1, n3);
print(n2);
printf("[1] <-> [3]: ");
swap(n1, n3);
print(n2);
printf("[3] <-> [1]: ");
swap(n3, n1);
print(n2);
printf("[3] <-> [1]: ");
swap(n3, n1);
print(n2);
printf("--------------------------------\n");
printf("[1] <-> [4]: ");
swap(n1, n4);
print(n3);
printf("[1] <-> [4]: ");
swap(n1, n4);
print(n3);
printf("[4] <-> [1]: ");
swap(n4, n1);
print(n3);
printf("[4] <-> [1]: ");
swap(n4, n1);
print(n3);
printf("--------------------------------\n");
printf("[2] <-> [3]: ");
swap(n2, n3);
print(n3);
printf("[2] <-> [3]: ");
swap(n2, n3);
print(n3);
printf("[3] <-> [2]: ");
swap(n3, n2);
print(n3);
printf("[3] <-> [2]: ");
swap(n3, n2);
print(n3);
printf("--------------------------------\n");
printf("[2] <-> [4]: ");
swap(n2, n4);
print(n3);
printf("[2] <-> [4]: ");
swap(n2, n4);
print(n3);
printf("[4] <-> [2]: ");
swap(n4, n2);
print(n3);
printf("[4] <-> [2]: ");
swap(n4, n2);
print(n3);
printf("--------------------------------\n");
printf("[3] <-> [4]: ");
swap(n3, n4);
print(n4);
printf("[3] <-> [4]: ");
swap(n3, n4);
print(n4);
printf("[4] <-> [3]: ");
swap(n4, n3);
print(n4);
printf("[4] <-> [3]: ");
swap(n4, n3);
print(n4);
printf("--------------------------------\n");
return 0;
}
假设这是您的初始结构TMP -> L -> R -> X您没有正确更新 X->prev。在你的最后一行right->next->prev = left->prev;right->next 是左边。所以你正在更新 left 的 prev，这是错误的。相反，你应该做
if(left->next != null)
left->next(which is X)->prev = left
所以，我认为这会奏效
void node_swap(struct s_node *left, struct s_node *right)
{
struct s_node *tmp;
tmp = left->prev;
if (tmp)
tmp->next = right;
right->prev = tmp;
left->prev = right;
left->next = right->next;
right->next = left;
if(left->next != null)
left->next(which is X)->prev = left
}