前言：

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

目錄：

1.單鏈表

1.1.鏈表的概念與單鏈表

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

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

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

2.1.單鏈表的打印

2.2.單鏈表的尾插

2.3.單鏈表的頭插

2.4.單鏈表的尾刪

2.5.單鏈表的頭刪

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

正文：

1.單鏈表

1.1.鏈表的概念

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

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

引例：

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

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

1.2.1.結(jié)點的概念

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

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

??

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

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

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

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

2.結(jié)點一般都是從堆上申請的。

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

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

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

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

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

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

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

??2.1.單鏈表的打印

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

??

void SLTprintf(SLTNode* phead);//此時phead代表的是頭節(jié)點，就是第一個節(jié)點

? 正如代碼解釋所說，phead屬于頭結(jié)點，我們想要打印每一個結(jié)點的數(shù)據(jù)，肯定要先知道它的頭節(jié)點，之后我們可以通過它的頭結(jié)點來開始對下一個節(jié)點進行遍歷直到遇到NULL，這樣我們便可以停止打印，所以不難想到，這里我們用到了循環(huán)的知識，通過每一次循環(huán)來打印數(shù)據(jù)，之后再讓下一個結(jié)點代替當(dāng)前結(jié)點，不過在這之前，我們應(yīng)該做到對于頭結(jié)點不讓它做出改變，因為我們倘若任由頭節(jié)點進行改變，那么之后我們在這個函數(shù)中會再也不會找到鏈表的頭，這樣就得不償失了，所以我們用一個新的結(jié)點來存放頭節(jié)點，讓它做出對應(yīng)的的改變，下面是代碼的呈現(xiàn)：

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

? 2.2.單鏈表的尾插

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

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

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

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

? 之后我們就開始進行插入操作，這里我們分為兩種情況：

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

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

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

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

2.3.單鏈表的頭插

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

? 我們在看完尾插操作以后，緊接著頭插就來了，同樣的，頭插函數(shù)也需要先有一個新的結(jié)點的建立去，小編在上面已經(jīng)敘述了，就不再多謝了，同樣的，頭插也同樣分為了兩種情況：

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

? 第二種情況是頭節(jié)點是存在的，這時候需要我們將新節(jié)點的下一個結(jié)點指向為原來的頭節(jié)點，再將頭節(jié)點更改為新節(jié)點就好了。具體情況小編用圖文進行解釋：

? 不過此時不難看拿出，頭插函數(shù)似乎是不需要分兩種情況討論的，因為兩種情況都涉及了將新節(jié)點的下一個結(jié)點變?yōu)轭^節(jié)點，所以我們將兩種情況合并下來就好了，下面是代碼呈現(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);

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

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

? 第一種是如果只有頭節(jié)點的話，我們直接將頭節(jié)點變?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é)點是否為空，如果為空直接報錯就好了，之后我們就要進行正常的頭刪操作了，頭刪操作我們也要創(chuàng)建一個指針·，這個指針表示頭節(jié)點，之后我們直接讓現(xiàn)頭節(jié)點變成原頭節(jié)點的下一個結(jié)點，然后我們再將指針釋放，這里我們便完成了單鏈表的頭刪操作，是不是很簡單呢？下面小編給出圖文解釋和代碼呈現(xiàn)：

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

總結(jié)：

? 正如小編上面所說，小編不想讓文章的篇幅太大，于是小編就把博客分裝成了兩部分來進行書寫，單鏈表的操作當(dāng)然不僅限于這些了，下一篇將會是重點，如果文章有錯誤，懇請在評論區(qū)指出，小編肯定會改正，下面小編將要肝下篇文章了，那我們下一篇文章見嘍！?

?

?

?

?