之前有一篇文章介紹完順序表，可以點(diǎn)擊(順序表文章)即可看到順序表的知識(shí)后，我們就要開(kāi)始學(xué)習(xí)鏈表了，鏈表的種類有很多，比如說(shuō)單鏈表、雙向鏈表、循環(huán)或者非循環(huán)鏈表以及帶頭或者不帶頭鏈表等，那么鏈表和順序表有哪些不同呢，相較于順序表，鏈表做了哪些改變呢，有什么優(yōu)勢(shì)呢？今天我就帶大家先了解最簡(jiǎn)單的鏈表——單鏈表。
一萬(wàn)字詳細(xì)解說(shuō)單鏈表，順序表有關(guān)知識(shí)詳細(xì)解答~??
目錄
一.鏈表的概念及結(jié)構(gòu)
1.1鏈表的概念
1.2 鏈表的結(jié)構(gòu)
二.單鏈表和順序表區(qū)別
2.1名字區(qū)別?
2.1單鏈表和順序表的區(qū)別與優(yōu)缺點(diǎn)
?編輯
三.八種鏈表類型
ps:頭指針和頭結(jié)點(diǎn)
ps:帶哨兵位和不帶哨兵位
3.1單向帶頭循環(huán)鏈表
3.2單向帶頭非循環(huán)鏈表
3.3單向不帶頭循環(huán)鏈表
3.4 單向不帶頭非循環(huán)鏈表
3.5 雙向帶頭循環(huán)鏈表
3.6雙向帶頭非循環(huán)鏈表
3.7 雙向不帶頭循環(huán)鏈表
3.8雙向不帶頭非循環(huán)鏈表
?四.單鏈表的說(shuō)明與實(shí)現(xiàn)
單鏈表的定義
單鏈表的特點(diǎn)
單鏈表的實(shí)現(xiàn)
4.1單鏈表的結(jié)構(gòu)定義
4.2 鏈表的功能
4.3鏈表的功能實(shí)現(xiàn)
ps:assert斷言的使用
4.3.1打印鏈表
4.3.2創(chuàng)建結(jié)點(diǎn)
4.3.3 單鏈表尾插
4.3.4 單鏈表尾刪
4.3.5單鏈表頭刪
4.3.6單鏈表的頭插
4.3.7查找某個(gè)結(jié)點(diǎn)
4.3.8刪除某個(gè)結(jié)點(diǎn)
4.3.9單鏈表刪除pos位置之后的結(jié)點(diǎn)
4.3.10單鏈表結(jié)點(diǎn)修改
?編輯
4.3.11?單鏈表pos前插入結(jié)點(diǎn)?
4.3.12單鏈表pos后插入結(jié)點(diǎn)?
4.3.13對(duì) 4.3.7~~4.3.12實(shí)踐檢測(cè)
4.3.14銷(xiāo)毀鏈表
五.源代碼?
1.SL.h
2.SL.c?
3.test-SL.c
一.鏈表的概念及結(jié)構(gòu)
1.1鏈表的概念
概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)，非順序的存儲(chǔ)結(jié)構(gòu)，但鏈表在邏輯上是連續(xù)的，順序的，而數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針連接次序?qū)崿F(xiàn)的。
1.2 鏈表的結(jié)構(gòu)
鏈表是由一個(gè)個(gè)結(jié)點(diǎn)組成的，結(jié)點(diǎn)如下圖所示：
?鏈表中的最后一個(gè)結(jié)點(diǎn)的next指向空，next=NULL。
一個(gè)個(gè)結(jié)點(diǎn)串成了鏈表，如下圖所示：
??有人可能會(huì)有疑問(wèn)，不是說(shuō)鏈表只是在邏輯結(jié)構(gòu)上是連續(xù)的，在物理存儲(chǔ)結(jié)構(gòu)上是不連續(xù)的，那為什么上圖中一個(gè)個(gè)結(jié)點(diǎn)明明是挨在一起的，那么它在物理存儲(chǔ)結(jié)構(gòu)上肯定是連續(xù)的呀，其實(shí)不然，上圖是為了方便大家理解，才用線條連接了結(jié)點(diǎn)，實(shí)際上在內(nèi)存中，每個(gè)結(jié)點(diǎn)可能會(huì)隔得很遠(yuǎn)，仔細(xì)觀察每個(gè)結(jié)點(diǎn)上面的紅色文字，那就是這個(gè)結(jié)點(diǎn)的地址，而藍(lán)色文字是下一個(gè)結(jié)點(diǎn)的地址，很明顯能看到這兩個(gè)結(jié)點(diǎn)并不是相鄰的，因此也驗(yàn)證了順序表在邏輯結(jié)構(gòu)上確實(shí)是連續(xù)的，但在物理存儲(chǔ)結(jié)構(gòu)上確實(shí)是不連續(xù)的。
二.單鏈表和順序表區(qū)別
2.1名字區(qū)別?
單鏈表的英文名——single linked list，我們簡(jiǎn)寫(xiě)成SL
順序表的SeqList或者SQL
2.1單鏈表和順序表的區(qū)別與優(yōu)缺點(diǎn)
這是兩種不同的存儲(chǔ)結(jié)構(gòu)，我們先談?wù)剠^(qū)別吧，
順序表是順序存儲(chǔ)結(jié)構(gòu)，它的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰。
但是鏈表不同
鏈表是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，特點(diǎn)是不需要邏輯上相鄰的元素在物理位置上也相鄰。
因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以通過(guò)結(jié)點(diǎn)中的指針域直接找到下一個(gè)結(jié)點(diǎn)的位置。
?**單鏈表的優(yōu)缺點(diǎn)：
1.優(yōu)點(diǎn)：可以按照實(shí)際所需創(chuàng)建結(jié)點(diǎn)增減鏈表的長(zhǎng)度，更大程度地使用內(nèi)存。
2.缺點(diǎn)：進(jìn)行尾部或者任意位置上插入或刪除時(shí)時(shí)間復(fù)雜度和空間復(fù)雜度較大，每次都需要通過(guò)指針的移動(dòng)找到所需要的位置，相對(duì)于順序表查找而言效率較低。
互補(bǔ)關(guān)系
**順序表的優(yōu)缺點(diǎn)：
1.優(yōu)點(diǎn)：可以通過(guò)下標(biāo)直接訪問(wèn)所需要的數(shù)據(jù)
2.缺點(diǎn)：不能按實(shí)際所需分配內(nèi)存，只能使用malloc或者realloc函數(shù)進(jìn)行擴(kuò)容，容易實(shí)現(xiàn)頻繁擴(kuò)容，容易導(dǎo)致內(nèi)存浪費(fèi)與數(shù)據(jù)泄露等問(wèn)題。
ps：我們拿一個(gè)指針指向一塊連續(xù)的空間，然后有一個(gè)size記錄當(dāng)前有效數(shù)據(jù)，capicity記錄容量，這樣好處是我們可以通過(guò)下標(biāo)來(lái)訪問(wèn)其中每一個(gè)數(shù)據(jù)，但缺點(diǎn)是當(dāng)我們開(kāi)辟數(shù)組的時(shí)候，第一個(gè)數(shù)組容量可能是10，然后我們放11個(gè)元素進(jìn)去，這個(gè)時(shí)候空間不夠，我們就重新開(kāi)辟空間，一般我們開(kāi)辟空間都是直接將原空間翻倍，但這里20個(gè)空間只放11個(gè)元素，空間就有些浪費(fèi)了。
三.八種鏈表類型
在了解鏈表的類型之前，我們需要了解鏈表的幾個(gè)特點(diǎn)：
1.單向和雙向
2.帶哨兵位和不帶哨兵位
3.循環(huán)和非循環(huán)
我們可以通過(guò)組合的方式，如：?jiǎn)蜗驇ь^循環(huán)鏈表，雙向不帶頭非循環(huán)鏈表
?每一層都有2種類型，所以2*2 *2總共有8種類型鏈表
ps:頭指針和頭結(jié)點(diǎn)
通常會(huì)用頭指針來(lái)標(biāo)識(shí)一個(gè)單鏈表，頭指針為NULL時(shí)表示一個(gè)空表。但是，為了操作方便，會(huì)在單鏈表的第一個(gè)結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不設(shè)任何信息，也可以記錄表長(zhǎng)等信息。頭結(jié)點(diǎn)的指針域指向線性表的第一個(gè)元素結(jié)點(diǎn)。如下圖所示：
頭結(jié)點(diǎn)數(shù)據(jù)域可以不設(shè)置值，指針域指向第一個(gè)元素的結(jié)點(diǎn)
?頭結(jié)點(diǎn)和頭指針的區(qū)分：不管帶不帶頭結(jié)點(diǎn)，頭指針始終指向單鏈表的第一個(gè)結(jié)點(diǎn)，而頭結(jié)點(diǎn)是帶頭結(jié)點(diǎn)的單鏈表中的第一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)內(nèi)通常不存儲(chǔ)信息。?
ps:帶哨兵位和不帶哨兵位
帶頭結(jié)點(diǎn)之后，什么情況下形參必須傳二級(jí)指針（或者一級(jí)指針的引用）
***如果鏈表有頭結(jié)點(diǎn)，那么頭指針就是指向頭結(jié)點(diǎn)數(shù)據(jù)域的指針。?
***單鏈表也可以沒(méi)有頭結(jié)點(diǎn)，沒(méi)有頭結(jié)點(diǎn)的單鏈表??
??
?3.1單向帶頭循環(huán)鏈表
?3.2單向帶頭非循環(huán)鏈表
?3.3單向不帶頭循環(huán)鏈表
3.4 單向不帶頭非循環(huán)鏈表
3.5 雙向帶頭循環(huán)鏈表
?3.6雙向帶頭非循環(huán)鏈表
3.7 雙向不帶頭循環(huán)鏈表
?3.8雙向不帶頭非循環(huán)鏈表
?四.單鏈表的說(shuō)明與實(shí)現(xiàn)
單鏈表的定義
由于順序表的插入刪除操作需要移動(dòng)大量的元素，影響了運(yùn)行效率，因此引入了線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表。單鏈表通過(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素，不需要使用地址連續(xù)的存儲(chǔ)單元，因此它不要求在邏輯上相鄰的兩個(gè)元素在物理位置上也相鄰。
單鏈表的特點(diǎn)
- 單鏈表不要求邏輯上相鄰的兩個(gè)元素在物理位置上也相鄰，因此不需要連續(xù)的存儲(chǔ)空間。
- 單鏈表是非隨機(jī)的存儲(chǔ)結(jié)構(gòu)，即不能直接找到表中某個(gè)特定的結(jié)點(diǎn)。查找某個(gè)特定的結(jié)點(diǎn)時(shí)，需要從表頭開(kāi)始遍歷，依次查找。
包括倆個(gè)域：
1.數(shù)據(jù)域: 存儲(chǔ)數(shù)據(jù)元素信息的域
2.指針域：存儲(chǔ)直接后繼存儲(chǔ)位置的域
指針域中存儲(chǔ)的信息稱為指針或鏈，n個(gè)結(jié)點(diǎn)（數(shù)據(jù)元素的存儲(chǔ)映像）鏈接成一個(gè)鏈表
每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，稱為線性鏈表或單鏈表
?對(duì)于每個(gè)鏈表結(jié)點(diǎn)，除了存放元素自身的信息外，還需要存放一個(gè)指向其后繼的指針。?
typedef int SLDateType;
typedef struct SLTNode定義單鏈表結(jié)點(diǎn)類型
{
SLDateType data;//數(shù)據(jù)域，可以是別的各種數(shù)據(jù)類型，只用將上面的int改成其他類型即可
struct SLTNode* next;指針域
}SLTNode;
單鏈表的實(shí)現(xiàn)
下面我們實(shí)現(xiàn)的單鏈表是很多數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，也就是單向不帶頭非循環(huán)鏈表。
4.1單鏈表的結(jié)構(gòu)定義
單鏈表的結(jié)構(gòu)與順序表是完全不同的，分為倆個(gè)部分數(shù)據(jù)域和指針域
typedef int SLDateType;
typedef struct SLTNode
{
SLDateType data;
struct SLTNode* next;
}SLTNode;
4.2 鏈表的功能
鏈表要實(shí)現(xiàn)那些功能呢？其實(shí)這些功能我們都很熟悉，數(shù)據(jù)結(jié)構(gòu)無(wú)非是對(duì)數(shù)據(jù)進(jìn)行管理，要實(shí)現(xiàn)數(shù)據(jù)的增刪查改，因此鏈表的基本功能也都是圍繞著數(shù)據(jù)的增刪查改展開(kāi)。
//創(chuàng)建一個(gè)結(jié)點(diǎn)
SLTNode* BuyListNode(SLTDateType x);
//銷(xiāo)毀單鏈表
void SLTDestory(SLTNode** pphead);
//單鏈表頭插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
//單鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
//單鏈表頭刪
void SLTPopFront(SLTNode** pphead);
//單鏈表尾刪
void SLTPopBack(SLTNode** pphead);
//單鏈表結(jié)點(diǎn)查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x);
//單鏈表結(jié)點(diǎn)刪除(刪除pos位置的結(jié)點(diǎn))
void SLTErase(SLTNode** pphead, SLTNode* pos);
//單鏈表結(jié)點(diǎn)刪除(刪除pos位置之后的結(jié)點(diǎn))
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);
//單鏈表結(jié)點(diǎn)插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 單鏈表結(jié)點(diǎn)插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 單鏈表結(jié)點(diǎn)修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x);
//打印單鏈表
void SLTPrint(SLTNode* phead);如何分別傳送一級(jí)指針與二級(jí)指針
我們可以看到上面的接口，有的使用一級(jí)指針，而有的則使用二級(jí)指針。這是為什么呢？->這是因?yàn)橛行┙涌谛枰婕案淖儗?shí)參（更改節(jié)點(diǎn)內(nèi)部的內(nèi)容），所以
需要二級(jí)指針傳參，如果使用一級(jí)指針改變實(shí)參是無(wú)法修改實(shí)參的，使用一級(jí)指針只會(huì)修改這個(gè)一級(jí)指針的指針變量的地址，無(wú)法找到實(shí)參的地址。
比如：如果要改變鏈表的頭指針就傳二級(jí)指針，改變頭指針不能傳一級(jí)指針因?yàn)閭魉偷倪^(guò)程就是拷貝的過(guò)程，相當(dāng)于將頭指針復(fù)制了一份，形參的改變不會(huì)影響實(shí)參，因此要改變鏈表的頭指針需要傳送二級(jí)指針。
若傳入二級(jí)指針時(shí)，必須assert斷言其是否為空。而若為一級(jí)指針，則無(wú)需判斷，因?yàn)槿翩湵頌榭?，則其值便是NULL。
4.3鏈表的功能實(shí)現(xiàn)
ps:assert斷言的使用
assert這個(gè)函數(shù)在指針傳參的時(shí)候非常好用，在鏈表中我們用來(lái)判斷鏈表指針是否為空。
而且assert函數(shù)在調(diào)試的時(shí)候非常好用，一旦指針為空，會(huì)立刻報(bào)錯(cuò)，**而且會(huì)幫我提示報(bào)錯(cuò)在哪個(gè)文件和在哪行代碼。**在以后實(shí)戰(zhàn)項(xiàng)目中對(duì)我們有很好的幫助，所以要善于利用assert函數(shù)
斷言
空鏈表可以打印，不用斷言
空鏈表能尾插，*pphead不用斷言，pphead需要斷言，因?yàn)?strong>pphead是指向plist的地址，它永遠(yuǎn)不能為空
空鏈表能頭插，*pphead不用斷言，pphead需要斷言，因?yàn)?strong>pphead是指向plist的地址，它永遠(yuǎn)不能為空
空鏈表不能尾刪頭刪，*pphead需要斷言，pphead也需要斷言，因?yàn)閜phead是指向plist的地址，是頭指針的地址
pphead需要在所有地方斷言，因?yàn)橛肋h(yuǎn)不能為空
*pphead要結(jié)合場(chǎng)景來(lái)判斷是否需要斷言，比如插入不需要斷言，空鏈表是可以為空的，但是刪除是需要斷言的，如果空鏈表刪除是不可以的。
pphead是指向plist的地址，但是pphead解引用的值是plist的值,pphead本身就有地址，所以pphead是不可能是NULL的，pphead是指向plist頭指針的地址。plist是頭指針，plist是存放頭結(jié)點(diǎn)的地址，plist解引用后就是頭結(jié)點(diǎn)的值。
4.3.1打印鏈表
注意：鏈表和順序不同的是，順序表傳過(guò)來(lái)的指針是肯定不會(huì)為空的，而鏈表傳過(guò)來(lái)的指針是可能為空的，比如說(shuō)當(dāng)鏈表中沒(méi)有元素時(shí)，頭指針?biāo)赶虻木褪荖ULL，如果在第一行寫(xiě)上斷言就會(huì)有問(wèn)題。
當(dāng)cur指向空的時(shí)候就可以停止打印了。
//打印單鏈表
void SLTPrint(SLTNode* phead)
{
//不需要斷言assert(phead);
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
printf("\n");
}
在打完以上代碼之后，我相信一定有很多疑惑，比如：
為什么不用斷言？為什么將phead賦值給cur？為什么不是cur++而是cur->next?這三個(gè)疑惑也曾經(jīng)疑惑著我，現(xiàn)在我明白了，我來(lái)給你們細(xì)細(xì)說(shuō)上.....
為什么鏈表打印不用斷言？而順序表中指針都需要斷言？
單鏈表：?jiǎn)捂湵碇袥](méi)有元素時(shí)，頭指針?biāo)赶虻木褪荖ULL，結(jié)點(diǎn)表示空，結(jié)點(diǎn)為空直接打印空就行了，如果這個(gè)頭指針指向的是NULL，那么就是個(gè)空表，如果在第一行寫(xiě)上斷言就會(huì)有問(wèn)題?？战Y(jié)點(diǎn)是代表沒(méi)有結(jié)點(diǎn)也一樣可以打印的，只是NULL而已。
順序表：而順序表是一個(gè)結(jié)構(gòu)體包含了三個(gè)成員變量（a數(shù)組，size，capacity),指針指向一塊數(shù)組空間，由size來(lái)決定是不是空，但是指向的空間都是空的，就不用size判斷了。
為什么將phead賦值給cur？
當(dāng)我們遍歷單鏈表的時(shí)候，最好給一個(gè)另外的變量賦值去遍歷，因?yàn)槲覀冇袝r(shí)候會(huì)需要找到頭的地址，為了不丟失頭指針的地址，所以我們不用頭指針phead自己遍歷單鏈表。
cur=cur->next,為什么不是cur++?
結(jié)合邏輯和物理結(jié)構(gòu)
在邏輯結(jié)構(gòu)上是連續(xù)的，但是在物理結(jié)構(gòu)上可能是不連續(xù)的，因此不能保證鏈表中每個(gè)結(jié)點(diǎn)都是連續(xù)的，所以不能cur++
通過(guò)對(duì)以上的分析，大家對(duì)細(xì)節(jié)部分更加理解通透，進(jìn)行后面的功能實(shí)現(xiàn)吧
4.3.2創(chuàng)建結(jié)點(diǎn)
后面我們要在單鏈表中進(jìn)行頭插和尾插，此時(shí)插入的不再是像順序表一樣簡(jiǎn)單的SLDateType數(shù)據(jù)了，而是一個(gè)結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)是包括SLTDateType數(shù)據(jù)以及SLTDateType*的指針，因此，為了方便和減少代碼的重復(fù)度，我們另寫(xiě)一個(gè)函數(shù)用來(lái)專門(mén)創(chuàng)建新結(jié)點(diǎn)。
//創(chuàng)建一個(gè)結(jié)點(diǎn)
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail:");
return 1;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}4.3.3 單鏈表尾插
注意：在創(chuàng)建結(jié)點(diǎn)時(shí)，已經(jīng)讓?結(jié)點(diǎn).next=NULL，所以不需要在插入完結(jié)點(diǎn)后，再讓新結(jié)點(diǎn)的next指針為NULL。
//單鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
//鏈表為空
//鏈表不為空
if (*pphead == NULL)
{
*pphead = newnode;
//不需要讓newnode->next=NULL,在BuySLTNode中我們就已經(jīng)進(jìn)行過(guò)這個(gè)操作了
}
else
{
//先找到鏈表的尾部
SLTNode*tail= *pphead;
while (tail->next!=NULL)
{
tail= tail->next;
}
tail->next =newnode;
}
}
?
?
在敲完以上代碼之后，大家肯定又有一些疑惑？
比如：為什么要傳二級(jí)指針？為什么尾插又要斷言了？為什么不是tail!=NULL而是tail->next!=NULL這倆個(gè)問(wèn)題曾經(jīng)也想過(guò)，現(xiàn)在給你們解答
為什么要傳二級(jí)指針？
在函數(shù)中如果需要改變鏈表中的頭節(jié)點(diǎn)地址，則傳參的時(shí)候需要傳址調(diào)用，結(jié)合參數(shù)已經(jīng)是指針了，形參用二級(jí)指針接收。
因?yàn)榻Y(jié)構(gòu)體里面的next本身就是一個(gè)一級(jí)指針，尾插和頭插，都會(huì)改變結(jié)構(gòu)體里面存儲(chǔ)的數(shù)據(jù)，而修改一級(jí)指針的內(nèi)容就需要去二級(jí)指針來(lái)存儲(chǔ)一級(jí)指針的地址，并傳址才能改變單鏈表的內(nèi)容，如果使用一級(jí)指針來(lái)存儲(chǔ)一級(jí)指針的地址出了循環(huán)以后就會(huì)銷(xiāo)毀，并不會(huì)影響單鏈表的內(nèi)容也不能增刪查改和管理存儲(chǔ)數(shù)據(jù)。相當(dāng)于形參與實(shí)參的差別。形參不會(huì)影響實(shí)參的改變，只是實(shí)參的臨時(shí)的一份拷貝。所以要用二級(jí)指針。
鏈表為空的尾插：phead原先是空，需要尾插，需要將弄成二級(jí)指針，需要改變phead的值，所以要存下這個(gè)的地址，一級(jí)指針存一級(jí)指針的地址出了循環(huán)就銷(xiāo)毀了，需要用二級(jí)指針來(lái)存儲(chǔ)一級(jí)指針的地址，出了循環(huán)也會(huì)記住這個(gè)地址，記住phead新的地址，然后不為空了。
為什么斷言？
至于這個(gè)什么時(shí)候要斷言指針，什么時(shí)候不用斷言指針：一級(jí)指針也就是phead，當(dāng)鏈表為空的時(shí)候，phead就是為NULL，而二級(jí)指針永遠(yuǎn)指向phead，phead的地址是永遠(yuǎn)存在的，那么pphead就一定不可能為空，所以需要斷言pphead。
為什么這里是cur->next!= NULL,而不是cur!=NULL
這些是我曾經(jīng)出錯(cuò)的地方，還有什么需要解答的，可以在評(píng)論區(qū)寫(xiě)出疑惑，我會(huì)解答。
4.3.4 單鏈表尾刪
要想刪除鏈表中的元素，就必須保證原鏈表就有元素，因此要斷言assert(*pphead)
//單鏈表尾刪
void SLTPopBack(SLTNode** pphead)
{
//0.鏈表為空
assert(*pphead);
assert(pphead);
//1.鏈表一個(gè)結(jié)點(diǎn)
if ((*pphead)->next== NULL)
{
free(*pphead);
*pphead = NULL;
}
//2.多個(gè)結(jié)點(diǎn)
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = tail;
}
}
//2.多個(gè)結(jié)點(diǎn)
else
{
SLTNode* tail = *pphead;
while (tail->next->next!= NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next= NULL;
}
??4.3.5單鏈表頭刪
頭刪需要注意的就是要斷言即可
//單鏈表頭刪
void SLTPopFront(SLTNode** pphead)
{
assert(*pphead);
assert(pphead);
SLTNode*first= *pphead;
*pphead = first->next;
free(first);
first= NULL;
}
?
?4.3.6單鏈表的頭插
//單鏈表頭插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
4.3.7查找某個(gè)結(jié)點(diǎn)
這個(gè)函數(shù)返回值不再是void，而是SListNode*，把找到的結(jié)點(diǎn)的地址返回去，這個(gè)函數(shù)一般會(huì)跟結(jié)點(diǎn)修改之類的函數(shù)一起使用。
//單鏈表結(jié)點(diǎn)查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}4.3.8刪除某個(gè)結(jié)點(diǎn)
//單鏈表結(jié)點(diǎn)刪除(刪除pos位置的結(jié)點(diǎn))
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead);
assert(pphead);
assert(pos);
//頭刪
if (*pphead == pos)
{
SLTPopFront(pphead);
}
//非頭刪
else
{
SLTNode* prev = *pphead;
while (prev->next!= pos)
{
prev = prev->next;
assert(prev->next);
//這里為什么需要斷言
}
prev->next = pos->next;
free(pos);
}
}注意：
- pos也要斷言，pos可不能為空呀！
- prev->next也要斷言，因?yàn)楫?dāng)prev->next為NULL時(shí)，說(shuō)明整個(gè)鏈表的結(jié)點(diǎn)都排查完了，最后還是沒(méi)有找到地址為pos的結(jié)點(diǎn)，證明pos傳值有誤。
??
?4.3.9單鏈表刪除pos位置之后的結(jié)點(diǎn)
//單鏈表結(jié)點(diǎn)刪除(刪除pos位置之后的結(jié)點(diǎn))
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
assert(pos);
assert(pos->next);
assert(pphead);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
4.3.10單鏈表結(jié)點(diǎn)修改
// 單鏈表結(jié)點(diǎn)修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x)
{
assert(pos);
SLTNode* cur = phead;
while (cur!=pos)
{
cur = cur->next;
assert(cur);
}
pos->data = x;
}
4.3.11?單鏈表pos前插入結(jié)點(diǎn)?
//單鏈表結(jié)點(diǎn)插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pos);
assert(pphead);
//頭插
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
//找到前面一個(gè)位置
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
?4.3.12單鏈表pos后插入結(jié)點(diǎn)?
// 單鏈表結(jié)點(diǎn)插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
newnode->next= pos->next;
pos->next = newnode;
}
?
4.3.13對(duì) 4.3.7~~4.3.12實(shí)踐檢測(cè)
我們?nèi)绾伟堰@幾個(gè)函數(shù)使用起來(lái)呢，在初始完鏈表后，我們可以用SLTNodeFInd函數(shù)去找到一個(gè)結(jié)點(diǎn)（比如說(shuō)找到某個(gè)數(shù)據(jù)值是4的結(jié)點(diǎn)的地址），得到函數(shù)返回值——目標(biāo)結(jié)點(diǎn)的地址后，我們可以把它的地址作為pos傳給函數(shù)，比如說(shuō)SLTNodeModify函數(shù)，或者SLTNodeInsertBack函數(shù)，去修改順序表。
//刪除pos
SLTNode* pos = SLTNodeFind(plist, 5);
SLTErase(&plist, pos);
//刪除pos后結(jié)點(diǎn)
SLTNode* pos = SLTNodeFind(plist, 3);
SLTEraseAfter(&plist,pos);
//單鏈表結(jié)點(diǎn)修改
SLTNode* pos = SLTNodeFind(plist, 5);
SLTModify(plist, pos, 30);
//在pos之前插入
SLTNode* pos = SLTNodeFind(plist, 5);
SLTInsert(&plist,pos,30);
//在pos之后插入
SLTNode* pos = SLTNodeFind(plist, 5);
SLTInsertBack(&plist,pos,30);
SLTPrint(plist);
SLTDestory(&plist);4.3.14銷(xiāo)毀鏈表
銷(xiāo)毀鏈表這一塊，咱可不敢直接free(phead)，鏈表在物理結(jié)構(gòu)上是不連續(xù)存儲(chǔ)的，銷(xiāo)毀鏈表必須要一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)去銷(xiāo)毀?。。?！最后不要忘記把phead置為NULL。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-742190.html
//銷(xiāo)毀單鏈表
void SLTDestory(SLTNode** pphead)
{
assert(*pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}五.源代碼?
1.SL.h
#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SLTNode
{
SLTDateType data;
struct SLTNode* next;
}SLTNode;
//創(chuàng)建一個(gè)結(jié)點(diǎn)
SLTNode* BuyListNode(SLTDateType x);
//銷(xiāo)毀單鏈表
void SLTDestory(SLTNode** pphead);
//單鏈表頭插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
//單鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
//單鏈表頭刪
void SLTPopFront(SLTNode** pphead);
//單鏈表尾刪
void SLTPopBack(SLTNode** pphead);
//單鏈表結(jié)點(diǎn)查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x);
//單鏈表結(jié)點(diǎn)刪除(刪除pos位置的結(jié)點(diǎn))
void SLTErase(SLTNode** pphead, SLTNode* pos);
//單鏈表結(jié)點(diǎn)刪除(刪除pos位置之后的結(jié)點(diǎn))
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);
//單鏈表結(jié)點(diǎn)插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 單鏈表結(jié)點(diǎn)插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 單鏈表結(jié)點(diǎn)修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x);
//打印單鏈表
void SLTPrint(SLTNode* phead);2.SL.c?
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include"SL.h"
//打印單鏈表
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
printf("\n");
}
//銷(xiāo)毀單鏈表
void SLTDestory(SLTNode** pphead)
{
assert(*pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
//創(chuàng)建一個(gè)結(jié)點(diǎn)
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail:");
return 1;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//單鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
//鏈表為空
//鏈表不為空
if (*pphead == NULL)
{
*pphead = newnode;
//不需要讓newnode->next=NULL,在BuySLTNode中我們就已經(jīng)進(jìn)行過(guò)這個(gè)操作了
}
else
{
//先找到鏈表的尾部
SLTNode*tail= *pphead;
while (tail->next!=NULL)
{
tail= tail->next;
}
tail->next =newnode;
}
}
//單鏈表尾刪
void SLTPopBack(SLTNode** pphead)
{
//0.鏈表為空
assert(*pphead);
assert(pphead);
//1.鏈表一個(gè)結(jié)點(diǎn)
if ((*pphead)->next== NULL)
{
free(*pphead);
*pphead = NULL;
}
//2.多個(gè)結(jié)點(diǎn)
else
{
SLTNode* tail = *pphead;
while (tail->next->next!= NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next= NULL;
}
}
//單鏈表頭刪
void SLTPopFront(SLTNode** pphead)
{
assert(*pphead);
assert(pphead);
SLTNode* cur = *pphead;
*pphead = (*pphead)->next;
free(cur);
cur = NULL;
}
//單鏈表頭插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//單鏈表結(jié)點(diǎn)查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//單鏈表結(jié)點(diǎn)刪除(刪除pos位置的結(jié)點(diǎn))
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead);
assert(pphead);
//頭刪
if (*pphead == pos)
{
SLTPopFront(pphead);
}
//非頭刪
else
{
SLTNode* prev = *pphead;
while (prev->next!= pos)
{
prev = prev->next;
assert(prev->next);
//這里為什么需要斷言
}
prev->next = pos->next;
free(pos);
}
}
// 單鏈表結(jié)點(diǎn)修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x)
{
assert(pos);
SLTNode* cur = phead;
while (cur!=pos)
{
cur = cur->next;
assert(cur);
}
pos->data = x;
}
//單鏈表結(jié)點(diǎn)插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pos);
assert(pphead);
//頭插
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
//找到前面一個(gè)位置
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
// 單鏈表結(jié)點(diǎn)插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pos);
assert(pphead);
SLTNode* newnode = BuyListNode(x);
newnode->next= pos->next;
pos->next = newnode;
}
//單鏈表結(jié)點(diǎn)刪除(刪除pos位置之后的結(jié)點(diǎn))
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
assert(pos);
assert(pos->next);
assert(pphead);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
3.test-SL.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SL.h"
void Test()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPushBack(&plist, 5);
SLTPushBack(&plist, 6);
/*SLTPrint(plist);
SLTDestory(&plist);*/
SLTPushFront(&plist, 40);
SLTPushFront(&plist, 50);
/*SLTPrint(plist);
SLTDestory(&plist);*/
SLTPopBack(&plist);
/*SLTPrint(plist);
SLTDestory(&plist);*/
SLTPopFront(&plist);
/*SLTPrint(plist);
SLTDestory(&plist);*/
SLTNode* pos = SLTNodeFind(plist,5);
//刪除pos
SLTNode* pos = SLTNodeFind(plist, 5);
SLTErase(&plist, pos);
//刪除pos后結(jié)點(diǎn)
SLTNode* pos = SLTNodeFind(plist, 3);
SLTEraseAfter(&plist,pos);
//單鏈表結(jié)點(diǎn)修改
SLTNode* pos = SLTNodeFind(plist, 5);
SLTModify(plist, pos, 30);
//在pos之前插入
SLTNode* pos = SLTNodeFind(plist, 5);
SLTInsert(&plist,pos,30);
//在pos之后插入
SLTNode* pos = SLTNodeFind(plist, 5);
SLTInsertBack(&plist,pos,30);
SLTPrint(plist);
SLTDestory(&plist);
}
int main()
{
Test();
return 0;
}花會(huì)沿途盛開(kāi)，以后也是~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-742190.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之單鏈表非常詳細(xì)介紹(適合小白）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
