在单链表交换节点 [英] Swap nodes in a singly-linked list
问题描述
我想交换两个节点。例如，如果节点 A 和 B 我传递指针结果（A-1） - ＆gt;接下来和（B-1） - ＆gt;接下来这基本上是节点 A 和 b 。
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.
推荐答案
无限循环是因为的之后的调用掉期（）功能自循环在你的名单。在掉期（） code下面的语句是马车。
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;
为什么：因为在）赋值语句互换（后函数 temp1目录 下一个开始指向 b 节点。和节点[B] 的下一个点，以自身的循环。而在自环是原因的无限循环，在某处你code，你遍历链表。
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:
您没有提及，但我假设有下面之间的关系链表 A 和 B （阅读红色注释的）
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"
（步骤3）：马车声明
(*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"
请参阅（temp1中） - ＆gt;接下来，其实就是 B 和您要分配（* b） - ＆gt;接下来=（* b） （* b） - ＆gt;接下来=（temp1中） - ＆gt;接下来，因此增加一个自我循环。
See (temp1)->next; is actually b and you are assigning (*b)->next = (*b) by doing (*b)->next = (temp1)->next; hence adding a self loop.
（步4）：结果
我觉得跟图可以很容易地理解你的掉期（） code的最后两行正在做的：
(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
（步5）：您的功能，即使最后一行掉期（）左环如下：
(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.
一种方法是交换节点的数据，而不是在链表交换节点的位置，它的自我（的我要评论你的问题的）。但的你想交换节点的的在列表中的位置。结果
嗯，这很好！如果节点数据量越大，时间它能够更好地交换节点的位置，而不是交换节点的数据（交换的数据将是不错的选择的）
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)
由于您有单链表，交换任意两个节点列表中，您的需求的有 previous节点地址的了。 （这是你没有在交换逻辑考虑点的）
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)
为什么需要previous指针：结果
假设一些成功插入（推）操作之后，您的列表变为如下：
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
一个水平diagramstyle中假设的要交换的说两个节点（Q）和（P）：
A horizontal diagram- Suppose you want to swap say two nodes (q) and (p):
+---+ +---+ +---+ +---+ +---+
| 0 |--->| 9 |--->| 2 |--->| 6 |--->| 5 |---
+---+ +---+ +---+ +---+ +---+ |
^ ^ ^ null
| | |
| (q) (p)
(head)
正如我所说的，交换我们需要previous指针。你需要考虑以下左右结果
（从理论上讲，我写这封信给特定节点的（P）和（Q）只是为了解释。简单，但我实现退出一般的）：
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):
在列表previous指针：
In list previous pointers:
node[0] points to node[9] that is (q), and
node[2] points to node[6] that is (p)
和
node[9] points to node[2]
node[6] points to node[5]
注意：如果您想要交换两个节点说节点[9] 和节点[6] 那么你应该使用节点previous的指针，这两个节点。结果
例如：二互换节点[9] 和 [6] ，你也需要改变的下一个指针节点[0] 和
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.
交换这两个节点后，如何将名单？
+---+ +---+ +---+ +---+ +---+
| 0 |--->| 6 |--->| 2 |--->| 9 |--->| 5 |---
+---+ +---+ +---+ +---+ +---+ |
^ ^ ^ null
| | |
| (p) (q)
(head)
现在什么是previous节点 [O] 和 [2] ？结果
交换，在列表previous指针后
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)
和
node[9] points to node[5]
node[6] points to node[2]
所以，如果你想要交换的两个节点;立即有previous节点还效应，因为名单是你需要previous三分球过于单一链接列表。
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.
如何找到previous节点指针？
假设你想要交换任意两个节点节点[P] 和节点[Q] 则可以使用头指针找到previous节点。
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
和您将调用类的函数：
swap(&head, &p, &q);
定义：（要了解code，请阅读我的意见几乎在每行添加的）
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("\n Nothing to swap, just return \n");
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;
}
在掉期（）功能，你可以看到，我称之为辅助函数的get_ prevnd（，）; 。此功能在列表返回previous节点的地址。在功能的get_ prevnd（，）; ，第一个参数是列表头，第二个参数是您正在寻找的节点。
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){ //seach while not reach to end or
pre_a = temp; // find previous node
temp = temp->next;
}
if(temp!=a){// node[a] not present in list
fprintf(stderr, "\n error: node not found!\n");
exit(EXIT_FAILURE); // bad technique to exit()
}
return pre_a;
}
和幸运的是，code是工作:)。下面是链接，这code的在线测试。我已经测试了各种形式的投入。
And fortunately the code is WORKING :). Below is link for online test of this code. I have tested for various kind of inputs.
codePAD： 要交换单链表节点 请检查输出。
CodePad: To Swap node in single linked list. Please check output.
<子>很遗憾坏英语
这篇关于在单链表交换节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
