【 C 】在单链表中插入一个新节点的尝试（二）

在上篇博文中：【 C 】在单链表中插入一个新节点的尝试（一），我们最后提到了如果向单链表的开头（起始位置）插入一个节点，上篇博文中给出的程序显然完成不了这任务。

这篇博文中，我们将解决这个问题，给出一个在单链表中插入一个新节点的通用程序，就是无论在哪里插入节点都可以。

下面我们来分析这个棘手的问题：

这篇博文中讨论的案例在上篇博文中，也就是在一个顺序链表中插入一个节点。该链表如下：

试图将 3 插入到链表中，如何做到？难点在哪里？

为了在链表的起始位置插入一个节点，函数必须修改根指针。但是，函数不能访问变量root。

一个稍微好点的解决办法就是把一个指向root的指针作为参数传递给函数。然后使用间接访问操作，函数不仅可以获得root（指向链表第1个节点的指针，也就是根指针）的值，也可以向它存储一个新的指针值。这个参数的类型是什么呢？

由于root是一个指向Node的指针，所以参数的类型固然是Node **，也就是一个指向Node的指针的指针。

调用该函数的方式为：

result = sll_insert( &root, 3 );

下面给出程序：

  

   

    

     

    
    

     

      //插入到一个有序的单链表。函数的参数是一个指向链表根指针的指针以及需要插入的新值
     
    
   

    

     

    
    

     

      #include <stdlib.h>
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include "sll_node.h" //这个头文件是前面自己创建的
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define FALSE 0
     
    
   

    

     

    
    

     

      #define TRUE 1
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int sll_insert( Node **rootp, int new_value )
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       Node *previous;
     
    
   

    

     

    
    

     

       Node *current;
     
    
   

    

     

    
    

     

       Node *new; //需要插入的新节点
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 //得到指向第一个节点的指针
     
    
   

    

     

    
    

     

       current = *rootp;
     
    
   

    

     

    
    

     

       previous = NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 //寻找正确的插入位置，方法是顺序访问链表，直到到达其值大于或等于新插入的节点的值
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 while( current != NULL && current->value < new_value )
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       previous = current; //始终保存当前节点之前的那个节点
     
    
   

    

     

    
    

     

       current = current->link; //当前节点移动到下一个节点
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 //为新节点分配内存，并把新值存储到新节点中，如果内存分配失败，函数返回FALSE
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 new = ( Node *)malloc( sizeof( Node ) );
     
    
   

    

     

    
    

     
 if( new == NULL )
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 return FALSE;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 new->value = new_value;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 //把新节点插入到链表中，并返回TRUE
     
    
   

    

     

    
    

     
 new->link = current; //新节点的指针指向当前节点
     
    
   

    

     

    
    

     
 if( previous == NULL )
     
    
   

    

     

    
    

     

       *rootp = new;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       previous->link = new;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 return TRUE;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
  
 

下面对上面的某些语句做出解释：

previous = NULL;

我们需要这条语句，这样我们就可以在以后检查新值是否为链表的第一个节点。

current = *rootp;

这条语句对根指针参数执行间接访问操作，得到的结果是root的值，也就是指向链表第一个节点的指针。

 if( previous == NULL )
        *rootp = new;
    else
        previous->link = new;

这条语句被添加到函数的最后。它用于检查新值是否应该被添加到链表的起始位置。如果是，我们使用间接访问修改根指针，使它指向新节点。如果不是，修改前一个节点的指针指向当前节点。

这个函数可以正确完成任务，而且在许多语言中，这是你能够获得的最佳方案。

在C语言中还有一种看似更好的方案来实现单链表的插入，但看了之后我觉得这种方案已经很不错了，如果感兴趣就自己查看《C与指针》，了解相关内容！

文章来源: reborn.blog.csdn.net，作者：李锐博恩，版权归原作者所有，如需转载，请联系作者。

原文链接：reborn.blog.csdn.net/article/details/82660204