交换双链表中的节点
我正在尝试实现一个交换双链表的两个节点的函数，以便对当前目录的内容进行排序。 但我的function似乎’删除’我的列表中的一些元素，这里是代码：
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; } 我看不出这有什么不对？
假设这是您的初始结构TMP -> L -> R -> X您没有正确更新X-> prev。 在你的最后一行right->next->prev = left->prev; 对 – >接下来就是了。 所以你要更新左边的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 }
从您问题中发布的代码中，我推断出您的函数假设您正在交换相邻节点。
请尝试以下方法：
if ( left->prev ) left->prev->next = right; if ( right->next ) right->next->prev = left; left->next = right->next; right->prev = left->prev; right->next = left; left->prev = right;
编辑：在原始问题中发表评论后，执行以下操作要快得多：
char* tmpName = right->name; right->name = left->name; left->name = tmpName;
如果你写下你想做的事情，你就可以实现一个非常简单直接的解决方案。
[[工作代码在答案的最后]]
例如，如果您想要交换两个节点（比如A和B） ，根据节点的位置有两个可能性。 他们可能相邻或不相邻。
相邻案例
在相邻的情况下，您可以写：
[X] - [A] - [B] - [Y] A->prev = X; A->next = B; B->prev = A; B->next = Y;
如果您将A与B交换，您最终会：
[X] - [B] - [A] - [Y] A->prev = B; A->next = Y; B->prev = X; B->next = A;
这就是你想要的。 您必须重新排列指针以交换两个节点A和B.
如果您使用矩阵forms，则规则将更直观：
ABAB prev XA => prev BX next BY next YA
或者只写单独的矩阵：
XA --\ BX BY --/ YA
请注意，交换矩阵顺时针旋转90度。 如果索引矩阵中的元素，则可以组成一个assotiation表：
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; ABAB prev WY => prev YW next XZ next ZX WY --\ YW XZ --/ ZX 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); }
介绍的工作计划
以下程序的optput：
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
使用更正的交换function更新了链接： http ： //codepad.org/LbRYjvPr
#include #include 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; }
非常短的代码非常有效，花费了2个小时：
你需要交换两个节点……
但也要确保在两个方向上保留2个交换节点与第三个和最后一个节点之间存在的链接。
static inline void swap_list(t_lst **lst) { t_lst *tmp; if ((*lst)->next) // you need to make sure you have at least 2 items in your list { tmp = *lst; // let's store 1st node's address, that will become the second one after the swap *lst = (*lst)->next; // Reversely our 2nd one will become the 1st one after the swap. It also allows us to set the beginning of our list. /* ** Now you need to work on the 6 links that exist : between the last elem (that may be the 2nd one) ** and the 1st one you have 2 links (next and prev), same between the 1st one ** and the 2nd one (2 links again) and finally 2 links between the 2nd one ** and the 3d one (that may be the first node) */ tmp->next = (*lst)->next; // tmp will have second position and needs to point to the third elem. Since *lst is now (*lst)->next, here we refer to the 3rd elem. tmp->next->prev = tmp; // we have then to tell this third elem where stands the second one with this line. (*lst)->prev = tmp->prev; // before destroying the link to last node that tmp contains, we assign it to the future 1st elem of our list tmp->prev = *lst; // now we can safely tell the second node its link to the first. (*lst)->next = tmp; // and reversely tells where is the second elem after the first. (*lst)->prev->next = *lst; // finally we tell the last node where it the first one. } }
我希望它可以提供帮助。
ps：万一你想知道：
typedef struct s_lst { void *data; // or a more specific type if you wish struct s_lst *prev; struct s_lst *next; } t_lst;