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

文章目录

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

缘起

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

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

带头节点的头插

#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，也就是第一个节点的地址。

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

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

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

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

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

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

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

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

注意这句话： head = node;

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

最后剩下什么？

链表还是原来的链表，头指针 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; }

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

二级指针

再看第二个方法。

咱们深挖一下这张图，我们的目的不是修改 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

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

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

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

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

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

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

【end】

总结

以上是生活随笔为你收集整理的不带头节点的单链表如何头插（多图易懂）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。