??前言
-
怎么說呢?光乍一聽名字好像很難的樣子是吧,那如果你這樣認(rèn)為的話,可就要讓你大跌眼鏡了哦,其實(shí)雙向帶頭循環(huán)鏈表從操作和理解上來說都是要易于單項(xiàng)不帶頭不循環(huán)鏈表(俗稱單鏈表)的。
-
咱們就來見識(shí)見識(shí)吧!希望真的能讓你們“大跌眼鏡”哈!
-
雙向帶頭循環(huán)鏈表是一種最為常見的數(shù)據(jù)結(jié)構(gòu)之一,非常適合于需要常操作插入、刪除等操作的情況。其基本結(jié)構(gòu)和單向鏈表相似,不同的是除了對(duì)前驅(qū)結(jié)點(diǎn)的引用,還有對(duì)后繼結(jié)點(diǎn)的引用。
-
在循環(huán)鏈表中,表頭和表尾是相連的,形成了一個(gè)閉環(huán)。而帶頭指針則是為了方便操作而加入的,同時(shí)便于對(duì)空鏈表的判斷。由于雙向循環(huán)鏈表可以雙向循環(huán)遍歷,因此它的操作非常靈活,可以很容易地修改鏈表,使得其更加高效、穩(wěn)定。
??帶頭雙向循環(huán)鏈表的結(jié)構(gòu)體搭建和初始化的操作
- 先簡(jiǎn)單看看這個(gè)邏輯圖,整體的節(jié)點(diǎn)之間的聯(lián)系在圖中就能表現(xiàn)的非常清楚了。
- 這一步還是一如既往的相同,所需頭文件的包含和結(jié)構(gòu)體的定義。
具體代碼:
//帶頭雙向循環(huán)鏈表
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//數(shù)據(jù)的類型
typedef int LTDataType;
// 結(jié)構(gòu)體的定義
typedef struct ListNode
{
// 指向下一個(gè)節(jié)點(diǎn)的指針
struct ListNode* next;
// 指向前一個(gè)節(jié)點(diǎn)的指針
struct ListNode* prev;
// 儲(chǔ)存數(shù)據(jù)
LTDataType data;
}LTNode;
- 各個(gè)函數(shù)的的聲明
具體代碼:
//創(chuàng)建返回鏈表的頭結(jié)點(diǎn)
LTNode* ListCreate();
// 雙向鏈表的節(jié)點(diǎn)申請(qǐng)
LTNode* BuyLTNode(LTDataType x);
// 雙向鏈表的初始化
LTNode* LTInit();
// 雙向鏈表的打印
void LTPrint(LTNode* phead);
// 雙向鏈表的判空
bool LTEmpty(LTNode* phead);
// 雙向鏈表的銷毀
void LTDestroy(LTNode* phead);
// 雙向鏈表的尾插
void LTPushBack(LTNode* phead, LTDataType x);
// 雙向鏈表的頭插
void LTPushFront(LTNode* phead, LTDataType x);
// 雙向鏈表的尾刪
void LTPopBack(LTNode* phead);
// 雙向鏈表的頭刪
void LTPopFront(LTNode* phead);
// 雙向鏈表的查找
LTNode* LTFind(LTNode* phead, LTDataType x);
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 刪除pos位置的節(jié)點(diǎn)
void LTErase(LTNode* pos);
??創(chuàng)造一個(gè)哨兵位頭結(jié)點(diǎn)
- 哨兵位頭節(jié)點(diǎn)(sentinel node)是一種特殊的節(jié)點(diǎn),通常用于鏈表等數(shù)據(jù)結(jié)構(gòu)中。這個(gè)節(jié)點(diǎn)不代表任何真實(shí)的值,而是在表頭部提供了一個(gè)便利的占位符,來簡(jiǎn)化一些操作的實(shí)現(xiàn),從而減少代碼的復(fù)雜性。
- 創(chuàng)建哨兵位頭節(jié)點(diǎn):
這個(gè)節(jié)點(diǎn)的值可以是任意值,但是它的 next 指針應(yīng)該指向鏈表的頭節(jié)點(diǎn)。這個(gè)函數(shù)會(huì)返回一個(gè)指向哨兵節(jié)點(diǎn)的指針,你可以像使用普通鏈表一樣使用它。但是,注意到哨兵節(jié)點(diǎn)不存儲(chǔ)任何有用的值,因此,當(dāng)你插入或者刪除元素時(shí),要特別小心喔。
具體代碼:
// 創(chuàng)建返回鏈表的頭結(jié)點(diǎn)
LTNode* ListCreate()
{
// BuyListNode() 該函數(shù)是申請(qǐng)一個(gè)節(jié)點(diǎn),下面會(huì)講解
LTNode* head = BuyLTNode(-1);
return head;
}
- 這里需要注意一個(gè)小細(xì)節(jié):上述代碼中頭結(jié)點(diǎn)與哨兵位頭結(jié)點(diǎn)是等價(jià)的。
??申請(qǐng)一個(gè)節(jié)點(diǎn)
- 因?yàn)楹竺骖l繁需要用到申請(qǐng)一個(gè)節(jié)點(diǎn),所以我們不妨就獎(jiǎng)這個(gè)功能單獨(dú)實(shí)現(xiàn)一個(gè)函數(shù),在后面需要這個(gè)功能的時(shí)候直接調(diào)用就OK啦。
- 這個(gè)功能實(shí)際上就是在內(nèi)存上申請(qǐng)一塊空間,這塊空間就用作newnode這塊空間。
- 申請(qǐng)這個(gè)節(jié)點(diǎn)我們可以讓每個(gè)節(jié)點(diǎn)首先指向空,然后再將自己給定的值存入數(shù)據(jù)中,最后直接返回這個(gè)節(jié)點(diǎn)的地址即可。(因?yàn)檫@段空間的是在堆上的,所以銷毀棧幀不會(huì)影響這段空間)
具體代碼:
//申請(qǐng)一個(gè)節(jié)點(diǎn)
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
??初始化
- 這個(gè)操作相信大家已經(jīng)在熟悉不過了,而雙向鏈表也不過如此,就是將鏈表的頭節(jié)點(diǎn)的next和prev指向自己。
- 最后記得返回頭結(jié)點(diǎn)。
具體代碼:
//初始化
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
??打印
- 相較于單向鏈表,它可以通過指向前驅(qū)節(jié)點(diǎn)的指針實(shí)現(xiàn)反向遍歷,提高了遍歷的效率。
- 我們定義了一個(gè)指針變量 cur,將其初始化為鏈表頭節(jié)點(diǎn)的指針 phead。然后,使用 while 循環(huán)遍歷鏈表,同時(shí)打印節(jié)點(diǎn)的值。最后,在每次打印完所有節(jié)點(diǎn)后,我們使用 printf 函數(shù)輸出一個(gè)換行符,以便美化輸出結(jié)果。
具體代碼:
//打印
void LTPrint(LTNode* phead)
{
assert(phead);
printf("guard<==>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<==>", cur->data);
cur = cur->next;
}
printf("\n");
}
總的來說,打印雙向鏈表并非復(fù)雜的操作,只需遍歷鏈表,并打印每個(gè)節(jié)點(diǎn)的值即可。
??判空
- 這里的判空不是判斷有沒有數(shù)據(jù),而是判斷有沒有節(jié)點(diǎn),若有節(jié)點(diǎn),說明不為空,就返回false;若無(wú)節(jié)點(diǎn),說明為空,就返回true。
-
LTEmpty函數(shù)接收一個(gè)頭指針 phead 作為參數(shù),如果 phead 指向空,那么我們認(rèn)為該雙向鏈表為空,返回頭節(jié)點(diǎn)。否則鏈表不為空。
具體代碼:
//判空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
??銷毀
- 在使用完雙向鏈表之后需要將它銷毀以釋放占用的內(nèi)存空間。
- 由于雙向鏈表中每個(gè)節(jié)點(diǎn)都有兩個(gè)指針,銷毀該鏈表時(shí)需要遍歷整個(gè)鏈表來把每個(gè)節(jié)點(diǎn)都銷毀。
- 可以定義一個(gè)名為LTDestroy的函數(shù)來銷毀雙向鏈表。該函數(shù)接收一個(gè)頭指針 phead 作為參數(shù),并將每個(gè)節(jié)點(diǎn)都銷毀,最后將頭節(jié)點(diǎn)也銷毀并將頭指針置free掉。
具體代碼:
//銷毀
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
??尾插
- 因?yàn)槭俏膊?,就是在鏈表的最后一?jié)點(diǎn)后面鏈接一個(gè)節(jié)點(diǎn),我們首先要申請(qǐng)一個(gè)節(jié)點(diǎn),然后再找到尾部的節(jié)點(diǎn),在進(jìn)行鏈接。
- 又因?yàn)檫@是循環(huán)鏈表,所以找到尾部節(jié)點(diǎn)不就是找到newnode的prev嗎,那就變得so easy了。
- 過程就是可以簡(jiǎn)單理解為這樣:
具體代碼:
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
//申請(qǐng)一個(gè)節(jié)點(diǎn)
LTNode* newnode = BuyLTNode(x);
//存放最后一個(gè)節(jié)點(diǎn)的指針
LTNode* tail = phead->prev;
//將整個(gè)鏈表鏈接起來
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
需要注意的是:
在執(zhí)行這些指針操作時(shí),要確保所有指針都指向正確的節(jié)點(diǎn),否則可能導(dǎo)致程序崩潰或出現(xiàn)其他錯(cuò)誤。
??頭插
- 首先將新節(jié)點(diǎn)的 prev 指針置為NULL,即表示該節(jié)點(diǎn)是雙向鏈表的頭節(jié)點(diǎn)。然后將新節(jié)點(diǎn)的 next 指針指向頭節(jié)點(diǎn)的后繼節(jié)點(diǎn)。
- 如果頭節(jié)點(diǎn)的后繼節(jié)點(diǎn)不為空,則將其 prev 指針指向新節(jié)點(diǎn);否則,新節(jié)點(diǎn)就是雙向鏈表的尾節(jié)點(diǎn)。
- 最后,將頭節(jié)點(diǎn)的 next 指針指向新節(jié)點(diǎn),完成頭插操作。
- 過程簡(jiǎn)單的可視化:
具體代碼:
//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
//申請(qǐng)一個(gè)節(jié)點(diǎn)
LTNode* newnode = BuyLTNode(x);
//存放下一個(gè)節(jié)點(diǎn)
LTNode* first = phead->next;
//將鏈表連接起來
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
需要注意的是:
如果不存放當(dāng)前頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址,那么需要先將新的節(jié)點(diǎn)與頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)連接,然后才與頭節(jié)點(diǎn)連接,因?yàn)橄扰c頭節(jié)點(diǎn)連接的話,就找不到下一個(gè)節(jié)點(diǎn)了,此時(shí)就會(huì)連接中斷。
??尾刪
- 使用指針遍歷整個(gè)鏈表,直到找到最后一個(gè)節(jié)點(diǎn),然后將其刪除。(刪除就記得要判空)
- 刪除操作需要改變兩個(gè)指針值,即前驅(qū)節(jié)點(diǎn)的 next 指針和待刪除節(jié)點(diǎn)的 prev指針,同時(shí)需要使用 free 函數(shù)釋放該節(jié)點(diǎn)占用的內(nèi)存空間。
- 至于如果是空指針咋辦,交給assert就好了。其他的情況都是這套操作。
- 靜態(tài)過程就放在下面了:
具體代碼:
//尾刪
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
}
??頭刪
- 首先找到第一個(gè)實(shí)際節(jié)點(diǎn),并將其存儲(chǔ)在指針 phead 中。(記得刪除就要判空)
- 然后,將頭節(jié)點(diǎn)的 next 指針設(shè)置為 phead 的 next 指針,以繞過要?jiǎng)h除的節(jié)點(diǎn),并修改待刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)的 prev 指針。
- 最后,使用 free 函數(shù)釋放該節(jié)點(diǎn)占用的內(nèi)存空間。
具體代碼:
//頭刪
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
// 存放當(dāng)前鏈表頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址
LTNode* prev = phead->next;
// 存放當(dāng)前鏈表頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址
LTNode* next = prev->next;
//鏈接
phead->next = next;
next->prev = phead;
//釋放
free(prev);
}
??查找
- 這里的查找我們輸入的是數(shù)據(jù),然后再鏈表中尋找data與輸入的數(shù)據(jù)相等的節(jié)點(diǎn),最后返回這個(gè)節(jié)點(diǎn)的地址。若沒有找到,則返回NULL。
- 查找?不就是將整個(gè)鏈表遍歷一遍嗎?
上代碼:
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
??在pos位置之前插入
- 這里的插入是指在任意位置的插入,就是在你輸入的節(jié)點(diǎn)之前插入數(shù)據(jù)。
- 竟然時(shí)任意位置,自然的這里就會(huì)再多一個(gè)變量,這時(shí)候這里需要傳遞一個(gè)指針(pos)來指向你輸入的節(jié)點(diǎn)的前面。
- 再加上咱們前面學(xué)習(xí)的頭插,直接復(fù)用就好了,這里就不再多啰嗦了。
- 然后要記得存放要插入的前一個(gè)位置的節(jié)點(diǎn),插入之后記得鏈接。
具體代碼:
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyLTNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
??刪除pos位置的節(jié)點(diǎn)
- 刪除任意節(jié)點(diǎn)的位置放在這個(gè)位置是不是顯得格外渺小,與插入類似,就是需要多傳遞一個(gè)變量來接收任意位置節(jié)點(diǎn)的地址。
- 都看到這里了,其他的操作就不必多說了。算了,還是描述一下為好。
- 當(dāng)我們想要?jiǎng)h除節(jié)點(diǎn) pos 時(shí),首先需要修改其前驅(qū)節(jié)點(diǎn)的 next 指針,使其指向 pos 的后繼節(jié)點(diǎn);再修改其后繼節(jié)點(diǎn)的 prev 指針,使其指向 pos 的前驅(qū)節(jié)點(diǎn)。最后,使用 free 函數(shù)釋放待刪除節(jié)點(diǎn)占用的內(nèi)存空間。
具體代碼:
// 刪除pos位置的值
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
??完整代碼
List.h
//帶頭雙向循環(huán)鏈表
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 結(jié)構(gòu)體的定義
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
//創(chuàng)建返回鏈表的頭結(jié)點(diǎn)
LTNode* ListCreate();
// 雙向鏈表的節(jié)點(diǎn)申請(qǐng)
LTNode* BuyLTNode(LTDataType x);
// 雙向鏈表的初始化
LTNode* LTInit();
// 雙向鏈表的打印
void LTPrint(LTNode* phead);
// 雙向鏈表的判空
bool LTEmpty(LTNode* phead);
// 雙向鏈表的銷毀
void LTDestroy(LTNode* phead);
// 雙向鏈表的尾插
void LTPushBack(LTNode* phead, LTDataType x);
// 雙向鏈表的頭插
void LTPushFront(LTNode* phead, LTDataType x);
// 雙向鏈表的尾刪
void LTPopBack(LTNode* phead);
// 雙向鏈表的頭刪
void LTPopFront(LTNode* phead);
// 雙向鏈表的查找
LTNode* LTFind(LTNode* phead, LTDataType x);
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 刪除pos位置的節(jié)點(diǎn)
void LTErase(LTNode* pos);
List.c
#include"List.h"
// 創(chuàng)建返回鏈表的頭結(jié)點(diǎn)
LTNode* ListCreate()
{
// BuyListNode() 該函數(shù)是申請(qǐng)一個(gè)節(jié)點(diǎn),下面會(huì)講解
LTNode* head = BuyLTNode(-1);
return head;
}
//申請(qǐng)一個(gè)節(jié)點(diǎn)
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
//初始化
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
//打印
void LTPrint(LTNode* phead)
{
assert(phead);
printf("guard<==>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<==>", cur->data);
cur = cur->next;
}
printf("\n");
}
//判空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
//銷毀
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead, x);
// LTNode* tail = phead->prev;
// LTNode* newnode = BuyLTNode(x);
//
// tail->next = newnode;
// newnode->prev = tail;
// newnode->next = phead;
// phead->prev = newnode;
}
//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{
/*assert(phead);
LTNode* newnode = BuyLTNode(x);
LTNode* first = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;*/
LTInsert(phead->next, x);
}
//尾刪
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->prev);
/*LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;*/
}
//頭刪
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->next);
//LTNode* first = phead->next;
//LTNode* second = first->next;
//phead->next = second;
//second->prev = phead;
//free(first);
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyLTNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
// 刪除pos位置的值
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
Test.c
#include"List.h"
void TestList1()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
void TestList2()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
void TestList3()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
if (pos)
{
LTInsert(pos, 30);
}
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
int main()
{
//TestList1();
//TestList2();
TestList3();
return 0;
}
有了任意位置的插入和刪除,我們可以在其他位置插入和刪除操作上調(diào)用文章來源:http://www.zghlxwxcb.cn/news/detail-468953.html
??寫在最后
?希望本篇博客能讓大家更好地理解雙向鏈表的基本原理及實(shí)現(xiàn)方法,幫助大家在實(shí)際開發(fā)中更好地使用該數(shù)據(jù)結(jié)構(gòu)。??也特別感謝大家持續(xù)的關(guān)注和支持,我會(huì)繼續(xù)努力更新更好的博客。
最后感謝各位閱讀本小白的博客,希望能幫助到大家!也請(qǐng)大家嚴(yán)厲指出并糾正我在文章中的錯(cuò)誤。??文章來源地址http://www.zghlxwxcb.cn/news/detail-468953.html
到了這里,關(guān)于數(shù)據(jù)結(jié)構(gòu)——實(shí)現(xiàn)雙向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!