手把手教你實(shí)現(xiàn)一個(gè)C++單鏈表
一. 節(jié)點(diǎn)聲明
鏈表是一種數(shù)據(jù)結(jié)構(gòu)，用于數(shù)據(jù)的存儲(chǔ)。
如圖，每一個(gè)鏈表節(jié)點(diǎn)所在的內(nèi)存空間是不延續(xù)的，因?yàn)椴皇沁B續(xù)存儲(chǔ)，所以需要存入下一個(gè)節(jié)點(diǎn)的地址，這樣方便找到下一個(gè)數(shù)值，而最后一個(gè)鏈表指向的空間為NULL，因此我們可以聲明一個(gè)結(jié)構(gòu)體，代表一個(gè)節(jié)點(diǎn)。
typedef int ListDataType;
typedef struct SListNode
{
ListDataType data;
struct SListNode* Next;
}SLNode;
SListNode 是我們的節(jié)點(diǎn)結(jié)構(gòu)體，ListDataType是存儲(chǔ)數(shù)據(jù)的類型。
二. 尾插
鏈表的節(jié)點(diǎn)建立好后，接下來我們來進(jìn)行尾部插入數(shù)據(jù)。
那么我們只需要找到尾部節(jié)點(diǎn)，把尾部節(jié)點(diǎn)指向的NULL值置為新節(jié)點(diǎn)。新節(jié)點(diǎn)指向NULL
因此我們要新建一個(gè)節(jié)點(diǎn)，然后找到最后一個(gè)節(jié)點(diǎn)。
void SListPushBack(SLNode** phead, ListDataType x)
{
//新開辟一個(gè)節(jié)點(diǎn)
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (newNode == NULL)
{
//空間開辟失敗
printf("SListPushBack::newNode");
exit(-1);
}
//找到最后一個(gè)節(jié)點(diǎn)
SLNode* cru = *phead;
//如果cru指向NULL，說明cru是最后一個(gè)節(jié)點(diǎn)
while (cru->Next != NULL)
{
cru = cru->Next;
}
//cru 指向新節(jié)點(diǎn)
cru->Next = newNode;
//新節(jié)點(diǎn)指向NULL，存儲(chǔ)數(shù)據(jù)x
newNode->data = x;
newNode->Next = NULL;
}
但是這種方法，我們需要注意一種情況，那就是如果鏈表中本身沒有節(jié)點(diǎn)，那么cru初始就是一個(gè)空指針，而循環(huán)條件我們對(duì)空指針進(jìn)行了解引用，所以我們需要判斷一下。
//尾部數(shù)據(jù)插入
void SListPushBack(SLNode** phead, ListDataType x)
{
//新開辟一個(gè)節(jié)點(diǎn)
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (newNode == NULL)
{
//空間開辟失敗
printf("SListPushBack::newNode");
exit(-1);
}
//新節(jié)點(diǎn)指向NULL，存儲(chǔ)數(shù)據(jù)x
newNode->data = x;
newNode->Next = NULL;
if (*phead == NULL)
{
//當(dāng)前鏈表為空，那么我直接讓新節(jié)點(diǎn)替代phead
*phead = newNode;
return;
}
//找到最后一個(gè)節(jié)點(diǎn)
SLNode* cru = *phead;
//如果cru指向NULL，說明cru是最后一個(gè)節(jié)點(diǎn)
while (cru->Next != NULL)
{
cru = cru->Next;
}
//cru 指向新節(jié)點(diǎn)
cru->Next = newNode;
}
然后我們測(cè)試一下，發(fā)現(xiàn)鏈表已經(jīng)鏈接起來了
三. 鏈表打印
為了方便后面測(cè)試，我們決定先實(shí)現(xiàn)打印鏈表的函數(shù)。我們只需要依次查找節(jié)點(diǎn)指向的元素，直到最后一個(gè)指向NULL時(shí)，我們停下來。
//鏈表打印
void SListPrint(SLNode* head)
{
SLNode* cru = head;
while (cru)
{
printf("%d->",cru->data);
cru = cru->Next;
}
printf("NULL\n");
}
四. 頭插
頭部插入和尾部插入差不多，我們只需要把新節(jié)點(diǎn)指向鏈表中的第一個(gè)節(jié)點(diǎn)，然后把頭節(jié)點(diǎn)換成新節(jié)點(diǎn)。
因?yàn)槲覀兾膊宓臅r(shí)候創(chuàng)建了節(jié)點(diǎn)，頭插又創(chuàng)建節(jié)點(diǎn)，太麻煩了，所以我們把創(chuàng)建節(jié)點(diǎn)封裝成一個(gè)函數(shù)。
//創(chuàng)建節(jié)點(diǎn)
SLNode* SListCreateNode(ListDataType x)
{
//新開辟一個(gè)節(jié)點(diǎn)
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (newNode == NULL)
{
//空間開辟失敗
printf("SListPushBack::newNode");
exit(-1);
}
//新節(jié)點(diǎn)指向NULL，存儲(chǔ)數(shù)據(jù)x
newNode->data = x;
newNode->Next = NULL;
return newNode;
}
尾插函數(shù)調(diào)整
//尾部數(shù)據(jù)插入
void SListPushBack(SLNode** phead, ListDataType x)
{
SLNode* newNode = SListCreateNode(x);
if (*phead == NULL)
{
//當(dāng)前鏈表為空，那么我直接讓新節(jié)點(diǎn)替代phead
*phead = newNode;
return;
}
//找到最后一個(gè)節(jié)點(diǎn)
SLNode* cru = *phead;
//如果cru指向NULL，說明cru是最后一個(gè)節(jié)點(diǎn)
while (cru->Next != NULL)
{
cru = cru->Next;
}
//cru 指向新節(jié)點(diǎn)
cru->Next = newNode;
}
頭插函數(shù)
//頭部數(shù)據(jù)插入
void SListPushFront(SLNode** phead, ListDataType x)
{
//新建節(jié)點(diǎn)
SLNode* newNode = SListCreateNode(x);
//讓節(jié)點(diǎn)指向頭
newNode->Next = *phead;
//頭節(jié)點(diǎn)更替為新節(jié)點(diǎn)
*phead = newNode;
}
頭插測(cè)試
五. 尾刪
尾刪也就是刪除鏈表中的最后一個(gè)節(jié)點(diǎn)。那么我們需要找到最后一個(gè)節(jié)點(diǎn)，把它釋放，并且要把它的前一個(gè)節(jié)點(diǎn)置為空指針，否則它會(huì)變成一個(gè)野指針。
//尾部數(shù)據(jù)刪除
void SListPopBack(SLNode** phead)
{
SLNode* cru = *phead; //最后一個(gè)節(jié)點(diǎn)
SLNode* prve = NULL; //前一個(gè)節(jié)點(diǎn)
//最后一個(gè)節(jié)點(diǎn)指向空
while (cru->Next)
{
prve = cru;
cru = cru->Next;
}
//cru 為最后一個(gè)節(jié)點(diǎn)。釋放掉
free(cru);
//前一個(gè)節(jié)點(diǎn)指向空
prve->Next = NULL;
}
但是這個(gè)尾刪是建立在有數(shù)據(jù)的情況下的，如果沒有數(shù)據(jù)我們進(jìn)行此操作，那會(huì)造成空指針prve訪問，所以我們?cè)谇懊嬉獢嘌砸幌?/p>
void SListPopBack(SLNode** phead)
{
//鏈表為空無法刪除
assert(*phead);
SLNode* cru = *phead; //最后一個(gè)節(jié)點(diǎn)
SLNode* prve = NULL; //前一個(gè)節(jié)點(diǎn)
//最后一個(gè)節(jié)點(diǎn)指向空
while (cru->Next)
{
prve = cru;
cru = cru->Next;
}
//cru 為最后一個(gè)節(jié)點(diǎn)。釋放掉
free(cru);
//前一個(gè)節(jié)點(diǎn)指向空
prve->Next = NULL;
}
即使這樣，以上代碼依然有問題，因?yàn)楫?dāng)鏈表只有一個(gè)節(jié)點(diǎn)時(shí)，并不會(huì)進(jìn)入while循環(huán)，也就導(dǎo)致 prve對(duì)空指針解引用，所以我們還需要判斷一下，如果鏈表只有一個(gè)節(jié)點(diǎn)，那么就直接釋放頭節(jié)點(diǎn)。
//尾部數(shù)據(jù)刪除
void SListPopBack(SLNode** phead)
{
//鏈表為空無法刪除
assert(*phead);
//只有一個(gè)節(jié)點(diǎn)時(shí)
if((*phead)->Next == NULL)
{
//釋放頭空間
free(*phead);
//置為空指針
*phead = NULL;
return;
}
SLNode* cru = *phead; //最后一個(gè)節(jié)點(diǎn)
SLNode* prve = NULL; //前一個(gè)節(jié)點(diǎn)
//找到最后一個(gè)節(jié)點(diǎn)
while (cru->Next)
{
prve = cru;
cru = cru->Next;
}
//cru 為最后一個(gè)節(jié)點(diǎn)。釋放掉
free(cru);
//前一個(gè)節(jié)點(diǎn)指向空
prve->Next = NULL;
}
代碼測(cè)試
六. 頭刪
尾刪都會(huì)了，頭刪還遠(yuǎn)嗎？頭刪我們只需要把頭節(jié)點(diǎn)指向的空間釋放，然后讓頭節(jié)點(diǎn)的指針指向下一個(gè)節(jié)點(diǎn)。
當(dāng)然，如果鏈表為空，我們是無法操作的，我們也要斷言或者if判斷一下。
//頭部數(shù)據(jù)刪除
void SListPopFront(SLNode** phead)
{
//斷言
assert(*phead);
//鏈表不為空，存儲(chǔ)下一個(gè)位置的地址
SLNode* NextNode = (*phead)->Next;
//釋放 *phead
free(*phead);
//存儲(chǔ)的節(jié)點(diǎn)給*phead
*phead = NextNode;
}
測(cè)試一下代碼
七. 查找值
在鏈表里查找值，我們只需要找節(jié)點(diǎn)，如果與找的值相等，就返回當(dāng)前下標(biāo)或者節(jié)點(diǎn)，這里我們用返回節(jié)點(diǎn)演示。
SLNode* SListFindNode(SLNode* head, ListDataType x)
{
SLNode* cru = head;
//查找值
while (cru)
{
//如果當(dāng)前節(jié)點(diǎn)等于要查找的值
if (cru->data == x)
{
//返回當(dāng)前節(jié)點(diǎn)，也可以返回下標(biāo)，把函數(shù)返回值改成int
return cru;
}
//下一個(gè)節(jié)點(diǎn)
cru = cru->Next;
}
//遍歷完沒有找到， 返回空指針
return NULL;
}
看看測(cè)試結(jié)果
鏈表里我們插入了三個(gè)值，1，2，3。然后找1的值并返回當(dāng)前節(jié)點(diǎn)，最終提示我們找到了。
當(dāng)然，也可以用返回下標(biāo)的方式，然后利用下標(biāo)控制查找次數(shù)。
八.指定插入
指定插入，我們這里來演示前插，也就是在一個(gè)節(jié)點(diǎn)的前面進(jìn)行插入，我們只需要把這個(gè)節(jié)點(diǎn)前面的節(jié)點(diǎn)指向新節(jié)點(diǎn)，然后新節(jié)點(diǎn)指向這個(gè)節(jié)點(diǎn)。
所以我們要先創(chuàng)建一個(gè)節(jié)點(diǎn)，讓被插入節(jié)點(diǎn)之前的節(jié)點(diǎn)指向該節(jié)點(diǎn)，讓新節(jié)點(diǎn)指向被插入的節(jié)點(diǎn)。
//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
//首先插入之前，我們必須保證被插入的pos節(jié)點(diǎn)存在，不然無法插入
assert(pos);
SLNode* cru = *phead; //用來查找被插入的節(jié)點(diǎn)
//查找pos節(jié)點(diǎn)
while (cru->Next != pos)
{
cru = cru->Next;
}
//找到后，創(chuàng)建一個(gè)新節(jié)點(diǎn)
SLNode* newNode = SListCreateNode(x);
//新節(jié)點(diǎn)指向pos
newNode->Next = pos;
//pos的前一個(gè)節(jié)點(diǎn)指向cru
cru->Next = newNode;
}
此時(shí)這個(gè)代碼仍有問題，因?yàn)槿绻?pos是第一個(gè)節(jié)點(diǎn)時(shí)，cru->next無法判斷判斷第一個(gè)節(jié)點(diǎn)，所以我們要加個(gè)判斷，如果是頭節(jié)點(diǎn)，直接調(diào)用頭插函數(shù)。
//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
//首先插入之前，我們必須保證被插入的pos節(jié)點(diǎn)存在，不然無法插入
assert(pos);
//頭節(jié)點(diǎn)就是pos
if (*phead == pos)
{
//調(diào)用頭插
SListPushFront(phead,x);
return 0;
}
SLNode* cru = *phead; //用來查找被插入的節(jié)點(diǎn)
//查找pos節(jié)點(diǎn)
while (cru->Next != pos)
{
cru = cru->Next;
}
//找到后，創(chuàng)建一個(gè)新節(jié)點(diǎn)
SLNode* newNode = SListCreateNode(x);
//新節(jié)點(diǎn)指向pos
newNode->Next = pos;
//pos的前一個(gè)節(jié)點(diǎn)指向cru
cru->Next = newNode;
}
代碼測(cè)試
九.指定刪除
指定刪除和指定插入差不多，我們只需要把被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，指向后一個(gè)節(jié)點(diǎn)，然后刪除節(jié)點(diǎn)。如果要?jiǎng)h除的是頭節(jié)點(diǎn)，直接調(diào)用頭刪函數(shù)，或者也可以再次寫一個(gè)頭刪。
//指定節(jié)點(diǎn)刪除
void SListEase(SLNode** phead, SLNode* pos)
{
//pos是空指針，干掉程序
assert(pos);
//如果頭節(jié)點(diǎn)與pos相等，直接調(diào)用頭刪
if (*phead == pos)
{
SListPopFront(phead);
return;
}
//創(chuàng)建一個(gè)節(jié)點(diǎn)
SLNode* cru = *phead; //查找被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
while (cru->Next != pos)
{
cru = cru->Next;
}
//cru指向 pos 后的位置
cru->Next = pos->Next;
//釋放pos所在空間
free(pos);
pos = NULL;
}代碼測(cè)試
十.銷毀鏈表
如果這個(gè)鏈表不想用了，我們想要清空鏈表。那我們只需要把依次釋放內(nèi)存。
//銷毀鏈表
void SListDestroy(SLNode** phead)
{
SLNode* cru = NULL;
while (*phead)
{
//存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址
cru = (*phead)->Next;+
//當(dāng)前地址置空
*phead = NULL;
//釋放當(dāng)前空間
free(*phead);
//換成下一個(gè)節(jié)點(diǎn)繼續(xù)
*phead = cru;
}
}然后我們測(cè)試一下，發(fā)現(xiàn)所有的節(jié)點(diǎn)都置空了
以上代碼以上傳至git，點(diǎn)這里獲取
到此這篇關(guān)于手把手教你實(shí)現(xiàn)一個(gè)C++單鏈表的文章就介紹到這了,更多相關(guān)C++單鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
下面呢，小編就為大家介紹一下VC中庫函數(shù)qsort()的用法。需要的朋友可以過來參考下2013-09-09
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)彈跳小球項(xiàng)目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
C語言用棧實(shí)現(xiàn)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的方法示例
這篇文章主要介紹了C語言用棧實(shí)現(xiàn)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的方法,結(jié)合實(shí)例形式分析了C語言棧的定義及進(jìn)制轉(zhuǎn)換使用技巧,需要的朋友可以參考下2017-06-06
C++ abs函數(shù)實(shí)際應(yīng)用詳解
本文我們來講C++的abs函數(shù)以及實(shí)戰(zhàn)運(yùn)用，C++中的abs函數(shù)。在C++中使用abs函數(shù)要注意存在兩種版本，一種是在stdlmb.h中定義的版本，另一個(gè)是在cmath頭文件中定義的。夷實(shí)上在stdlib.h文件是C的函數(shù),而cmath中的是C++版本2022-08-08
這篇文章主要給大家介紹了關(guān)于C++對(duì)象大小的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
以下是對(duì)snprintf函數(shù)的具體使用方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-07-07
C++深入分析講解函數(shù)與重載知識(shí)點(diǎn)
C++?允許多個(gè)函數(shù)擁有相同的名字，只要它們的參數(shù)列表不同就可以，這就是函數(shù)的重載（Function?Overloading），借助重載，一個(gè)函數(shù)名可以有多種用途2022-06-06
這篇文章主要給大家介紹了關(guān)于c++中引用作為形參的使用方法以及作用的相關(guān)資料,引用是地址傳值,作為引用的形參數(shù)值被修改的同時(shí),也修改了對(duì)應(yīng)實(shí)參的值,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-11-11
這篇文章主要介紹了 C++ 類的繼承與派生實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06
C語言實(shí)現(xiàn)手寫字符串處理工具的示例代碼
這篇文章主要為大家詳細(xì)介紹了利用C語言實(shí)現(xiàn)手寫字符串處理工具的相關(guān)資料，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，需要的可以參考一下2022-09-09