交换单向链表中的节点 [英] Swap nodes in a singly-linked list
问题描述
我正在尝试交换两个节点.例如，如果节点是 a 和 b 我正在传递指针(a-1)->next 和 (b-1)->next 基本上是节点 a 和 b.
void swap(struct stack **a,struct stack **b){结构栈 *temp1 = *a, *temp2 = *b, *temp3 = *b;*a = *b;(*b)->next = (temp1)->next;温度 2 = 温度 1；(temp2)->next = temp3->next;}我做错了什么?当我在调用函数后尝试打印节点时，它是一个无限循环.请帮忙.
为什么是无限循环?
无限循环是因为列表中的自循环after调用swap()函数.在 swap() 代码下面的语句是错误的.
(*b)->next = (temp1)->next;为什么?:因为在swap()函数中的赋值语句之后temp1的next开始指向b节点.并且 node[b] 的 next 在循环中指向自身.而自循环是无限循环的原因，在您遍历链表的代码中的某处.
我在下面绘制以展示 swap() 如何逐步工作.可能这有助于您了解您的错误:
你没有提到，但我假设链表在 a 和 b 之间具有以下关系:(阅读红色评论)
(第 1 步):
+----+----+----+ +---+----+----+|一个|----->|二 |+----+----+----+ +---+---+-----+^ ^ ^ ^|||||*一个 |*b||temp1 temp2, temp3在分配给临时变量之后"(第 2 步):^|*a = *b |*a "<--- 下一步"(第 3 步):有缺陷的语句
(*b)->next = (temp1)->next;更改链接:(temp1)->next; 是`two` 节点""*b 是`two`，所以自循环"+----+----+----+ +---+----+----+ <---||一 ||两个|-----|+----+----+----+ +---+---+-----+^ ^ ^ ^||||||*b *a||temp1 temp2, temp3分配给 temp"后参见 (temp1)->next; 实际上是 b 并且您正在分配 (*b)->next = (*b) 通过执行 (*b)->next = (temp1)->next; 从而添加一个自循环.
(第 4 步):
我认为通过图表你可以很容易地理解你的 swap() 代码的最后两行在做什么:
temp2 = temp1;(temp2)->next = temp3->next;以下是我对这两行的图表:
temp2 = temp1;+----+----+----+ +---+----+----+ <---||一 ||两个|-----|"<--- 自循环"+----+----+----+ +---+---+-----+^ ^ ^ ^||||||*b *a||温度 2 = 温度 1；温度3(第 5 步): 函数的最后一行 swap() 左循环如下:
(temp2)->next = temp3->next;你的代码的最后一行"+----+----+----+ +---+----+----+ <---||一个|----->|两个|-----|"<-- 自循环"+----+----+----+ +---+---+-----+^ ^ ^ ^||||||*b *a||温度 2 = 温度 1；温度3所以循环仍然在 two 节点所以无限循环.
如何交换单链表中的两个节点?
一种方法是交换节点的数据，而不是交换节点在链表中的位置(正如我对您的问题的评论).但是您想交换节点在列表中的位置.
嗯，这很好！如果节点数据较大，那么此时最好交换节点的位置而不是交换节点的数据(交换数据将是一个糟糕的选择)
因为您有单链表，要交换列表中的任意两个节点，您需要还有前一个节点地址.(这是您在交换逻辑中没有考虑的点)
为什么需要以前的指针?:
假设在一些成功的插入(推送)操作之后，你的列表变成如下:
0 <--------TOP - 头"9 <--p26 <--q5水平图-假设你想交换两个节点(q)和(p):
+---+ +---+ +---+ +---+ +---+|0 |--->|9 |--->|2 |--->|6 |--->|5 |---+---+ +---+ +---+ +---+ +---+ |^ ^ ^ 空||||(q) (p)(头)正如我所说，要交换我们需要先前的指针.你需要考虑以下
(理论上，我正在为特定节点编写 (p) 和 (q) 只是为了保持解释简单.但我的实现是通用的):
在前一个指针列表中:
node[0] 指向 node[9] 即 (q)，并且node[2] 指向 node[6] 即 (p)还有
node[9] 指向 node[2]节点[6]指向节点[5]注意:如果你想交换两个节点，比如 node[ 9 ] 和 node[ 6 ] 那么你应该使用这两个节点之前的节点.
例如:两个交换node[9]和[6]，还需要改变node[0]的next指针和next指针node[2] 在上图中.
交换这两个节点后的列表会怎样?
+---+ +---+ +---+ +---+ +---+|0 |--->|6 |--->|2 |--->|9 |--->|5 |---+---+ +---+ +---+ +---+ +---+ |^ ^ ^ 空||||(p) (q)(头)现在在以前的节点 [o] 和 [2] 中是什么?
交换后，In list previous pointers
node[0] 指向 node[6] 即 (q)，并且node[2] 指向 node[9] 即 (p)和
node[9] 指向 node[5]节点[6]指向节点[2]所以如果你想交换两个节点；前一个节点也有影响，因为列表是单链表，所以你也需要前一个指针.
如何找到以前的节点指针?
假设你想交换任意两个节点 node[p] 和 node[q] 那么你可以使用 head pointer 来找到前一个节点.
所以交换函数语法(在我的实现中)就像:
void swap(struct stack **head,//头节点struct stack **a,//第一个要交换的候选节点结构栈**b);//第一个要交换的候选节点你会调用这样的函数:
swap(&head, &p, &q);定义:(要理解代码，请阅读我几乎在每一行添加的注释)
void swap(struct stack **head,结构栈**a，结构栈**b){//首先检查一个agrgument是否为空if( (*head) == NULL ||//空列表(*a) == NULL ||(*b) == NULL){//一个节点为空//没什么可交换的，只是返回printf("
没什么可交换的，只需返回
");返回;}//查找前一个节点struct stack* pre_a = get_prevnd(*head, *a);struct stack* pre_b = get_prevnd(*head, *b);//现在交换上一个节点的下一个if(pre_a) pre_a->next = (*b);//a 的前一个变成 b 的前一个，并且if(pre_b) pre_b->next = (*a);//b 的前一个变成 a 的前一个//现在交换候选节点的下一个字段结构栈*临时=空；temp = (*a)->next;(*a)->next = (*b)->next;(*b)->next = temp;//改变头部:如果任何节点是头部if((*head)==(*a))*头 = *b;别的if((*head)==(*b))*头= *一;}在swap() 函数中，您可以注意到我调用了一个辅助函数get_prevnd(, );.此函数返回列表中前一个节点的地址.在函数 get_prevnd(, ); 中，第一个参数是列表头，第二个参数是您要查找的节点.
//查找上一个节点 function()结构栈* get_prevnd(结构栈*头，结构栈* a){如果(头== a){//node[a] 是第一个节点返回空；}结构栈*临时=头；//temp 是当前节点结构栈* pre_a = NULL;while(temp && temp!=a){//搜索而没有到达终点或节点pre_a = 温度；//找到上一个节点temp = temp->next;}if(temp!=a){//node[a] 不在列表中fprintf(stderr, "
error: node not found!
");退出(EXIT_FAILURE)；//错误的退出技术()}返回 pre_a;}幸运的是代码正在运行:).以下是此代码的在线测试链接.我已经测试了各种输入.
CodePad:在单链表中交换节点.请检查输出.
抱歉英语不好
I am trying to swap two nodes. For example if the nodes are a and b I am passing the pointers
(a-1)->next and (b-1)->next which are basically nodes a and b.
void swap(struct stack **a,struct stack **b)
{
struct stack *temp1 = *a, *temp2 = *b, *temp3 = *b;
*a = *b;
(*b)->next = (temp1)->next;
temp2 = temp1;
(temp2)->next = temp3->next;
}
What am I doing wrong? When I am trying to print the nodes after calling the function it's an infinite loop. Please help.
Why Infinite loop?
Infinite loop is because of self loop in your list after calling swap() function. In swap() code following statement is buggy.
(*b)->next = (temp1)->next;
Why?: Because after the assignment statement in swap() function temp1's next starts pointing to b node. And node[b]'s next point to itself in a loop. And the self loop is reason for infinite loop, somewhere in your code where you traverse linked list.
Below I drawn to show how swap() works step-by-step. May be this help you to understand your error:
You didn't mention but I am assuming linked list having following relation between a and b: (read red comments)
(step-1):
+----+----+----+ +---+----+----+
| one |----->| two |
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| *a | *b
| |
temp1 temp2, temp3 "after assignment to temp variables"
(step-2): ^
|
*a = *b | *a "<--- next step"
(step-3): The buggy statement
(*b)->next = (temp1)->next; "Change link: (temp1)->next; is `two` node"
" *b is `two`, So Self loop"
+----+----+----+ +---+----+----+ <---|
| one | | two |-----|
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp1 temp2, temp3 " after assignment to temp"
See (temp1)->next; is actually b and you are assigning (*b)->next = (*b) by doing (*b)->next = (temp1)->next; hence adding a self loop.
(step-4):
I think with the diagram you can easily understand what last two lines of your swap() code are doing:
temp2 = temp1;
(temp2)->next = temp3->next;
Following is my diagram for this two lines:
temp2 = temp1;
+----+----+----+ +---+----+----+ <---|
| one | | two |-----| "<--- Self loop"
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp2 = temp1; temp3
(step-5): Even last line of your function swap() left loop as below:
(temp2)->next = temp3->next; " last line of your code"
+----+----+----+ +---+----+----+ <---|
| one |----->| two |-----| "<-- Self loop"
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp2 = temp1; temp3
So loop still there at two node so infinite loop.
How to swap two nodes in single linked list?
One way is swap node's data instead of swapping node's position it self in linked list (as I commented to your question). But you wants to swap node's position in list.
Well this good! if node data size is larger, that time its better to swap node's position rather then swap node's data(swapping data will be bad choice)
Because you having single linked list, to swap any two arbitrary nodes in list you need there previous node addresses too. (this is the point you don't consider in your swapping logic)
WHY need previous pointers?:
Suppose after some successful insert(push) operations, your list becomes as follows:
0 <--------TOP - "head"
9 <--p
2
6 <--q
5
A horizontal diagram- Suppose you want to swap say two nodes (q) and (p):
+---+ +---+ +---+ +---+ +---+
| 0 |--->| 9 |--->| 2 |--->| 6 |--->| 5 |---
+---+ +---+ +---+ +---+ +---+ |
^ ^ ^ null
| | |
| (q) (p)
(head)
As I said, to swap we need previous pointers. You need to think about following
(In theory, I am writing for specific nodes (p) and (q) just to keep explanation simple. but my implementation is quit general):
In list previous pointers:
node[0] points to node[9] that is (q), and
node[2] points to node[6] that is (p)
And
node[9] points to node[2]
node[6] points to node[5]
NOTICE: If you want to swap two nodes say node[ 9 ] and node[ 6 ] then you should use pointers of the nodes previous to these two nodes.
For example: two swap node[ 9 ] and [ 6 ], you also need to change next pointer of node[ 0 ] and next pointer of node[ 2 ] in above diagram.
How would be the list after swapping this two nodes?
+---+ +---+ +---+ +---+ +---+
| 0 |--->| 6 |--->| 2 |--->| 9 |--->| 5 |---
+---+ +---+ +---+ +---+ +---+ |
^ ^ ^ null
| | |
| (p) (q)
(head)
What is now in previous nodes [o] and [2]?
After swapping, In list previous pointers
node[0] points to node[6] that is (q), and
node[2] points to node[9] that is (p)
And
node[9] points to node[5]
node[6] points to node[2]
So if you want to swap two nodes; there immediate previous node also effects and because list is single link list you need previous pointers too.
How to find previous node pointers?
Suppose you want to swap any two nodes node[p] and node[q] then you can use head pointer to find previous node.
So swap function syntax (In my implementation) is like:
void swap(struct stack **head, // head node
struct stack **a, // first candidate node to swap
struct stack **b); // first candidate node to swap
And you will call function like:
swap(&head, &p, &q);
Definition: (To understand code please read comments I added at almost each line)
void swap(struct stack **head,
struct stack **a,
struct stack **b){
// first check if a agrgument is null
if( (*head) == NULL || // Empty list
(*a) == NULL || (*b) == NULL){ // one node is null
// Nothing to swap, just return
printf("
Nothing to swap, just return
");
return;
}
// find previos nodes
struct stack* pre_a = get_prevnd(*head, *a);
struct stack* pre_b = get_prevnd(*head, *b);
//Now swap previous node's next
if(pre_a) pre_a->next = (*b); // a's previous become b's previous, and
if(pre_b) pre_b->next = (*a); // b's previous become a's previous
//Now swap next fiels of candidate nodes
struct stack* temp = NULL;
temp = (*a)->next;
(*a)->next = (*b)->next;
(*b)->next = temp;
//change head: if any node was a head
if((*head)==(*a))
*head = *b;
else
if((*head)==(*b))
*head = *a;
}
In swap() function you can notice that I call a helper function get_prevnd(, );. This function returns address of previous node in list. In The function get_prevnd(, );, first argument is list head and second argument is node for which you are looking for.
// find previous node function()
struct stack* get_prevnd(
struct stack* head,
struct stack* a
){
if(head == a){
// node[a] is first node
return NULL;
}
struct stack* temp = head; // temp is current node
struct stack* pre_a = NULL;
while(temp && temp!=a){ //search while not reach to end or the node
pre_a = temp; // find previous node
temp = temp->next;
}
if(temp!=a){// node[a] not present in list
fprintf(stderr, "
error: node not found!
");
exit(EXIT_FAILURE); // bad technique to exit()
}
return pre_a;
}
And fortunately the code is WORKING :). Below is link for online test of this code. I have tested for various kind of inputs.
CodePad: To Swap node in single linked list. Please check output.
And sorry for bad English
这篇关于交换单向链表中的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
