C++零基礎(chǔ)精通數(shù)據(jù)結(jié)構(gòu)之帶頭雙向循環(huán)鏈表
更新時間：2022年03月30日 16:43:41 作者：雪芙花
帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單
與單鏈表的區(qū)別
單向/雙向
單向：只有一個ｎｅｘｔ指針，只指向下一位元素
雙向：有兩個指針，指向上一位和下一位元素，尋找前一節(jié)點和后一節(jié)點很便利
帶頭/不帶頭
帶頭：在本來的頭結(jié)點之前還有一個哨兵衛(wèi)節(jié)點作為頭節(jié)點，它的址域指針指向頭節(jié)點，值域不做使用
不帶頭：沒有哨兵衛(wèi)頭節(jié)點，在尾刪尾插等問題中要考慮頭結(jié)點的情況（局限）
循環(huán)/非循環(huán)
循環(huán)：頭結(jié)點會與尾節(jié)點相連
非循環(huán)：頭結(jié)點不與尾節(jié)點相連
代碼的實現(xiàn)
接口
// 創(chuàng)建鏈表（鏈表初始化） ListNode* ListCreate(); //創(chuàng)建節(jié)點 ListNode* BuyListNode(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的前面進行插入 void ListInsert(ListNode* pos, LTDataType x); // 雙向鏈表刪除pos位置的節(jié)點 void ListErase(ListNode* pos);
節(jié)點的構(gòu)造
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
初始化鏈表
// 創(chuàng)建鏈表（初始化）
ListNode* ListCreate()
{
//開辟哨兵衛(wèi)頭結(jié)點
ListNode* plist = (ListNode*)malloc(sizeof(ListNode));
if (plist == NULL)//失敗打印錯誤信息并結(jié)束進程
{
perror("ListCreat fail:");
exit(-1);
}
plist->next = plist;
plist->prev = plist;
return plist;
}
開辟節(jié)點
//創(chuàng)建節(jié)點
ListNode* BuyListNode(LTDataType x)
{
//創(chuàng)建節(jié)點
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)//失敗打印錯誤信息并結(jié)束進程
{
perror("creatnode fail:");
exit(-1);
}
newnode->data = x;
//初始化結(jié)點
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
銷毀鏈表
注：動態(tài)開辟的鏈表空間，在不使用后需要將之釋放，避免造成內(nèi)存泄漏
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{
//斷言傳入指針不為NULL
assert(pHead);
ListNode* cur = pHead;
pHead->prev->next = NULL;
while (cur!=NULL)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
return;
}
打印鏈表
// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
//斷言傳入指針不為NULL
assert(pHead);
//創(chuàng)建尋址指針
ListNode* cur = pHead->next;
//循環(huán)遍歷鏈表
while (cur != pHead)
{
//打印數(shù)據(jù)
printf("%d->", cur->data);
//找到下一個節(jié)點
cur = cur->next;
}printf("NULL\n");
return;
}
尾插鏈表
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
//斷言傳入指針不為NULL
assert(pHead);
//創(chuàng)建節(jié)點
ListNode* newnode = BuyListNode(x);
//找到尾節(jié)點
ListNode* tail=pHead->prev;
tail->next = newnode;
newnode->prev = tail;
pHead->prev = newnode;
newnode->next = pHead;
}
尾刪鏈表
尾刪前記錄前一節(jié)點的地址
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
//斷言傳入指針不為NULL
assert(pHead);
//只剩哨兵衛(wèi)頭結(jié)點的情況
if (pHead->prev == pHead)
return;
//記錄尾節(jié)點及其前一節(jié)點
ListNode* tail = pHead->prev;
ListNode* tailprev = tail->prev;
//釋放尾節(jié)點
free(tail);
//構(gòu)建尾節(jié)點前一節(jié)點與哨兵衛(wèi)頭結(jié)點的關(guān)系
tailprev->next = pHead;
pHead->prev = tailprev;
return;
}
頭插鏈表
頭插前記錄哨兵衛(wèi)頭節(jié)點的下一節(jié)點
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
//斷言傳入指針不為NULL
assert(pHead);
//創(chuàng)建節(jié)點
ListNode* newnode = BuyListNode(x);
//記錄哨兵衛(wèi)頭結(jié)點的下一節(jié)點
ListNode* next = pHead->next;
//構(gòu)建各節(jié)點之間的關(guān)系
pHead->next = newnode;
newnode->prev = pHead;
newnode->next = next;
next->prev = newnode;
return;
}
頭刪鏈表
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
//斷言傳入指針不為NULL
assert(pHead);
//只剩哨兵衛(wèi)頭結(jié)點的情況
if (pHead->next == pHead)
return;
//記錄哨兵衛(wèi)頭結(jié)點下一節(jié)點及其的下一節(jié)點
ListNode* next = pHead->next;
ListNode* nextNext = next->next;
//釋放節(jié)點
free(next);
pHead->next = nextNext;
nextNext->prev = pHead;
return;
}
查找鏈表
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
//斷言傳入指針不為NULL
assert(pHead);
//創(chuàng)建尋址指針
ListNode* cur = pHead->next;
while (cur != pHead)
{
//比較數(shù)據(jù)
if (cur->data == x)
return cur;
//找到下一個節(jié)點
cur = cur->next;
}
//沒找到則返回NULL
return NULL;
}
鏈表pos位置的刪除
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
return;
}
總結(jié)
我們在實帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單現(xiàn)的時候可以看出其實帶頭雙向循環(huán)鏈表實現(xiàn)起來并不難，而且在雙向循環(huán)特點的加持下，在一些方面顯得格外方便。
但是因為帶頭雙向循環(huán)鏈表結(jié)構(gòu)的復(fù)雜性，我們通常還是會使用邏輯結(jié)構(gòu)相對簡單的單鏈表，并且在oj題上考的最多的也是單鏈表。
但我們?nèi)砸炀氄莆諑ь^雙向循環(huán)鏈表的結(jié)構(gòu)和實現(xiàn)方式，因為這是一種特別且方便的結(jié)構(gòu)，且用處十分強大。
到此這篇關(guān)于C++零基礎(chǔ)精通數(shù)據(jù)結(jié)構(gòu)之帶頭雙向循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C++ 帶頭雙向循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)幀間差分法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
構(gòu)造函數(shù)主要作用在于創(chuàng)建對象時為對象的成員屬性賦值，構(gòu)造函數(shù)由編譯器自動調(diào)用,無須手動調(diào)用；析構(gòu)函數(shù)主要作用在于對象銷毀前系統(tǒng)自動調(diào)用，執(zhí)行一些清理工作2023-02-02
這篇文章主要為大家詳細介紹了用C語言實現(xiàn)簡單五子棋小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
這篇文章主要介紹了C語言、C++中的union用法總結(jié),本文講解了什么是union、C中使用union、當(dāng)union遇到對象等內(nèi)容,需要的朋友可以參考下2014-10-10
背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高2022-04-04
VC實現(xiàn)動態(tài)菜單的創(chuàng)建方法
這篇文章主要介紹了VC實現(xiàn)動態(tài)菜單的創(chuàng)建方法,需要的朋友可以參考下2014-07-07
俄羅斯方塊是一個最初由阿列克謝帕吉特諾夫在蘇聯(lián)設(shè)計和編程的益智類視頻游戲。本文將利用Matlab實現(xiàn)這一經(jīng)典的小游戲，需要的可以參考一下2022-03-03
關(guān)于C++中菱形繼承和虛繼承的問題總結(jié)
C++的三大特性為：封裝，繼承，多態(tài)。但是在繼承中，存在一些使用方面的問題需要注意，下面這篇文章主要給大家總結(jié)介紹了關(guān)于C++中菱形繼承和虛繼承的問題，需要的朋友可以參考借鑒，下面來一起看看吧。2017-08-08
這篇文章主要介紹了C/C++中的typedef和#define詳解的相關(guān)資料,需要的朋友可以參考下2017-02-02
C++實現(xiàn)轉(zhuǎn)置矩陣的循環(huán)
大家好，本篇文章主要講的是C++實現(xiàn)轉(zhuǎn)置矩陣的循環(huán)，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01