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