C++零基礎(chǔ)精通數(shù)據(jù)結(jié)構(gòu)之帶頭雙向循環(huá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)最復雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復雜，但是使用代碼實現(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)的復雜性，我們通常還是會使用邏輯結(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)文章
這篇文章主要為大家詳細介紹了C語言之包含min函數(shù)的棧，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
C語言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實現(xiàn)
這篇文章主要介紹了C語言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實現(xiàn),,文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的朋友可以參考一下2022-09-09
C語言數(shù)組實現(xiàn)學生信息管理系統(tǒng)設(shè)計
這篇文章主要為大家詳細介紹了C語言數(shù)組實現(xiàn)學生信息管理系統(tǒng)設(shè)計，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
C語言中的setlinebuf()、utmpname()、rewind函數(shù)使用
這篇文章主要介紹了C語言中的setlinebuf()、utmpname()、rewind函數(shù)使用,是C語言中操作文件的一些基本函數(shù),需要的朋友可以參考下2015-08-08
本文主要介紹C語言邏輯運算符,這里詳細講解了C語言中的邏輯運算符,并提供了實例代碼以便大家學習參考,希望能幫助有需要的小伙伴2016-07-07
下面小編就為大家?guī)硪黄獪\談VS中添加頭文件時顯示無法找到文件的問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
C++?OpenCV實現(xiàn)boxfilter方框濾波的方法詳解
box?filter的作用很簡單，即對局部區(qū)域求平均，并把值賦給某個點，一般我們賦給區(qū)域中心。本文將用C++實現(xiàn)boxfilter方框濾波，需要的可以了解一下2022-10-10
學習過C語言的小伙伴知道：C語言是面向過程的，關(guān)注的是過程，分析出求解問題的步驟，通過函數(shù)調(diào)用逐步解決問題，這篇文章主要介紹了C++面向?qū)ο笾袠?gòu)造函數(shù)使用2022-10-10
Qt圖形圖像開發(fā)之高性能曲線圖模塊QCustomplot庫詳細使用方法與實例(支持動、靜曲線圖)
這篇文章主要介紹了Qt圖形圖像開發(fā)之高性能曲線圖模塊QCustomplot庫詳細使用方法與實例(支持動、靜曲線圖),需要的朋友可以參考下2020-03-03
C++實現(xiàn)LeetCode(12.整數(shù)轉(zhuǎn)化成羅馬數(shù)字)
這篇文章主要介紹了C++實現(xiàn)LeetCode(12.整數(shù)轉(zhuǎn)化成羅馬數(shù)字),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07