?

? ? ? ?鏈表是一種常見且重要的數據結構，在 C 語言中，它通過指針將一系列的節點連接起來，每個節點可以存儲不同類型的數據。相比數組，鏈表在插入和刪除元素時不需要移動大量數據，具有更好的靈活性，尤其適合處理動態變化的數據集合。

? ? ? ?當然，既然鏈表涉及到指針，而且與指針關系密切，所以只有當我們在對于指針有了一定扎實的了解后，才能更好、更輕松的了解鏈表這一新概念。然而，我認為對于鏈表這樣一類概念來說，增刪查改是最好去了解其本質的方法，所以今天，我們來看看鏈表的增刪查改。

? ? ? ?首先，我們來看看比較簡單的頭插、頭刪、尾插、尾刪這四個：

一.前期準備：

對于前期準備我已經老調重彈了很多遍，這里不再過多贅述，首先最關鍵的就是鏈表節點的定義。

1. 鏈表節點的定義

? ? ? ?鏈表由一個個節點組成，每個節點包含兩部分：數據域和指針域。數據域用來存儲數據，指針域指向下一個節點。所以我們選擇用結構體去定義節點：

typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

代碼解釋：

1.?typedef int SLTDataType：

? ? ? ?這行代碼定義了一個類型別名?SLTDataType，它實際上是?int?的同義詞。也就說可以選擇直接在結構體內部用 int data；之所以這樣做的目的是：

• 提高代碼可維護性：如果后續需要存儲其他類型（如?float、char*），只需修改這一行，而不必改動整個代碼。
• 增強可讀性：SLTDataType?比直接用?int?更直觀，表示這是鏈表節點的數據類型。

2.?struct SListNode?結構體定義

這個結構體定義了單鏈表的節點結構，包含兩個成員：

SLTDataType data;

• 數據域，用于存儲具體的數據。
• 由于?SLTDataType?被 typedef 為?int，因此這里實際上存儲的是整數。

struct SListNode* next;

• 指針域，指向下一個節點的地址。
• 這是實現鏈表連接的關鍵：每個節點通過?next?指針指向下一個節點，直到最后一個節點的?next?為?NULL，表示鏈表結束。
• 并非一個結構體，是一個結構體類型的指針

3.?SLTNode;

這行代碼將?struct SListNode?重命名為?SLTNode，目的是簡化類型名。

• 之后可以直接用?SLTNode?聲明變量，而不需要寫?struct SListNode。
• 例如：SLTNode* node = malloc(sizeof(SLTNode));

二.打印函數：

為了更好地在測試文件里測試函數的可行性，我們首先寫一個打印函數。

void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

代碼解釋：

1. 定義遍歷指針

SLTNode* cur = phead;

• 創建一個臨時指針?cur（current 的縮寫，意為 “當前節點”），并將其初始化為頭指針?phead。
• 作用：用?cur?遍歷鏈表，避免直接修改頭指針?phead（如果直接移動?phead，會導致鏈表 “頭節點丟失”，無法再訪問整個鏈表）。

2. 遍歷鏈表并打印數據

while (cur)

• 循環條件?cur?等價于?cur != NULL，表示：只要當前節點?cur?不是空指針（即還沒遍歷到鏈表末尾），就繼續循環。

printf("%d->", cur->data);

• 打印當前節點?cur?的數據域?data（%d?對應?SLTDataType?為?int?的情況），并在后面加上?->?符號，模擬鏈表的 “指向” 關系。

cur = cur->next;

• 讓?cur?指向當前節點的下一個節點（通過指針域?next），實現遍歷的 “移動”。

3. 打印鏈表末尾標識

printf("NULL\n");

?

• 當循環結束時（cur?變為?NULL，即遍歷到鏈表末尾），打印?NULL，表示鏈表的終止。

三.尾插函數：

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (*pphead == NULL){*pphead = newnode;}else{//找尾：SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

代碼解釋：

函數定義解析：

void SLTPushBack(SLTNode** pphead, SLTDataType x)

• 參數：
  • SLTNode** pphead：指向頭指針的指針（二級指針）。因為尾插可能改變頭指針（當鏈表為空時），必須通過二級指針修改原頭指針的值。
  • SLTDataType x：要插入的數據（類型為?int，因為?SLTDataType?被 typedef 為?int）。
• 返回值：void，只執行插入操作，不返回數據。

函數體詳解

1. 斷言檢查

assert(pphead);

• 確保傳入的二級指針?pphead?不為空（即頭指針的地址必須有效）。
• 若?pphead?為空，程序會觸發斷言錯誤并終止（防止野指針）。

2. 創建新節點

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{perror("malloc fail");return;
}
newnode->data = x;
newnode->next = NULL;

• 內存分配：用?malloc?動態分配一個節點大小的內存空間。
• 錯誤處理：若?malloc?失敗（返回?NULL），打印錯誤信息并提前返回。
• 初始化節點：將數據?x?存入新節點的數據域?data，并將指針域?next?置為?NULL（因為新節點將成為尾節點）。

3. 處理鏈表為空的情況

if (*pphead == NULL)
{*pphead = newnode;
}

• 若鏈表為空（頭指針?*pphead?為?NULL），直接讓頭指針指向新節點。
• 關鍵點：通過?*pphead?修改原頭指針的值，使新節點成為鏈表的第一個節點。

4. 鏈表不為空時的尾插操作

else
{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;
}

?

• 遍歷找尾：從鏈表頭開始，用?tail?指針遍歷到最后一個節點（即?tail->next == NULL?的節點）。
• 插入新節點：將尾節點的?next?指針指向新節點?newnode，使新節點成為新的尾節點。

函數定義進階解析：

到這里相信很多人仍然對于二級指針那個點感到糊涂：為什么前面打印函數定義時就是一級指針，而到了插入函數開始就用二級指針了呢？下面我先順著原始思路去解釋，認為和打印函數一樣用的是一級指針的代碼和測試代碼會如下：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (phead == NULL){phead = newnode;}else{//找尾：SLTNode* tail = phead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

void TestSList1()
{SLTNode* plist = NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);
}int main()
{TestSList1();return 0;
}

然而這樣最終編譯結果為：

我們可以看到，結果好像不是我們想要的，這是因為：

問題核心：形參與實參的區別

void SLTPushBack(SLTNode* phead, SLTDataType x) 

• 參數?phead?是實參的副本：當調用?SLTPushBack(plist, 1)?時，函數內部的?phead?是?plist?的拷貝，它們指向同一塊內存，但本身是兩個不同的變量。
• 修改?phead?不影響實參?plist：在函數內部，當鏈表為空時執行?phead = newnode，只是修改了副本?phead?的值，原頭指針?plist?仍為?NULL。

示例分析：

SLTNode* plist = NULL;  // plist 指向 NULL

第一次調用?SLTPushBack(plist, 1)：

1. 傳值調用：phead?是?plist?的副本，初始值為?NULL。
2. 創建新節點：newnode?指向新分配的節點（數據為 1，next?為?NULL）。
3. 執行?phead = newnode：phead?指向新節點，但?plist?仍為?NULL（因為?phead?是副本）。
4. 函數返回：phead?被銷毀，原?plist?未被修改，仍為?NULL。

后續調用?SLTPushBack(plist, 2)、SLTPushBack(plist, 3)?等：

• 每次都重復上述過程，plist?始終為?NULL，所有新節點都無法連接到鏈表中。
• 最終結果：鏈表為空，SLTPrint(plist)?輸出?NULL。

正確做法：使用二級指針

void SLTPushBack(SLTNode** pphead, SLTDataType x)

?

• 傳址調用：pphead?是指向頭指針?plist?的指針，通過?*pphead?可以直接修改原頭指針。
• 修改?*pphead?影響實參：當鏈表為空時，*pphead = newnode?直接將原頭指針?plist?指向新節點。

?明白了這點之后，后續函數該用一級指針還是二級指針我們就清楚了。

四.新增節點函數：

完成尾插函數以后，我們發現需要開辟新的節點，我們也能預想到，后續函數也會用到新增節點，所以我們不妨封裝這個函數，簡化代碼量：

SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;return newnode;
}

之后在開辟時，直接調用即可；

五.頭插函數：

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}

代碼解釋：?

1. 斷言檢查

assert(pphead);

• 確保傳入的二級指針?pphead?不為空（即頭指針的地址必須有效）。
• 若?pphead?為空，程序會觸發斷言錯誤并終止（防止野指針）。

2. 創建新節點

SLTNode* newnode = BuySLTNode(x);

• 調用?BuySLTNode?函數，創建一個新節點并初始化為數據?x，next?指針為?NULL。

3. 插入新節點到頭部

newnode->next = *pphead;
*pphead = newnode;

?

• 關鍵點：

  1. 將新節點的?next?指針指向原頭節點（*pphead）。
  2. 將原頭指針?*pphead?更新為新節點?newnode，使新節點成為鏈表的新頭。

• 無論鏈表是否為空，這兩行代碼都能正確工作：

  • 若鏈表為空（*pphead == NULL），新節點的?next?為?NULL，并成為唯一節點。
  • 若鏈表非空，新節點的?next?指向原頭節點，實現頭插。

頭插函數很簡約，理解起來也沒什么大問題；

六.尾刪函數：

void SLTPopBack(SLTNode** pphead)
{//暴力檢查：assert(pphead);assert(*pphead);//只有一個節點；// 有多個節點；if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找尾：SLTNode* prev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

代碼解釋：?

1. 斷言檢查

assert(pphead);
assert(*pphead);

• 第一個斷言：確保傳入的二級指針?pphead?不為空（防止野指針）。
• 第二個斷言：確保鏈表不為空（*pphead != NULL）。若鏈表為空時調用此函數，會觸發斷言錯誤，終止程序。

2. 處理只有一個節點的情況

if ((*pphead)->next == NULL)
{free(*pphead);*pphead = NULL;
}

• 若鏈表只有一個節點（即頭節點的?next?為?NULL）：
  1. 釋放頭節點的內存（free(*pphead)）。
  2. 將頭指針置為?NULL（*pphead = NULL），表示鏈表已空。

3. 處理多個節點的情況

else
{SLTNode* prev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;
}

• 遍歷找尾：
  • tail?指針遍歷到最后一個節點，prev?始終指向?tail?的前一個節點。
• 釋放尾節點：
  1. 釋放?tail?指向的尾節點（free(tail)）。
  2. 將?tail?置為?NULL（這一步是多余的，后面會解釋）。
• 更新鏈表：
  將?prev?的?next?置為?NULL，使?prev?成為新的尾節點。
• 注意對于這段代碼，while內的代碼邏輯極其重要，不能找到尾以后就直接刪去，這樣將導致刪完以后，尾部出現隨機值的情況，需要格外注意！！！

但其實這段代碼還存在一點小問題：

存在的問題：

free(tail);
tail = NULL;  // 這一步無效！

• 問題：tail = NULL?僅將局部變量?tail?置為?NULL，無法影響原鏈表。
• 原因：tail?是局部指針，free(tail)?后內存已釋放，但?tail?本身仍保存著被釋放內存的地址。將?tail?置為?NULL?只是修改了局部變量，對鏈表無影響。
• 修正：刪除?tail = NULL?這一行，因為它不影響鏈表結構，且是多余操作。

七.頭刪函數：

void SLTPopFront(SLTNode** pphead)
{//暴力檢查：assert(pphead);assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}

代碼解釋：?

1. 斷言檢查

assert(pphead);
assert(*pphead);

• 第一個斷言：確保傳入的二級指針?pphead?不為空（防止野指針）。
• 第二個斷言：確保鏈表不為空（*pphead != NULL）。若鏈表為空時調用此函數，會觸發斷言錯誤，終止程序。

2. 保存原頭節點并更新頭指針

SLTNode* first = *pphead;
*pphead = first->next;

?

• 關鍵點：
  1. 用臨時指針?first?保存原頭節點的地址。
  2. 將頭指針?*pphead?更新為原頭節點的下一個節點（first->next）。
• 處理單節點情況：若鏈表只有一個節點，first->next?為?NULL，更新后頭指針?*pphead?變為?NULL，鏈表為空。

3. 釋放原頭節點的內存

free(first);
first = NULL;

?

• 釋放內存：調用?free(first)?釋放原頭節點占用的內存。
• 置空局部指針：將?first?置為?NULL（這一步是可選的，因為?first?是局部變量，函數返回后會被銷毀）。

? ? ? ?這樣一來，我們基礎的尾插、尾刪、頭插、頭刪都已經講完了，除了上面我們所關注到的細節點以外，還有一個點就是斷言，我們發現有的地方加入了斷言，有的地方沒有，有的地方只有一個，而有的地方卻有兩個，我們來談談斷言：

斷言：

在 C 語言鏈表操作中，斷言（assert）?是一種強大的調試工具，用于確保程序運行時的某些條件始終為真。

一、斷言的本質與作用

斷言是 C 標準庫?<assert.h>?提供的宏，定義為：

void assert(int expression);

?

• 功能：若?expression?為假（0），程序會立即終止，并打印錯誤信息（包括斷言失敗的位置、表達式內容）。
• 目的：在開發和測試階段盡早發現邏輯錯誤，避免程序在錯誤狀態下繼續運行導致更嚴重的問題。

二、鏈表操作中常見的斷言場景

1.?檢查指針有效性

assert(pphead);  // 確保二級指針（頭指針的地址）不為NULL

• 場景：在需要修改頭指針的函數中（如?SLTPushBack、SLTPopFront），若傳入的?pphead?為?NULL，后續解引用?*pphead?會導致野指針錯誤。
• 錯誤示例：

  SLTNode* plist = NULL;
  SLTPushBack(NULL, 1);  // 錯誤：傳入NULL作為pphead
  

2.?檢查鏈表非空

assert(*pphead);  // 確保鏈表不為空（頭指針不為NULL）

• 場景：在刪除操作（如?SLTPopBack、SLTPopFront）中，若鏈表為空，刪除操作無意義且可能導致崩潰。
• 錯誤示例：

  SLTNode* plist = NULL;
  SLTPopFront(&plist);  // 錯誤：對空鏈表執行頭刪
  

三、斷言的優缺點

優點：

1. 快速定位錯誤：斷言失敗時會直接打印錯誤位置和表達式，無需調試器即可快速發現問題。
2. 強制約束條件：明確函數的前置條件（如 “鏈表必須非空”），提高代碼安全性。
3. 零運行時開銷：在發布版本中可通過?#define NDEBUG?禁用斷言，消除性能影響。

缺點：

1. 僅在調試階段有效：發布版本中斷言被禁用，無法檢查運行時錯誤。
2. 可能掩蓋真實問題：若斷言條件過于嚴格，可能導致程序頻繁崩潰，需謹慎設置。

所以，鏈表細節滿滿，需要大家多花時間去了解，剩下的一些函數，將會放到下一篇博客中，敬請期待......

?