????????不可否認(rèn)的是，前幾節(jié)我們講解的順序表存在一下幾點(diǎn)問(wèn)題：

????????1. 中間、頭部的插入和刪除，需要移動(dòng)一整串?dāng)?shù)據(jù)，時(shí)間復(fù)雜度O(N)

????????2. 增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗

????????3. 增容一般是2倍的增長(zhǎng)，這勢(shì)必會(huì)造成空間的浪費(fèi)

????????那如何解決這些問(wèn)題呢，此時(shí)，鏈表出現(xiàn)了

1. 鏈表的概念和結(jié)構(gòu)

????????我們之前說(shuō)過(guò)，線性表的特點(diǎn)就是邏輯上是連續(xù)的，物理上不一定連續(xù)。順序表是邏輯上是連續(xù)的，物理上也是連續(xù)的。而今天的鏈表就是邏輯上是連續(xù)的，但是物理上是不連續(xù)的

????????最簡(jiǎn)單的鏈表是由節(jié)點(diǎn)們串在一起組成的，每個(gè)節(jié)點(diǎn)包含了兩個(gè)內(nèi)容：

????????????????1. 要存入的有效數(shù)據(jù)

????????????????2. 下一個(gè)節(jié)點(diǎn)的地址

? ? ? ? 可以看出，每個(gè)節(jié)點(diǎn)在物理上都是獨(dú)立的，不連續(xù)的。但是每個(gè)節(jié)點(diǎn)在邏輯上又有關(guān)聯(lián)，每個(gè)節(jié)點(diǎn)都知道下一個(gè)節(jié)點(diǎn)的指針，要找到下一個(gè)節(jié)點(diǎn)就訪問(wèn)那個(gè)指針就好了

? ? ? ? 具體來(lái)講就是把 plist 當(dāng)成一個(gè)鑰匙，最開(kāi)始保存的是第一個(gè)節(jié)點(diǎn)的地址，用完第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)之后，把第一個(gè)節(jié)點(diǎn)中存儲(chǔ)的地址再給到plist，這樣plist就可以開(kāi)第二個(gè)節(jié)點(diǎn)了，以此類推···

????????下面我們依照上面的圖片做一個(gè)簡(jiǎn)單的節(jié)點(diǎn)結(jié)構(gòu)

????????????????????????????????

? ? ? ? 到這里，鏈表的地基就學(xué)會(huì)了，下面我們嘗試實(shí)現(xiàn)一下

2. 單鏈表(Single linked list)的實(shí)現(xiàn)

? ? ? ? 跟順序表一樣，先是把準(zhǔn)備工作，三個(gè)文件準(zhǔn)備好

????????????????????????????????

? ? ? ? 再把鏈表節(jié)點(diǎn)寫(xiě)出來(lái)

????????????????????????? ? ? ? ???????

? ? ? ? 在這里我要重點(diǎn)聲明一下，接下來(lái)如果從主函數(shù)前去訪問(wèn)鏈表時(shí)用的都是plist參數(shù)，從主函數(shù)中給子函數(shù)傳參也是plist，就像這樣

??????????????????????????????????????????????

? ? ? ? 然后就正式進(jìn)入鏈表實(shí)現(xiàn)啦，大家伙坐穩(wěn)嘍

2.1 鏈表的打印

? ? ? ? 打印的邏輯就是先拿到第一個(gè)節(jié)點(diǎn)的地址 pcur，把這個(gè)地址訪問(wèn)到 data 打印出來(lái)，然后將pcur的內(nèi)容變成下一個(gè)要打印的節(jié)點(diǎn)的地址，直到pcur的內(nèi)容是NULL為止

??????????????????????????????????????

2.2 鏈表的插入

? ? ? ? 因?yàn)椴迦刖鸵欢ㄐ枰暾?qǐng)一個(gè)新的節(jié)點(diǎn)，所以我們先把這個(gè)功能封裝好

? ? ? ? 向堆區(qū)申請(qǐng)一塊空間用來(lái)存放節(jié)點(diǎn)，記錄這個(gè)節(jié)點(diǎn)的地址

? ? ? ? 當(dāng)然，如果你想把newnode的類型改成 SLTNode 也可以，不過(guò)后面要用到節(jié)點(diǎn)地址的時(shí)候就要取地址一下，很麻煩，所以我們干脆直接返回節(jié)點(diǎn)的地址

2.2.1 尾插

? ? ? ? 在鏈表的尾端插入一個(gè)數(shù)據(jù)。

????????因?yàn)槿绻湵頌榭?沒(méi)有節(jié)點(diǎn))的時(shí)候要修改 plist 的內(nèi)容，讓它指向我們新添加的第一個(gè)節(jié)點(diǎn)，所以我們傳參的時(shí)候要傳 &plist ，因此函數(shù)參數(shù)要用二級(jí)指針來(lái)接收這個(gè)可能會(huì)被修改的plist

? ? ? ? 如果鏈表不為空，就去找尾節(jié)點(diǎn)，把為節(jié)點(diǎn)的next成員內(nèi)容從NULL變成我們新添加的節(jié)點(diǎn)地址，可以這么理解：

? ? ? ? 這個(gè)圖里有一點(diǎn)不恰當(dāng)，就是這個(gè) pphead 要解引用一次 (*pphead) 才能找到第一個(gè)節(jié)點(diǎn)的地址

???????????????

????????接下來(lái)我們運(yùn)行一下看看效果

2.2.2 頭插

? ? ? ? 頭插比尾插好理解一點(diǎn)，直接上思路圖(畫(huà)的太丑了QAQ)

????????

? ? ? ? 很明顯，鏈表是否為空對(duì)于需要的操作是沒(méi)有影響的，上代碼：

????????

? ? ? ? 最后運(yùn)行一下看結(jié)果：

????????

? ? ? ? 因?yàn)槊看味际前压?jié)點(diǎn)插到最前面，所以反著打出來(lái)是對(duì)的

2.3 鏈表的刪除

2.3.1 尾刪

? ? ? ? 尾刪的邏輯就是找到最后一個(gè)節(jié)點(diǎn) ptail 和倒數(shù)第二個(gè)節(jié)點(diǎn) prev ，把倒數(shù)第二個(gè)節(jié)點(diǎn)的next成員置為空指針，釋放掉最后一個(gè)節(jié)點(diǎn)。當(dāng)然，如果鏈表為空，也就是說(shuō)沒(méi)有節(jié)點(diǎn)的話就不能執(zhí)行刪除操作，用assert斷言報(bào)錯(cuò)

??????????????????????????????????????

? ? ? ? 上代碼：

????????

2.3.2 頭刪

? ? ? ? 頭刪也是需要兩個(gè)指針控制，要注意的就是要先釋放掉*pphead也就是第一個(gè)節(jié)點(diǎn)，然后再把*pphead的內(nèi)容改成第二個(gè)節(jié)點(diǎn)的地址，接上第二個(gè)節(jié)點(diǎn)

????????????????????? ? ? ??????????

? ? ? ? 代碼如下：

???????????????????????

2.4 查找

? ? ? ? 鏈表的查找很簡(jiǎn)單，就是遍歷鏈表，找到了就返回節(jié)點(diǎn)地址，沒(méi)找到就返回空指針

????????

2.5?在任意位置插入數(shù)據(jù)

2.5.1?在指定位置前插入數(shù)據(jù)

? ? ? ? 可以用SLTFind找到要被前插的節(jié)點(diǎn)的地址pos，在這個(gè)節(jié)點(diǎn)前面插入節(jié)點(diǎn)，還需要直到它前面那個(gè)節(jié)點(diǎn)的地址prev

??????????????????????????????????????

? ? ? ? 在實(shí)現(xiàn)這個(gè)功能的時(shí)候我們要注意，當(dāng)pos是頭節(jié)點(diǎn)的情況：

????????

? ? ? ? 下面使用一下

????????

2.5.2?在指定位置后插入數(shù)據(jù)

? ? ? ? 這個(gè)比較簡(jiǎn)單，但是要注意給地址的順序，要先把后面那個(gè)節(jié)點(diǎn)的地址給到新節(jié)點(diǎn)，再把指定位置pos節(jié)點(diǎn)的地址成員改成新節(jié)點(diǎn)的地址，否則就會(huì)導(dǎo)致后面那個(gè)節(jié)點(diǎn)地址的丟失，沒(méi)辦法接到新節(jié)點(diǎn)后面了

? ? ? ? 還有就是我們不需要知道鏈表的頭節(jié)點(diǎn)是什么了，只需要關(guān)注pos就行了

??????????????????????????????????????

????????

2.6?在任意位置刪除節(jié)點(diǎn)

2.6.1?刪除pos節(jié)點(diǎn)

? ? ? ? 刪除pos節(jié)點(diǎn)要先知道它前面的那個(gè)節(jié)點(diǎn)prev，然后把prev跟pos后面那個(gè)節(jié)點(diǎn)先連起來(lái)，最后再把pos釋放掉。還有要注意的一點(diǎn)就是當(dāng)pos就是鏈表頭節(jié)點(diǎn)的時(shí)候要特殊處理一下

????????????????????????????????????????

????????

2.6.2?刪除pos后面的一個(gè)節(jié)點(diǎn)

? ? ? ? 這個(gè)功能也是只需要關(guān)注pos后面的內(nèi)容就行，所以只需要傳pos一個(gè)參數(shù)。還要注意一點(diǎn)就是pos不能是鏈表中的最后一個(gè)節(jié)點(diǎn)，否則它后面沒(méi)有節(jié)點(diǎn)了還刪什么

???????????????????????

???????????????????????

2.7 鏈表的銷毀

? ? ? ? 兩個(gè)變量，pcur記錄當(dāng)前要準(zhǔn)備銷毀的節(jié)點(diǎn)地址，next記錄下一個(gè)節(jié)點(diǎn)地址，防止銷毀上一個(gè)節(jié)點(diǎn)之后找不到下一個(gè)節(jié)點(diǎn)了。然后兩個(gè)變量一直循環(huán)向后掃描銷毀，直到pcur指向NULL

??????????????????????????????????????

????????????????????????

3. 鏈表的分類

????????鏈表按帶頭或不帶頭，單向或雙向，循環(huán)或不循環(huán)，排列組合有8種

????????我們剛剛學(xué)的單鏈表全稱就是：不帶頭單向不循環(huán)鏈表

????????帶頭不帶頭是說(shuō)鏈表有沒(méi)有一個(gè)不存儲(chǔ)有效數(shù)據(jù)的節(jié)點(diǎn)，放在第一個(gè)存放有效數(shù)據(jù)節(jié)點(diǎn)之前

??????????????????????????????????????

????????單向雙向是說(shuō)鏈表能通過(guò)后一項(xiàng)找到前一項(xiàng)就是雙向的，如果只能根據(jù)前一項(xiàng)找到后一項(xiàng)鏈表就是單項(xiàng)的?；蛘哒f(shuō)雙向鏈表的節(jié)點(diǎn)中的兩個(gè)存放地址的成員中，一個(gè)存下一個(gè)節(jié)點(diǎn)的地址，一個(gè)存上一個(gè)節(jié)點(diǎn)的地址。

??????????????????????????????????????

????????循環(huán)不循環(huán)是說(shuō)最后一個(gè)節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)就是循環(huán)鏈表，要是最后一個(gè)節(jié)點(diǎn)指向NULL就是不循環(huán)鏈表

????????????????????????

????????雖然鏈表的種類很多，但是常用的只有兩種：

????????????????1.單鏈表(不帶頭單向不循環(huán)鏈表)

? ? ? ? 單鏈表結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存貯數(shù)據(jù)，它一般作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)出現(xiàn)

????????????????2.雙向鏈表(帶頭雙向循環(huán)鏈表)

? ? ? ? 雙向鏈表結(jié)構(gòu)最復(fù)雜，一般用來(lái)單獨(dú)存儲(chǔ)數(shù)據(jù)。它雖然復(fù)雜，但是之后實(shí)現(xiàn)它的實(shí)際就會(huì)發(fā)現(xiàn)它有很多優(yōu)勢(shì)，致使實(shí)現(xiàn)它反而變得簡(jiǎn)單了，后面會(huì)有實(shí)現(xiàn)它的章節(jié)的。

4. 本節(jié)代碼

? ? ? ? SList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//鏈表是由節(jié)點(diǎn)構(gòu)成的
typedef int SLTDataType;typedef struct SListNode 
{SLTDataType data;struct SListNode* next;
}SLTNode;//鏈表的打印
void SLTPrint(SLTNode* phead); //鏈表的插入
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//鏈表的頭刪和尾刪
//尾刪
void SLTPopBack(SLTNode** pphead);
//頭刪
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//在任意位置插入數(shù)據(jù)
//在指定位置前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//在任意位置刪除節(jié)點(diǎn)
//刪除pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos);
//刪除pos后面的一個(gè)節(jié)點(diǎn)
void SLTEraseAfter(SLTNode* pos);//銷毀鏈表
void SLTDestory(SLTNode** pphead);

? ? ? ? SList.c

#include"SList.h"//鏈表的打印	
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//申請(qǐng)一個(gè)新節(jié)點(diǎn)
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;return newnode;
}//鏈表的插入
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//申請(qǐng)一個(gè)新節(jié)點(diǎn)SLTNode* newnode = SLTBuyNode(x);//鏈表為空，新節(jié)點(diǎn)作為頭if (*pphead == NULL){*pphead = newnode;return;}//鏈表不為空，找尾節(jié)點(diǎn)SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//找到尾節(jié)點(diǎn)了ptail->next = newnode;
}//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//申請(qǐng)一個(gè)新節(jié)點(diǎn)SLTNode* newnode = SLTBuyNode(x);//鏈表為不為空，操作都一樣//斬?cái)嗟谝粋€(gè)連接，再把新節(jié)點(diǎn)接進(jìn)去newnode->next = *pphead;*pphead = newnode;
}//鏈表的頭刪和尾刪
//尾刪
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//鏈表不能為空assert(*pphead);//鏈表不為空//鏈表只有一個(gè)節(jié)點(diǎn)if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}//鏈表有多個(gè)節(jié)點(diǎn)SLTNode* ptail = *pphead;SLTNode* prev = NULL;//找到尾節(jié)點(diǎn)while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}//頭刪
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//鏈表不能為空assert(*pphead);//讓第二個(gè)節(jié)點(diǎn)變成新的頭節(jié)點(diǎn)//釋放舊的頭節(jié)點(diǎn)SLTNode* sec = (*pphead)->next;free(*pphead);*pphead = sec;
}//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍歷鏈表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//在任意位置插入數(shù)據(jù)
//在指定位置前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//這里斷言*pphead不能為空//因?yàn)橹付ü?jié)點(diǎn)的地址pos不能為空，所以這個(gè)鏈表也不能為空assert(*pphead);//當(dāng)pos是頭節(jié)點(diǎn),執(zhí)行頭插if (pos == *pphead){SLTPushFront(pphead, x);return;}//當(dāng)pos不是頭節(jié)點(diǎn)//申請(qǐng)一個(gè)新節(jié)點(diǎn)SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;
}//在指定位置后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);//申請(qǐng)一個(gè)新節(jié)點(diǎn)SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//在任意位置刪除節(jié)點(diǎn)
//刪除pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);assert(*pphead);//如果pos指向頭節(jié)點(diǎn)，執(zhí)行頭刪if (*pphead == pos){SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}//刪除pos后面的一個(gè)節(jié)點(diǎn)
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//pos->next不能為空//就是說(shuō)pos不能是最后一個(gè)節(jié)點(diǎn)assert(pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}//銷毀鏈表
void SLTDestory(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;SLTNode* next = NULL;while (pcur){next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}