前言：

??小編在近日學(xué)習(xí)了單鏈表的知識(shí)，為了加強(qiáng)記憶，于是誕生了這一篇文章，單鏈表是數(shù)據(jù)結(jié)構(gòu)比較重要的知識(shí)，讀者朋友們一定要去好好的學(xué)習(xí)！這個(gè)可以說(shuō)是比順序表更好用的線性表，下面廢話不多說(shuō)，開(kāi)始進(jìn)入單鏈表的學(xué)習(xí)嘍！

目錄：

1.單鏈表

1.1.鏈表的概念與單鏈表

1.2.單鏈表的結(jié)構(gòu)

1.3.單鏈表的性質(zhì)

2.單鏈表功能的代碼實(shí)現(xiàn)

2.1.單鏈表的打印

2.2.單鏈表的尾插

2.3.單鏈表的頭插

2.4.單鏈表的尾刪

2.5.單鏈表的頭刪

3.還有一些函數(shù)沒(méi)寫(xiě)，由于小編不想讓篇幅太大，所以分成了兩部分

正文：

1.單鏈表

1.1.鏈表的概念

? 鏈表是一種物理結(jié)構(gòu)上非連續(xù)，非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表也有很多的種類(lèi)，比如單鏈表，雙鏈表等等，小編今天講述的就是單鏈表，下面小編來(lái)講述一下單鏈表的結(jié)構(gòu)！

1.2.單鏈表的結(jié)構(gòu)

引例：

??對(duì)于單鏈表的結(jié)構(gòu)，小編先給出一個(gè)引例：火車(chē)我相信各位讀者朋友都坐過(guò)，沒(méi)坐過(guò)也應(yīng)該見(jiàn)過(guò)，火車(chē)是由車(chē)頭和一節(jié)一節(jié)的車(chē)廂組成，如下圖所示：

? 在人們乘車(chē)少的時(shí)候，火車(chē)可以減少車(chē)廂，具體減少哪個(gè)車(chē)廂，這是可以隨機(jī)指出的，并不一定就是去掉最后一個(gè)車(chē)廂，我們也可以把中間的給刪除，在旅游旺季的時(shí)候，我們同樣也可以加上幾節(jié)車(chē)廂來(lái)應(yīng)對(duì)人多車(chē)少的情況。

1.2.1.結(jié)點(diǎn)的概念

??單鏈表就類(lèi)似火車(chē)車(chē)廂一樣，它也可以隨時(shí)的減少，隨時(shí)的增加，我們把單鏈表中的每一表稱(chēng)之為結(jié)點(diǎn)，所以可以這么說(shuō)，單鏈表是由一個(gè)一個(gè)結(jié)點(diǎn)構(gòu)成的，單鏈表和順序表最大的不同，就是單鏈表當(dāng)中的結(jié)點(diǎn)是一個(gè)一個(gè)動(dòng)態(tài)內(nèi)存申請(qǐng)出來(lái)的，不是和順序表一樣基于數(shù)組來(lái)進(jìn)行書(shū)寫(xiě)的，下面小編將會(huì)給各位講述一下單鏈表的結(jié)構(gòu)：

·1.2.2.單鏈表的結(jié)構(gòu)

??

? 小編在上圖給各位讀者朋友了單鏈表的結(jié)構(gòu)圖，細(xì)細(xì)一看，我們可以看出每一個(gè)結(jié)點(diǎn)，里面都存儲(chǔ)著數(shù)據(jù)類(lèi)型和一個(gè)地址，不難發(fā)現(xiàn)，結(jié)點(diǎn)里面的地址都對(duì)應(yīng)著下一個(gè)結(jié)點(diǎn)，所以單鏈表就是靠地址來(lái)進(jìn)行連接的，那么肯定有讀者朋友會(huì)感到疑惑，這么一看，單鏈表的物理結(jié)構(gòu)不還是連續(xù)的？其實(shí)這個(gè)說(shuō)法是錯(cuò)誤的，可能每一個(gè)單鏈表都隔著很遠(yuǎn)才進(jìn)行的鏈接，所以單鏈表是不連續(xù)的，不和順序表的一樣，我們可以看到，單鏈表中最后一個(gè)結(jié)點(diǎn)指向的是NULL，這里展示了單鏈表也是有始有終的，下面我們來(lái)簡(jiǎn)單介紹一下單鏈表的性質(zhì)

1.3.單鏈表的性質(zhì)

??單鏈表的性質(zhì)可以分為三個(gè)：

1.單鏈表在邏輯上是連續(xù)的（線性表統(tǒng)一的性質(zhì)）在物理結(jié)構(gòu)是不連續(xù)的。

2.結(jié)點(diǎn)一般都是從堆上申請(qǐng)的。

3.從堆上申請(qǐng)的空間，是按照一定策略分配出來(lái)的，每次申請(qǐng)的空間可能連續(xù)，也可能不連續(xù)

? 其實(shí)性質(zhì)我們用多了，自然也會(huì)記住了，對(duì)于編程的學(xué)習(xí)，我們不是靠死記硬背下來(lái)的，而是不斷的去應(yīng)用，應(yīng)用多了自然就熟悉了！?

? 我們已經(jīng)講述了單鏈表的概念和性質(zhì)，我們可不能紙上談兵，下面，小編將帶著大家手動(dòng)的一步一步的去實(shí)現(xiàn)單鏈表！

2.單鏈表功能的代碼實(shí)現(xiàn)

? 在講述那些單鏈表的增刪查改之前，我們現(xiàn)在肯定要先創(chuàng)建一個(gè)單鏈表，我們已經(jīng)學(xué)習(xí)了順序表和單鏈表的知識(shí)，單鏈表的結(jié)構(gòu)圖也在上面進(jìn)行展示了，那么下面我們就可以實(shí)現(xiàn)單鏈表的創(chuàng)建了，對(duì)于數(shù)據(jù)部分，我們不一定是存儲(chǔ)整型，浮點(diǎn)型等等，所以我們可以類(lèi)似順序表用typedef關(guān)鍵字來(lái)對(duì)類(lèi)型改名，后面我們可以統(tǒng)一進(jìn)行替換。下面是代碼的實(shí)現(xiàn)：

typedef int SLdate;   //方便后面整體類(lèi)型的改變//創(chuàng)立一個(gè)單鏈表
typedef struct Slist {//先設(shè)置一個(gè)類(lèi)型SLdate date;struct Slist* next;   //存放下一個(gè)節(jié)點(diǎn)的地址
}SLTNode;

? 此外，對(duì)于單鏈表代碼的書(shū)寫(xiě)，小編同樣是分成了三個(gè)文件，與順序表一樣，這三個(gè)文件分別是頭文件（用于單鏈表的創(chuàng)建，各種函數(shù)的聲明），源文件（函數(shù)的實(shí)現(xiàn)），源文件（代碼的測(cè)試），我們每寫(xiě)完一個(gè)函數(shù)，一定一定記著先測(cè)試，免得到后面在慢慢改，這樣顯得太麻煩了，下面，我們開(kāi)始實(shí)現(xiàn)一一函數(shù)的功能！

??2.1.單鏈表的打印

??雖然我們還沒(méi)有開(kāi)始放置數(shù)據(jù)，但我們一定要先學(xué)會(huì)單鏈表的打印，這個(gè)與我們正常的打印是不同的！? 首先，我們肯定要?jiǎng)?chuàng)建一個(gè)函數(shù)，下面是代碼呈現(xiàn)：

??

void SLTprintf(SLTNode* phead);//此時(shí)phead代表的是頭節(jié)點(diǎn)，就是第一個(gè)節(jié)點(diǎn)

? 正如代碼解釋所說(shuō)，phead屬于頭結(jié)點(diǎn)，我們想要打印每一個(gè)結(jié)點(diǎn)的數(shù)據(jù)，肯定要先知道它的頭節(jié)點(diǎn)，之后我們可以通過(guò)它的頭結(jié)點(diǎn)來(lái)開(kāi)始對(duì)下一個(gè)節(jié)點(diǎn)進(jìn)行遍歷直到遇到NULL，這樣我們便可以停止打印，所以不難想到，這里我們用到了循環(huán)的知識(shí)，通過(guò)每一次循環(huán)來(lái)打印數(shù)據(jù)，之后再讓下一個(gè)結(jié)點(diǎn)代替當(dāng)前結(jié)點(diǎn)，不過(guò)在這之前，我們應(yīng)該做到對(duì)于頭結(jié)點(diǎn)不讓它做出改變，因?yàn)槲覀兲热羧斡深^節(jié)點(diǎn)進(jìn)行改變，那么之后我們?cè)谶@個(gè)函數(shù)中會(huì)再也不會(huì)找到鏈表的頭，這樣就得不償失了，所以我們用一個(gè)新的結(jié)點(diǎn)來(lái)存放頭節(jié)點(diǎn)，讓它做出對(duì)應(yīng)的的改變，下面是代碼的呈現(xiàn)：

void SLTprintf(SLTNode* phead)
{SLTNode* pour = phead;    //這么做是為了保證頭節(jié)點(diǎn)不會(huì)發(fā)生改變while (pour){printf("%d->", pour->date);pour = pour->next;}printf("NULL\n");
}   //這個(gè)操作是打印單鏈表的數(shù)據(jù)

? 2.2.單鏈表的尾插

? 我們?cè)诤?jiǎn)述完打印后，肯定要講述單鏈表的增刪查改了，我們先從單鏈表的尾插說(shuō)起，對(duì)于單鏈表的尾插，這其實(shí)和順序表的尾插有點(diǎn)類(lèi)似的，不過(guò)在順序表中，在順序表中，我們是擴(kuò)容操作，而在單鏈表中，我們實(shí)現(xiàn)的是插入結(jié)點(diǎn)操作，在插入結(jié)點(diǎn)之前，我們是肯定先要?jiǎng)?chuàng)建一個(gè)新的結(jié)點(diǎn)，作為我們要插入的結(jié)點(diǎn)，不過(guò)我們?cè)趯?shí)現(xiàn)尾插之前，肯定是要先創(chuàng)建一個(gè)函數(shù)的，這里有我們值得注意的一個(gè)點(diǎn)，那就是我們傳過(guò)去的應(yīng)該是單鏈表指針的地址，也就是傳一個(gè)二級(jí)指針過(guò)去，這是一個(gè)重要的點(diǎn)，因?yàn)槲覀円獙?duì)單鏈表指針進(jìn)行改變，對(duì)于內(nèi)容的改變我們需要傳址調(diào)用來(lái)實(shí)現(xiàn)，下面是函數(shù)的創(chuàng)建：

void SLTPushBack(SLTNode** pphead, SLdate x);

? 首先，我們需要先分裝出一個(gè)函數(shù)，用來(lái)作為新結(jié)點(diǎn)的創(chuàng)建，這里我們需要用到malloc函數(shù)來(lái)對(duì)開(kāi)辟出一個(gè)新的空間來(lái)作為新節(jié)點(diǎn)空間，之后我們?cè)賹?shù)據(jù)轉(zhuǎn)化為我們想要的數(shù)據(jù)，再讓下一個(gè)結(jié)點(diǎn)置為空就好，這個(gè)操作可以類(lèi)似于順序表的擴(kuò)容操作，下面是代碼實(shí)現(xiàn)：

SLTNode* SLTbuynode(SLdate x)
{SLTNode* pour = (SLTNode*)malloc(sizeof(SLTNode));assert(pour);pour->date = x;pour->next = NULL;return pour;
}

? 之后我們就開(kāi)始進(jìn)行插入操作，這里我們分為兩種情況：

? 第一種情況是頭節(jié)點(diǎn)為空，這個(gè)就很簡(jiǎn)單了，我們將新節(jié)點(diǎn)的內(nèi)容直接給予頭節(jié)點(diǎn)就好了，這對(duì)于屏幕前的你當(dāng)然是小case，尾插的大頭就是下一個(gè)情況了：

? 第二種情況就是頭節(jié)點(diǎn)不為空，正式進(jìn)行尾插操作，這個(gè)操作其實(shí)是蠻簡(jiǎn)單的，我們只需要先進(jìn)行循環(huán)，找到尾結(jié)點(diǎn)，讓尾結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)就好了，下面我們用圖文進(jìn)行解釋（這里用pcur當(dāng)作尾結(jié)點(diǎn)！）：

? ?這樣我們便可以實(shí)現(xiàn)尾插操作，下面是代碼實(shí)現(xiàn)：

void SLTPushBack(SLTNode** pphead, SLdate x)
{//首先可以先建一個(gè)函數(shù)，這個(gè)函數(shù)是來(lái)開(kāi)辟一個(gè)新節(jié)點(diǎn)的（后面想要插入直接調(diào)用就好了）assert(pphead);SLTNode * p = SLTbuynode(x);if (*pphead == NULL)  //首先判斷{*pphead = p;}else{SLTNode* pour = *pphead;   //保證頭節(jié)點(diǎn)不做出改變while (pour -> next){pour = pour->next;}pour->next = p;}
}

2.3.單鏈表的頭插

//頭插
void SLTPushFront(SLTNode** pphead, SLdate x);

? 我們?cè)诳赐晡膊宀僮饕院?#xff0c;緊接著頭插就來(lái)了，同樣的，頭插函數(shù)也需要先有一個(gè)新的結(jié)點(diǎn)的建立去，小編在上面已經(jīng)敘述了，就不再多謝了，同樣的，頭插也同樣分為了兩種情況：

? 第一種情況是是頭結(jié)點(diǎn)是不存在的，這時(shí)候只需要將新節(jié)點(diǎn)設(shè)置為頭節(jié)點(diǎn)就好了。

? 第二種情況是頭節(jié)點(diǎn)是存在的，這時(shí)候需要我們將新節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向?yàn)樵瓉?lái)的頭節(jié)點(diǎn)，再將頭節(jié)點(diǎn)更改為新節(jié)點(diǎn)就好了。具體情況小編用圖文進(jìn)行解釋：

? 不過(guò)此時(shí)不難看拿出，頭插函數(shù)似乎是不需要分兩種情況討論的，因?yàn)閮煞N情況都涉及了將新節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)變?yōu)轭^節(jié)點(diǎn)，所以我們將兩種情況合并下來(lái)就好了，下面是代碼呈現(xiàn)：

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

2.3.單鏈表的尾刪

//尾刪
void SLTPopBack(SLTNode** pphead);

??簡(jiǎn)單的插入函數(shù)就先告一段落了，下面我們來(lái)進(jìn)行刪除操作，首先登場(chǎng)的就是尾刪，尾刪操作，與順序表的尾刪一個(gè)概念，就是把單鏈表的尾結(jié)點(diǎn)置為空，首先，我們需要保證頭節(jié)點(diǎn)是存在的，不然單鏈表都是空的，我們刪來(lái)刪去也沒(méi)什么意思了，這里可以用assert斷言來(lái)判斷下頭節(jié)點(diǎn)是否為空，之后我們就可以進(jìn)行刪除操作·。

? 首先，我們要先定義兩個(gè)指針一個(gè)指向頭節(jié)點(diǎn)，這個(gè)的作用是找到尾結(jié)點(diǎn)，一個(gè)為空（這個(gè)的作用我們稍后就知道），之后我們采用循環(huán)，讓空指針在剛開(kāi)始指向第一個(gè)指針，再讓第一個(gè)指針一直往后走，我們是要找到尾結(jié)點(diǎn)，所以我們循環(huán)結(jié)束的條件就是第一個(gè)指針的下一個(gè)結(jié)點(diǎn)不指向空，之后第一個(gè)指針變成了尾結(jié)點(diǎn)，第二個(gè)指針變成了尾結(jié)點(diǎn)之前的結(jié)點(diǎn)，這樣，我們就可以讓第二個(gè)指針的下一個(gè)置為空，然后再讓第一個(gè)指針釋放掉，這樣我們就完成了尾刪操作，不過(guò)此時(shí)，細(xì)心的讀者朋友可能會(huì)發(fā)現(xiàn)，如果單鏈表只有頭節(jié)點(diǎn)的話，這時(shí)候上面就不成立了，我們這里就對(duì)空指針進(jìn)行解引用了，所以尾刪操作，我們同樣也是分為兩種情況！：

? 第一種是如果只有頭節(jié)點(diǎn)的話，我們直接將頭節(jié)點(diǎn)變?yōu)榭?#xff0c;這里就完成了尾刪操作。

? 第二種情況就是正常情況，方法就是上面所講，下面是圖文解釋+代碼呈現(xiàn)：

?

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){*pphead = NULL;}else{SLTNode* pour = *pphead;SLTNode* plist = NULL;while (pour->next){plist = pour;pour = pour->next;}plist->next = NULL;free(pour);pour = NULL;}
}

2.5.單鏈表的頭刪?

? 尾刪我們講完了，下面是頭刪環(huán)節(jié)，與尾刪一樣，我們首先要判斷頭節(jié)點(diǎn)是否為空，如果為空直接報(bào)錯(cuò)就好了，之后我們就要進(jìn)行正常的頭刪操作了，頭刪操作我們也要?jiǎng)?chuàng)建一個(gè)指針·，這個(gè)指針表示頭節(jié)點(diǎn)，之后我們直接讓現(xiàn)頭節(jié)點(diǎn)變成原頭節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，然后我們?cè)賹⒅羔樶尫?#xff0c;這里我們便完成了單鏈表的頭刪操作，是不是很簡(jiǎn)單呢？下面小編給出圖文解釋和代碼呈現(xiàn)：

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pour = *pphead;*pphead = (*pphead)->next;free(pour);pour = NULL;
}

總結(jié)：

? 正如小編上面所說(shuō)，小編不想讓文章的篇幅太大，于是小編就把博客分裝成了兩部分來(lái)進(jìn)行書(shū)寫(xiě)，單鏈表的操作當(dāng)然不僅限于這些了，下一篇將會(huì)是重點(diǎn)，如果文章有錯(cuò)誤，懇請(qǐng)?jiān)谠u(píng)論區(qū)指出，小編肯定會(huì)改正，下面小編將要肝下篇文章了，那我們下一篇文章見(jiàn)嘍！?

?

?

?

?