文章目錄

• • 緣起
  • 帶頭節(jié)點(diǎn)的頭插
  • 不帶頭節(jié)點(diǎn)的頭插
  • • 錯(cuò)誤的代碼
    • 為什么錯(cuò)誤
    • 如何修改
    • • 返回新的頭指針
      • 二級指針

緣起

本文想說的是單向非循環(huán)鏈表的頭插。單向非循環(huán)鏈表，可以是帶頭節(jié)點(diǎn)的，也可以是不帶頭節(jié)點(diǎn)的。

對于前者，代碼比較簡單，后文會(huì)說。對于后者，不帶頭節(jié)點(diǎn)的單向鏈表的頭插，我發(fā)現(xiàn)即使有多年工作經(jīng)驗(yàn)的老鳥，也可能寫出錯(cuò)誤的代碼。

帶頭節(jié)點(diǎn)的頭插

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

運(yùn)行結(jié)果是：

6 5 4 3 2 1

不帶頭節(jié)點(diǎn)的頭插

錯(cuò)誤的代碼

把上面的代碼改動(dòng)一下，就可以得到一份錯(cuò)誤的代碼！

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

你猜運(yùn)行結(jié)果是什么？

結(jié)果是：

the list is empty

為什么錯(cuò)誤

插入操作失敗了。罪魁禍?zhǔn)拙褪沁@個(gè)函數(shù)

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

為什么不對呢？畫圖說明。

假設(shè)有一個(gè)單向鏈表，頭指針 head 的值是 0x200，也就是第一個(gè)節(jié)點(diǎn)的地址。

調(diào)用 insert_head 函數(shù)，假設(shè)調(diào)用者傳遞的參數(shù)是頭指針 head 和數(shù)字 3（實(shí)參），用藍(lán)色表示。

在調(diào)用函數(shù)時(shí)，系統(tǒng)會(huì)把實(shí)參的值傳遞給被調(diào)用函數(shù)的形參（單向拷貝）；

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

這里的 head 和全局變量 head 同名，但不是一回事：全局變量 head 是實(shí)參，這里的 head 是形參，當(dāng)然也可以取別的名字；

形參屬于函數(shù)內(nèi)的局部變量，在函數(shù)被調(diào)用的時(shí)候，形參的內(nèi)存在棧上分配，函數(shù)執(zhí)行完畢后，分配的內(nèi)存被釋放，即棧幀被銷毀。

假設(shè)已經(jīng)完成了值的拷貝，咱們繼續(xù)分析：

代碼中有三行我標(biāo)成紅色。

首先分配節(jié)點(diǎn)的內(nèi)存，在堆上分配（假設(shè)地址是 0x300），用深藍(lán)色表示；然后用 num 和 head 給節(jié)點(diǎn)的成員賦值，這都沒有問題。繼續(xù)執(zhí)行。

注意這句話： head = node;

這導(dǎo)致棧上的 head = 0x300；似乎達(dá)到了目的，讓 head 指向新插入的節(jié)點(diǎn)，但是，函數(shù)返回后，棧上的變量都會(huì)消失。

最后剩下什么？

鏈表還是原來的鏈表，頭指針 head 依然指向 0x200；

唯一剩下的就是分配了一個(gè)新節(jié)點(diǎn)，且這個(gè)新節(jié)點(diǎn)指向舊的第一個(gè)節(jié)點(diǎn)。

如何修改

如果要修改錯(cuò)誤的代碼，我提供兩個(gè)思路，第一個(gè)就是根據(jù)上面的圖，返回新的頭指針，第二個(gè)是用二級指針。

返回新的頭指針

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; // 返回新的頭指針 }

主函數(shù)修改為：

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

也就是說每次插入都要刷新頭指針。

二級指針

再看第二個(gè)方法。

咱們深挖一下這張圖，我們的目的不是修改 head 的值，因?yàn)樗皇穷^指針的一份拷貝，無論怎么修改，都無法修改函數(shù)外面的那個(gè)頭指針。

那怎么辦？我們可以傳進(jìn)來頭指針的地址，跑得了和尚跑不了廟，既然拿到了你的內(nèi)存地址，還怕修改不了你的值？這就是 C 語言的威力，給我一根指針，我能戳動(dòng)地球！

代碼可以這樣寫：

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

主函數(shù)修改為

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

再用圖解釋一下：

假設(shè)頭指針 head 的地址是 0x800

傳參完成后（下圖中的黃色部分），分配新節(jié)點(diǎn)的內(nèi)存，在堆上分配（假設(shè)地址是 0x300），用深藍(lán)色表示；然后用 num 和 *head 給節(jié)點(diǎn)的成員賦值；

注意，*head 表示地址 0x800 中的內(nèi)容，即 0x200

還有，棧上的變量 head 指向了全局變量——頭指針 head

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

也就是說，不是把新節(jié)點(diǎn)的地址 0x300 賦值給棧上的變量 head，而是賦值給 head 指向的內(nèi)存。

可以看到，修改成功，頭指針確實(shí)指向了新節(jié)點(diǎn)。

【end】

總結(jié)

以上是生活随笔為你收集整理的不带头节点的单链表如何头插（多图易懂）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。