網(wǎng)站首頁 編程語言 正文
前言
對于鏈表來說，不只有單鏈表這一個品種；
鏈表有很多種形態(tài)
按方向分：單向、雙向
按帶不帶頭：帶頭、不帶頭
按循環(huán)：循環(huán)、不循環(huán)
1、單向或則雙向：
2、帶頭或者不帶頭：
3、循環(huán)或者不循環(huán)：
組合排列一下的話，鏈表一共有8種形態(tài)！！！
今天我們就來學(xué)習(xí)一下結(jié)構(gòu)最復(fù)雜的帶頭雙向循環(huán)鏈表！！！；
雖然名字聽上去比較復(fù)雜，但是實現(xiàn)起來比單鏈表（全名：不帶頭、不循環(huán)、單向鏈表）更加簡單，也不需要過多考慮特殊情況；
?
兩種鏈表的比較：（上面是單鏈表，下面是帶頭雙向循環(huán)鏈表）
結(jié)構(gòu)分析
首先鏈表的頭節(jié)點是不存儲有效數(shù)據(jù)的（該節(jié)點被稱為哨兵位），其次我們只需要知道改頭節(jié)點的指針就能找到整個鏈表，并且便于對整個鏈表進(jìn)行維護(hù)；
當(dāng)然既然是雙向的嘛，那節(jié)點一定有個指針域指向前一個節(jié)點，另一個指針域指向后一個節(jié)點；
那么我們的單個節(jié)點的數(shù)據(jù)結(jié)構(gòu)就是：
現(xiàn)在我們定義了一個plist指針用來維護(hù)整個鏈表，根據(jù)上面說的plist就應(yīng)該用來存儲哨兵位的頭節(jié)點的指針，那么如何表示鏈表為NULL的情況？
鏈表為空：
就是:
head->next=head;
head->prev=head;
鏈表的基本操作實現(xiàn)
創(chuàng)建節(jié)點
ListNode* ListCreate(LTDataType x)
{
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (!NewNode)
exit(-1);
NewNode->val = x;
NewNode->prev = NULL;
NewNode->next = NULL;
return NewNode;
}
我們在創(chuàng)建節(jié)點的時候就一起將數(shù)據(jù)域初始化，方標(biāo)后續(xù)操作；
初始化鏈表
void InitDummyHead(ListNode* pHead)
{
assert(pHead);
pHead->prev = pHead;
pHead->next = pHead;
}
鏈表銷毀
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
ListNode* next = NULL;
while (cur!=pHead)
{
next = cur->next;
free(cur);
cur = next;
}
free(cur);
}
實現(xiàn)思路：
打印鏈表
除了哨兵位的節(jié)點存到是無效數(shù)據(jù)不打印外，其他節(jié)點的數(shù)據(jù)都要打印：
// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
while (cur != pHead)
{
ListNode* next = cur->next;
printf("%d->",cur->val);
cur = next;
}
printf("NULL\n");
}
鏈表尾插
該鏈表的尾插，比單鏈表的尾插簡單太多了，不用遍歷找尾：
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* NewNode = ListCreate(x);
ListNode* tail = pHead->prev;
tail->next = NewNode;
NewNode->prev = tail;
pHead->prev = NewNode;
NewNode->next = pHead;
}
鏈表尾刪
由于是循環(huán)的，哨兵位的前一個節(jié)點就是尾節(jié)點，同時尾節(jié)點的前一個節(jié)點我們也不用遍歷，可以很輕松的拿到：
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(!is_Empty(pHead));//判空
ListNode* tail = pHead->prev;
ListNode* prev = tail->prev;
ListNode* next = pHead;
free(tail);
prev->next = next;
next->prev = prev;
}
鏈表頭插
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* prev = pHead;
ListNode* cur = pHead->next;
ListNode* NewNode = ListCreate(x);
prev->next = NewNode;
NewNode->prev = prev;
NewNode->next = cur;
cur->prev = NewNode;
}
鏈表頭刪
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(!is_Empty(pHead));//判空
ListNode* prev = pHead;
ListNode* cur = pHead->next;
ListNode* next = cur->next;
free(cur);
prev->next = next;
next->prev = prev;
}
鏈表查找
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
assert(!is_Empty(pHead));//表都為NULL了，就沒辦法找了
ListNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->val == x)
return cur;
else
cur = cur->next;
}
return NULL;
}
鏈表pos位置前面去插入
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);//pos不能為NULL,由于參數(shù)限制我們無法對pos判斷是否為哨兵位頭節(jié)點，因此我們假設(shè)pos傳的都是合法指針和NULL
ListNode* NewNode = ListCreate(x);
ListNode* prev = pos->prev;
NewNode->next = pos;
pos->prev = NewNode;
prev->next = NewNode;
NewNode->prev = prev;
}
刪除pos位置
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos)
{
assert(pos);//由于參數(shù)限制，我們無法判斷表是否為NULL；
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
}
鏈表判空
//判斷鏈表是否為NULL
bool is_Empty(ListNode* pHead)
{
assert(pHead);
return pHead == pHead->prev;
}
代碼復(fù)用
我們上面既然實現(xiàn)了在pos位置之前插入和刪除pos位置的數(shù)據(jù)；
那么：
ListInsert(plist,x);//相當(dāng)于尾插
ListInsert(plist->next, x);//相當(dāng)于頭插
ListErase(plist->next);//相當(dāng)于頭刪
ListErase(plist->prev);//相當(dāng)于尾刪;
那么實際上我們只要實現(xiàn)ListInsert、ListErase這兩個接口就能快速實現(xiàn)出帶頭雙向循環(huán)鏈表了；
總代碼及頭文件
頭文件的包含：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 帶頭+雙向+循環(huán)鏈表增刪查改實現(xiàn)
typedef int LTDataType;
typedef struct ListNode
{
LTDataType val;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
// 創(chuàng)建返回鏈表的頭結(jié)點.
ListNode* ListCreate(LTDataType x);
//初始化哨兵位的頭節(jié)點;
void InitDummyHead(ListNode* pHead);
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead);
// 雙向鏈表打印
void ListPrint(ListNode* pHead);
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead);
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead);
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos);
//判斷鏈表是否為NULL
bool is_Empty(ListNode* pHead);
功能代碼實現(xiàn)：
#include"DList.h"
ListNode* ListCreate(LTDataType x)
{
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (!NewNode)
exit(-1);
NewNode->val = x;
NewNode->prev = NULL;
NewNode->next = NULL;
return NewNode;
}
void InitDummyHead(ListNode* pHead)
{
assert(pHead);
pHead->prev = pHead;
pHead->next = pHead;
}
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
ListNode* next = NULL;
while (cur!=pHead)
{
next = cur->next;
free(cur);
cur = next;
}
free(cur);
}
// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
while (cur != pHead)
{
ListNode* next = cur->next;
printf("%d->",cur->val);
cur = next;
}
printf("NULL\n");
}
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
/*ListNode* NewNode = ListCreate(x);
ListNode* tail = pHead->prev;
tail->next = NewNode;
NewNode->prev = tail;
pHead->prev = NewNode;
NewNode->next = pHead;*/
ListInsert(pHead,x);//函數(shù)復(fù)用
}
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(!is_Empty(pHead));//判空
/*ListNode* tail = pHead->prev;
ListNode* prev = tail->prev;
ListNode* next = pHead;
free(tail);
prev->next = next;
next->prev = prev;*/
ListErase(pHead->prev);//函數(shù)復(fù)用
}
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
/*ListNode* prev = pHead;
ListNode* cur = pHead->next;
ListNode* NewNode = ListCreate(x);
prev->next = NewNode;
NewNode->prev = prev;
NewNode->next = cur;
cur->prev = NewNode;*/
ListInsert(pHead->next,x);//函數(shù)復(fù)用
}
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(!is_Empty(pHead));//判空
/*ListNode* prev = pHead;
ListNode* cur = pHead->next;
ListNode* next = cur->next;
free(cur);
prev->next = next;
next->prev = prev;*/
ListErase(pHead->next);//函數(shù)復(fù)用
}
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
assert(!is_Empty(pHead));//表都為NULL了，就沒辦法找了
ListNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->val == x)
return cur;
else
cur = cur->next;
}
return NULL;
}
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);//pos不能為NULL,由于參數(shù)限制我們無法對pos判斷是否為哨兵位頭節(jié)點，因此我們假設(shè)pos傳的都是合法指針和NULL
ListNode* NewNode = ListCreate(x);
ListNode* prev = pos->prev;
NewNode->next = pos;
pos->prev = NewNode;
prev->next = NewNode;
NewNode->prev = prev;
}
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos)
{
assert(pos);//由于參數(shù)限制，我們無法判斷表是否為NULL；
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
}
//判斷鏈表是否為NULL
bool is_Empty(ListNode* pHead)
{
assert(pHead);
return pHead == pHead->prev;
}
原文鏈接：https://blog.csdn.net/qq_62106937/article/details/127741856
相關(guān)推薦
- 2022-08-20 windows系統(tǒng)安裝配置nginx環(huán)境_nginx
- 2023-10-15 centos 切換g++
- 2022-06-17 教你Docker安裝GitLab功能_docker
- 2022-08-10 C語言折半查找法的超詳細(xì)講解_C 語言
- 2022-07-21 微信小程序使用vant weapp報錯
- 2022-08-02 Android開發(fā)雙向滑動選擇器范圍SeekBar實現(xiàn)_Android
- 2022-04-10 微信小程序與普通網(wǎng)頁的區(qū)別是什么
- 2022-09-26 符合選擇器和css三大特性組合
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運算符，流程控制 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錯誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速