在上一篇文章中，我們探索了順序表這一基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，它提供了一種有序存儲(chǔ)數(shù)據(jù)的方法，使得數(shù)據(jù)的訪(fǎng) 問(wèn)和操作變得更加高效。想要進(jìn)一步了解，大家可以移步于上一篇文章：探索順序表：數(shù)據(jù)結(jié)構(gòu)中的秩序之美

今天，我們將進(jìn)一步深入，探討另一個(gè)重要的數(shù)據(jù)結(jié)構(gòu)——鏈表

鏈表和順序表一樣，都屬于線(xiàn)性表，也用于存儲(chǔ)數(shù)據(jù)，但其內(nèi)部結(jié)構(gòu)和操作方式有著明顯的不同。通過(guò)C語(yǔ)言的具體實(shí)現(xiàn)，我們將會(huì)更加直觀(guān)地理解它

源碼可以打我的gitee里面查找：唔姆/比特學(xué)習(xí)過(guò)程2 (gitee.com)

---

文章目錄

• • @[toc]
• 一.鏈表的概念及結(jié)構(gòu)
• 二.鏈表的分類(lèi)
• 三.無(wú)頭單向非循環(huán)鏈表的實(shí)現(xiàn)
• • 1.項(xiàng)目文件規(guī)劃
  • 2.基本結(jié)構(gòu)及功能一覽
  • 3.各功能接口具體實(shí)現(xiàn)
  • • 3.1打印單鏈表
    • 3.2尾插
    • 3.3頭插
    • 3.4尾刪
    • 3.5頭刪
    • 3.6查找
    • 3.7插入pos前一個(gè)
    • 3.8刪除pos前一個(gè)
    • 3.9插入pos后一個(gè)
    • 3.10刪除pos后一個(gè)
    • 3.11銷(xiāo)毀（避免內(nèi)存泄露）

一.鏈表的概念及結(jié)構(gòu)

鏈表是一種物理存儲(chǔ)(實(shí)際上)結(jié)構(gòu)上==非連續(xù)、非順序==（雜亂隨意排序）的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的

實(shí)際情況中：

從上圖可發(fā)現(xiàn)：

1. 鏈表在邏輯上連續(xù)，在物理上是不連續(xù)的
2. 各個(gè)節(jié)點(diǎn)（Node）一般都是從堆上面申請(qǐng)空間的
3. 從堆上面申請(qǐng)的空間是有一定策略的，可能連續(xù)，可也能不連續(xù)

---

二.鏈表的分類(lèi)

• 單向或者雙向

• 帶頭或者不帶頭

• 循環(huán)或者非循環(huán)

三種情況隨意組合起來(lái)就有8種鏈表結(jié)構(gòu)

其中，最為常用的是：

無(wú)頭單向非循環(huán)和帶頭雙向循環(huán)

無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，但是一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)它反而簡(jiǎn)單了

這兩種結(jié)果都會(huì)給大家實(shí)現(xiàn)的，今天先來(lái)無(wú)頭單向非循環(huán)鏈表

---

三.無(wú)頭單向非循環(huán)鏈表的實(shí)現(xiàn)

1.項(xiàng)目文件規(guī)劃

• 頭文件SList.h:用來(lái)基礎(chǔ)準(zhǔn)備（常量定義，typedef），鏈表表的基本框架，函數(shù)的聲明
• 源文件SList.h:用來(lái)各種功能函數(shù)的具體實(shí)現(xiàn)
• 源文件test.c:用來(lái)測(cè)試功能是否有問(wèn)題，進(jìn)行基本功能的使用

2.基本結(jié)構(gòu)及功能一覽

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLDataType;typedef struct SingleListNode
{int data;SingleListNode* next;
}SLNode;void SLPrint(SLNode* phead);// 單鏈表打印void SLPushBack(SLNode** pphead, int n);// 單鏈表尾插
void SLPushFront(SLNode** pphead, int n);// 單鏈表頭插
void SLPopBack(SLNode** pphead);// 單鏈表尾刪
void SLPopFront(SLNode** pphead);// 單鏈表尾刪SLNode* SLFind(SLNode* phead, int n);
SLNode* SLInsert(SLNode** pphead, SLNode* pos, int n);//在pos前面插入
SLNode* SLErase(SLNode** pphead, SLNode* pos);//刪除pos前面那個(gè)void SLInsertAfter(SLNode* pos, int n);//在pos后面插入
void SLEraseAfter(SLNode* pos);//在pos后面刪除void SLDestory(SLNode** pphead);

3.各功能接口具體實(shí)現(xiàn)

3.1打印單鏈表

void SLPrint(SLNode* phead)
{assert(phead);SLNode* cur = phead;while (cur != NULL)//與while(cur)同樣的效果{printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

3.2尾插

SLNode* CreateNode(int n)
{SLNode* newNode= (SLNode*)malloc(sizeof(SLNode));if (newNode == NULL){perror("malloc error");return -1;}newNode->data = n;newNode->next = NULL;return newNode;
}void SLPushBack(SLNode** pphead, int n)
{assert(pphead);SLNode* newNode = CreateNode(n);//先把節(jié)點(diǎn)搞好//先考慮一下沒(méi)有節(jié)點(diǎn)的情況if (*pphead == NULL){*pphead = newNode;  //這就是傳二級(jí)指針的原因：//我們要改變 SLNode* phead本身的指向，就把他地址傳過(guò)來(lái)//當(dāng)我們只是要改變指向的結(jié)構(gòu)體里的內(nèi)容時(shí)只要傳SLNode* phead就行了}else{SLNode* tail = *pphead;while (tail->next != NULL)//找到最后一個(gè)節(jié)點(diǎn){tail = tail->next;}tail->next = newNode;}
}

1. 通過(guò) CreateNode 函數(shù)創(chuàng)建了一個(gè)含有數(shù)值 n 的新節(jié)點(diǎn) newNode
2. 然后根據(jù)鏈表是否為空進(jìn)行不同的操作：

• 如果鏈表為空（即頭指針指向空），則將新節(jié)點(diǎn) newNode 賦值給頭指針 *pphead
• 如果鏈表不為空，則需要找到鏈表末尾的節(jié)點(diǎn)，通過(guò)遍歷找到最后一個(gè)節(jié)點(diǎn)(tail)，并將其 next 指針指向新節(jié)點(diǎn) newNode，以將新節(jié)點(diǎn)插入到鏈表的末尾

為什么傳入二級(jí)指針：

這種設(shè)計(jì)方式的原因在于需要修改指針本身的值，而不是只修改指針?biāo)赶虻膬?nèi)容

考慮到單鏈表在插入節(jié)點(diǎn)時(shí)，可能會(huì)涉及鏈表頭指針的修改，如果直接傳遞單級(jí)指針（指向頭指針），在函數(shù)內(nèi)部對(duì)頭指針進(jìn)行修改是不會(huì)反映到函數(shù)外部的==(形參是實(shí)參的臨時(shí)拷貝)==。但如果使用二級(jí)指針，可以在函數(shù)內(nèi)部修改指針的指向，這樣修改后的指向會(huì)在函數(shù)外部保持

3.3頭插

void SLPushFront(SLNode** pphead, int n)
{assert(pphead);SLNode* newNode = CreateNode(n);//先把節(jié)點(diǎn)搞好if (*pphead == NULL){*pphead = newNode;}else{newNode->next = (*pphead)->next;(*pphead)->next = newNode;}//或者//newNode->next = (*pphead);//*pphead = newNode;
}

1. 通過(guò) CreateNode 函數(shù)創(chuàng)建了一個(gè)含有數(shù)值 n 的新節(jié)點(diǎn) newNode
2. 接著，根據(jù)鏈表是否為空進(jìn)行不同的操作：
   • 如果鏈表為空（即頭指針指向空），則將新節(jié)點(diǎn) newNode 賦值給頭指針 *pphead
   • 如果鏈表不為空，則將新節(jié)點(diǎn) newNode 的 next 指針指向當(dāng)前頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)（原鏈表的第二個(gè)節(jié)點(diǎn)），然后將當(dāng)前頭節(jié)點(diǎn)的 next 指針指向新節(jié)點(diǎn) newNode，以完成插入

注釋部分顯示了另一種寫(xiě)法，通過(guò)先設(shè)置新節(jié)點(diǎn)的 next 指針指向當(dāng)前頭節(jié)點(diǎn)，然后再將鏈表的頭指針指向新節(jié)點(diǎn)，實(shí)現(xiàn)了同樣的插入操作

3.4尾刪

void SLPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);//防止一個(gè)都沒(méi)有還刪if ((*pphead)->next == NULL)//只有一個(gè){free(*pphead);*pphead = NULL;}else{//找到倒數(shù)第二個(gè)SLNode* pre_tail = *pphead;while (pre_tail->next->next != NULL){pre_tail = pre_tail->next;}free(pre_tail->next);pre_tail->next = NULL;}
}

1. 檢查鏈表頭指針 *pphead 是否存在（不為 NULL），以及鏈表是否為空（只有一個(gè)節(jié)點(diǎn)）
2. ?
3. • 如果鏈表中只有一個(gè)節(jié)點(diǎn)，則直接釋放該節(jié)點(diǎn)，并將鏈表頭指針設(shè)置為 NULL，表示鏈表為空
   • 如果鏈表中有多個(gè)節(jié)點(diǎn)，則會(huì)找到倒數(shù)第二個(gè)節(jié)點(diǎn)，即指向最后一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。它通過(guò)遍歷鏈表直到找到倒數(shù)第二個(gè)節(jié)點(diǎn) pre_tail，然后釋放最后一個(gè)節(jié)點(diǎn)，并將倒數(shù)第二個(gè)節(jié)點(diǎn)的 next 指針設(shè)置為 NULL，表示該節(jié)點(diǎn)成為新的末尾節(jié)點(diǎn)

3.5頭刪

void SLPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);//防止一個(gè)都沒(méi)有還刪SLNode* first = (*pphead)->next;//一個(gè)和多個(gè)都適用free(*pphead);*pphead = first;
}

1. 創(chuàng)建了一個(gè)臨時(shí)指針 first 來(lái)指向原鏈表的第二個(gè)節(jié)點(diǎn)（如果存在）。這是因?yàn)橐獎(jiǎng)h除的是鏈表的頭節(jié)點(diǎn)，為了不斷開(kāi)鏈表，需要先保存第二個(gè)節(jié)點(diǎn)的地址
2. 通過(guò) free(*pphead) 釋放掉原來(lái)的頭節(jié)點(diǎn)，然后將鏈表的頭指針 *pphead 更新為原頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) first

3.6查找

SLNode* SLFind(SLNode* phead, int n)
{assert(phead);SLNode* cur = phead;while (cur != NULL)//與while(cur)同樣的效果{if (cur->data == n){return cur;}cur = cur->next;}return NULL;
}

3.7插入pos前一個(gè)

void SLInsert(SLNode** pphead, SLNode* pos, int n)//在pos前面插入
{assert(pphead);assert(pos);SLNode* cur = *pphead;if (*pphead == pos)//在第一個(gè)節(jié)點(diǎn)前面插入{// 頭插SLTPushFront(pphead, n);}else{while (cur->next != pos){cur = cur->next;}SLNode* newNode = CreateNode(n);newNode->next = cur->next;cur->next = newNode;}
}

• 如果要插入的位置 pos 就是鏈表的頭節(jié)點(diǎn) *pphead，即在第一個(gè)節(jié)點(diǎn)前面插入，則調(diào)用 SLTPushFront 函數(shù)，直接在鏈表頭部插入新節(jié)點(diǎn) newNode
• 如果要插入的位置不是頭節(jié)點(diǎn)，則通過(guò)循環(huán)遍歷鏈表，直到找到 pos 的前一個(gè)節(jié)點(diǎn) cur，然后創(chuàng)建新節(jié)點(diǎn) newNode 并將其插入到 pos 前面，完成節(jié)點(diǎn)的插入操作

3.8刪除pos前一個(gè)

void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(pos);assert(*pphead != pos);//防止前面沒(méi)有SLNode* cur = *pphead;SLNode* pre_cur = *pphead;while (cur->next != pos){pre_cur = cur;cur = cur->next;}pre_cur->next = pos;free(cur);cur = NULL;
}

3.9插入pos后一個(gè)

void SLInsertAfter(SLNode* pos, int n)
{assert(pos);SLNode* newNode =CreateNode(n);newNode->next = pos->next;pos->next = newNode;
}

1. 創(chuàng)建一個(gè)新節(jié)點(diǎn) newNode，并將新節(jié)點(diǎn)的 next 指針指向 pos 節(jié)點(diǎn)原本的下一個(gè)節(jié)點(diǎn)，以保證鏈表的連續(xù)性
2. 將 pos 節(jié)點(diǎn)的 next 指針指向新節(jié)點(diǎn) newNode，完成了在指定節(jié)點(diǎn)之后插入新節(jié)點(diǎn)的操作

3.10刪除pos后一個(gè)

void SLEraseAfter(SLNode* pos)
{assert(pos);SLNode* next = pos->next->next;free(pos->next);pos->next = NULL;pos->next = next;
}

3.11銷(xiāo)毀（避免內(nèi)存泄露）

void SLDestory(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;SLNode* next = *pphead;while (cur!=NULL){next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

循環(huán)刪除每一個(gè)Node，最后把原本的結(jié)構(gòu)體指針指向NULL

---

好啦，這次知識(shí)就先到這里啦！下一次大概率是雙向帶頭循環(huán)的代碼實(shí)現(xiàn)了。