C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)單鏈表接口函數(shù)全面講解教程
前言
上一期數(shù)據(jù)結(jié)構(gòu)專欄我們學(xué)習(xí)了順序表后:C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表
在運(yùn)用時(shí),細(xì)心的同學(xué)可能會(huì)發(fā)現(xiàn),如果要頭插、尾插或者任意位置。如果原先的空間已經(jīng)被占滿了,你是需要擴(kuò)容的,動(dòng)態(tài)鏈表擴(kuò)容往往是2倍,但是擴(kuò)容后,如果后面沒(méi)有使用完全擴(kuò)容后空間就會(huì)造成空間浪費(fèi),為了解決這個(gè)問(wèn)題,我們今天將學(xué)習(xí)鏈表。
提示:以下是本篇文章正文內(nèi)容,下面案例可供參考
一、鏈表的概念及結(jié)構(gòu)
1.概念
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上的非連續(xù)。非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。
(圖片來(lái)自比特就業(yè)課)
上圖是一個(gè)普通鏈表,它物理上是不連續(xù)的,那怎么讓這些數(shù)據(jù)建立聯(lián)系呢?鏈表每個(gè)位置會(huì)存放兩個(gè)數(shù)據(jù)——1個(gè)是數(shù)據(jù),另1個(gè)是指針
typedef int SLTDataType;//這里是方便將來(lái)改數(shù)據(jù)類型,在這里把int修改一下即可 typedef struct SlistNode//一個(gè)位置放多個(gè)數(shù)據(jù)用結(jié)構(gòu)體 { int data; struct SlistNode*next;//指針是指向下一個(gè)節(jié)點(diǎn),下一個(gè)節(jié)點(diǎn)也是結(jié)構(gòu)體,所以這里是結(jié)構(gòu)體指針 }SLTNode;//將結(jié)構(gòu)體類型名用SLTNode重命名
我們用一張圖來(lái)深入了解一下它的邏輯結(jié)構(gòu):
圖示是鏈表的三個(gè)相連元素,第一個(gè)元素存放數(shù)據(jù)1和第二個(gè)元素的地址,然后以此類推。那到這里可能有同學(xué)會(huì)問(wèn):“那每個(gè)都是有存放下一個(gè)地址,最后一個(gè)節(jié)點(diǎn)存放誰(shuí)的地址?”是這樣的,最后一個(gè)節(jié)點(diǎn)存放的是NULL空指針,空指針也是作為鏈表結(jié)尾的標(biāo)記
到這里,我們知道,鏈表的每個(gè)節(jié)點(diǎn)放的是當(dāng)前節(jié)點(diǎn)內(nèi)容和下一個(gè)節(jié)點(diǎn)的指針,那我們?cè)趺凑业竭@條鏈表呢?畢竟你第一個(gè)節(jié)點(diǎn)放的是第二個(gè)節(jié)點(diǎn)的指針,事實(shí)上,我們會(huì)定義一個(gè)指針指向第一個(gè)節(jié)點(diǎn),以此來(lái)確定該鏈表
二、鏈表的使用
1.遍歷整個(gè)鏈表
代碼如下(示例):
void SListPrint(SLTNode*phead) { SLTNode*cur = phead; while (cur != NULL) { printf("%d", cur->data); cur = cur->next; } }
我們以這張圖來(lái)理解一下這段代碼,我們創(chuàng)建一個(gè)結(jié)構(gòu)體指針cur,并把鏈表首元素地址賦給cur,也就是說(shuō),cur指向了鏈表的首節(jié)點(diǎn),我們知道首節(jié)點(diǎn)里是有第二個(gè)節(jié)點(diǎn)的地址的,我們通過(guò)cur = cur->next;可以找到第二段節(jié)點(diǎn),以此類推。
2.尾插
(圖片來(lái)自比特就業(yè)課)
想要尾插一個(gè)節(jié)點(diǎn),我們首先要malloc(擴(kuò)容函數(shù))一塊空間出來(lái),開(kāi)辟出那塊空間之后,要把新節(jié)點(diǎn)與鏈表連接起來(lái),就需要鏈表尾部節(jié)點(diǎn)的地址,我們用循環(huán)遍歷得到,然后把新節(jié)點(diǎn)地址賦給之前鏈表的尾部節(jié)點(diǎn)即可
代碼如下(示例):
void SListPushBack(SLTNode**pphead, SLTDataType x) { SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode)); //開(kāi)辟一塊大小為一個(gè)SLTNode類型的空間出來(lái),并強(qiáng)制轉(zhuǎn)換成結(jié)構(gòu)體指針賦給newnode newnode->data = x; newnode->next = NULL; if (*pphead == NULL)//防止一開(kāi)始鏈表里面什么也沒(méi)有, {//由于pphead是頭節(jié)點(diǎn)的地址的地址,*解引用一下得到頭結(jié)點(diǎn)的地址 *pphead = newnode; } else { SLTNode*tail = *pphead; while (tail->next != NULL)//尋找尾節(jié)點(diǎn)的指針 { tail = tail->next; } tail->next = newnode;//新增的節(jié)點(diǎn)地址賦給尾結(jié)點(diǎn)存儲(chǔ) } }
這里為什么用二級(jí)指針傳參?解釋如下:
我們進(jìn)行尾插時(shí),要先找到鏈表所在嘛,然后這個(gè)是靠鏈表頭節(jié)點(diǎn)地址確定的,你傳了一個(gè)地址過(guò)去,注意這個(gè)地址是實(shí)參,你實(shí)參過(guò)去函數(shù)里會(huì)再創(chuàng)建一個(gè)形參也是這個(gè)地址,然后進(jìn)行操作,改變的是形參里的東西,實(shí)參不會(huì)受影響。這里也就是傳值調(diào)用和傳址調(diào)用的區(qū)別,為了形參可以影響到實(shí)參,我們用傳址調(diào)用,也就是傳地址的地址
3.頭插
(圖片來(lái)自比特就業(yè)課)
我們假設(shè)現(xiàn)在要在一個(gè)鏈表前面插入0這個(gè)數(shù)據(jù)(如上圖所示),0所在地址為0x0006708,那是不是要把原鏈表首節(jié)點(diǎn)地址放到0這個(gè)節(jié)點(diǎn)里面,然后頭節(jié)點(diǎn)地址更新為0這個(gè)新節(jié)點(diǎn)的地址。如下圖:
ps:plist/phead表示鏈表首節(jié)點(diǎn)地址
代碼如下(示例):
void SListPushFront(SLTNode**pphead, SLTDataType x) { SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode)); //開(kāi)辟一塊大小為一個(gè)SLTNode類型的空間出來(lái),并強(qiáng)制轉(zhuǎn)換成結(jié)構(gòu)體指針賦給newnode newnode->data = x;//插入節(jié)點(diǎn)的數(shù)據(jù) newnode->next = *pphead;//把原先節(jié)點(diǎn)首元素地址賦給新節(jié)點(diǎn) *pphead = newnode;//新節(jié)點(diǎn)首元素地址用新插入的節(jié)點(diǎn)地址賦值 }
4.頭刪
關(guān)于頭刪,很多同學(xué)可能有一種想法,就是直接把頭結(jié)點(diǎn)free(對(duì)動(dòng)態(tài)分配的內(nèi)存進(jìn)行釋放)掉,剩下的就是我們需要的鏈表。但這里會(huì)有一個(gè)問(wèn)題,就是你把頭節(jié)點(diǎn)去了,因?yàn)殒湵硎怯玫刂愤B接的,我們?cè)臼怯妙^節(jié)點(diǎn)地址找到該鏈表,現(xiàn)在頭節(jié)點(diǎn)去掉了,我們?cè)趺粗朗O碌逆湵碓谀睦?。所以這里的解決方案是,先把第二個(gè)節(jié)點(diǎn)地址保存起來(lái)然后再釋放掉頭節(jié)點(diǎn)
代碼如下(示例):
void SListPopFront(SLTNode**pphead) { SLTNode*next = (*pphead)->next; free(*pphead); *pphead = next; }
5.尾刪
尾刪和頭刪有同樣的問(wèn)題,我們能不能直接把尾部節(jié)點(diǎn)給free掉?答案也是不可以的,同學(xué)你細(xì)想一下,尾部節(jié)點(diǎn)是不是連接著倒數(shù)第二個(gè)節(jié)點(diǎn),而倒數(shù)第二個(gè)節(jié)點(diǎn)保存著尾結(jié)點(diǎn)地址,你把尾結(jié)點(diǎn)free掉了,那倒數(shù)第二個(gè)節(jié)點(diǎn)保存的就是野指針了,這顯然是不行的,所以我們需要把倒數(shù)第二個(gè)節(jié)點(diǎn)存儲(chǔ)的指針變成空指針,然后free掉尾結(jié)點(diǎn)
void SListPopBack(SLTNode**pphead) { if (*pphead == NULL)//如果節(jié)點(diǎn)本來(lái)就沒(méi)有,那就沒(méi)有刪除的說(shuō)法了 { return; } else if ((*pphead)->next == NULL)//如果本來(lái)鏈表只有一個(gè)節(jié)點(diǎn),你刪除一個(gè),之前會(huì)有一個(gè)指針指向首節(jié)點(diǎn)來(lái)記錄這個(gè)鏈表,你現(xiàn)在把唯一的節(jié)點(diǎn)刪除了,那個(gè)記錄鏈表的指針就成野指針了 { free(*pphead); *pphead = NULL; } else { SLTNode*prev = NULL;//prev為tail前個(gè)節(jié)點(diǎn)指針 SLTNode*tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); prev->next = NULL; } }
這里還是有注意的點(diǎn)的,比如你要?jiǎng)h除的鏈表本來(lái)就是空鏈表,刪除就無(wú)從談起了,還有就是原先鏈表只有一個(gè)節(jié)點(diǎn),你刪除一個(gè),之前會(huì)有一個(gè)指針指向首節(jié)點(diǎn)來(lái)記錄這個(gè)鏈表,你現(xiàn)在把唯一的節(jié)點(diǎn)刪除了,那個(gè)記錄鏈表的指針就成野指針了
6.任意位置插入數(shù)據(jù)
上圖紅色是原有鏈表,我們要在2和3直接插入一個(gè)30怎么做?首先我們要把2、30、3這3個(gè)節(jié)點(diǎn)連接起來(lái),也就是說(shuō),2節(jié)點(diǎn)要指向30這個(gè)節(jié)點(diǎn),30這個(gè)節(jié)點(diǎn)要指向3這個(gè)節(jié)點(diǎn)。這里如何操作呢?我們需要設(shè)計(jì)一個(gè)函數(shù)先找到2節(jié)點(diǎn)和3節(jié)點(diǎn)的地址,然后進(jìn)行插入操作
查找函數(shù)和插入函數(shù)如下
SLTNode* SListFind(SLTNode*phead, SLTDataType x)//查找鏈表 { SLTNode*cur = phead; while (cur)//非空指針則進(jìn)行循環(huán) { if (cur->data == x)//給定鏈表中一個(gè)數(shù)據(jù)進(jìn)行查找 { return cur;//返回所查找位置指針 } cur = cur->next; } return NULL; } void SListInsert(SLTNode**pphead,SLTNode*pos, SLTDataType x)//在pos前插入x,x是要插入的數(shù) { if (pos == *pphead)//原鏈表只有1個(gè)節(jié)點(diǎn) { SListPushFront(pphead, x); } else { SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode)); //開(kāi)辟一塊大小為一個(gè)SLTNode類型的空間出來(lái),并強(qiáng)制轉(zhuǎn)換成結(jié)構(gòu)體指針賦給newnode newnode->data = x; newnode->next = NULL;//開(kāi)辟1個(gè)新節(jié)點(diǎn) SLTNode*prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos;//把新節(jié)點(diǎn)連接上去 } }
兩個(gè)函數(shù)一起調(diào)用是這樣的
if (pos)//防止該位置是空指針 { SlistInsert(&plist, pos, 30); } SListPrint(&plist); }
7.任意位置刪除數(shù)據(jù)
比如說(shuō)我們現(xiàn)在要把3刪除,那這里就會(huì)出現(xiàn)一個(gè)需要:3刪除了,要把2和4連接起來(lái),然后把3節(jié)點(diǎn)釋放掉
void SListErase(SLTNode**pphead, SLTNode*pos)//刪除pos位置的值 { SLTNode*prev = *pphead; while (prev->next != pos)//找到3節(jié)點(diǎn)的位置 { prev = prev->next; } prev->next = pos->next;//prev是2,pos是3,pos->next是4,要把4接上2 free(pos);//2和4接上之后就可以free掉3了 }
ps:上述prev是2,pos是3這種是方便同學(xué)你理解,并不特指它真的是2和3
然后這里進(jìn)行函數(shù)調(diào)用的時(shí)候,依然需要進(jìn)行find定位一下需要?jiǎng)h除位置地址
SLTNode*pos = SListFind(plist, 3); if (pos)//防止該位置是空指針 { SListErase(&plist, pos); }
后記
鏈表是數(shù)據(jù)結(jié)構(gòu)非常重要的一塊知識(shí),本文著重介紹了鏈表的接口函數(shù),下一期筆者會(huì)更新特殊鏈表的使用,點(diǎn)贊三連可以加快更新速度哦~更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)單鏈表接口函數(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C語(yǔ)言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實(shí)現(xiàn)
這篇文章主要介紹了C語(yǔ)言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實(shí)現(xiàn),,文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的朋友可以參考一下2022-09-09OpenCV實(shí)現(xiàn)低對(duì)比度圖像臟污區(qū)域檢測(cè)
本文主要介紹了OpenCV實(shí)現(xiàn)低對(duì)比度圖像臟污區(qū)域檢測(cè),文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-09-09C++20 新特性 協(xié)程 Coroutines(2)
上篇文章簡(jiǎn)單給大介紹了 C++20 特性 協(xié)程 Coroutines co_yield 和 co_return 那么這篇文章繼續(xù)給大家介紹C++20 的新特性協(xié)程 Coroutines co_await,需要的朋友可以參考一下2021-10-10詳解C語(yǔ)言處理算經(jīng)中著名問(wèn)題百錢(qián)百雞
古代的很多數(shù)學(xué)問(wèn)題都可以用現(xiàn)代的編程語(yǔ)言去嘗試解決,就如本篇,將會(huì)帶你通過(guò)C語(yǔ)言來(lái)解決算經(jīng)中百錢(qián)百雞問(wèn)題,感興趣的朋友來(lái)看看吧2022-02-02最新VScode C/C++ 環(huán)境配置的詳細(xì)教程
這篇文章主要介紹了最新VScode C/C++ 環(huán)境配置的詳細(xì)教程,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-11-11C語(yǔ)言實(shí)現(xiàn)頁(yè)面置換算法(FIFO、LRU)
這篇文章主要介紹了通過(guò)C語(yǔ)言實(shí)現(xiàn)的兩種頁(yè)面置換算法:先進(jìn)先出(FIFO)頁(yè)面置換算法和最近最久未使用(LRU)頁(yè)面置換算法。文中的代碼具有一定的學(xué)習(xí)或工作價(jià)值,快來(lái)跟隨小編學(xué)習(xí)一下吧2021-12-12