網站首頁 編程語言 正文
一. 節點聲明
鏈表是一種數據結構，用于數據的存儲。
如圖，每一個鏈表節點所在的內存空間是不延續的，因為不是連續存儲，所以需要存入下一個節點的地址，這樣方便找到下一個數值，而最后一個鏈表指向的空間為NULL，因此我們可以聲明一個結構體，代表一個節點。
typedef int ListDataType;
typedef struct SListNode
{
ListDataType data;
struct SListNode* Next;
}SLNode;
SListNode 是我們的節點結構體，ListDataType是存儲數據的類型。
二. 尾插
鏈表的節點建立好后，接下來我們來進行尾部插入數據。
那么我們只需要找到尾部節點，把尾部節點指向的NULL值置為新節點。新節點指向NULL
因此我們要新建一個節點，然后找到最后一個節點。
void SListPushBack(SLNode** phead, ListDataType x)
{
//新開辟一個節點
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (newNode == NULL)
{
//空間開辟失敗
printf("SListPushBack::newNode");
exit(-1);
}
//找到最后一個節點
SLNode* cru = *phead;
//如果cru指向NULL，說明cru是最后一個節點
while (cru->Next != NULL)
{
cru = cru->Next;
}
//cru 指向新節點
cru->Next = newNode;
//新節點指向NULL，存儲數據x
newNode->data = x;
newNode->Next = NULL;
}
但是這種方法，我們需要注意一種情況，那就是如果鏈表中本身沒有節點，那么cru初始就是一個空指針，而循環條件我們對空指針進行了解引用，所以我們需要判斷一下。
//尾部數據插入
void SListPushBack(SLNode** phead, ListDataType x)
{
//新開辟一個節點
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (newNode == NULL)
{
//空間開辟失敗
printf("SListPushBack::newNode");
exit(-1);
}
//新節點指向NULL，存儲數據x
newNode->data = x;
newNode->Next = NULL;
if (*phead == NULL)
{
//當前鏈表為空，那么我直接讓新節點替代phead
*phead = newNode;
return;
}
//找到最后一個節點
SLNode* cru = *phead;
//如果cru指向NULL，說明cru是最后一個節點
while (cru->Next != NULL)
{
cru = cru->Next;
}
//cru 指向新節點
cru->Next = newNode;
}
然后我們測試一下，發現鏈表已經鏈接起來了
三. 鏈表打印
為了方便后面測試，我們決定先實現打印鏈表的函數。我們只需要依次查找節點指向的元素，直到最后一個指向NULL時，我們停下來。
//鏈表打印
void SListPrint(SLNode* head)
{
SLNode* cru = head;
while (cru)
{
printf("%d->",cru->data);
cru = cru->Next;
}
printf("NULL\n");
}
四. 頭插
頭部插入和尾部插入差不多，我們只需要把新節點指向鏈表中的第一個節點，然后把頭節點換成新節點。
因為我們尾插的時候創建了節點，頭插又創建節點，太麻煩了，所以我們把創建節點封裝成一個函數。
//創建節點
SLNode* SListCreateNode(ListDataType x)
{
//新開辟一個節點
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (newNode == NULL)
{
//空間開辟失敗
printf("SListPushBack::newNode");
exit(-1);
}
//新節點指向NULL，存儲數據x
newNode->data = x;
newNode->Next = NULL;
return newNode;
}
尾插函數調整
//尾部數據插入
void SListPushBack(SLNode** phead, ListDataType x)
{
SLNode* newNode = SListCreateNode(x);
if (*phead == NULL)
{
//當前鏈表為空，那么我直接讓新節點替代phead
*phead = newNode;
return;
}
//找到最后一個節點
SLNode* cru = *phead;
//如果cru指向NULL，說明cru是最后一個節點
while (cru->Next != NULL)
{
cru = cru->Next;
}
//cru 指向新節點
cru->Next = newNode;
}
頭插函數
//頭部數據插入
void SListPushFront(SLNode** phead, ListDataType x)
{
//新建節點
SLNode* newNode = SListCreateNode(x);
//讓節點指向頭
newNode->Next = *phead;
//頭節點更替為新節點
*phead = newNode;
}
頭插測試
五. 尾刪
尾刪也就是刪除鏈表中的最后一個節點。那么我們需要找到最后一個節點，把它釋放，并且要把它的前一個節點置為空指針，否則它會變成一個野指針。
//尾部數據刪除
void SListPopBack(SLNode** phead)
{
SLNode* cru = *phead; //最后一個節點
SLNode* prve = NULL; //前一個節點
//最后一個節點指向空
while (cru->Next)
{
prve = cru;
cru = cru->Next;
}
//cru 為最后一個節點。釋放掉
free(cru);
//前一個節點指向空
prve->Next = NULL;
}
但是這個尾刪是建立在有數據的情況下的，如果沒有數據我們進行此操作，那會造成空指針prve訪問，所以我們在前面要斷言一下
void SListPopBack(SLNode** phead)
{
//鏈表為空無法刪除
assert(*phead);
SLNode* cru = *phead; //最后一個節點
SLNode* prve = NULL; //前一個節點
//最后一個節點指向空
while (cru->Next)
{
prve = cru;
cru = cru->Next;
}
//cru 為最后一個節點。釋放掉
free(cru);
//前一個節點指向空
prve->Next = NULL;
}
即使這樣，以上代碼依然有問題，因為當鏈表只有一個節點時，并不會進入while循環，也就導致 prve對空指針解引用，所以我們還需要判斷一下，如果鏈表只有一個節點，那么就直接釋放頭節點。
//尾部數據刪除
void SListPopBack(SLNode** phead)
{
//鏈表為空無法刪除
assert(*phead);
//只有一個節點時
if((*phead)->Next == NULL)
{
//釋放頭空間
free(*phead);
//置為空指針
*phead = NULL;
return;
}
SLNode* cru = *phead; //最后一個節點
SLNode* prve = NULL; //前一個節點
//找到最后一個節點
while (cru->Next)
{
prve = cru;
cru = cru->Next;
}
//cru 為最后一個節點。釋放掉
free(cru);
//前一個節點指向空
prve->Next = NULL;
}
代碼測試
六. 頭刪
尾刪都會了，頭刪還遠嗎？頭刪我們只需要把頭節點指向的空間釋放，然后讓頭節點的指針指向下一個節點。
當然，如果鏈表為空，我們是無法操作的，我們也要斷言或者if判斷一下。
//頭部數據刪除
void SListPopFront(SLNode** phead)
{
//斷言
assert(*phead);
//鏈表不為空，存儲下一個位置的地址
SLNode* NextNode = (*phead)->Next;
//釋放 *phead
free(*phead);
//存儲的節點給*phead
*phead = NextNode;
}
測試一下代碼
七. 查找值
在鏈表里查找值，我們只需要找節點，如果與找的值相等，就返回當前下標或者節點，這里我們用返回節點演示。
SLNode* SListFindNode(SLNode* head, ListDataType x)
{
SLNode* cru = head;
//查找值
while (cru)
{
//如果當前節點等于要查找的值
if (cru->data == x)
{
//返回當前節點，也可以返回下標，把函數返回值改成int
return cru;
}
//下一個節點
cru = cru->Next;
}
//遍歷完沒有找到， 返回空指針
return NULL;
}
看看測試結果
鏈表里我們插入了三個值，1，2，3。然后找1的值并返回當前節點，最終提示我們找到了。
當然，也可以用返回下標的方式，然后利用下標控制查找次數。
八.指定插入
指定插入，我們這里來演示前插，也就是在一個節點的前面進行插入，我們只需要把這個節點前面的節點指向新節點，然后新節點指向這個節點。
所以我們要先創建一個節點，讓被插入節點之前的節點指向該節點，讓新節點指向被插入的節點。
//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
//首先插入之前，我們必須保證被插入的pos節點存在，不然無法插入
assert(pos);
SLNode* cru = *phead; //用來查找被插入的節點
//查找pos節點
while (cru->Next != pos)
{
cru = cru->Next;
}
//找到后，創建一個新節點
SLNode* newNode = SListCreateNode(x);
//新節點指向pos
newNode->Next = pos;
//pos的前一個節點指向cru
cru->Next = newNode;
}
此時這個代碼仍有問題，因為如果 pos是第一個節點時，cru->next無法判斷判斷第一個節點，所以我們要加個判斷，如果是頭節點，直接調用頭插函數。
//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
//首先插入之前，我們必須保證被插入的pos節點存在，不然無法插入
assert(pos);
//頭節點就是pos
if (*phead == pos)
{
//調用頭插
SListPushFront(phead,x);
return 0;
}
SLNode* cru = *phead; //用來查找被插入的節點
//查找pos節點
while (cru->Next != pos)
{
cru = cru->Next;
}
//找到后，創建一個新節點
SLNode* newNode = SListCreateNode(x);
//新節點指向pos
newNode->Next = pos;
//pos的前一個節點指向cru
cru->Next = newNode;
}
代碼測試
九.指定刪除
指定刪除和指定插入差不多，我們只需要把被刪除節點的前一個節點，指向后一個節點，然后刪除節點。如果要刪除的是頭節點，直接調用頭刪函數，或者也可以再次寫一個頭刪。
//指定節點刪除
void SListEase(SLNode** phead, SLNode* pos)
{
//pos是空指針，干掉程序
assert(pos);
//如果頭節點與pos相等，直接調用頭刪
if (*phead == pos)
{
SListPopFront(phead);
return;
}
//創建一個節點
SLNode* cru = *phead; //查找被刪除節點的前一個節點
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)
{
//存儲下一個節點的地址
cru = (*phead)->Next;+
//當前地址置空
*phead = NULL;
//釋放當前空間
free(*phead);
//換成下一個節點繼續
*phead = cru;
}
}然后我們測試一下，發現所有的節點都置空了
以上代碼以上傳至git，點這里獲取
原文鏈接：https://blog.csdn.net/a778129656/article/details/128077075
相關推薦
- 2022-07-20 SQL?Server中搜索特定的對象_MsSql
- 2022-02-27 解決No converter for XXX with preset Content-Type ‘a
- 2022-09-15 docker倉庫登錄及配置insecure-registries的方法_docker
- 2022-05-07 Python中list列表的賦值方法及遇到問題處理_python
- 2023-02-27 python定時任務timeloop庫用法實例詳解_python
- 2022-06-02 Z-Order加速Hudi大規模數據集方案分析_服務器其它
- 2022-11-21 Android?Jetpack系列之App?Startup使用詳解_Android
- 2022-12-01 Git基礎學習之分支操作的示例詳解_相關技巧
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速