網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
1.鏈表概況
1.1 鏈表的概念及結(jié)構(gòu)
概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
1.2 鏈表的分類
實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu)
單向或者雙向
帶頭或者不帶頭
循環(huán)或者非循環(huán)
雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)
- 無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
- 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單了，后面我們代碼實(shí)現(xiàn)了就知道了
2. 單向鏈表的實(shí)現(xiàn)
單向鏈表結(jié)構(gòu)
2.1 SList.h（頭文件的匯總，函數(shù)的聲明）
#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
int data;//數(shù)據(jù)
struct SListNode* next;//下一個(gè)節(jié)點(diǎn)的地址
}SListNode;
void SListPrint(SListNode* phead);//打印
SListNode* BuySListNode(SLTDataType x);//搞出一個(gè)新節(jié)點(diǎn)
void SListPushBack(SListNode** pphead, SLTDataType x);//尾插
void SListPushFront(SListNode** pphead, SLTDataType x);//頭插
void SListPopBack(SListNode** pphead);//尾刪
void SListPopFront(SListNode** pphead);//頭刪
SListNode* SListFind(SListNode* phead, SLTDataType x);//查找
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDataType x);//在pos位置之后插入
void SListErase(SListNode** pphead, SListNode* pos);//刪除pos位置
void SListEraseAfter(SListNode* pos);//刪除pos之后位置
void SListDestroy(SListNode** pphead);//銷毀
2.2 SList.c（函數(shù)的具體實(shí)現(xiàn)邏輯）
2.2.1 打印鏈表
//打印
void SListPrint(SListNode* phead)
{
//assert(phead);//沒必要斷言，空鏈表也能打印
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//test.c
void TestSList1()
{
SListNode* slist;//結(jié)構(gòu)體指針，用于存節(jié)點(diǎn)的地址
SListNode* n1 = (SListNode *)malloc(sizeof(SListNode));
SListNode* n2 = (SListNode*)malloc(sizeof(SListNode));
SListNode* n3 = (SListNode*)malloc(sizeof(SListNode));
n1->data = 1;
n2->data = 2;
n3->data = 3;
n1->next = n2;
n2->next = n3;
n3->next = NULL;
slist = n1;
SListPrint(slist);
}
2.2.2 搞出一個(gè)新節(jié)點(diǎn)（為其他函數(shù)服務(wù)）
//搞出一個(gè)新節(jié)點(diǎn)
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;
}
2.2.3 鏈表尾插
//尾插
void SListPushBack(SListNode** pphead,SLTDataType x)//會(huì)改變實(shí)參slist，要傳二級(jí)指針
{
assert(pphead);//就算鏈表是空，它的二級(jí)指針也不為空
SListNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//遍歷找尾
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void TestSList2()
{
SListNode* slist = NULL;
for (int i = 0; i < 6; i++)
{
SListPushBack(&slist,i);
}
SListPrint(slist);
}
2.2.4 鏈表頭插
//頭插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);//就算鏈表是空，它的二級(jí)指針也不為空
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void TestSList2()
{
SListNode* slist = NULL;
for (int i = 0; i < 6; i++)
{
SListPushFront(&slist,i);
}
SListPrint(slist);
}
2.2.5 鏈表尾刪
方法1（用兩個(gè)指針，分別找最后一個(gè)和倒數(shù)第二個(gè)）：
方法2（直接找倒數(shù)第二個(gè)）：
//尾刪
void SListPopBack(SListNode** pphead)//如果只有一個(gè)節(jié)點(diǎn)但還要尾刪，就會(huì)改變實(shí)參slist，建議傳二級(jí)指針
{
assert(pphead);//就算鏈表是空，它的二級(jí)指針也不為空
//三種情況：
//1.空
//2.一個(gè)節(jié)點(diǎn)
//3.多個(gè)節(jié)點(diǎn)
if (*pphead == NULL)
{
return;
}
else if ((*pphead)->next == NULL)//優(yōu)先級(jí)，記得加括號(hào)
{
free(*pphead);
*pphead = NULL;
}
//第一種寫法（用兩個(gè)指針，分別找最后一個(gè)和倒數(shù)第二個(gè)）
else
{
SListNode* prev = NULL;//找倒數(shù)第二個(gè)元素，用于將它指向NULL
SListNode* tail = *pphead;//找尾
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;//習(xí)慣性free掉就將其置空
prev->next = NULL;
}
//方法二（直接找倒數(shù)第二個(gè)）
//else
//{
//SListNode* tail = *pphead;//找尾
//while (tail->next->next != NULL)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
//}
}
2.2.6 鏈表頭刪
//頭刪
void SListPopFront(SListNode** pphead)
{
assert(pphead);
//1.空
//2.非空
if (*pphead == NULL)
{
return;
}
else
{
SListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}
2.2.7 查找節(jié)點(diǎn)
//查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
SListNode* cur = phead;
while (phead != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
2.2.8 在pos位置之前插入
//在pos位置之前插入（一般跟find配合使用）
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);//間接檢測(cè)鏈表是否為空，因?yàn)榭真湵碚也坏絧os
//1.pos是第一個(gè)節(jié)點(diǎn)（頭插）
//2.pos不是第一個(gè)節(jié)點(diǎn)
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
2.2.9 在pos位置之后插入
方法1：兩個(gè)指針，先連接pos和newnode還是先連接newnode和next都行
方法2：只有一個(gè)指針，一定要先通過pos連接newnode和下一個(gè)，再連接pos和newnode，否則會(huì)找不到下一個(gè)的地址。
//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
SListNode* next = pos->next;
newnode->next = next;//順序無(wú)所謂
pos->next = newnode;
//或者不定義next
//newnode->next = pos->next;
//pos->next = newnode;//順序要定好，否則會(huì)找不到
}
2.2.10 刪除pos位置
//刪除pos位置
void SListErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;//好習(xí)慣
}
}
2.2.11 刪除pos之后位置
//刪除pos之后位置
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* next = pos->next;
if (next)//防止pos是最后一個(gè)元素
{
pos->next = next->next;
free(next);
next = NULL;
}
}
2.2.12 鏈表銷毀
一個(gè)個(gè)找，一個(gè)個(gè)銷毀，最終將slist置空。
//銷毀
void SListDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
總結(jié)：?jiǎn)捂湵斫Y(jié)構(gòu)，適合頭插頭刪。尾部或者中間某個(gè)位置插入刪除不適合。如果要使用鏈表單獨(dú)存儲(chǔ)數(shù)據(jù)，那我們之后會(huì)學(xué)的雙向鏈表更合適。單鏈表學(xué)習(xí)的意義：
- 單鏈表會(huì)作為我們之后學(xué)習(xí)復(fù)雜數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)（圖的鄰接表、哈希桶）
- 單鏈表會(huì)出很多經(jīng)典的練習(xí)題。
鏈表系列有很多重點(diǎn)內(nèi)容，我會(huì)花不少時(shí)間來(lái)跟大家講解鏈表，相信大家跟著練習(xí)的話編程嚴(yán)謹(jǐn)性會(huì)大大提升，加油哦！
原文鏈接：https://blog.csdn.net/qq_47882731/article/details/123411413
相關(guān)推薦
- 2022-11-15 Python中class內(nèi)置方法__init__與__new__作用與區(qū)別解析_python
- 2022-12-26 react?Input組件Compositionstart和Compositionend事件_Rea
- 2023-07-27 Android啟動(dòng)優(yōu)化之布局優(yōu)化
- 2022-11-17 一文講解如何獲取k8s容器里運(yùn)行的jar包_云其它
- 2022-07-08 分割python多空格字符串的兩種方法小結(jié)_python
- 2022-11-17 Go語(yǔ)言學(xué)習(xí)教程之指針的示例詳解_Golang
- 2022-08-06 Qt實(shí)現(xiàn)簡(jiǎn)單折線圖表_C 語(yǔ)言
- 2021-11-30 Linux?Autofs自動(dòng)掛載服務(wù)安裝部署教程_Linux
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速