c - 交换单向链表中的节点

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的 next 开始指向 b节点。和 node[b]的 next 在循环中指向自身。和 自循环是 的原因无限循环 ，在您遍历链表的代码中的某处。

下面我画图来展示如何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 ]的next指针和 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;   
}

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

键盘:To Swap node in single linked list.请检查输出。

抱歉英语不好