網站首頁 編程語言 正文
鏈表分類
鏈表主要有下面三種分類方法：
- 單向或者雙向
- 帶頭或者不帶頭
- 循環或者非循環綜合來看鏈表有八種類型，本文主要針對的是不帶頭節點的非循環單鏈表。
單鏈表的介紹
typedef struct SListNode
{
DataType data;//數據域
struct SListNode *next;//結構體指針，指向下一個節點
}SListNode;//類型別名
如圖
鏈表的每一個節點由數據域和指針域構成，數據域存放數據，指針域中的指針指向下一個節點。
plist表示鏈表的指針，指向鏈表的第一個節點，最后一個節點的指針為空。
單鏈表的基本操作
創建
創建單鏈表有幾點需注意：
- 鏈表與順序表的區別是，順序表是物理空間上連續的，而鏈表只在邏輯上連續，所以鏈表申請空間時是使用一個申請一個，順序表則是一次申請一段空間，空間不足時進行擴容。
- 如果在棧上申請空間，在函數調用結束后會釋放，所以需要在堆區申請空間。
- 每次申請一個節點都要存入數據，所以鏈表總是滿的，而順序表則可能有一段空間沒有利用。
- 函數的返回值是指向節點的結構體類型的指針
SListNode* BuySListNode(DataType x)
{
SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
if (plist == NULL)
{
return NULL;//判斷是否申請成功
}
plist->data = x;
plist->next = NULL;
return plist;
}
打印
遍歷鏈表，進行打印
void SListPrint(SListNode* plist)
{
assert(plist);
SListNode* cur = plist;
while (cur)
{
printf("%d-->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
尾插
尾插的操作步驟：
- 若鏈表為空，*pplist指向新插入的節點
- 鏈表不為空則遍歷鏈表，找到最后一個節點
- 令最后一個節點的next指向新插入的節點
- 新插入的節點next指向NULL
注意事項：
- 因為插入元素要改變原鏈表中指針的指向，故傳參時要傳入二級指針。
- assert(pplist)是判斷鏈表是否存在，因為pplist是指向鏈表的指針的地址，若pplist為空，說明鏈表的地址不存在，即鏈表不存在；而如果(*pplist)為空，表示的是該鏈表是空鏈表。
void SListPushBack(SListNode** pplist, DataType x)
{
//改變指針指向，參數傳二級指針
assert(pplist);//判斷鏈表是否存在,與鏈表是否為空不同
//1.若鏈表為空，*pplist指向插入的節點
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
else {
//2.鏈表不為空，指針移動到鏈表最后一個節點，其next指向插入的節點
SListNode* cur = *pplist;
while (cur->next)
{
cur = cur->next;//cur的next為空時，cur指向最后一個節點
}
cur->next = BuySListNode(x);
}
}
頭插
頭插操作順序：
- 申請一個新節點
- 新節點的next指向原來的第一個節點，即*pplist
- 改變*pplist指向，使其指向新增的節點
進行頭插時，要注意各個步驟的順序，如果直接令*pplist指向了新增的的節點，會導致原有的第一個節點無法找；另外，鏈表為空時的操作方法與鏈表非空時代碼可以合并，不用再分開寫各種情況。
void SListPushFront(SListNode** pplist, DataType x)
{
assert(pplist);
//if (NULL == *pplist)
//{
// //鏈表為空
// *pplist = BuySListNode(x);
//}
//else
//{
// SListNode* temp = *pplist;//temp指向鏈表原來的第一個節點
// *pplist = BuySListNode(x);//plist指向新增的節點
// (*pplist)->next = temp;//新增的節點指向原來的第一個節點
//}
//上面兩種情況代碼可以合并
SListNode* node = BuySListNode(x);//申請一個新節點
node->next = *pplist;//新增的節點的next指向原來的第一個節點
*pplist = node;//*pplist指向新增的節點
}
尾刪
尾刪步驟：
- 判斷鏈表是否為空或只有一個結點
- 遍歷找到最后一個節點的前驅結點prev
- 令prev的next指向NULL
- 釋放原來最后一個節點申請的空間
注意事項：
- 區分鏈表為空、單個結點、多個結點各種情況
- 不能找到最后一個節點并將其置空，而是要找到其前驅節點，斷開與最后一個節點的連接
- 刪除節點后要釋放空間，避免內存泄漏
void SListPopBack(SListNode** pplist)
{
assert(pplist);
//1.鏈表為空
if (NULL== *pplist)
{
return;
}
//2.鏈表只有一個元素
else if (NULL == (*pplist)->next)
{
free(*pplist);
*pplist = NULL;
}
//3.鏈表有多個元素
else
{
SListNode* prev = NULL;
SListNode* cur = *pplist;
while (cur->next)
{
prev = cur;
cur = cur->next;//循環結束時cur指向最后一個節點
}
//cur= NULL;//這里不能寫cur=NULL,需要找到cur的前一個節點，將其next置空\
否則前一個結點的next依然指向原來的最后一個節點
prev->next = NULL;//prev成為最后一個節點
free(cur);//釋放原來最后一個節點的空間
}
頭刪
頭刪的操作步驟：
- 保存第一個節點的指針信息
- 令*pplist指向第二個節點
- 釋放原來的第一個節點的空間
同樣的，頭刪也要注意保存原來第一個節點的位置，否則*pplist指向改變后，原來的第一個節點就找不到了，會無法釋放空間造成內存泄漏。
void SListPopFront(SListNode** pplist)
{
assert(pplist);
//1.單鏈表為空
if (NULL == *pplist)
{
return;
}
2.單鏈表有一個節點
//else if (NULL == (*pplist)->next)
//{
// *pplist = NULL;//刪除后鏈表為空
//}
3.單鏈表有多個節點
//else
//{
//*pplist= (*pplist)->next;
//}
//兩種情況可以合并，只有一個節點時，*pplist的next為空
else
{
SListNode* delNode = *pplist;
*pplist = delNode->next;
free(delNode);//釋放刪除節點的空間
}
}
查找
用于查找某一元素是否存在于鏈表中，若存在則返回其第一次出現在鏈表中的位置，不存在則返回NULL。
遍歷時注意循環條件。
SListNode* SListFind(SListNode* plist, DataType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
任意位置插入
pos節點后插入的步驟：
- 申請一個新的節點
- 新增節點的next指向原pos的next
- pos的next指向新增的節點
注意事項
- 任意位置的插入操作只能在給定節點的后面插入，前面的節點無法同通過給出的節點找到。
- 要注意插入的操作順序，否則原來鏈表pos后的節點可能會找不到
void SListInsertAfter(SListNode* pos, DataType x)
{
assert(pos);//指針合法性校驗
SListNode* newNode = BuySListNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
任意位置刪除
與任意位置的插入相同，只能刪除給定節點pos后面的節點
void SListDeleteAfter(SListNode* pos)
{
assert(pos);
//1.鏈表有一個節點
if (NULL == pos->next)
{
return;
}
//2.鏈表有多個節點
else
{
SListNode* temp = pos->next;
pos->next = temp->next;
free(temp);
}
}
銷毀
鏈表的銷毀，遍歷一遍，逐個釋放空間
void SListDestroy(SListNode** pplist)
{
assert(pplist);//鏈表是否存在
//1.鏈表為空
if (NULL == *pplist)
{
return;
}
else
{
SListNode* cur = NULL;
while (*pplist)
{
cur = *pplist;
*pplist = (*pplist)->next;
free(cur);
}
}
}
完整代碼
work.h
頭文件包含，函數聲明，定義結構體
#pragma once
#include<stdio.h>
#include<Windows.h>
#include<assert.h>
#include<assert.h>
typedef int DataType;
typedef struct SListNode
{
DataType data;//數據域
struct SListNode *next;//結構體指針，指向下一個節點
}SListNode;//類型別名
//函數聲明
SListNode* BuySListNode(DataType x);//節點申請
void SListPrint(SListNode* pst);//單鏈表遍歷打印
void SListPushBack(SListNode** pplist, DataType x);//單鏈表尾插
void SListPushFront(SListNode** pplist, DataType x);//單鏈表頭插
void SListPopBack(SListNode** pplist);//單鏈表尾刪
void SListPopFront(SListNode** pplist);//單鏈表頭刪
SListNode* SListFind(SListNode* plist, DataType x);//單鏈表查找
void SListInsertAfter(SListNode* pos, DataType x);//pos后位置的插入
void SListDeleteAfter(SListNode* pos);//pos后位置的刪除
void SListDestroy(SListNode** pplist);//釋放鏈表空間
work.c
各操作函數的具體實現
#include"work.h"
//鏈表與順序表的區別是，順序表是物理空間上連續的
//而鏈表只在邏輯上連續，所以鏈表申請空間時是使用一個申請一個
//順序表則是一次申請一段空間
SListNode* BuySListNode(DataType x)
{
//若在棧申請內存函數調用結束后會釋放，所以使用動態申請
SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
if (plist == NULL)
{
return NULL;//判斷是否申請成功
}
plist->data = x;
plist->next = NULL;
return plist;
}
void SListPrint(SListNode* plist)
{
assert(plist);
SListNode* cur = plist;
while (cur)
{
printf("%d-->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//尾插法
void SListPushBack(SListNode** pplist, DataType x)
{
//改變指針指向，參數傳二級指針
assert(pplist);//判斷鏈表是否存在,與鏈表是否為空不同
//1.若鏈表為空，*pplist指向插入的節點
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
else {
//2.鏈表不為空，指針移動到鏈表最后一個節點，其next指向插入的節點
SListNode* cur = *pplist;
while (cur->next)
{
cur = cur->next;//cur的next為空時，cur指向最后一個節點
}
cur->next = BuySListNode(x);
}
}
//頭插法
void SListPushFront(SListNode** pplist, DataType x)
{
assert(pplist);
//if (NULL == *pplist)
//{
// //鏈表為空
// *pplist = BuySListNode(x);
//}
//else
//{
// SListNode* temp = *pplist;//temp指向鏈表原來的第一個節點
// *pplist = BuySListNode(x);//plist指向新增的節點
// (*pplist)->next = temp;//新增的節點指向原來的第一個節點
//}
//鏈表為空的情況可以和不為空合并
SListNode* node = BuySListNode(x);//申請一個新節點
node->next = *pplist;//新增的節點的next指向原來的第一個節點
*pplist = node;//*pplist指向新增的節點
}
//尾刪法？
void SListPopBack(SListNode** pplist)
{
assert(pplist);
//1.鏈表為空
if (NULL== *pplist)
{
return;
}
//2.鏈表只有一個元素
else if (NULL == (*pplist)->next)
{
free(*pplist);
*pplist = NULL;
}
//3.鏈表有多個元素
else
{
SListNode* prev = NULL;
SListNode* cur = *pplist;
while (cur->next)
{
prev = cur;
cur = cur->next;//循環結束時cur指向最后一個節點
}
//cur= NULL;//這里不能寫cur=NULL,需要找到cur的前一個節點，將其next置空\
否則前一個結點的next依然指向原來的最后一個節點
prev->next = NULL;//prev最后一個節點
free(cur);//釋放原來最后一個節點的空間
}
}
//頭刪
void SListPopFront(SListNode** pplist)
{
assert(pplist);
//1.單鏈表為空
if (NULL == *pplist)
{
return;
}
2.單鏈表有一個節點
//else if (NULL == (*pplist)->next)
//{
// *pplist = NULL;//刪除后鏈表為空
//}
3.單鏈表有多個節點
//else
//{
//*pplist= (*pplist)->next;
//}
//兩種情況可以合并，只有一個節點時，*pplist的next為空
else
{
SListNode* delNode = *pplist;
*pplist = delNode->next;
free(delNode);//釋放刪除節點的空間
}
}
//單鏈表查找
SListNode* SListFind(SListNode* plist, DataType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
//任意位置的插入
//只能在pos的后面插入
void SListInsertAfter(SListNode* pos, DataType x)
{
assert(pos);//指針合法性校驗
SListNode* newNode = BuySListNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
//任意位置的刪除
//只能刪除給定的pos后面的節點
void SListDeleteAfter(SListNode* pos)
{
assert(pos);
//1.鏈表有一個節點
if (NULL == pos->next)
{
return;
}
//2.鏈表有多個節點
else
{
SListNode* temp = pos->next;
pos->next = temp->next;
free(temp);
}
}
// 鏈表空間釋放
void SListDestroy(SListNode** pplist)
{
assert(pplist);//鏈表是否存在
//1.鏈表為空
if (NULL == *pplist)
{
return;
}
else
{
SListNode* cur = NULL;
while (*pplist)
{
cur = *pplist;
*pplist = (*pplist)->next;
free(cur);
}
}
}
main.c
程序入口，測試用例
#include"work.h"
void Test()
{
SListNode* node = NULL;//定義一個結構體指針
//尾插法插入五個節點
SListPushBack(&node, 1);
SListPushBack(&node, 2);
SListPushBack(&node, 3);
SListPushBack(&node, 4);
SListPushBack(&node, 5);
SListPrint(node);//遍歷打印
SListPushFront(&node, 0);//頭插一個節點
SListPrint(node);//遍歷打印
SListPopBack(&node);//尾刪最后一個節點
SListPrint(node);//遍歷打印
SListPopFront(&node);//頭刪第一個節點
SListPrint(node);//遍歷打印
printf("%p\n", SListFind(node, 4));//查找3在鏈表中的位置
printf("%p\n", SListFind(node, 99));//查找99在鏈表中的位置
SListInsertAfter(SListFind(node, 4), 99);//4后面插入一個節點99
SListPrint(node);//遍歷打印
SListDeleteAfter(SListFind(node, 4));//刪除4的下一個節點
SListPrint(node);//遍歷打印
}
int main()
{
Test();
system("pause");
return 0;
}
總結
原文鏈接：https://blog.csdn.net/qq_44631587/article/details/122281347
相關推薦
- 2022-12-23 Kubernetes存儲系統數據持久化管理詳解_云其它
- 2022-09-09 使用Dockerfile腳本定制鏡像的方法_docker
- 2022-06-22 為Visual?Studio2019添加Git組件_實用技巧
- 2022-11-04 golang?cache帶索引超時緩存庫實戰示例_Golang
- 2022-07-27 C++詳細講解圖論的基礎與圖的儲存_C 語言
- 2022-06-22 使用Git向GitHub上傳更新內容_其它綜合
- 2022-10-16 Python?numpy生成矩陣基礎用法實例代碼_python
- 2021-12-02 Centos8搭建配置nis域服務詳細步驟_Linux
- 最近更新
-
- 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加速