C語言詳解無頭單向非循環(huán)鏈表各種操作方法
鏈表引入
問：上次我們看了順序表，那么順序表有些什么優(yōu)缺點(diǎn)呢？
優(yōu)點(diǎn)：
順序表是連續(xù)的物理空間，方便下標(biāo)的隨機(jī)訪問。
缺點(diǎn)：
1.增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊的空間。會(huì)有一定消耗。
2.頭部或者中間位置插入或者刪除數(shù)據(jù)，需要挪動(dòng)數(shù)據(jù)，效率較低。
3.可能存在一定空間占用，浪費(fèi)空間，不能按需申請和釋放空間。
為了解決上訴問題，我們引入了鏈表。首先我們先來看看單鏈表。
鏈表介紹
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)節(jié)點(diǎn)包含兩部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。
實(shí)際上，鏈表的結(jié)構(gòu)多樣，如下：
1.單向或者雙向
2.帶頭或者不帶頭
3.循環(huán)或者非循環(huán)
創(chuàng)建鏈表
鏈表是由結(jié)點(diǎn)鏈接而成的，所以創(chuàng)建鏈表需要?jiǎng)?chuàng)建一個(gè)結(jié)點(diǎn)類型。該類型由指針域和數(shù)據(jù)域組成。
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;//用來存放該結(jié)點(diǎn)的數(shù)據(jù)
struct SListNode* next;//用來存放下一個(gè)結(jié)點(diǎn)的地址
}SListNode;
打印鏈表
從頭指針指向的位置開始，依次向后打印，知道cur訪問到NULL就結(jié)束循環(huán)。
void SListPrint(SListNode* phead);
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;//我們一般不會(huì)改變頭指針，所以我們把頭指針賦值給cur
while (cur)//鏈表結(jié)束條件
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");//表示數(shù)據(jù)已經(jīng)打印完畢
}創(chuàng)建結(jié)點(diǎn)
每當(dāng)我們需要插入一個(gè)數(shù)據(jù)，我們就需要申請一個(gè)結(jié)點(diǎn)，如果每次都重新申請就會(huì)很麻煩，所以我們將創(chuàng)建一個(gè)新結(jié)點(diǎn)封裝為一個(gè)函數(shù)。
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
printf("BuySListNode::%s\n", strerror(errno));//若申請失敗，則打印錯(cuò)誤信息
exit(-1);
}
else
{
newnode->data = x;//將數(shù)據(jù)賦值到新點(diǎn)的數(shù)據(jù)域
newnode->next = NULL;//新結(jié)點(diǎn)指針域置為空指針
}
return newnode;//返回新結(jié)點(diǎn)的地址
}單鏈表尾插
我們需要將尾插分為兩種情況：
情況一： 鏈表為空，我們直接讓頭指針指向新的結(jié)點(diǎn)即可。
情況二： 鏈表已經(jīng)有多個(gè)結(jié)點(diǎn)，我們需要找到鏈表的最后一個(gè)結(jié)點(diǎn)，然后讓最后一個(gè)結(jié)點(diǎn)指向新的結(jié)點(diǎn)。
void SListPushBack(SListNode** pphead, SLTDataType x);
void SListPushBack(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);
//鏈表為空
if (*pphead == NULL)
{
*pphead = newnode;//頭指針指向新的結(jié)點(diǎn)
}
//鏈表不為空
else
{
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}注意： 鏈表頭插函數(shù)的參數(shù)我們應(yīng)該傳頭指針的地址，而不是頭指針本身。如果為傳值調(diào)用，那么形參是實(shí)參的一份臨時(shí)拷貝，對形參的改變不會(huì)影響實(shí)參。
單鏈表頭插
單鏈表頭插時(shí)，我們申請一個(gè)新的結(jié)點(diǎn)，然后讓新結(jié)點(diǎn)的指針域指向之前的第一個(gè)結(jié)點(diǎn)，然后讓頭指針指向新結(jié)點(diǎn)。
注意：這兩步操作的順序不可以顛倒，如果先讓頭指針指向了新結(jié)點(diǎn)，那么將不可能找到第一個(gè)結(jié)點(diǎn)的位置了。也不可能在找到后面的數(shù)據(jù)了。
void SListPushFront(SListNode** pphead, SLTDataType x);
void SListPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}單鏈表尾刪
演示一種錯(cuò)誤的寫法：
對于單鏈表的尾刪，我們需要考慮三種情況：
1.鏈表為空時(shí)，不做任何處理。
2.鏈表只有一個(gè)結(jié)點(diǎn)時(shí)，釋放該結(jié)點(diǎn)，然后將頭指針置為空。
3.鏈表有多個(gè)結(jié)點(diǎn)時(shí)，有兩種處理方法，詳見一下代碼。
代碼一： 找到最后一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，釋放最后一個(gè)結(jié)點(diǎn)。將前一個(gè)結(jié)點(diǎn)的指針域置為空指針。
void SListPopBack(SListNode** pphead);
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)
return;
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* prev = NULL;
SListNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}代碼二： 找到最后一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，將后一個(gè)結(jié)點(diǎn)釋放掉，然后在置為空就可以了。
void SListPopBack(SListNode** pphead);
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)
return;
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}單鏈表頭刪
若鏈表為空，則不處理。若鏈表不為空，讓頭指針指向第二個(gè)結(jié)點(diǎn)，釋放掉第一個(gè)結(jié)點(diǎn)。
void SListPopFront(SListNode** pphead);
void SListPopFront(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//鏈表為空
return;
else
{
SListNode* head = *pphead;
*pphead = head->next;//讓頭指針指針域中的地址指向頭指針
free(head);//釋放第一個(gè)結(jié)點(diǎn)
head = NULL;
}
}
在pos位置之前插入數(shù)據(jù)
若pos是第一個(gè)結(jié)點(diǎn)，我們直接調(diào)用之前寫的頭插。若pos不是第一個(gè)結(jié)點(diǎn)，我們找到pos位置的前一個(gè)結(jié)點(diǎn)，讓新的結(jié)點(diǎn)指向地址為pos的結(jié)點(diǎn)，然后讓前一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)。
void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x);
void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SListPushFront(pphead,x);//頭插函數(shù)
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)//找到pos的前一個(gè)結(jié)點(diǎn)
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
newnode->next = prev->next;//讓新結(jié)點(diǎn)指向pos結(jié)點(diǎn)
prev->next = newnode;//讓前一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)
}
}在pos位置之后插入數(shù)據(jù)
讓新結(jié)點(diǎn)指向該位置的下一個(gè)位置，然后讓該位置的結(jié)點(diǎn)指向新結(jié)點(diǎn)。
void SListInsertAfter(SListNode** pphead, SListNode* pos, SLTDataType x);
void SListInsertAfter(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}刪除pos位置結(jié)點(diǎn)
void SListErase(SListNode** pphead, SListNode* pos);
void SListErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SListPopFront(pphead);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}刪除pos位置之后的結(jié)點(diǎn)
void SListEraseAfter(SListNode* pos);
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* next = pos->next;
if (next)//如果next不為空，則條件為真
{
pos->next = next->next;//讓pos指向要?jiǎng)h除位置的后一個(gè)結(jié)點(diǎn)
free(next);//釋放pos的下一個(gè)結(jié)點(diǎn)
next = NULL;
}
}銷毀鏈表
在銷毀鏈表時(shí)。首先我們將頭指針賦值給一個(gè)新的指針，用該指針依次遍歷鏈表，先把該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的地址保存，然后在釋放該結(jié)點(diǎn)，最后將頭指針置為空。
注意： 一定要在釋放該指針之前保存該指針的下一個(gè)結(jié)點(diǎn)的地址，否則就找不到下一個(gè)結(jié)點(diǎn)了。
void SListDestroy(SListNode** pphead);
void SListDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;//存放下一個(gè)結(jié)點(diǎn)地址
free(cur);//釋放當(dāng)前結(jié)點(diǎn)
cur = NULL;
}
*pphead = NULL;//將頭指針置為空
}鏈表查找
SListNode* SListFind(SListNode* phead, SLTDataType x)；
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
SListNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}提示：我們在寫鏈表的時(shí)候，盡量畫圖分析，幫助我們理清思路。
到此這篇關(guān)于C語言詳解無頭單向非循環(huán)鏈表各種操作方法的文章就介紹到這了,更多相關(guān)C語言無頭單向非循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言詳細(xì)解析有符號(hào)數(shù)與無符號(hào)數(shù)的表示
我們知道，在C語言中存在無符號(hào)數(shù)和有符號(hào)數(shù)，但是對于計(jì)算機(jī)而言，其本身并不區(qū)別有符號(hào)數(shù)和無符號(hào)數(shù)，因?yàn)樵谟?jì)算機(jī)里面都是O或者1，但是在我們的實(shí)際使用中有時(shí)候需要使用有符號(hào)數(shù)來表示一個(gè)整數(shù)，因此我們規(guī)定，當(dāng)最高位為1的時(shí)，表示為負(fù)數(shù)，最高位為0時(shí)，表示為正數(shù)2022-04-04
2~62位任意進(jìn)制轉(zhuǎn)換方法(c++)
下面小編就為大家?guī)硪黄?~62位任意進(jìn)制轉(zhuǎn)換方法(c++)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-06-06
C++類模板與函數(shù)模板基礎(chǔ)詳細(xì)講解
C++語言的模板技術(shù)包括函數(shù)模板和類模板，模板技術(shù)是一種代碼重用技術(shù)，函數(shù)和類是C++語言中兩種主要的重用代碼形式，這篇文章主要介紹了C++函數(shù)模板和類模板,需要的朋友可以參考下2022-08-08
C語言中計(jì)算正弦的相關(guān)函數(shù)總結(jié)
這篇文章主要介紹了C語言中計(jì)算正弦的相關(guān)函數(shù)總結(jié),包括正弦和雙曲線正弦以及反正弦的函數(shù),需要的朋友可以參考下2015-08-08
當(dāng)談?wù)揅++編程語言時(shí),以下術(shù)語經(jīng)常被提及：int、DWORD和QWORD,它們是用于表示不同數(shù)據(jù)類型和長度的關(guān)鍵字,本文通過舉例給大家詳細(xì)介紹,感興趣的朋友一起看看吧2024-06-06
這篇文章主要介紹了OpenCV 顏色追蹤的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-01-01
c++實(shí)現(xiàn)值機(jī)系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了c++實(shí)現(xiàn)在線值機(jī)系統(tǒng)程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
C++默認(rèn)參數(shù)與函數(shù)重載及注意事項(xiàng)
這篇文章主要介紹了C++默認(rèn)參數(shù)與函數(shù)重載及注意事項(xiàng)包括語法與使用，通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2020-03-03
本文主要介紹了Qt在線安裝加速的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
C++中隱式類型轉(zhuǎn)換學(xué)習(xí)筆記
在本篇文章里小編給大家整理的是一篇關(guān)于C++中隱式類型轉(zhuǎn)換學(xué)習(xí)筆記內(nèi)容，有興趣的跟著小編來學(xué)習(xí)下吧。2020-02-02