在双链表中交换节点 [英] 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.
[[工作代码在答案的结尾]]
[[working code is at the end of the answer]]
例如，如果您有两个节点要交换(例如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;
如果您将A与B交换，您将得到以下结果:
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;
用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
指向节点的指针
由于我们正在处理链表，因此仅更改特定节点中的指针是不够的.我们必须更新指向我们要交换的节点的指针.该指针位于可交换对象的附近.
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("\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;
}
这篇关于在双链表中交换节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
