C語言編程數(shù)據(jù)結(jié)構(gòu)帶頭雙向循環(huán)鏈表全面詳解
前言
上一篇數(shù)據(jù)結(jié)構(gòu)專欄：C語言數(shù)據(jù)結(jié)構(gòu)單鏈表接口函數(shù)全面講解教程
我們介紹了單鏈表的各個接口函數(shù)，大家可能會發(fā)現(xiàn)單鏈表存在一些缺陷：比如它一個節(jié)點要存儲數(shù)據(jù)+下一個節(jié)點地址，占用的空間要遠(yuǎn)多于順序表；并且由于單鏈表是無法從后往前找的，如果你想進(jìn)行尾刪這樣的操作，你必須從第一個節(jié)點往后找，你的時間復(fù)雜度一定是O（n）。
為了解決上面的一些缺陷，我們今天來介紹帶頭雙向循環(huán)鏈表
一、什么是帶頭循環(huán)雙向鏈表
這種鏈表會有一個哨兵位head節(jié)點指向d1,然后d1指向d2…這和單鏈表非常相似。
但和單鏈表最大的區(qū)別就是：這種鏈表的每個節(jié)點不僅會存儲下一個節(jié)點地址而且會存儲上一個節(jié)點的地址，然后尾節(jié)點會存儲一個指向哨兵位head的地址，然后哨兵位head會存儲一個指向尾結(jié)點的地址。
具體代碼如下：
typedef int LTDataType;//萬一以后需要改鏈表數(shù)據(jù)類型，可以直接在這里更改（int）
typedef struct ListNode
{
struct ListNode*next;
struct ListNode*prev;
LTDataType data;
}ListNode;//結(jié)構(gòu)體重命名
示例：pandas 是基于NumPy 的一種工具，該工具是為了解決數(shù)據(jù)分析任務(wù)而創(chuàng)建的。
二、鏈表初始化
類似于上圖的效果，剛開始創(chuàng)建只有一個節(jié)點，它儲存的前地址和后地址都指向自己
代碼如下（示例）：
#include<stdlib.h>//malloc函數(shù)頭文件
ListNode* BuyListNode(LTDataType x)//創(chuàng)建一個節(jié)點
{
ListNode*newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
ListNode* ListInit()//鏈表初始化
{
ListNode*phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
ps：這里L(fēng)istInit函數(shù)用的是返回值的方法，你也可以用二級指針傳參來進(jìn)行初始化操作
三、鏈表接口函數(shù)
1.尾插
我們以上圖為例，原先鏈表的head節(jié)點的前驅(qū)指向3，然后3的后驅(qū)指向head節(jié)點，那在3后面怎么進(jìn)行尾插呢？由于head節(jié)點里存放了3節(jié)點的地址，所以我們可以直接找到3節(jié)點，找到之后怎么辦?把head節(jié)點的前驅(qū)改成4節(jié)點地址，3節(jié)點后驅(qū)改為4節(jié)點地址，最后4節(jié)點后驅(qū)指向head節(jié)點。如下圖：
代碼如下（示例）：
#include<assert.h>//assert函數(shù)頭文件
void ListPushBack(ListNode*phead, LTDataType x)//尾插
{
assert(phead);//對傳過來的指針進(jìn)行斷言,因為你要進(jìn)行尾插至少得有個頭節(jié)點啊
//如果傳過來的是空指針會進(jìn)行報錯
ListNode*tail = phead->prev;
ListNode*newnode = BuyListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->data = phead;
phead->prev = newnode;
}
2.頭插
如上圖，先要在head和d1之間進(jìn)行頭插，怎么操作？非常簡單，思路和尾插一模一樣
head的后驅(qū)指向newnode，newnode的前驅(qū)和后驅(qū)分別指向phead和d1，d1前驅(qū)指向newnode如下圖：
代碼如下（示例）：
void ListPushFront(ListNode*phead,LTDataType x)
{
assert(phead);
ListNode*first = phead->next;
ListNode*newnode = BuyListNode(x);
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
注意?。?！這里是先定義了一個first來存放d1這個地址，如果不事先定義的話，phead->next = newnode;head不再存儲d1地址，你就找不到d1了。當(dāng)然了，如果你就是不想先定義一個first來存放d1地址也可以。怎么做呢？“先連后斷”，newnode后驅(qū)先接上d1節(jié)點，然后你head節(jié)點后驅(qū)接上newnode。
3.頭刪
頭刪也是和前面兩個類似的思想
頭刪也就是把d1節(jié)點刪掉，我們定義2個指針分別指向d1和d2，然后把head節(jié)點后驅(qū)接指向d2，d2前驅(qū)指向head即可，如下圖：
代碼如下（示例）：
void ListPopFront(ListNode*phead)
{
assert(phead);
ListNode*first = phead->next;
ListNode*second = first->next;
phead->next = second;
second->prev = phead;
}
4.尾刪
現(xiàn)在要刪除d3這個節(jié)點，我們定義一個tail和prev指針分別指向d3和d2，然后把d2后驅(qū)接上head，head前驅(qū)接上d2即可，如下圖：
代碼如下（示例）：
void ListPopBack(ListNode*phead)
{
assert(phead);
assert(phead->next != phead);//要進(jìn)行尾刪至少保證有一個節(jié)點可刪（非head節(jié)點）
ListNode*tail = phead->prev;//頭節(jié)點前驅(qū)指向尾部
ListNode*prev = tail->prev;//通過尾部得到d2地址
prev->next = phead;//d2后驅(qū)head節(jié)點
phead->prev = prev;//head前驅(qū)指向d2節(jié)點
}
5.任意位置插入數(shù)據(jù)
要在某個位置前插入數(shù)據(jù)，你需要先找到那個位置在哪里，我們先寫一個查找函數(shù)
怎么個找法呢？很簡單，定義一個cur指針，然后從d1開始遍歷看有沒有我們想要找的數(shù)據(jù)，遍歷到head節(jié)點結(jié)束。
代碼如下（示例）：
ListNode* ListFind(ListNode*phead, LTDataType x)
{
assert(phead);
ListNode*cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;//遍歷完鏈表都沒有找到就返回空指針
}
找到所需位置后就是進(jìn)行，插入操作
void ListInsert(ListNode*pos, LTDataType x)
{
assert(pos);
ListNode*prev = pos->prev;
ListNode*newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
兩個函數(shù)一起調(diào)用也是很簡單的，比如我現(xiàn)在要在鏈表里數(shù)據(jù)3的位置前插入300，下面兩行代碼即可完成兩個函數(shù)的運(yùn)用。
ListNode*pos = ListFind(plist, 3); ListInsert(pos, 300);
ps:這里找到所需位置指針，你如果需要，也可以通過該指針對該位置的值進(jìn)行修改，比如（返回的指針）->data=n
6.任意位置刪除數(shù)據(jù)
現(xiàn)在要刪除pos位置的數(shù)據(jù)，怎么操作？非常簡單！定義一個prev指向pos前一個節(jié)點，定義一個next指向pos后一個節(jié)點，然后prev和next連起來即可，如圖：
代碼如下（示例）：
void ListErase(ListNode*pos)//指定位置刪除
{
assert(pos);
ListNode*prev = pos->prev;
ListNode*next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);//prev和next連起來了，pos就可以被釋放掉了
}
四、打印鏈表
以上圖為例：要打印一個鏈表，head節(jié)點是不需要打印的，我們只需要打印存儲實際數(shù)據(jù)的d1，d2，d3即可，定義一個變量cur，讓它從d1開始遍歷，到head節(jié)點結(jié)束即可。
代碼如下（示例）：
void ListPrint(ListNode*phead)
{
ListNode*cur = phead->next;
while (cur != phead)
{
printf("%d\n", cur->data);
cur = cur->next;
}
printf("\n");
}
總結(jié)
本文介紹了帶頭循環(huán)雙向鏈表，包括其定義、各個接口函數(shù)、及其遍歷打印。雖然是鏈表中最復(fù)雜的結(jié)構(gòu)，但它的代碼操作卻是最簡單的，希望通過今天的學(xué)習(xí)讀者能有所收獲~更多關(guān)于帶頭雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
本篇文章是對c語言中調(diào)試工具的用法進(jìn)行了匯總，需要的朋友參考下2013-05-05
這篇文章主要介紹了關(guān)閉所有窗口的方法,原理是枚舉所有窗口句柄，然后發(fā)送WM_CLOSE消息來關(guān)閉窗口,需要的朋友可以參考下2014-01-01
這篇文章主要介紹了MFC列表控件CListCtrl使用方法示范,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-07-07
本文主要對紅黑樹進(jìn)行了詳細(xì)介紹，并對其核心功能進(jìn)行了模擬實現(xiàn)。文中的代碼對我們的學(xué)習(xí)或工作有一定的價值，感興趣的小伙伴可以了解一下2021-12-12
這篇文章主要介紹了C++11原子類型與原子操作的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)c++,感興趣的朋友可以了解下2020-08-08
這篇文章主要介紹了C++遞歸實現(xiàn)螺旋數(shù)組的實例代碼，代碼簡單易懂，非常不錯，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-04-04
VS2019安裝配置MFC(安裝vs2019時沒有安裝mfc)
這篇文章主要介紹了VS2019安裝配置MFC(安裝vs2019時沒有安裝mfc)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
這篇文章主要介紹了c++ 智能指針基礎(chǔ)的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)使用c++，感興趣的朋友可以了解下，希望能給你帶來幫助2021-08-08
實例講解C++設(shè)計模式編程中State狀態(tài)模式的運(yùn)用場景
這篇文章主要介紹了實例講解C++設(shè)計模式編程中State狀態(tài)模式的運(yùn)用場景,文章最后的適用性部分則介紹了一些State模式善于處理的情況,需要的朋友可以參考下2016-03-03
C++名字空間是一種描述邏輯分組的機(jī)制,也就是說,如果有一些聲明按照某種準(zhǔn)則在邏輯上屬于同一個模塊,就可以將它們放在同一個名字空間,以表明這個事實,這篇文章主要給大家介紹了關(guān)于C++語言中命名空間 (namespace)的相關(guān)資料,需要的朋友可以參考下2021-08-08