???W…Y：個(gè)人主頁(yè)
在學(xué)習(xí)之前看一下美麗的夕陽(yáng)，也是很不錯(cuò)的。
如果覺(jué)得博主的美景不錯(cuò)，博客也不錯(cuò)的話，關(guān)注一下博主吧??
在上一期中，我們說(shuō)完了順序表，并且提出順序表中的問(wèn)題
1. 中間/頭部的插入刪除，時(shí)間復(fù)雜度為O(N)
2. 增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗。
3. 增容一般是呈2倍的增長(zhǎng)，勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到 200，我們?cè)倮^續(xù)插入了5個(gè)數(shù)據(jù)，后面沒(méi)有數(shù)據(jù)插入了，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間。
思考：如何解決以上問(wèn)題呢？
今天的鏈表就會(huì)解決這些順序表中出現(xiàn)的問(wèn)題。那什么是鏈表呢？
目錄
鏈表
鏈表的概念及結(jié)構(gòu)
鏈表的分類
無(wú)頭(無(wú)哨兵位)單鏈表實(shí)現(xiàn)
單鏈表結(jié)構(gòu)
創(chuàng)建節(jié)點(diǎn)
?打印鏈表內(nèi)容
頭插
尾插
頭刪
?尾刪
查找需要內(nèi)容具體位置?
其他功能
鏈表
鏈表的概念及結(jié)構(gòu)
概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表 中的指針鏈接次序?qū)崿F(xiàn)的 。
鏈表如同小火車，一節(jié)與一節(jié)相關(guān)聯(lián)
注意：
1.鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但在物理上不一定連續(xù)。
2.節(jié)點(diǎn)都是從堆上申請(qǐng)的。
3.從堆上申請(qǐng)空間，是按一定策略分配的，申請(qǐng)的空間可能連續(xù)，可能不連續(xù)。?
假設(shè)在32位系統(tǒng)上，結(jié)點(diǎn)中值域?yàn)閕nt類型，則一個(gè)節(jié)點(diǎn)的大小為8個(gè)字節(jié)，則也可能有下述鏈表：
鏈表的分類
實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu)：
1. 單向或者雙向
2. 帶頭或者不帶頭
3. 循環(huán)或者非循環(huán)
雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)：
?1. 無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
2. 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(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)單了，后面我們代碼實(shí)現(xiàn)了就知道了。
下面就是對(duì)無(wú)哨兵位單鏈表實(shí)現(xiàn)?
無(wú)頭(無(wú)哨兵位)單鏈表實(shí)現(xiàn)
單鏈表結(jié)構(gòu)
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;使用typedef將int 與結(jié)構(gòu)體重命名更好的使用清晰，定義next指針需要指向下一個(gè)結(jié)構(gòu)的地址方便鏈接。
單鏈表是只有一個(gè)指針指向后面節(jié)點(diǎn)，當(dāng)頭部指針向后移動(dòng)時(shí)就找不到前面的節(jié)點(diǎn)了，所以在創(chuàng)建單鏈表時(shí)，我們要?jiǎng)?chuàng)建一個(gè)結(jié)構(gòu)體指針變量固定在頭位置，確保這個(gè)單鏈表完整性
我們?cè)谥骱瘮?shù)中創(chuàng)建：SLTNode* plist = NULL;
plist要等于鏈表中的第一個(gè)結(jié)構(gòu)體的地址，防止找不到鏈表的頭部。
創(chuàng)建節(jié)點(diǎn)
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}?將需要存放的數(shù)據(jù)傳入創(chuàng)建節(jié)點(diǎn)函數(shù)，使用malloc在堆中創(chuàng)建需要的空間。在這里我們必須對(duì)創(chuàng)建的空間進(jìn)行檢測(cè)是否創(chuàng)建成功，否則直接將退出程序。
創(chuàng)建出的空間也是結(jié)構(gòu)體，我們需要給data賦需要存儲(chǔ)的數(shù)據(jù)，將next賦值為空，否則將成為野指針。將創(chuàng)建好的空間進(jìn)行返回即可。
?打印鏈表內(nèi)容
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}創(chuàng)建一個(gè)可以遍歷的指針，進(jìn)行逐一遍歷打印即可。
頭插
頭插在進(jìn)行過(guò)程中，一定會(huì)改變plist指向的節(jié)點(diǎn)，無(wú)論鏈表是否為空過(guò)程都是相同的，所以我們?cè)陬^插時(shí)一定會(huì)改變指針plist指向的內(nèi)容，所以這是我們就得傳入plist的地址進(jìn)行調(diào)用修改，這時(shí)我們就得使用二級(jí)指針進(jìn)行操作。
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
先將*pphead指向的空間賦給新創(chuàng)建的空間中的next，再使用二級(jí)指針將頭指針的內(nèi)容修改為新空間的地址即可。
尾插
在創(chuàng)建尾插函數(shù)時(shí)，我們就要考慮鏈表是否為空，當(dāng)我們?cè)阪湵頌榭諘r(shí)進(jìn)行尾插，就必須改變頭指針，所以尾插這個(gè)函數(shù)應(yīng)該分情況進(jìn)行：
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
//改變的結(jié)構(gòu)體的指針，所以要用二級(jí)指針
*pphead = newnode;
}
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
//改變的為結(jié)構(gòu)體，所以用一級(jí)指針
tail->next = newnode;
}
?再往后插入就不需要對(duì)頭指針做動(dòng)作了。
?所以這里我們一定要把問(wèn)題想周全，要不然程序就會(huì)報(bào)錯(cuò)甚至直接崩潰。
頭刪
void SLTPopFront(SLTNode** pphead);
{
assert(*pphead);
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}?頭刪時(shí)我們應(yīng)該先創(chuàng)建一個(gè)臨時(shí)指針指向需要釋放的空間，如果直接釋放空間，我們就使鏈表直接“斷裂”，找不到下一個(gè)節(jié)點(diǎn)地址。
當(dāng)我們進(jìn)行頭刪時(shí)，需要判斷鏈表是否為空鏈表再進(jìn)行釋放。在頭刪時(shí)，頭指針的地址就應(yīng)該指向下一個(gè)節(jié)點(diǎn)地址，我們應(yīng)該提前進(jìn)行標(biāo)記，在釋放完成后將下一個(gè)節(jié)點(diǎn)地址再次付給頭指針即可。
?尾刪
尾刪和尾插都要考慮很多，尾刪要考慮兩種情況：1.只有一個(gè)節(jié)點(diǎn)2.有很多節(jié)點(diǎn)。當(dāng)只剩最后一個(gè)節(jié)點(diǎn)時(shí)，我們刪除時(shí)就要改變頭指針，將頭指針置空。我們一般使用兩個(gè)指針，一個(gè)指向尾節(jié)點(diǎn)，一個(gè)指向尾節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)。當(dāng)尾節(jié)點(diǎn)釋放后，我們使用另一個(gè)指針將其next置空即可。
void SLTPopBack(SLTNode** pphead)
{
assert(*pphead == NULL);
if ((*pphead)->next = NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tailPrev = NULL;
SLTNode* tail = *pphead;
while (tail->next)
{
tailPrev = tail;
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;
}
}
假設(shè)只剩最后一個(gè)節(jié)點(diǎn)：
?在空鏈表時(shí)，我們一定要進(jìn)行判斷assert(*pphead)，防止出錯(cuò)。?
查找需要內(nèi)容具體位置?
當(dāng)我們想要知道我們存儲(chǔ)的數(shù)據(jù)在哪個(gè)位置時(shí)，我們就需要進(jìn)行查找，返回其地址即可
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* find = phead;
while (find)
{
if (find->data == x)
return find;
find = find->next;
}
printf("沒(méi)找到\n");
return NULL;
}這里我們依舊使用暴力查找法，進(jìn)行逐一對(duì)比查找?。?！
單鏈表的基本功能我們已經(jīng)形成，我們已經(jīng)完成了頭插、尾插、頭刪、尾刪。單鏈表的基本內(nèi)容和注意事項(xiàng)已經(jīng)強(qiáng)調(diào)。我們其實(shí)還可以繼續(xù)完善單鏈表，使其功能更加強(qiáng)大，在這里博主就不過(guò)多的說(shuō)明了，其中的原理和注意事項(xiàng)和前面差不多。
現(xiàn)在我將剩下一些功能逐一展現(xiàn)供大家參考：
其他功能
//在pos之前插入x
void SLTNInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//刪除pos的后一個(gè)位置
void SLTEraseAfter(SLTNode* pos);在pos之前插入x：?
void SLTNInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && pos);
SLTNode* newnode = BuySListNode(x);
SLTNode* find = *pphead;
SLTNode* finding = NULL;
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
return;
}
else
while (find != pos)
{
finding = find;
find = find->next;
}
finding->next = newnode;
newnode->next = find;
}在pos之后插入x：
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}刪除pos位置的數(shù)據(jù)：
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead&&pos);
SLTNode* find = *pphead;
SLTNode* finding = NULL;
while (find != pos)
{
finding = find;
find = find->next;
}
if (*pphead == pos)
{
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}
else
{
finding->next = find->next;
free(find);
find = NULL;
}
}刪除pos之后的數(shù)據(jù)：
void SLTErasetAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
printf("后面沒(méi)有數(shù)可以刪除\n");
return;
}
else
{
pos->next = pos->next->next;
free(pos);
pos = NULL;
}
}
以上就是復(fù)現(xiàn)無(wú)頭單鏈表的全部?jī)?nèi)容，有興趣的可以繼續(xù)打磨添加一些新功能。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-627176.html
本期內(nèi)容到這里就結(jié)束了，覺(jué)得博主內(nèi)容有用的關(guān)注一下博主，一健三連是對(duì)博主最大的鼓勵(lì)！再次感謝大家觀看?。?！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-627176.html
到了這里，關(guān)于鏈表的總體涵蓋以及無(wú)哨兵位單鏈表實(shí)現(xiàn)——【數(shù)據(jù)結(jié)構(gòu)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
