不带头节点的单链表如何头插（多图易懂）

傷城~ 2022-12-23 06:14 64阅读 0赞

### 文章目录 ###

*   *  缘起
     *  带头节点的头插
     *  不带头节点的头插
     *   *  错误的代码
         *  为什么错误
         *  如何修改
         *   *  返回新的头指针
             *  二级指针

## 缘起 ##

本文想说的是单向非循环链表的头插。单向非循环链表，可以是带头节点的，也可以是不带头节点的。

对于前者，代码比较简单，后文会说。对于后者，不带头节点的单向链表的头插，我发现即使有多年工作经验的老鸟，也可能写出错误的代码。

## 带头节点的头插 ##

#include <stdio.h>
    #include <assert.h>
    #include <stdlib.h>
    
    
    typedef struct node{ 
        int data;
        struct node *next;
    }node_t;
    
    
    node_t *create_list(void)
    { 
        node_t *head = malloc(sizeof(node_t));
        if(head == NULL){ 
            printf("create list failed\n");
            return NULL;
        }
    
        head->next = NULL;
        return head;
    }
    
    int insert_head(node_t *head,  int num)
    { 
        assert(head != NULL);
        node_t *node = malloc(sizeof(node_t));
        if(node == NULL)
            return -1;
    
        node->data = num;
        node->next = head->next;
        head->next = node;
        return 0;
    }
    
    void printf_list(node_t *head)
    { 
        assert(head != NULL);
        if(head->next == NULL){ 
            printf("the list is empty\n");
            return;
        }
    
        node_t *temp = head->next;
        while(temp){ 
            printf("%d\n",temp->data);
            temp = temp->next;
        }
    }
    
    
    int main(void)
    { 
        int a[]={ 1,2,3,4,5,6};
        node_t *head = create_list();
        if(head == NULL)
            return -1;
        for(int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
        { 
            insert_head(head, a[i]);
        }
    
        printf_list(head);
        return 0;
    }

运行结果是：

6
    5
    4
    3
    2
    1

## 不带头节点的头插 ##

### 错误的代码 ###

把上面的代码改动一下，就可以得到一份**错误**的代码！

#include <stdio.h>
    #include <assert.h>
    #include <stdlib.h>
    
    
    typedef struct node{ 
        int data;
        struct node *next;
    }node_t;
    
    node_t *head = NULL; // 全局变量，链表的头指针
    
    
    int insert_head(node_t *head,  int num)
    { 
        node_t *node = malloc(sizeof(node_t));
        if(node == NULL)
            return -1;
    
        node->data = num;
        node->next = head;
        head  = node;  // !!!!!! 这里是有问题的
        return 0;
    }
    
    void printf_list(node_t *head)
    {   
        if(head == NULL){ 
            printf("the list is empty\n");
            return;
        }
    
        node_t *temp = head;
        while(temp){ 
            printf("%d\n",temp->data);
            temp = temp->next;
        }
    }
    
    
    int main(void)
    { 
        int a[]={ 1,2,3,4,5,6};
        
        for(int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
        { 
            insert_head(head, a[i]);
        }
    
        printf_list(head);
        return 0;
    }

你猜运行结果是什么？

结果是：

the list is empty

### 为什么错误 ###

插入操作失败了。罪魁祸首就是这个函数

int insert_head(node_t *head,  int num)
    { 
        node_t *node = malloc(sizeof(node_t));
        if(node == NULL)
            return -1;
    
        node->data = num;
        node->next = head;
        head  = node;  // !!!!!! 这里是有问题的
        return 0;
    }

为什么不对呢？画图说明。

假设有一个单向链表，头指针 head 的值是 0x200，也就是第一个节点的地址。  
![在这里插入图片描述][20201122211826198.png_pic_center]

调用 insert\_head 函数，假设调用者传递的参数是头指针 head 和数字 3（实参），用蓝色表示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center]

在调用函数时，系统会把实参的值传递给被调用函数的形参（单向拷贝）；

`int insert_head(node_t *head, int num)` 中的 head 和 num 就是形参；

这里的 head 和全局变量 head 同名，但不是一回事：全局变量 head 是实参，这里的 head 是形参，当然也可以取别的名字；

形参属于函数内的局部变量，在函数被调用的时候，形参的内存在栈上分配，函数执行完毕后，分配的内存被释放，即栈帧被销毁。

假设已经完成了值的拷贝，咱们继续分析：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 1]

代码中有三行我标成红色。

首先分配节点的内存，在堆上分配（假设地址是 0x300），用深蓝色表示；然后用 num 和 head 给节点的成员赋值，这都没有问题。继续执行。

注意这句话： head = node;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 2]

这导致栈上的 head = 0x300；似乎达到了目的，让 head 指向新插入的节点，但是，函数返回后，栈上的变量都会消失。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 3]

最后剩下什么？

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 4]

链表还是原来的链表，头指针 head 依然指向 0x200；

唯一剩下的就是分配了一个新节点，且这个新节点指向旧的第一个节点。

### 如何修改 ###

如果要修改错误的代码，我提供两个思路，第一个就是根据上面的图，返回新的头指针，第二个是用二级指针。

#### 返回新的头指针 ####

node_t *insert_head_2(node_t *head,  int num)
    { 
        node_t *node = malloc(sizeof(node_t));
        if(node == NULL)
    	{ 
            printf("malloc failed\n");
    		return head;
    	}
    
        node->data = num;
        node->next = head;
        return node; // 返回新的头指针
    }

主函数修改为：

int main(void)
    { 
        int a[]={ 1,2,3,4,5,6};
        
        for(int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
        { 
            head = insert_head_2(head, a[i]); 
        }
    
        printf_list(head);
        return 0;
    }

也就是说每次插入都要刷新头指针。

#### 二级指针 ####

再看第二个方法。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 5]

咱们深挖一下这张图，我们的目的不是修改 head 的值，因为他只是头指针的一份拷贝，无论怎么修改，都无法修改函数外面的那个头指针。

那怎么办？我们可以传进来头指针的地址，跑得了和尚跑不了庙，既然拿到了你的内存地址，还怕修改不了你的值？这就是 C 语言的威力，给我一根指针，我能戳动地球！

代码可以这样写：

int insert_head_3(node_t **head,  int num)
    { 
        node_t *node = malloc(sizeof(node_t));
        if(node == NULL)
    	{ 
            printf("malloc failed\n");
    		return -1;
    	}
    
        node->data = num;
        node->next = *head;
    	*head = node; // 修改头指针的值
    	return 0;
    	
    }

主函数修改为

int main(void)
    { 
        int a[]={ 1,2,3,4,5,6};
        
        for(int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
        { 
            insert_head_3(&head, a[i]);
        }
    
        printf_list(head);
        return 0;
    }

再用图解释一下：

假设头指针 head 的地址是 0x800

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 6]

传参完成后（下图中的黄色部分），分配新节点的内存，在堆上分配（假设地址是 0x300），用深蓝色表示；然后用 `num` 和 `*head` 给节点的成员赋值；

注意，`*head` 表示地址 0x800 中的内容，即 0x200

还有，栈上的变量 head 指向了全局变量——头指针 head

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 7]

最后一步：修改头指针的值，`*head = node;`

也就是说，不是把新节点的地址 0x300 赋值给栈上的变量 head，而是赋值给 head 指向的内存。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 8]

可以看到，修改成功，头指针确实指向了新节点。

【end】

[20201122211826198.png_pic_center]: /images/20221120/1e7ec1257c054c57877eb2801492579c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/9e3328ea6f43469da99464150425a39b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/49c279cd76d7495ebc4a2ba1f074950c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201122211921353.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201122211930569.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201122211941434.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201122211958821.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201122212011830.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201122212024840.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201122212036854.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTA4OTY=,size_16,color_FFFFFF,t_70#pic_center