網站首頁 編程語言 正文
1 鏈表的概念及結構
概念：鏈表是一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈 接次序實現的 。
注意：
1. 從上圖可以看出，鏈式結構在邏輯上是連續的，但是在物理上不一定是連續
2. 現實中的節點一般是從堆上申請出來的
3. 從對上申請的空間，是按照一定的策略來分配的，兩次申請的空間可能連續，也可能不連續
2 鏈表的分類
實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：
1、單向或者雙向鏈表
2、帶頭或者不帶頭鏈表
3、循環或非循環鏈表
最常用的有兩種：無頭單向非循環鏈表、帶頭雙向循環鏈表
- 無頭單向非循環鏈表：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結 構，如哈希桶、圖的鄰接表等等。另外這種結構在筆試面試中出現很多。
- 帶頭雙向循環鏈表：結構最復雜，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向 循環鏈表。另外這個結構雖然結構復雜，但是使用代碼實現以后會發現結構會帶來很多優勢，實現反而簡單了，后面我們代碼實現了就知道了。
3 鏈表的實現無頭+單向+非循環鏈表增刪查改實現
3.1 鏈表的定義
typedef int SLTDataType;//
typedef struct SListNode
{
int data;//val，存儲的數據，此處假設存儲的數據為int型
struct SListNode* next;//存儲下一個節點的位置
}SListNode,SLN;3.2 鏈表數據的打印
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}3.3 鏈表的尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}在找尾的過程中，務必不能寫成下面的代碼：
while(tail!=NULL)
{
tail = tail->next;
}
tail->next = newnode;
當然，上面的介紹的是尾刪的情況。
尾插其實也是類似的，尾插的話像上面的代碼中，當tail!=NULL不成立之后，tail等于空，然后執行賦值操作，tail->next = newnode這行代碼相當于下面的代碼：
(*tail).next，此處相當于是對空指針進行解引用，其實就是非法訪問了，并還試圖非法修改未授權內存中的數據，這將必然會引發程序的崩潰。而且也并沒有將新節點的地址存儲到之前為節點的next中。
這個地方需要弄明白鏈表進行遍歷的根本原理：
鏈表是一個相對靜態的存儲在堆區中的數據空間，我們通過改變棧區中的局部變量tail中的數據（即每一個鏈表節點的地址）來進行遍歷，之所以能夠通過tail變量能夠進行訪問并且修改節點數據的原因就是因為tail的數據類型是SListNode*，即指向節點的指針，指針的類型決定了對指針解引用能夠訪問的數據類型，所以*tail能夠訪問堆區中的節點的數據并且能夠進行修改。
3.4 鏈表空間的動態申請
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
return newnode;
}3.5 鏈表的頭插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}3.6 鏈表的尾刪
需要考慮三種情況：
- 空
- 一個節點
- 多個節點
兩種寫法：
第一種：
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//空鏈表
{
return;
}
else if ((*pphead)->next == NULL)//一個節點
{
free(*pphead);//*pphead就是plist的值
*pphead = NULL;
}
else//多個節點
{
SListNode* tail = *pphead;
SListNode* prev = NULL;//為什么要置為空呢？因為這個地方相當于是指向第一個節點之前的節點，這個節點并不存在，設為空
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
這種方式在面對只有一個節點時也不會出現問題。
第二種：
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//空鏈表
{
return;
}
else if ((*pphead)->next == NULL)//一個節點
{
free(*pphead);//*pphead就是plist的值
*pphead = NULL;
}
else//多個節點
{
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);//釋放尾節點
tail->next = NULL;//將新尾節點的next置為NULL
}
}
3.7 鏈表的頭刪
void SListPopFront(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//空鏈表
{
return;
}
else//非空鏈表
{
SListNode* next = (*pphead)->next;//next作為臨時變量存放的是被刪除的節點中next存儲的第二個節點的地址
free(*pphead);
*pphead = next;
}
}
3.8 鏈表任意位置的前插入
void SListInsertBefore(SListNode** pphead, SListNode* pos,SLTDataType x)
{
assert(pphead);
if (*pphead == pos)//pos是第一個節點，相當于頭插
{
SListPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
3.9 鏈表任意位置的后插入
兩種實現方式：
方式一：
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
//這兩行代碼順序是固定的，只能這個順序，無法進行改變
}圖示：
方式二：
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* next = pos->next;
SListNode* newnode = BuySListNode(x);
newnode->next = next;
pos->next = newnode;
//這兩行代碼可以任意改變順序，誰先誰后都不影響最后的結果
}圖示：
3.10?鏈表的任意位置的刪除
void SListErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)//當pos為頭節點的時候
{
SListPopFront(pphead);
}
else//當pos為非頭節點的時候
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}圖示：
3.11?鏈表的任意位置的前刪除
void SListEraseBefore(SListNode** pphead, SListNode* pos)//pos即為任意位置
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
return;
}
else if(pos==(*pphead)->next)
{
SListPopFront(pphead);
}
else
{
SListNode* prev = *pphead;//prev用來存儲pos的前一個位置的前一個位置
while (prev->next->next != pos)
{
prev = prev->next;
}
SListNode* next = prev->next;//保存pos前一個節點的地址
prev->next = prev->next->next;//將prev和pos的兩個節點進行連接
free(next);//刪除pos的前一個節點
}
}
3.12?鏈表的任意位置的后刪除
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* next = pos->next;
if (next == NULL)//當pos是最后一個節點的時候
{
return;
}
else
{
pos->next = next->next;
free(next);
next = NULL;
}
}圖示：
3.13?鏈表的銷毀
void SListDestory(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
SListNode* next = *pphead;//是為了存儲cur下一個節點的地址，因為free(cur)之后，cur指針指向的內存中的數據可能已經稱為亂碼了，即不能再正常的使用
while (cur)
{
next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}3.14?鏈表的總結
總結：單鏈表結構，適合頭插頭刪。尾部或者中間某個位置插入刪除都不適合。如果要使用鏈表結構單獨存儲數據，更適合用雙向鏈表。
單鏈表學習的意義：
- 單鏈表會作為我們以后學習復雜數據結構的子結構（圖的鄰接表、哈希桶）
- 單鏈表會有很多經典的練習題，在筆試面試中會有很多相關的題目。
原文鏈接：https://blog.csdn.net/m0_57304511/article/details/123549365
相關推薦
- 2023-07-07 更新node后項目報錯
- 2022-12-27 Golang中int,?int8,?int16,?int32,?int64和uint區別淺析_Gol
- 2022-03-28 C語言實現紅黑樹詳細步驟+代碼_C 語言
- 2022-10-10 python中sort()函數用法詳解_python
- 2023-01-14 詳解Go語言如何進行Http調用_Golang
- 2022-07-15 C語言函數棧幀的創建與銷毀原理圖解_C 語言
- 2022-04-28 C/C++的關鍵字之static你了解嗎_C 語言
- 2021-12-08 c語言單詞本的新增、刪除、查詢按順序顯示功能_C 語言
- 最近更新
-
- 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加速