在单链表中交换节点

Question

我试图交换两个节点.例如,如果节点是a,b我传递指针
(a-1)->next,(b-1)->next基本上是节点a和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;
}

我究竟做错了什么？当我在调用函数后尝试打印节点时,它是一个无限循环.请帮忙.

Answer 1

为什么无限循环？

无限循环是因为调用函数后列表中的自循环swap().在swap()代码中,以下语句是错误的.

(*b)->next = (temp1)->next; 

为什么？:因为在swap()函数temp1的下一个赋值语句开始指向b节点之后.而node[b]下一步指向循环.并且自循环是无限循环的原因,在代码中的某处,您遍历链表.

下面我将展示如何swap()逐步进行工作.可能这有助于您了解您的错误:

你没有提到,但我假设有以下关系之间链表a和b:(读红色评论)

(步骤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)->next;实际上看是b你正在分配(*b)->next = (*b),(*b)->next = (temp1)->next;因此添加一个自循环.

(步骤4):
我认为使用图表可以很容易地理解swap()代码的最后两行:

temp2 = temp1;
(temp2)->next = temp3->next;

以下是这两行的图表:

temp2 = temp1;         
+----+----+----+      +---+----+----+ <---|
|      one     |      |    two      |-----|  "<--- Self loop"
+----+----+----+      +---+---+-----+
  ^                    ^    ^    ^
  |                    |    |    |
  |                    |   *b    *a
  |                    | 
  temp2 = temp1;      temp3  

(步骤5): 即使你的函数的最后一行swap() 留下如下的循环:

 (temp2)->next = temp3->next;  " last line of your code"

+----+----+----+      +---+----+----+ <---|
|      one     |----->|    two      |-----|  "<-- Self loop"
+----+----+----+      +---+---+-----+
  ^                    ^    ^    ^
  |                    |    |    |
  |                    |   *b    *a
  |                    | 
temp2 = temp1;          temp3  

所以循环仍然在two节点那么无限循环.

如何在单个链表中交换两个节点？

一种方法是交换节点的数据,而不是交换节点在链表中自己的位置(正如我对你的问题所评论).但是你想在列表中交换节点的位置.
好吧这个好!如果节点数据大小较大,那么它更好地交换节点的位置而不是交换节点的数据(交换数据将是不好的选择)

因为你有单链表,掉在列表中,您任意两个节点需要有一个节点的地址了.(这是您在交换逻辑中不考虑的一点)

为什么需要以前的指针？:
假设在一些成功的插入(推送)操作之后,您的列表变为如下:

 0  <--------TOP - "head"
 9  <--p  
 2    
 6  <--q           
 5  

水平图 - 假设您要交换两个节点(q) 并且(p):

+---+    +---+    +---+    +---+    +---+                               
| 0 |--->| 9 |--->| 2 |--->| 6 |--->| 5 |---
+---+    +---+    +---+    +---+    +---+  |                                
 ^        ^                  ^            null  
 |        |                  | 
 |       (q)                (p)   
 (head)  

正如我所说,交换我们需要先前的指针.你需要考虑以下
(理论上,我正在为特定的节点编写(p),(q)只是为了使解释简单.但我的实现是退出一般):

在列表中的前一个指针:

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]     

注意:如果要交换两个节点node[ 9 ] ,node[ 6 ]那么应该使用这两个节点之前的节点的指针.
例如:两个交换node[ 9 ]和[ 6 ],你还需要更改的下一个指针node[ 0 ]和下一指针的node[ 2 ]上面图.

交换这两个节点后列表怎么样？

+---+    +---+    +---+    +---+    +---+                               
| 0 |--->| 6 |--->| 2 |--->| 9 |--->| 5 |---
+---+    +---+    +---+    +---+    +---+  |                                
 ^        ^                  ^            null  
 |        |                  | 
 |       (p)                (q)   
 (head) 

什么是以前的节点[o]和[2]？
交换后,列出以前的指针

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]

所以如果你想交换两个节点; 前一个节点也有效果,因为列表是单链接列表,你也需要先前的指针.

如何找到以前的节点指针？

假设您要交换任意两个节点node[p],node[q]然后您可以使用它head pointer来查找上一个节点.

所以交换函数语法(在我的实现中)就像:

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);

定义:(要理解的代码,请阅读我的评论几乎每一行加)

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;
}

在swap()函数中你可以注意到我调用了一个辅助函数get_prevnd(, );.此函数返回列表中上一个节点的地址.在该函数中get_prevnd(, );,第一个参数是列表头,第二个参数是您要查找的节点.

// 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, "\n error: node not found!\n");
        exit(EXIT_FAILURE); // bad technique to exit()
    }
    return pre_a;   
}

幸运的是代码是工作:).以下是此代码在线测试的链接.我已经测试了各种输入.

CodePad:在单个链表中交换节点.请检查输出.

_{抱歉英语不好}