C語言?超詳細(xì)模擬實(shí)現(xiàn)單鏈表的基本操作建議收藏
1 鏈表的概念及結(jié)構(gòu)
概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈 接次序?qū)崿F(xiàn)的 。
注意：
1. 從上圖可以看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定是連續(xù)
2. 現(xiàn)實(shí)中的節(jié)點(diǎn)一般是從堆上申請(qǐng)出來的
3. 從對(duì)上申請(qǐng)的空間，是按照一定的策略來分配的，兩次申請(qǐng)的空間可能連續(xù)，也可能不連續(xù)
2 鏈表的分類
實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：
1、單向或者雙向鏈表
2、帶頭或者不帶頭鏈表
3、循環(huán)或非循環(huán)鏈表
最常用的有兩種：無頭單向非循環(huán)鏈表、帶頭雙向循環(huán)鏈表
- 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié) 構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
- 帶頭雙向循環(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ì)帶來很多優(yōu)勢，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。
3 鏈表的實(shí)現(xiàn)無頭+單向+非循環(huán)鏈表增刪查改實(shí)現(xiàn)
3.1 鏈表的定義
typedef int SLTDataType;//
typedef struct SListNode
{
int data;//val，存儲(chǔ)的數(shù)據(jù)，此處假設(shè)存儲(chǔ)的數(shù)據(jù)為int型
struct SListNode* next;//存儲(chǔ)下一個(gè)節(jié)點(diǎn)的位置
}SListNode,SLN;3.2 鏈表數(shù)據(jù)的打印
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}3.3 鏈表的尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}在找尾的過程中，務(wù)必不能寫成下面的代碼：
while(tail!=NULL)
{
tail = tail->next;
}
tail->next = newnode;
當(dāng)然，上面的介紹的是尾刪的情況。
尾插其實(shí)也是類似的，尾插的話像上面的代碼中，當(dāng)tail!=NULL不成立之后，tail等于空，然后執(zhí)行賦值操作，tail->next = newnode這行代碼相當(dāng)于下面的代碼：
(*tail).next，此處相當(dāng)于是對(duì)空指針進(jìn)行解引用，其實(shí)就是非法訪問了，并還試圖非法修改未授權(quán)內(nèi)存中的數(shù)據(jù)，這將必然會(huì)引發(fā)程序的崩潰。而且也并沒有將新節(jié)點(diǎn)的地址存儲(chǔ)到之前為節(jié)點(diǎn)的next中。
這個(gè)地方需要弄明白鏈表進(jìn)行遍歷的根本原理：
鏈表是一個(gè)相對(duì)靜態(tài)的存儲(chǔ)在堆區(qū)中的數(shù)據(jù)空間，我們通過改變棧區(qū)中的局部變量tail中的數(shù)據(jù)（即每一個(gè)鏈表節(jié)點(diǎn)的地址）來進(jìn)行遍歷，之所以能夠通過tail變量能夠進(jìn)行訪問并且修改節(jié)點(diǎn)數(shù)據(jù)的原因就是因?yàn)閠ail的數(shù)據(jù)類型是SListNode*，即指向節(jié)點(diǎn)的指針，指針的類型決定了對(duì)指針解引用能夠訪問的數(shù)據(jù)類型，所以*tail能夠訪問堆區(qū)中的節(jié)點(diǎn)的數(shù)據(jù)并且能夠進(jìn)行修改。
3.4 鏈表空間的動(dòng)態(tài)申請(qǐng)
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
return newnode;
}3.5 鏈表的頭插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}3.6 鏈表的尾刪
需要考慮三種情況：
- 空
- 一個(gè)節(jié)點(diǎn)
- 多個(gè)節(jié)點(diǎn)
兩種寫法：
第一種：
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//空鏈表
{
return;
}
else if ((*pphead)->next == NULL)//一個(gè)節(jié)點(diǎn)
{
free(*pphead);//*pphead就是plist的值
*pphead = NULL;
}
else//多個(gè)節(jié)點(diǎn)
{
SListNode* tail = *pphead;
SListNode* prev = NULL;//為什么要置為空呢？因?yàn)檫@個(gè)地方相當(dāng)于是指向第一個(gè)節(jié)點(diǎn)之前的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)并不存在，設(shè)為空
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
這種方式在面對(duì)只有一個(gè)節(jié)點(diǎn)時(shí)也不會(huì)出現(xiàn)問題。
第二種：
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//空鏈表
{
return;
}
else if ((*pphead)->next == NULL)//一個(gè)節(jié)點(diǎn)
{
free(*pphead);//*pphead就是plist的值
*pphead = NULL;
}
else//多個(gè)節(jié)點(diǎn)
{
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);//釋放尾節(jié)點(diǎn)
tail->next = NULL;//將新尾節(jié)點(diǎn)的next置為NULL
}
}
3.7 鏈表的頭刪
void SListPopFront(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//空鏈表
{
return;
}
else//非空鏈表
{
SListNode* next = (*pphead)->next;//next作為臨時(shí)變量存放的是被刪除的節(jié)點(diǎn)中next存儲(chǔ)的第二個(gè)節(jié)點(diǎn)的地址
free(*pphead);
*pphead = next;
}
}
3.8 鏈表任意位置的前插入
void SListInsertBefore(SListNode** pphead, SListNode* pos,SLTDataType x)
{
assert(pphead);
if (*pphead == pos)//pos是第一個(gè)節(jié)點(diǎn)，相當(dāng)于頭插
{
SListPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
3.9 鏈表任意位置的后插入
兩種實(shí)現(xiàn)方式：
方式一：
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
//這兩行代碼順序是固定的，只能這個(gè)順序，無法進(jìn)行改變
}圖示：
方式二：
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* next = pos->next;
SListNode* newnode = BuySListNode(x);
newnode->next = next;
pos->next = newnode;
//這兩行代碼可以任意改變順序，誰先誰后都不影響最后的結(jié)果
}圖示：
3.10 鏈表的任意位置的刪除
void SListErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)//當(dāng)pos為頭節(jié)點(diǎn)的時(shí)候
{
SListPopFront(pphead);
}
else//當(dāng)pos為非頭節(jié)點(diǎn)的時(shí)候
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}圖示：
3.11 鏈表的任意位置的前刪除
void SListEraseBefore(SListNode** pphead, SListNode* pos)//pos即為任意位置
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
return;
}
else if(pos==(*pphead)->next)
{
SListPopFront(pphead);
}
else
{
SListNode* prev = *pphead;//prev用來存儲(chǔ)pos的前一個(gè)位置的前一個(gè)位置
while (prev->next->next != pos)
{
prev = prev->next;
}
SListNode* next = prev->next;//保存pos前一個(gè)節(jié)點(diǎn)的地址
prev->next = prev->next->next;//將prev和pos的兩個(gè)節(jié)點(diǎn)進(jìn)行連接
free(next);//刪除pos的前一個(gè)節(jié)點(diǎn)
}
}
3.12 鏈表的任意位置的后刪除
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* next = pos->next;
if (next == NULL)//當(dāng)pos是最后一個(gè)節(jié)點(diǎn)的時(shí)候
{
return;
}
else
{
pos->next = next->next;
free(next);
next = NULL;
}
}圖示：
3.13 鏈表的銷毀
void SListDestory(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
SListNode* next = *pphead;//是為了存儲(chǔ)cur下一個(gè)節(jié)點(diǎn)的地址，因?yàn)閒ree(cur)之后，cur指針指向的內(nèi)存中的數(shù)據(jù)可能已經(jīng)稱為亂碼了，即不能再正常的使用
while (cur)
{
next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}3.14 鏈表的總結(jié)
總結(jié)：單鏈表結(jié)構(gòu)，適合頭插頭刪。尾部或者中間某個(gè)位置插入刪除都不適合。如果要使用鏈表結(jié)構(gòu)單獨(dú)存儲(chǔ)數(shù)據(jù)，更適合用雙向鏈表。
單鏈表學(xué)習(xí)的意義：
- 單鏈表會(huì)作為我們以后學(xué)習(xí)復(fù)雜數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)（圖的鄰接表、哈希桶）
- 單鏈表會(huì)有很多經(jīng)典的練習(xí)題，在筆試面試中會(huì)有很多相關(guān)的題目。
到此這篇關(guān)于C語言 超詳細(xì)模擬實(shí)現(xiàn)單鏈表建議收藏的文章就介紹到這了,更多相關(guān)C語言 單鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
c/c++拷貝構(gòu)造函數(shù)和關(guān)鍵字explicit詳解
這篇文章主要介紹了c/c++拷貝構(gòu)造函數(shù)和關(guān)鍵字explicit的相關(guān)知識(shí)，非常不錯(cuò)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2018-08-08
使用C++實(shí)現(xiàn)MySQL數(shù)據(jù)庫連接池
這篇文章主要為大家詳細(xì)介紹了如何使用C++實(shí)現(xiàn)MySQL數(shù)據(jù)庫連接池,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,有需要的小伙伴可以了解下2024-03-03
華為云開發(fā)工具CodeArts IDE for C/C++開發(fā)使用指南
CodeArts IDE是一個(gè)集成開發(fā)環(huán)境（IDE）,它提供了開發(fā)語言和調(diào)試服務(wù),本文主要介紹了華為云開發(fā)工具CodeArts IDE for C/C++ 開發(fā)使用指南,感興趣的可以了解一下2023-08-08
C語言中動(dòng)態(tài)內(nèi)存管理圖文詳解
在編寫程序時(shí),通常并不知道需要處理的數(shù)據(jù)量,或者難以評(píng)估所需處理數(shù)據(jù)量的變動(dòng)程度,下面這篇文章主要給大家介紹了關(guān)于C語言中動(dòng)態(tài)內(nèi)存管理的相關(guān)資料,需要的朋友可以參考下2022-06-06
C/C++常用函數(shù)易錯(cuò)點(diǎn)分析
這篇文章主要介紹了C/C++常用函數(shù)易錯(cuò)點(diǎn)分析,包含了memset、sizeof、getchar三個(gè)常用函數(shù)的分析,需要的朋友可以參考下2014-08-08
C語言修煉之路初識(shí)分支句?循環(huán)助本心下篇
現(xiàn)實(shí)生活中我們經(jīng)常需要根據(jù)不同的條件做出不同的選擇。程序設(shè)計(jì)中也需要根據(jù)條件來選擇不同的程序進(jìn)行處理，這稱之為分支結(jié)構(gòu)，當(dāng)條件表達(dá)式不存在時(shí),它被假設(shè)為真。您也可以設(shè)置一個(gè)初始值和增量表達(dá)式,一般情況下,C?程序員偏向于使用?for(;;)?結(jié)構(gòu)來表示一個(gè)無限循環(huán)2022-03-03
C語言結(jié)構(gòu)體版學(xué)生成績管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言結(jié)構(gòu)體版的學(xué)生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02
C/C++中一次性執(zhí)行多個(gè)DOS命令的實(shí)現(xiàn)思路
在C語言中執(zhí)行DOS命令的方法很多，在這就不一給大家一一介紹了，本文重點(diǎn)給大家介紹C/C++中一次性執(zhí)行多個(gè)DOS命令的實(shí)現(xiàn)思路，需要的朋友參考下2017-12-12
這篇文章主要介紹了C++讀寫INI配置文件的類,實(shí)例分析了C++操作ini配置文件的相關(guān)技巧,需要的朋友可以參考下2015-06-06
C++ 標(biāo)準(zhǔn)模板庫 STL 順序容器詳解
這篇文章主要介紹了C++ 標(biāo)準(zhǔn)模板庫 STL 順序容器詳解,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-05-05