寫(xiě)在前面
在前面學(xué)完單鏈表后，我們思考這樣一個(gè)問(wèn)題，單鏈表和順序表比起來(lái)，功能確實(shí)相當(dāng)強(qiáng)大，有很多優(yōu)勢(shì)，但是于此同時(shí)，我們也應(yīng)思考下面的問(wèn)題
單鏈表有什么不足的地方？
如果你把單鏈表的各個(gè)函數(shù)都自己實(shí)現(xiàn)過(guò)，那么下面的問(wèn)題你一定有相同的感悟
- 單鏈表實(shí)現(xiàn)尾插尾刪等操作，需要尋找尾部節(jié)點(diǎn)，而尋找尾部節(jié)點(diǎn)是一個(gè)相當(dāng)繁瑣的過(guò)程，需要從前向后尋找尾
- 單鏈表實(shí)現(xiàn)插入功能，對(duì)于單鏈表來(lái)說(shuō)，通常實(shí)現(xiàn)的是在pos后插入，而不在pos前插入，原因就在于pos向前插入需要尋找前面的節(jié)點(diǎn)，而這個(gè)節(jié)點(diǎn)只能從前向后遍歷尋找
- 單鏈表在實(shí)現(xiàn)函數(shù)時(shí)，要時(shí)時(shí)刻刻想到鏈表為空的情況，對(duì)于鏈表為空的情況要有特殊的處理方式
那么能不能想辦法解決下面這些問(wèn)題？
- 找尾部節(jié)點(diǎn)方便
- 找一個(gè)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)方便
- 不需要考慮空鏈表的空指針問(wèn)題
于是數(shù)據(jù)結(jié)構(gòu)中對(duì)于雙向循環(huán)鏈表就解決了這個(gè)問(wèn)題
雙向循環(huán)鏈表的構(gòu)造布局
帶有哨兵位的布局
首先介紹什么是哨兵位
和它的名字一樣，所謂哨兵位就是一個(gè)站哨的位置，它并不屬于真實(shí)的隊(duì)伍中的成員，而在鏈表中也是如此，在前面總結(jié)單鏈表所學(xué)的知識(shí)時(shí)，沒(méi)有引入哨兵位的鏈表，而是直接用空鏈表進(jìn)行寫(xiě)入，這樣的目的不僅僅在于方便后續(xù)的OJ練習(xí)，同時(shí)也是適應(yīng)特殊情況，為后續(xù)的c++學(xué)習(xí)做鋪墊
而在雙向循環(huán)鏈表中我們引入哨兵位的概念，作為哨兵的位置，它本身并不屬于鏈表中的一部分，只是充當(dāng)一個(gè)頭的位置
哨兵位怎么設(shè)置？
鏈表的每一個(gè)節(jié)點(diǎn)我們都是通過(guò)結(jié)構(gòu)體創(chuàng)建出來(lái)的，而很明顯，哨兵位也是鏈表的節(jié)點(diǎn)，就意味著哨兵位也有指針部分和數(shù)據(jù)部分，那么對(duì)于數(shù)據(jù)部分我們應(yīng)該怎么對(duì)它定義？
在一部分書(shū)中，哨兵位的數(shù)字部分會(huì)定義的鏈表的長(zhǎng)度，也就是鏈表中元素的個(gè)數(shù)，這樣乍一看似乎還不錯(cuò)，借助這個(gè)哨兵位還能獲取到鏈表的長(zhǎng)度
但是這樣真的沒(méi)問(wèn)題嗎？
事實(shí)上這是存在一定的問(wèn)題的，假設(shè)這里選取的是char類(lèi)型的數(shù)據(jù)類(lèi)型，對(duì)于char類(lèi)型的數(shù)據(jù)范圍是從-128到127(char類(lèi)型占1個(gè)字節(jié)決定的) 那么這里就有了一個(gè)新的問(wèn)題，假設(shè)鏈表中存儲(chǔ)的是char類(lèi)型的數(shù)據(jù)，那么假設(shè)鏈表的長(zhǎng)度為128呢？那么就會(huì)導(dǎo)致鏈表的實(shí)際長(zhǎng)度和存儲(chǔ)長(zhǎng)度有很大差距
于是這里對(duì)于哨兵位我并不對(duì)它的數(shù)據(jù)部分有特殊的意義，單純給它賦予一個(gè)值-1
帶哨兵位的雙向循環(huán)鏈表如下
上面就是雙向循環(huán)鏈表的示意圖，從中可以看出，每一個(gè)節(jié)點(diǎn)可以輕松找到它的下一個(gè)節(jié)點(diǎn)，以及最后一個(gè)節(jié)點(diǎn)和頭節(jié)點(diǎn)是循環(huán)在一起的
既然是雙向的鏈表，那么在定義結(jié)構(gòu)體的過(guò)程就和單鏈表有所不同，這里的指針部分應(yīng)該有兩個(gè)，prev和next部分，那么結(jié)構(gòu)體的定義如下
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
這樣就實(shí)現(xiàn)了對(duì)鏈表的定義，prev和next均有
和單鏈表相同，雙向循環(huán)鏈表也離不開(kāi)增刪查改的基本操作，那么這里我們一個(gè)一個(gè)來(lái)實(shí)現(xiàn)這些功能
鏈表的構(gòu)建
鏈表的構(gòu)建就是構(gòu)建一個(gè)phead的哨兵位節(jié)點(diǎn)，這個(gè)過(guò)程還是很簡(jiǎn)單的
ListNode* ListCreate()
{
ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
if (phead == NULL)
{
perror("malloc fail");
}
assert(phead);
phead->_data = -1;
phead->_next = phead;
phead->_prev = phead;
return phead;
}
鏈表的銷(xiāo)毀
有創(chuàng)建就離不開(kāi)銷(xiāo)毀，銷(xiāo)毀的過(guò)程和單鏈表基本相似，都是通過(guò)指針把一個(gè)節(jié)點(diǎn)單獨(dú)拿出來(lái)，free后再置空，代碼實(shí)現(xiàn)如下
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur != pHead)
{
ListNode* next = cur->_next;
free(cur);
cur = next;
}
}
鏈表的輸出
鏈表要打印在屏幕上的基本思路也和單鏈表基本一致，但需要注意的是，單鏈表的截止條件是當(dāng)指針訪問(wèn)到空，而雙向循環(huán)鏈表的條件是指針訪問(wèn)到頭
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
printf("guard<==>");
while (cur != pHead)
{
printf("%d<==>", cur->_data);
cur = cur->_next;
}
printf("\n");
}
這樣，雙向循環(huán)鏈表也可以進(jìn)行可視化管理了，那么下面就開(kāi)始實(shí)現(xiàn)增刪查改四大功能
鏈表的尾插
和單鏈表相似，但和它比起來(lái)更加簡(jiǎn)單，示意圖如下：
那么代碼是如何實(shí)現(xiàn)的？代碼實(shí)現(xiàn)如下
ListNode* BuyListnode(LTDataType x)
{
ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
if (phead == NULL)
{
perror("malloc fail");
}
assert(phead);
phead->_data = x;
phead->_next = NULL;
phead->_prev = NULL;
return phead;
}
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyListnode(x);
ListNode* prevnode = pHead->_prev;
prevnode->_next = newnode;
newnode->_prev = prevnode;
newnode->_next = pHead;
pHead->_prev = newnode;
}
對(duì)比單鏈表的尾插不難發(fā)現(xiàn)，這個(gè)過(guò)程比單鏈表簡(jiǎn)單了很多，首先對(duì)于空鏈表的判斷就更為簡(jiǎn)單，同時(shí)雙向循環(huán)鏈表由于存在雙向箭頭，導(dǎo)致插入是很便利的，這個(gè)過(guò)程在pos位置插入時(shí)候會(huì)體現(xiàn)出雙向鏈表特有的優(yōu)勢(shì)
鏈表的尾刪
代碼實(shí)現(xiàn)如下
bool LTempty(ListNode* pHead)
{
assert(pHead);
return pHead->_next == pHead;
}
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(!LTempty(pHead));
ListNode* tail = pHead->_prev;
pHead->_prev = tail->_prev;
tail->_prev->_next = pHead;
free(tail);
tail = NULL;
}
== 這里我們對(duì)bool返回值的函數(shù)進(jìn)行補(bǔ)充==
bool值意為真和假，在進(jìn)行尾刪時(shí)，我們需要首先進(jìn)行判斷鏈表到底是否為空，但由于雙向循環(huán)鏈表，于是我們并不能直觀通過(guò)判斷空指針，這里封裝了一個(gè)函數(shù)，用來(lái)判斷是否為空，如果為空就返回真，如果不為空就返回假，那么我們?cè)诤瘮?shù)體內(nèi)斷言只需要看它不為空即可
鏈表的頭插
代碼實(shí)現(xiàn)如下：
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* next = pHead->_next;
ListNode* newnode = BuyListnode(x);
assert(newnode);
pHead->_next = newnode;
newnode->_prev = pHead;
next->_prev = newnode;
newnode->_next = next;
}
鏈表的頭刪
從頭刪中其實(shí)就體現(xiàn)出了雙向鏈表的優(yōu)越性
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(!LTempty(pHead));
ListNode* first = pHead->_next;
ListNode* second = first->_next;
pHead->_next = second;
second->_prev = pHead;
free(first);
first = NULL;
}
鏈表的查找
和單鏈表基本類(lèi)似，這里不多介紹
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur->_data != x)
{
cur = cur->_next;
}
return cur;
}
鏈表的插入
在pos前插入的原理如下
從中和單鏈表一對(duì)比就能夠體現(xiàn)出雙向鏈表的優(yōu)越的地方，在單鏈表中我們通常不在pos前插入，原因就是pos前面的節(jié)點(diǎn)并不方便尋找，而雙向鏈表就解決了這個(gè)問(wèn)題
代碼實(shí)現(xiàn)如下
void ListInsert(ListNode* pos, LTDataType x)
{
ListNode* posprev = pos->_prev;
ListNode* newnode = BuyListnode(x);
assert(newnode);
assert(pos);
posprev->_next = newnode;
newnode->_prev = posprev;
newnode->_next = pos;
pos->_prev = newnode;
}
鏈表的刪除
這里和單鏈表的刪除相似，不多描述文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-612189.html
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* posprev = pos->_prev;
ListNode* posnext = pos->_next;
posprev->_next = posnext;
posnext->_prev = posprev;
free(pos);
pos = NULL;
}
自此，雙向循環(huán)鏈表就實(shí)現(xiàn)完畢了，和單鏈表比起來(lái)，雙向循環(huán)鏈表確實(shí)有它獨(dú)特強(qiáng)大的地方，而真正使用什么數(shù)據(jù)結(jié)構(gòu)還需要根據(jù)實(shí)際情況進(jìn)行設(shè)計(jì)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-612189.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)！
