本篇要分享的內(nèi)容是帶頭雙向鏈表，以下為本片目錄
目錄
一、鏈表的所有結(jié)構(gòu)
二、帶頭雙向鏈表
2.1尾部插入
2.2哨兵位的初始化
2.3頭部插入
2.4 打印鏈表
2.5尾部刪除
2.6頭部刪除
?2.7查找結(jié)點(diǎn)
2.8任意位置插入
2.9任意位置刪除?
在剛開始接觸鏈表的時(shí)候，我們所學(xué)僅僅所學(xué)的是單鏈表，相信大家用C語言學(xué)習(xí)單鏈表時(shí)也倍受二級(jí)指針的折磨。當(dāng)然單鏈表只是鏈表結(jié)構(gòu)內(nèi)的一種，他的結(jié)構(gòu)非常簡單，但是理解并操作起來卻非常困難；而我們今天要研究的是鏈表中結(jié)構(gòu)最復(fù)雜，但是理解起來最簡單的鏈表的結(jié)構(gòu)。
一、鏈表的所有結(jié)構(gòu)
在學(xué)習(xí)帶頭雙向鏈表之前先了解一下鏈表的所有結(jié)構(gòu)
1.單向或雙向
?2.帶頭或不帶頭
?3.循環(huán)或不循環(huán)
?還可以將以上的鏈表結(jié)構(gòu)進(jìn)行組合
最終鏈表有八種結(jié)構(gòu)。
這里要說明的是帶頭和不帶頭的情況，這里的頭意思就是哨兵位，哨兵位也就是作為鏈表的開頭鏈接后面的數(shù)據(jù)，但是不存放任何數(shù)據(jù)，需要單獨(dú)開辟一個(gè)結(jié)點(diǎn)來確定哨兵位，這就是帶頭不帶頭的意思。
二、帶頭雙向鏈表
其實(shí)我們也沒有必要一個(gè)一個(gè)的去了解那么多的鏈表結(jié)構(gòu)，我們平時(shí)用到的最多的還是兩個(gè)結(jié)構(gòu)
?1. 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)
構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
2. 帶頭雙向循環(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ì)帶
來很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。
2.1尾部插入
和單鏈表相同，我們同樣掌握帶頭循環(huán)鏈表的增刪查改，但是帶頭循環(huán)鏈表的增刪查改會(huì)比單鏈表容易許多。
首先定義一個(gè)結(jié)構(gòu)體來存放前一個(gè)結(jié)點(diǎn)的位置和后一個(gè)結(jié)點(diǎn)的位置和數(shù)據(jù)；
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
LTDataType Data;
}LTNode;
接下來畫圖給大家演示一下
?這里要插入的是newnode這個(gè)結(jié)點(diǎn)，我們可以直接操作phead的prev來實(shí)現(xiàn)尾插。
和單鏈表的尾插相同的，尾插就得先找尾，這個(gè)鏈表結(jié)構(gòu)中的找尾，只需要通過phead的prev即可找到尾，比單鏈表中的找尾要方便許多。
插入newnode也非常簡單，只需要改變四個(gè)指針的位置即可，以下是尾部插入的代碼
void PushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}在對(duì)比一下以上兩幅圖和尾插的代碼，首先寫出一個(gè)開辟節(jié)點(diǎn)的代碼用來開辟newnode（放在后面說）。
newnode已經(jīng)開辟好，然后改變四個(gè)指針的方向；
先讓哨兵位phead通過prev來找尾，令尾為tail；
讓tail的next來指向新的結(jié)點(diǎn)newnode；
再讓新結(jié)點(diǎn)newnode的prev鏈接上一個(gè)結(jié)點(diǎn)tail；
再讓新節(jié)點(diǎn)newnode的next重新指向哨兵位；
最后讓哨兵位phead的prev指向新節(jié)點(diǎn)newnode；這樣newnode才能成為鏈表的尾結(jié)點(diǎn)；
這樣就是一個(gè)完整的尾插；
兄弟萌，對(duì)比單鏈表的尾插，在邏輯上帶頭循環(huán)鏈表的尾插是要簡單一些，一目了然。
2.2哨兵位的初始化
那為什么可以這么這么簡單呢？
如下圖
可以看到我們對(duì)哨兵位的初始化，如果鏈表為空時(shí)，phead的prev就指向自己，phead的next也可以指向自己，這就是對(duì)哨兵位的初始化
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
2.3頭部插入
既然都是插入我們不妨大膽猜測(cè)一下，他是否和尾插一樣呢？
接下來繼續(xù)畫圖分析：
頭插要注意的是要插入到哨兵位之后，因?yàn)槲覀冃枰ㄟ^哨兵位來找到這個(gè)鏈表，所以要在哨兵位后面插入，也就是頭插。
同樣的上圖先malloc了一個(gè)結(jié)點(diǎn)出來，那如何處理這個(gè)結(jié)點(diǎn)呢？
假設(shè)我們和尾插一樣，先處理這個(gè)結(jié)點(diǎn)前面的指針
讓phead的next指向newnode；
讓newnode的prev指向phead；
再讓newnode的next指向下一個(gè)結(jié)點(diǎn)；
這樣做真的可以做到嗎？
?當(dāng)然是不行的啦；
你有沒有發(fā)現(xiàn)，如果我們先改變phead的next，令他指向newnode的話，它還可以找到newnode的下一個(gè)結(jié)點(diǎn)嗎？顯然是不行的，所以在頭部插入時(shí)我們需要先改變newnode后面的結(jié)點(diǎn)，讓newnode先和后面的結(jié)點(diǎn)鏈接起來，再讓他和前面的結(jié)點(diǎn)進(jìn)行連接，這樣才是頭插的正確用法。
下面是頭插的代碼
void PushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode= BuyLTNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
可以對(duì)照上圖仔細(xì)閱讀一下代碼，應(yīng)該不難看懂；
2.4 打印鏈表
既然我們上面討論過頭插和尾插，我們不妨將其輸出驗(yàn)證一下結(jié)果
void LTPrint(LTNode* phead)
{
assert(phead);
printf("sentinel bit<==>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<==>", cur->Data);
cur = cur->next;
}
printf("\n");
}sentinel是哨兵位的意思，我們要通過哨兵位才能找到這些鏈表；
我們先定義一個(gè)新的結(jié)構(gòu)體指針cur，讓cur指向頭節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，向后迭代，通過cur來遍歷這個(gè)鏈表，簡單來說就是從哨兵位后面的那個(gè)結(jié)點(diǎn)開始遍歷，當(dāng)這個(gè)結(jié)點(diǎn)知道下一個(gè)是哨兵位的時(shí)候結(jié)束了。
那結(jié)合上面的圖示我們可以知道phead的next走到最后就會(huì)又回到phead的位置，所以我們不妨讓cur=phead成為循環(huán)結(jié)束的標(biāo)志，當(dāng)cur!=phead 的時(shí)候就打印鏈表內(nèi)容
我們應(yīng)用上面的兩個(gè)插入函數(shù)來驗(yàn)證
?可以看到我們的頭部插入和尾部插入，還有打印函數(shù)都非常的成功。
2.5尾部刪除
我們不妨先看看單鏈表的尾部刪除
?可以看到步驟是相當(dāng)?shù)姆爆崳驗(yàn)椴粌H要找尾，還要判空，還要判斷是否只有一個(gè)數(shù)據(jù)，非常非常的麻煩，可以說是集各種缺點(diǎn)于一身。
但是帶頭雙向鏈表的尾部刪除寫起來非常爽
再繼續(xù)畫圖來理解
?帶頭雙向鏈表的尾刪只要通過phead的prev就可以找到尾結(jié)點(diǎn)tail，并且找到尾結(jié)點(diǎn)tail后可以繼續(xù)通過tail->prev來找到tail的前一個(gè)結(jié)點(diǎn)，我們將他成為tailPrev
然后將phead的prev指向tailPrev這個(gè)結(jié)點(diǎn)；
再將tailPrev這個(gè)結(jié)點(diǎn)的next指向phead哨兵位，這樣就把tail孤立出去了，此時(shí)tailPrev就成為了新的尾結(jié)點(diǎn)
最后再將tail用free釋放掉就就可以達(dá)到尾刪的結(jié)果
以下是代碼
void PopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* tail = phead->prev;
LTNode* tailprev = tail->prev;
free(tail);
tailprev->next = phead;
phead->prev = tailprev;
}可以對(duì)照著上面的圖和文字步驟仔細(xì)理解一下代碼的內(nèi)容，應(yīng)該不難看懂。
2.6頭部刪除
既然是頭部刪除，那就繼續(xù)要在哨兵位上動(dòng)手腳，我們繼續(xù)來畫圖理解
?相信這個(gè)圖也很清晰了，通過哨兵位phead找到下一個(gè)結(jié)點(diǎn)的next，也就是next的next，然后free掉next來達(dá)到刪除的效果，再讓原先next的next的prev來指向哨兵位，這樣第二個(gè)結(jié)點(diǎn)就代替了第一個(gè)結(jié)點(diǎn)達(dá)到頭部刪除的效果，下面是代碼
void PopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* first = phead->next;
LTNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
}我們不妨將phead->next定義為first，將next->next定義位second，這樣代碼的可讀性就會(huì)大大提高，將代碼對(duì)照以上文字描述和圖片仔細(xì)理解，應(yīng)該不難看懂。
當(dāng)然在增強(qiáng)代碼可讀性方面還需要做的一點(diǎn)就是assert的斷言；可以看到上面的代碼中出現(xiàn)了
assert(!LTEmpty(phead));這樣一串代碼中assert怎么斷言一個(gè)函數(shù)呢？那這是什么意思呢？
我們用bool寫一個(gè)函數(shù)
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}意思就是說如果鏈表中沒有元素了，phead的next還是等于phead的話就說明鏈表已經(jīng)空了，這樣做的好處就是可以提醒你鏈表中已經(jīng)沒有元素來讓你刪除了，從而達(dá)到暴力檢查讓編譯器報(bào)錯(cuò)的效果。
我們?cè)谥骱瘮?shù)中使用以下我們上面所寫的刪除函數(shù)
?可以看到我們的尾部刪除已經(jīng)刪掉了尾部插入的4，那我們?cè)俣啻问褂脛h除函數(shù)會(huì)怎樣
?可以看到再main函數(shù)中直插入了四個(gè)數(shù)據(jù)，但是卻使用了五次刪除函數(shù)，運(yùn)行時(shí)就會(huì)報(bào)錯(cuò)，而報(bào)錯(cuò)的內(nèi)容就是我們剛剛寫的布爾函數(shù)，它可以大大加強(qiáng)代碼的可讀性。
?2.7查找結(jié)點(diǎn)
查找結(jié)點(diǎn)再帶頭雙向循環(huán)列表中也不困難，同樣的是要對(duì)鏈表進(jìn)行遍歷查找。我們要查找的是結(jié)點(diǎn)，所以定義函數(shù)類型的時(shí)候一定是結(jié)構(gòu)體指針類型，找到了就返回他的結(jié)點(diǎn)，找不到就返回空，這就是大體思路
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;
}這里就需要傳兩個(gè)參數(shù)了，一個(gè)是鏈表的頭節(jié)點(diǎn)以便于我們找到鏈表并遍歷查找，另一個(gè)就是我們想要找的數(shù)x。
當(dāng)然也需要重新定一個(gè)結(jié)構(gòu)體指針來遍歷數(shù)組，并且和打印函數(shù)的循環(huán)條件相同，當(dāng)檢測(cè)到下一個(gè)結(jié)點(diǎn)時(shí)哨兵位phead的時(shí)候就停止循環(huán)了，因?yàn)橄乱粋€(gè)結(jié)點(diǎn)是phead的時(shí)候已經(jīng)遍歷完整個(gè)鏈表了。
這時(shí)就要操作結(jié)構(gòu)體中的數(shù)據(jù)Data了，如果遍歷時(shí)結(jié)點(diǎn)中的數(shù)據(jù)Data等于我們傳入的參數(shù)x，那么就煩回這個(gè)結(jié)點(diǎn)，如果沒有找到就返回空。
其實(shí)查找函數(shù)可以和其他的函數(shù)嵌套使用，因?yàn)椴檎液瘮?shù)返回的是結(jié)構(gòu)體指針類型，而其它函數(shù)的參數(shù)也是結(jié)構(gòu)體指針類型，我們可以將其和插入函數(shù)和刪除函數(shù)一起使用。
2.8任意位置插入
和其他的插入方法一樣的只需要改變指針的指向的內(nèi)容即可。
以下是圖例
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;
}中間插入就不需要再使用phead了，因?yàn)閜head是哨兵位，而中間插入需要的是其他的結(jié)點(diǎn)，也就是通過剛剛討論過的查找函數(shù)所查找出來的結(jié)點(diǎn)，你就會(huì)發(fā)現(xiàn)，查找函數(shù)和其他函數(shù)就這樣連接在一起了。
首先定義一個(gè)結(jié)構(gòu)體指針prev來存放查找出來的那個(gè)結(jié)點(diǎn)的前面一個(gè)結(jié)點(diǎn)；
然后開辟一個(gè)新的結(jié)點(diǎn)newnode；
然后就和尾插一模一樣的方法改變指針指向的內(nèi)容即可。
也可以在main函數(shù)中使用驗(yàn)證一下
這里的意思就是通過查找函數(shù)找到3的位置，并且再3的前面插入30，驗(yàn)證正確；
2.9任意位置刪除?
同樣的也需要通過查找函數(shù)來確定刪除的位置，以下是圖例
?仔細(xì)研究完頭部刪除和尾部刪除的內(nèi)容應(yīng)該不難看懂。
首先要找到pos前面的一個(gè)結(jié)點(diǎn)和后面的一個(gè)結(jié)點(diǎn)，然后直接將前一個(gè)結(jié)點(diǎn)的next指向pos的下一個(gè)結(jié)點(diǎn)；
將pos的下一個(gè)結(jié)點(diǎn)的prev指向pos的上一個(gè)結(jié)點(diǎn)；
最后再free掉pos這個(gè)位置即可完成刪除操作；
以下是任意位置刪除的代碼
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
;
}?繼續(xù)再mian函數(shù)中使用?
可以看到3就被刪除掉了。文章來源：http://www.zghlxwxcb.cn/news/detail-453483.html
以上就是帶頭雙向循環(huán)鏈表增刪查改使用的所有內(nèi)容，如果對(duì)你有所幫助還請(qǐng)多多三聯(lián)支持，感謝您的閱讀。文章來源地址http://www.zghlxwxcb.cn/news/detail-453483.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】鏈表：帶頭雙向循環(huán)鏈表的增刪查改的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
