C語言詳解無頭單向非循環(huán)鏈表各種操作方法
鏈表引入
問：上次我們看了順序表，那么順序表有些什么優(yōu)缺點(diǎn)呢？
優(yōu)點(diǎn)：
順序表是連續(xù)的物理空間，方便下標(biāo)的隨機(jī)訪問。
缺點(diǎn)：
1.增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊的空間。會(huì)有一定消耗。
2.頭部或者中間位置插入或者刪除數(shù)據(jù)，需要挪動(dòng)數(shù)據(jù)，效率較低。
3.可能存在一定空間占用，浪費(fèi)空間，不能按需申請(qǐng)和釋放空間。
為了解決上訴問題，我們引入了鏈表。首先我們先來看看單鏈表。
鏈表介紹
鏈表是一種物理存儲(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ù)，我們就需要申請(qǐng)一個(gè)結(jié)點(diǎn)，如果每次都重新申請(qǐng)就會(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));//若申請(qǐng)失敗，則打印錯(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í)拷貝，對(duì)形參的改變不會(huì)影響實(shí)參。
單鏈表頭插
單鏈表頭插時(shí)，我們申請(qǐng)一個(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ò)誤的寫法：
對(duì)于單鏈表的尾刪，我們需要考慮三種情況：
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;
}提示：我們?cè)趯戞湵淼臅r(shí)候，盡量畫圖分析，幫助我們理清思路。
到此這篇關(guān)于C語言詳解無頭單向非循環(huán)鏈表各種操作方法的文章就介紹到這了,更多相關(guān)C語言無頭單向非循環(huán)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++雙向鏈表實(shí)現(xiàn)簡(jiǎn)單通訊錄
這篇文章主要為大家詳細(xì)介紹了C++雙向鏈表實(shí)現(xiàn)簡(jiǎn)單通訊錄，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
C語言中QString與QByteArray互相轉(zhuǎn)換的方法
本文主要介紹了C語言中QString與QByteArray互相轉(zhuǎn)換的方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05
這篇文章主要給大家介紹了關(guān)于C語言之預(yù)處理命令的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
OpenCV實(shí)現(xiàn)低對(duì)比度圖像臟污區(qū)域檢測(cè)
本文主要介紹了OpenCV實(shí)現(xiàn)低對(duì)比度圖像臟污區(qū)域檢測(cè)，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
內(nèi)核是操作系統(tǒng)最核心的內(nèi)容，主要提供硬件抽象層、磁盤及文件系統(tǒng)控制、多任務(wù)等功能，由于其涉及非常廣泛的計(jì)算機(jī)知識(shí)，很少被人們所熟悉，因而披上了一層神秘的面紗2021-08-08
這篇文章主要介紹了EasyC++靜態(tài)持續(xù)變量，除了自動(dòng)存儲(chǔ)變量之后，C++當(dāng)中還有靜態(tài)持續(xù)變量。關(guān)于靜態(tài)持續(xù)變量的定義C++和C語言是一樣的，它擁有三種鏈接性，即外部鏈接性、內(nèi)部連接性和無鏈接性，下面一起進(jìn)入文章了解更具體內(nèi)容吧2021-12-12
Qt數(shù)據(jù)庫(kù)應(yīng)用之實(shí)現(xiàn)csv文件轉(zhuǎn)xls
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)csv文件轉(zhuǎn)xls功能，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)或工作有一定參考價(jià)值，需要的可以了解一下2022-06-06
以下是對(duì)pthread_cond_wait的用法進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-07-07
QT實(shí)現(xiàn)自定義Http客戶端的示例代碼
這篇文章主要為大家詳細(xì)介紹了QT如何實(shí)現(xiàn)自定義Http客戶端的，可以實(shí)現(xiàn)支持get,post請(qǐng)求方式；支持連接超時(shí)處理；支持網(wǎng)絡(luò)錯(cuò)誤,嘗試重連等功能，感興趣的小伙伴可以學(xué)習(xí)一下2022-11-11
QT+Quick實(shí)現(xiàn)自定義組件的示例詳解
這篇文章主要為大家詳細(xì)介紹了如何利用QT+Quick實(shí)現(xiàn)自定義組件（按鈕、下拉菜單等），文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-11-11