C語言詳解無頭單向非循環(huán)鏈表各種操作方法
鏈表引入
問：上次我們看了順序表，那么順序表有些什么優(yōu)缺點呢？
優(yōu)點：
順序表是連續(xù)的物理空間，方便下標的隨機訪問。
缺點：
1.增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊的空間。會有一定消耗。
2.頭部或者中間位置插入或者刪除數(shù)據(jù)，需要挪動數(shù)據(jù)，效率較低。
3.可能存在一定空間占用，浪費空間，不能按需申請和釋放空間。
為了解決上訴問題，我們引入了鏈表。首先我們先來看看單鏈表。
鏈表介紹
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)、數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個節(jié)點包含兩部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。
實際上，鏈表的結(jié)構(gòu)多樣，如下：
1.單向或者雙向
2.帶頭或者不帶頭
3.循環(huán)或者非循環(huán)
創(chuàng)建鏈表
鏈表是由結(jié)點鏈接而成的，所以創(chuàng)建鏈表需要創(chuàng)建一個結(jié)點類型。該類型由指針域和數(shù)據(jù)域組成。
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;//用來存放該結(jié)點的數(shù)據(jù)
struct SListNode* next;//用來存放下一個結(jié)點的地址
}SListNode;
打印鏈表
從頭指針指向的位置開始，依次向后打印，知道cur訪問到NULL就結(jié)束循環(huán)。
void SListPrint(SListNode* phead);
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;//我們一般不會改變頭指針，所以我們把頭指針賦值給cur
while (cur)//鏈表結(jié)束條件
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");//表示數(shù)據(jù)已經(jīng)打印完畢
}創(chuàng)建結(jié)點
每當我們需要插入一個數(shù)據(jù)，我們就需要申請一個結(jié)點，如果每次都重新申請就會很麻煩，所以我們將創(chuàng)建一個新結(jié)點封裝為一個函數(shù)。
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
printf("BuySListNode::%s\n", strerror(errno));//若申請失敗，則打印錯誤信息
exit(-1);
}
else
{
newnode->data = x;//將數(shù)據(jù)賦值到新點的數(shù)據(jù)域
newnode->next = NULL;//新結(jié)點指針域置為空指針
}
return newnode;//返回新結(jié)點的地址
}單鏈表尾插
我們需要將尾插分為兩種情況：
情況一： 鏈表為空，我們直接讓頭指針指向新的結(jié)點即可。
情況二： 鏈表已經(jīng)有多個結(jié)點，我們需要找到鏈表的最后一個結(jié)點，然后讓最后一個結(jié)點指向新的結(jié)點。
void SListPushBack(SListNode** pphead, SLTDataType x);
void SListPushBack(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);
//鏈表為空
if (*pphead == NULL)
{
*pphead = newnode;//頭指針指向新的結(jié)點
}
//鏈表不為空
else
{
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}注意： 鏈表頭插函數(shù)的參數(shù)我們應該傳頭指針的地址，而不是頭指針本身。如果為傳值調(diào)用，那么形參是實參的一份臨時拷貝，對形參的改變不會影響實參。
單鏈表頭插
單鏈表頭插時，我們申請一個新的結(jié)點，然后讓新結(jié)點的指針域指向之前的第一個結(jié)點，然后讓頭指針指向新結(jié)點。
注意：這兩步操作的順序不可以顛倒，如果先讓頭指針指向了新結(jié)點，那么將不可能找到第一個結(jié)點的位置了。也不可能在找到后面的數(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;
}單鏈表尾刪
演示一種錯誤的寫法：
對于單鏈表的尾刪，我們需要考慮三種情況：
1.鏈表為空時，不做任何處理。
2.鏈表只有一個結(jié)點時，釋放該結(jié)點，然后將頭指針置為空。
3.鏈表有多個結(jié)點時，有兩種處理方法，詳見一下代碼。
代碼一： 找到最后一個結(jié)點的前一個結(jié)點，釋放最后一個結(jié)點。將前一個結(jié)點的指針域置為空指針。
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;
}
}代碼二： 找到最后一個結(jié)點的前一個結(jié)點，將后一個結(jié)點釋放掉，然后在置為空就可以了。
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;
}
}單鏈表頭刪
若鏈表為空，則不處理。若鏈表不為空，讓頭指針指向第二個結(jié)點，釋放掉第一個結(jié)點。
void SListPopFront(SListNode** pphead);
void SListPopFront(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//鏈表為空
return;
else
{
SListNode* head = *pphead;
*pphead = head->next;//讓頭指針指針域中的地址指向頭指針
free(head);//釋放第一個結(jié)點
head = NULL;
}
}
在pos位置之前插入數(shù)據(jù)
若pos是第一個結(jié)點，我們直接調(diào)用之前寫的頭插。若pos不是第一個結(jié)點，我們找到pos位置的前一個結(jié)點，讓新的結(jié)點指向地址為pos的結(jié)點，然后讓前一個結(jié)點指向新結(jié)點。
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的前一個結(jié)點
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
newnode->next = prev->next;//讓新結(jié)點指向pos結(jié)點
prev->next = newnode;//讓前一個結(jié)點指向新結(jié)點
}
}在pos位置之后插入數(shù)據(jù)
讓新結(jié)點指向該位置的下一個位置，然后讓該位置的結(jié)點指向新結(jié)點。
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é)點
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é)點
void SListEraseAfter(SListNode* pos);
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* next = pos->next;
if (next)//如果next不為空，則條件為真
{
pos->next = next->next;//讓pos指向要刪除位置的后一個結(jié)點
free(next);//釋放pos的下一個結(jié)點
next = NULL;
}
}銷毀鏈表
在銷毀鏈表時。首先我們將頭指針賦值給一個新的指針，用該指針依次遍歷鏈表，先把該結(jié)點的下一個結(jié)點的地址保存，然后在釋放該結(jié)點，最后將頭指針置為空。
注意： 一定要在釋放該指針之前保存該指針的下一個結(jié)點的地址，否則就找不到下一個結(jié)點了。
void SListDestroy(SListNode** pphead);
void SListDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;//存放下一個結(jié)點地址
free(cur);//釋放當前結(jié)點
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;
}提示：我們在寫鏈表的時候，盡量畫圖分析，幫助我們理清思路。
到此這篇關(guān)于C語言詳解無頭單向非循環(huán)鏈表各種操作方法的文章就介紹到這了,更多相關(guān)C語言無頭單向非循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細介紹了C++雙向鏈表實現(xiàn)簡單通訊錄，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
C語言中QString與QByteArray互相轉(zhuǎn)換的方法
本文主要介紹了C語言中QString與QByteArray互相轉(zhuǎn)換的方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-05-05
這篇文章主要給大家介紹了關(guān)于C語言之預處理命令的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
OpenCV實現(xiàn)低對比度圖像臟污區(qū)域檢測
本文主要介紹了OpenCV實現(xiàn)低對比度圖像臟污區(qū)域檢測，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
內(nèi)核是操作系統(tǒng)最核心的內(nèi)容，主要提供硬件抽象層、磁盤及文件系統(tǒng)控制、多任務等功能，由于其涉及非常廣泛的計算機知識，很少被人們所熟悉，因而披上了一層神秘的面紗2021-08-08
這篇文章主要介紹了EasyC++靜態(tài)持續(xù)變量，除了自動存儲變量之后，C++當中還有靜態(tài)持續(xù)變量。關(guān)于靜態(tài)持續(xù)變量的定義C++和C語言是一樣的，它擁有三種鏈接性，即外部鏈接性、內(nèi)部連接性和無鏈接性，下面一起進入文章了解更具體內(nèi)容吧2021-12-12
Qt數(shù)據(jù)庫應用之實現(xiàn)csv文件轉(zhuǎn)xls
這篇文章主要為大家詳細介紹了如何利用Qt實現(xiàn)csv文件轉(zhuǎn)xls功能，文中的示例代碼講解詳細，對我們學習或工作有一定參考價值，需要的可以了解一下2022-06-06
以下是對pthread_cond_wait的用法進行了詳細的分析介紹，需要的朋友可以過來參考下2013-07-07
這篇文章主要為大家詳細介紹了QT如何實現(xiàn)自定義Http客戶端的，可以實現(xiàn)支持get,post請求方式；支持連接超時處理；支持網(wǎng)絡錯誤,嘗試重連等功能，感興趣的小伙伴可以學習一下2022-11-11
這篇文章主要為大家詳細介紹了如何利用QT+Quick實現(xiàn)自定義組件（按鈕、下拉菜單等），文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下2022-11-11