C語言數(shù)據結構單鏈表接口函數(shù)全面講解教程
前言
上一期數(shù)據結構專欄我們學習了順序表后：C語言數(shù)據結構順序表
在運用時，細心的同學可能會發(fā)現(xiàn)，如果要頭插、尾插或者任意位置。如果原先的空間已經被占滿了，你是需要擴容的，動態(tài)鏈表擴容往往是2倍，但是擴容后，如果后面沒有使用完全擴容后空間就會造成空間浪費，為了解決這個問題，我們今天將學習鏈表。
提示：以下是本篇文章正文內容，下面案例可供參考
一、鏈表的概念及結構
1.概念
鏈表是一種物理存儲結構上的非連續(xù)。非順序的存儲結構，數(shù)據元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的。
（圖片來自比特就業(yè)課）
上圖是一個普通鏈表，它物理上是不連續(xù)的，那怎么讓這些數(shù)據建立聯(lián)系呢？鏈表每個位置會存放兩個數(shù)據——1個是數(shù)據，另1個是指針
typedef int SLTDataType;//這里是方便將來改數(shù)據類型，在這里把int修改一下即可
typedef struct SlistNode//一個位置放多個數(shù)據用結構體
{
int data;
struct SlistNode*next;//指針是指向下一個節(jié)點，下一個節(jié)點也是結構體，所以這里是結構體指針
}SLTNode;//將結構體類型名用SLTNode重命名
我們用一張圖來深入了解一下它的邏輯結構：
圖示是鏈表的三個相連元素，第一個元素存放數(shù)據1和第二個元素的地址，然后以此類推。那到這里可能有同學會問：“那每個都是有存放下一個地址，最后一個節(jié)點存放誰的地址？”是這樣的，最后一個節(jié)點存放的是NULL空指針，空指針也是作為鏈表結尾的標記
到這里，我們知道，鏈表的每個節(jié)點放的是當前節(jié)點內容和下一個節(jié)點的指針，那我們怎么找到這條鏈表呢？畢竟你第一個節(jié)點放的是第二個節(jié)點的指針，事實上，我們會定義一個指針指向第一個節(jié)點，以此來確定該鏈表
二、鏈表的使用
1.遍歷整個鏈表
代碼如下（示例）：
void SListPrint(SLTNode*phead)
{
SLTNode*cur = phead;
while (cur != NULL)
{
printf("%d", cur->data);
cur = cur->next;
}
}
我們以這張圖來理解一下這段代碼，我們創(chuàng)建一個結構體指針cur，并把鏈表首元素地址賦給cur，也就是說，cur指向了鏈表的首節(jié)點，我們知道首節(jié)點里是有第二個節(jié)點的地址的，我們通過cur = cur->next;可以找到第二段節(jié)點，以此類推。
2.尾插
（圖片來自比特就業(yè)課）
想要尾插一個節(jié)點，我們首先要malloc（擴容函數(shù)）一塊空間出來，開辟出那塊空間之后，要把新節(jié)點與鏈表連接起來，就需要鏈表尾部節(jié)點的地址，我們用循環(huán)遍歷得到，然后把新節(jié)點地址賦給之前鏈表的尾部節(jié)點即可
代碼如下（示例）：
void SListPushBack(SLTNode**pphead, SLTDataType x)
{
SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
//開辟一塊大小為一個SLTNode類型的空間出來，并強制轉換成結構體指針賦給newnode
newnode->data = x;
newnode->next = NULL;
if (*pphead == NULL)//防止一開始鏈表里面什么也沒有，
{//由于pphead是頭節(jié)點的地址的地址，*解引用一下得到頭結點的地址
*pphead = newnode;
}
else
{
SLTNode*tail = *pphead;
while (tail->next != NULL)//尋找尾節(jié)點的指針
{
tail = tail->next;
}
tail->next = newnode;//新增的節(jié)點地址賦給尾結點存儲
}
}
這里為什么用二級指針傳參？解釋如下：
我們進行尾插時，要先找到鏈表所在嘛，然后這個是靠鏈表頭節(jié)點地址確定的，你傳了一個地址過去，注意這個地址是實參，你實參過去函數(shù)里會再創(chuàng)建一個形參也是這個地址，然后進行操作，改變的是形參里的東西，實參不會受影響。這里也就是傳值調用和傳址調用的區(qū)別，為了形參可以影響到實參，我們用傳址調用，也就是傳地址的地址
3.頭插
（圖片來自比特就業(yè)課）
我們假設現(xiàn)在要在一個鏈表前面插入0這個數(shù)據（如上圖所示），0所在地址為0x0006708，那是不是要把原鏈表首節(jié)點地址放到0這個節(jié)點里面，然后頭節(jié)點地址更新為0這個新節(jié)點的地址。如下圖：
ps:plist/phead表示鏈表首節(jié)點地址
代碼如下（示例）：
void SListPushFront(SLTNode**pphead, SLTDataType x)
{
SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
//開辟一塊大小為一個SLTNode類型的空間出來，并強制轉換成結構體指針賦給newnode
newnode->data = x;//插入節(jié)點的數(shù)據
newnode->next = *pphead;//把原先節(jié)點首元素地址賦給新節(jié)點
*pphead = newnode;//新節(jié)點首元素地址用新插入的節(jié)點地址賦值
}
4.頭刪
關于頭刪，很多同學可能有一種想法，就是直接把頭結點free（對動態(tài)分配的內存進行釋放）掉，剩下的就是我們需要的鏈表。但這里會有一個問題，就是你把頭節(jié)點去了，因為鏈表是用地址連接的，我們原本是用頭節(jié)點地址找到該鏈表，現(xiàn)在頭節(jié)點去掉了，我們怎么知道剩下的鏈表在哪里。所以這里的解決方案是，先把第二個節(jié)點地址保存起來然后再釋放掉頭節(jié)點
代碼如下（示例）：
void SListPopFront(SLTNode**pphead)
{
SLTNode*next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
5.尾刪
尾刪和頭刪有同樣的問題，我們能不能直接把尾部節(jié)點給free掉？答案也是不可以的，同學你細想一下，尾部節(jié)點是不是連接著倒數(shù)第二個節(jié)點，而倒數(shù)第二個節(jié)點保存著尾結點地址，你把尾結點free掉了，那倒數(shù)第二個節(jié)點保存的就是野指針了，這顯然是不行的，所以我們需要把倒數(shù)第二個節(jié)點存儲的指針變成空指針，然后free掉尾結點
void SListPopBack(SLTNode**pphead)
{
if (*pphead == NULL)//如果節(jié)點本來就沒有，那就沒有刪除的說法了
{
return;
}
else if ((*pphead)->next == NULL)//如果本來鏈表只有一個節(jié)點，你刪除一個，之前會有一個指針指向首節(jié)點來記錄這個鏈表，你現(xiàn)在把唯一的節(jié)點刪除了，那個記錄鏈表的指針就成野指針了
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode*prev = NULL;//prev為tail前個節(jié)點指針
SLTNode*tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
這里還是有注意的點的，比如你要刪除的鏈表本來就是空鏈表，刪除就無從談起了，還有就是原先鏈表只有一個節(jié)點，你刪除一個，之前會有一個指針指向首節(jié)點來記錄這個鏈表，你現(xiàn)在把唯一的節(jié)點刪除了，那個記錄鏈表的指針就成野指針了
6.任意位置插入數(shù)據
上圖紅色是原有鏈表，我們要在2和3直接插入一個30怎么做？首先我們要把2、30、3這3個節(jié)點連接起來，也就是說，2節(jié)點要指向30這個節(jié)點，30這個節(jié)點要指向3這個節(jié)點。這里如何操作呢？我們需要設計一個函數(shù)先找到2節(jié)點和3節(jié)點的地址，然后進行插入操作
查找函數(shù)和插入函數(shù)如下
SLTNode* SListFind(SLTNode*phead, SLTDataType x)//查找鏈表
{
SLTNode*cur = phead;
while (cur)//非空指針則進行循環(huán)
{
if (cur->data == x)//給定鏈表中一個數(shù)據進行查找
{
return cur;//返回所查找位置指針
}
cur = cur->next;
}
return NULL;
}
void SListInsert(SLTNode**pphead,SLTNode*pos, SLTDataType x)//在pos前插入x，x是要插入的數(shù)
{
if (pos == *pphead)//原鏈表只有1個節(jié)點
{
SListPushFront(pphead, x);
}
else
{
SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
//開辟一塊大小為一個SLTNode類型的空間出來，并強制轉換成結構體指針賦給newnode
newnode->data = x;
newnode->next = NULL;//開辟1個新節(jié)點
SLTNode*prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;//把新節(jié)點連接上去
}
}
兩個函數(shù)一起調用是這樣的
if (pos)//防止該位置是空指針
{
SlistInsert(&plist, pos, 30);
}
SListPrint(&plist);
}
7.任意位置刪除數(shù)據
比如說我們現(xiàn)在要把3刪除，那這里就會出現(xiàn)一個需要：3刪除了，要把2和4連接起來，然后把3節(jié)點釋放掉
void SListErase(SLTNode**pphead, SLTNode*pos)//刪除pos位置的值
{
SLTNode*prev = *pphead;
while (prev->next != pos)//找到3節(jié)點的位置
{
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這種是方便同學你理解，并不特指它真的是2和3
然后這里進行函數(shù)調用的時候，依然需要進行find定位一下需要刪除位置地址
SLTNode*pos = SListFind(plist, 3);
if (pos)//防止該位置是空指針
{
SListErase(&plist, pos);
}
后記
鏈表是數(shù)據結構非常重要的一塊知識，本文著重介紹了鏈表的接口函數(shù)，下一期筆者會更新特殊鏈表的使用，點贊三連可以加快更新速度哦~更多關于C語言數(shù)據結構單鏈表接口函數(shù)的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了VS2019配置BOOST的方法(v1.70.0庫)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-08-08
鏈棧是棧的鏈式存儲結構，鏈?？梢杂脝捂湵淼念^插法實現(xiàn)，本文主要講述了如何用c語言去實現(xiàn)鏈棧，感興趣的朋友可以了解下2021-05-05
三子棋是一種民間傳統(tǒng)游戲，又叫九宮棋、圈圈叉叉、一條龍、井字棋等。將正方形對角線連起來，相對兩邊依次擺上三個雙方棋子，只要將自己的三個棋子走成一條線，對方就算輸了2021-10-10
c++動態(tài)內存空間示例(自定義空間類型大小和空間長度)
這篇文章主要介紹了c++動態(tài)內存空間示例,自定義空間類型大小和空間長度,需要的朋友可以參考下2014-04-04
JSON是一種對源自Javascript的對象數(shù)據進行編碼的格式,但現(xiàn)在被廣泛用作互聯(lián)網上的數(shù)據交換格式,本文主要介紹了Qt使用Json的項目實踐,詳細的介紹了主要使用的類以及Json實戰(zhàn),感興趣的可以了解一下2023-09-09
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易版掃雷游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
掃雷是電腦上很經典很經典的傳統(tǒng)老游戲，從小編第一次摸到計算機開始就玩過掃雷，雖然當時并不理解玩法原理，但終是第一次玩電腦游戲，下面來從掃雷的前世今生講起2021-11-11
項目中用到了監(jiān)測某磁盤（如：C盤、D盤等）的總容量和可用容量，查了一下，發(fā)現(xiàn)其實挺簡單，本文就來用QT實現(xiàn)這一功能吧，希望對大家有所幫助2023-04-04
error LNK2019: 無法解析的外部符號 問題的解決辦法
error LNK2019: 無法解析的外部符號 問題的解決辦法，需要的朋友可以參考一下2013-05-05
這篇文章主要介紹了C 語言結構體的使用,文章介紹了結構體定義的多種類型,想具體了解的朋友請看下面文章的內容2021-09-09