導(dǎo)航
1、鏈表的概念和結(jié)構(gòu)
概念： 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素
。因此，為了表示每個(gè)數(shù)據(jù)元素與其直接后繼數(shù)據(jù)元素之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素來(lái)說(shuō)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。這兩部分信息組成數(shù)據(jù)元素的存儲(chǔ)映像，稱為節(jié)點(diǎn)，它包括兩個(gè)域，其中存儲(chǔ)數(shù)據(jù)單元信息的域被稱為數(shù)據(jù)域，存儲(chǔ)直接后繼存儲(chǔ)位置的域被稱為指針域，指針域中的存儲(chǔ)信息乘坐指針或鏈。
結(jié)構(gòu)：
從上圖可以看出，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)；
現(xiàn)實(shí)中的結(jié)點(diǎn)一般都是從堆上申請(qǐng)出來(lái)的；
從堆上申請(qǐng)的空間，是按照一定的策略來(lái)分配的，兩次申請(qǐng)的空間可能連續(xù)，也可能不連續(xù)（一般都不是連續(xù)，這里大家可以用vscode跑一邊看看內(nèi)存監(jiān)視，這里就不演示了）。
2、鏈表的分類
實(shí)際中鏈表的結(jié)構(gòu)非常多樣，主要總結(jié)為以下6種特征組成的8種鏈表結(jié)構(gòu)：
①單向或雙向
②帶頭或不帶頭
③循環(huán)或者非循環(huán)
常用的兩種組合結(jié)構(gòu)：
無(wú)頭單向非循環(huán)鏈表：
結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。
帶頭雙向循環(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)單了。
3、鏈表的實(shí)現(xiàn)
這篇文章先實(shí)現(xiàn)第一種常用的鏈表——無(wú)頭單向非循環(huán)鏈表
因?yàn)閷W(xué)校的教材可能都是帶頭的，那樣更容易理解，但在現(xiàn)實(shí)運(yùn)用中，帶頭的并不常用，沒(méi)有學(xué)過(guò)不帶頭的UU也不用擔(dān)心，其實(shí)實(shí)現(xiàn)起來(lái)是類似的，而且學(xué)會(huì)不帶頭的，再去看帶頭的就簡(jiǎn)單很多了。特點(diǎn)：隨機(jī)存儲(chǔ)，順序存取
3.1 結(jié)構(gòu)體定義
首先我們先看看無(wú)頭單向非循環(huán)鏈表的結(jié)構(gòu)體如何實(shí)現(xiàn)
代碼如下：
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;//存放數(shù)據(jù)
struct SListNode* next;//指向下一結(jié)點(diǎn)的指針
}SLTNode;
3.2 接口函數(shù)定義
代碼如下：
SLTNode* BuyListNode(SLTDateType x);//動(dòng)態(tài)申請(qǐng)結(jié)點(diǎn)
void SListPushBack(SLTNode** pphead, SLTDateType x);//尾插
void SListPushFront(SLTNode** pphead, SLTDateType x);//頭插
void SListPopBack(SLTNode** pphead);//尾刪
void SListPopFront(SLTNode** pphead);//頭刪
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);//插入（之后）
void SListErase(SLTNode** pphead, SLTNode* pos);//刪除（之后）
void SListInsertAfter(SLTNode* pos, SLTDateType x);//插入（之前）
void SListEraseAfter(SLTNode* pos);//刪除（之前）
SLTNode* SListFind(SLTNode* phead, SLTDateType x);//查找
void SListPrint(SLTNode* phead);//打印
void SListDestory(SLTNode** pphead);//銷毀鏈表
3.3 接口函數(shù)的實(shí)現(xiàn)
這里提一句，接口函數(shù)的命名并不是固定的，但是要有由頭，不能瞎取一個(gè)優(yōu)秀程序員要有良好的代碼素養(yǎng)畢竟在公司里，代碼不僅是寫給你自己看的
動(dòng)態(tài)申請(qǐng)結(jié)點(diǎn)函數(shù)（BuyListNode）
你可以理解為新增結(jié)點(diǎn)初始化操作
代碼如下：
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
這里首先使用了一個(gè)malloc函數(shù)實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存分配，令第一個(gè)元素為x，并讓指向下一個(gè)節(jié)點(diǎn)為NULL，這里我們可以看到，和之前的順序表對(duì)比，我們會(huì)發(fā)現(xiàn)，在內(nèi)存分配上，鏈表所分配空間更合理，不會(huì)造成大量浪費(fèi)內(nèi)存的現(xiàn)象，這是鏈表的一個(gè)優(yōu)點(diǎn)。
尾部插入函數(shù)（SListPushBack）
顯而易見(jiàn)，就是在鏈表尾部插入新元素
代碼如下：
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
在上面的代碼中我們可以看到，在鏈表中插入元素，需要申請(qǐng)新的結(jié)點(diǎn)空間，這里我們考慮兩種情況：
一種是鏈表為空的情況，那我們直接進(jìn)行賦值插入即可；
第二種是鏈表中有元素的情況，我們借用另外一段臨時(shí)鏈表空間tail進(jìn)行插入（注意，這里要使用*進(jìn)行賦值，否則形參無(wú)法改變實(shí)參的結(jié)果，不理解的小伙伴可以再去復(fù)習(xí)一下C語(yǔ)言中指針的知識(shí)）
頭部插入函數(shù)（SListPushFront）
代碼如下：
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
頭插的實(shí)現(xiàn)我們只需要借助臨時(shí)鏈表newnode存儲(chǔ)要插入的值x，再將x指向要插入的鏈表pphead，再將臨時(shí)鏈表newnode賦回給pphead，即可完成頭插操作
尾部刪除函數(shù)（SListPopBack）
代碼如下：
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);//斷言鏈表為空
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
在這里，我們要考慮到鏈表是否已經(jīng)為空的情況，所以在這里加上第二句斷言，避免造成越界訪問(wèn)。
然后我們?cè)俜謨煞N情況處理：
第一種是鏈表已經(jīng)沒(méi)元素了，next指向的就是空，那么就直接釋放內(nèi)存，再置空；
第二種是鏈表還有元素的情況，在這里我們復(fù)制原鏈表利用while循環(huán)進(jìn)行遍歷，再釋放掉尾元素空間，令尾元素前一個(gè)元素指向空。
頭部刪除函數(shù)（SListPopBack）
代碼如下：
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);//斷言鏈表為空
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
在這里同樣考慮鏈表為空的情況，加一個(gè)斷言，避免越界訪問(wèn)，頭刪需要先把指針指向第二個(gè)元素再進(jìn)行釋放內(nèi)存，二者順序不可顛倒。
插入函數(shù)——之后（SListInsertAfter）
在單鏈表中，一般的插入都是再某元素之后，這里涉及到單鏈表的一個(gè)缺點(diǎn)，他不能像順序表一樣通過(guò)下標(biāo)直接訪問(wèn)某個(gè)元素，單鏈表查找元素都是通過(guò)遍歷查找的，因?yàn)樵趦?nèi)存中可能是不連續(xù)的，單鏈表僅僅是通過(guò)指針來(lái)訪問(wèn)下一個(gè)結(jié)點(diǎn)，而無(wú)法訪問(wèn)上一個(gè)結(jié)點(diǎn)，所以這里正常的插入是在某元素之后，在某個(gè)元素之前插入也可以實(shí)現(xiàn)，不過(guò)更復(fù)雜，對(duì)于初學(xué)者來(lái)說(shuō)，這個(gè)更簡(jiǎn)單也更適合。
代碼如下：
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
這里的第二個(gè)斷言是防止找不到上一個(gè)元素pos，導(dǎo)致無(wú)法插入，這個(gè)在pos元素后插入是先把要插入元素x封裝成一個(gè)節(jié)點(diǎn)指向pos的初始下一元素，再將pos指向要插入的元素結(jié)點(diǎn)，完成插入操作。要注意的是，順序不可以顛倒哦，如果先將pos指向x，那么x將無(wú)法找到下一個(gè)元素結(jié)點(diǎn)
刪除函數(shù)——之后1（SListErase）
在這里刪除函數(shù)不管是某函數(shù)之前還是之后相對(duì)都沒(méi)那么復(fù)雜了，我們先看刪除某個(gè)元素之后的寫法。
代碼如下：
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
這種寫法首先我們分兩種情況：
第一種是只剩一個(gè)元素結(jié)點(diǎn)，這個(gè)我們直接調(diào)用頭刪就可以了；
第二種是還有多個(gè)元素結(jié)點(diǎn)，使用while循環(huán)遍歷鏈表找到pos元素，將pos上一個(gè)元素結(jié)點(diǎn)指向pos元素的下一個(gè)元素結(jié)點(diǎn)，再將pos的內(nèi)存釋放。
插入函數(shù)——之前（SListInsertBefore）
代碼如下：
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead);
assert(pos);
SLTNode* newnode = BuyListNode(x);
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = newnode;
newnode->next = pos;
}
}
和前面一樣分兩種情況討論：
第一種情況是只有一個(gè)元素，那么我們就直接將x元素結(jié)點(diǎn)指向原鏈表pphead，再重新賦值即可；
第二種是鏈表中有多個(gè)元素，使用while循環(huán)遍歷鏈表找到pos上一元素結(jié)點(diǎn)，使其指向要插入的元素結(jié)點(diǎn)x，再將x指向pos元素結(jié)點(diǎn)，完成插入操作。
刪除函數(shù)——之后2（SListEraseAfter）
代碼如下：
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
這個(gè)寫法看起來(lái)比前面的刪除更為簡(jiǎn)潔，你覺(jué)得哪個(gè)更好，更符合實(shí)際應(yīng)用，就用哪個(gè)；
查找函數(shù)（SListFind）
代碼如下：
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
簡(jiǎn)單來(lái)說(shuō)就是利用循環(huán)來(lái)進(jìn)行遍歷查找，沒(méi)啥好講的。
打印函數(shù)（SListPrint）
代碼如下：
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
同樣的通過(guò)遍歷鏈表來(lái)進(jìn)行逐個(gè)打印元素，用->連接更為直觀。
銷毀鏈表函數(shù)（SListDestory）
代碼如下：
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
這里也是通過(guò)遍歷鏈表逐個(gè)元素節(jié)點(diǎn)釋放內(nèi)存空間。
4、結(jié)語(yǔ)
這就是無(wú)頭單向非循環(huán)鏈表的接口函數(shù)實(shí)現(xiàn)，對(duì)比一下我們會(huì)發(fā)現(xiàn)單鏈表和順序表各自的優(yōu)缺點(diǎn)，他們兩個(gè)都不完美，因此在實(shí)際應(yīng)用中，這兩種線性表都是有需求的，我們都需要掌握好，才能打好基礎(chǔ)，下一章節(jié)我們來(lái)講講帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-408411.html
制作不易，如有不正之處敬請(qǐng)指出，感謝大家的來(lái)訪，UU們的觀看是我堅(jiān)持下去的動(dòng)力，在時(shí)間的催化劑下，讓我們彼此都成為更優(yōu)秀的人吧?。?！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-408411.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門（C語(yǔ)言版）線性表中鏈表介紹及無(wú)頭單向非循環(huán)鏈表接口實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
