交换双链表中的节点 [英] Swapping nodes in double linked list
问题描述
我正在尝试实现一个交换双链表的两个节点的函数，以便对当前目录的内容进行排序.但是我的函数似乎删除"了我列表中的一些元素，这是代码:
I'm trying to implement a function that swap two nodes of my double linked list, in order to sort the content of the current directory. But my function seems to 'delete' some elements of my list, here is the code :
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;
}
我看不出这有什么问题?
I can't see what's wrong in this ?
推荐答案
如果你写下你想做什么，你可以实现一个非常简单直接的解决方案.
If you write down what you want to do, you can realize a really simple and straightforward solution.
[[工作代码在答案的最后]]
例如，如果您有两个要交换的节点(例如 A 和 B)，则根据节点的位置有 两种 可能性.它们可以相邻也可以不相邻.
For example, if you have two nodes you want to swap (say A and B), there are two possibilites according to the position of the nodes. They could be adjacent or not.
在相邻的情况下，你可以写:
In the adjacent case, you can write:
[X] - [A] - [B] - [Y]
A->prev = X;
A->next = B;
B->prev = A;
B->next = Y;
如果你用 B 交换 A，你会得到这样的结果:
If you swap A with B, you will end up this:
[X] - [B] - [A] - [Y]
A->prev = B;
A->next = Y;
B->prev = X;
B->next = A;
这就是你想要的.您必须重新排列指针以交换两个节点 A 和 B.
This is what you want to get. You have to rearrange the pointers to swap the two nodes A and B.
如果你使用矩阵形式，规则会更直观:
If you use a matrix form the rule will be more intuitive:
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 度.如果对矩阵中的元素进行索引，就可以组成一个关联表:
Notice, that the swapping matrix rotates 90 degrees clockwise. If you index the elements in the matrix, you can make up an assotiation table:
0 1 -- 2 0
2 3 --/ 3 1
因此，如果将指针存储在数组中，则可以轻松地重新排列它们:
So, if you store the pointers in an array, you can easily rearrange them:
0,1,2,3 -> 2,0,3,1
不相邻的情况
您也可以为不相邻的情况制定类似的规则:
Not adjacent case
You can make up a similar rule for the not adjacent case as well:
[W] - [A] - [X] - ... - [Y] - [B] - [Z]
A->prev = W;
A->next = X;
B->prev = Y;
B->next = Z;
将 A 与 B 交换:
Swap A with B:
[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
指向节点的指针
因为我们正在处理链表，所以改变特定节点中的指针是不够的.我们必须更新指向我们想要交换的节点的指针.该指针位于可交换对象的附近.
Pointers towards the nodes
Because we are dealing with linked lists, it is not enough to change the pointers in the particular nodes. We have to update the pointers that points to our nodes that we want to swap. This pointers are located in the neighbourhood of the swapable objects.
请注意，位于我们的指针指向的节点中的指针始终指向我们自己.
Notice, that the pointers that are located in the nodes that our pointers points to are always pointing to ourselves.
A->prev->next = A
A->next->prev = A
所以当你按照关联规则更新指针后，你只需要将外部指针指向给定的节点，就大功告成了！只要确保邻居当然存在.
So after you update the pointers according to the association rule, you only have to point the outer pointers to the given node, and you are done! Just make sure, that the neighbour exists of course.
您还需要检查节点A是否在节点B之前链接.如果没有，则需要交换两个参数.感谢 kralyk 的提醒.
You need to also check if node A is linked before node B. If not, you need to swap the two parameters. Thanks kralyk for the heads up.
这些信息足以编写执行交换的必要函数.
This is enough information to write the necessary functions that do the swapping.
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);
}
演示工作程序
以下程序的optput:
Working program for presentation
The optput of the following program:
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
Updated link with the corrected swapping function: 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("
");
}
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("
Initial state:");
print(n2);
printf("--------------------------------
");
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("--------------------------------
");
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("--------------------------------
");
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("--------------------------------
");
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("--------------------------------
");
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("--------------------------------
");
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("--------------------------------
");
return 0;
}
这篇关于交换双链表中的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
