C語言 超詳細介紹與實現(xiàn)線性表中的帶頭雙向循環(huán)鏈表
更新時間：2022年03月29日 16:19:28 作者：李逢溪
帶頭雙向循環(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)反而簡單
一、本章重點
- 帶頭雙向循環(huán)鏈表介紹
- 帶頭雙向循環(huán)鏈表常用接口實現(xiàn)
- 實現(xiàn)接口總結(jié)
- 在線oj訓(xùn)練與詳解
二、帶頭雙向循環(huán)鏈表介紹
2.1什么是帶頭雙向循環(huán)鏈表？
- 帶頭：存在一個哨兵位的頭節(jié)點，該節(jié)點是個無效節(jié)點，不存儲任何有效信息，但使用它可以方便我們頭尾插和頭尾刪時不用判斷頭節(jié)點指向NULL的情況，同時也不需要改變頭指針的指向，也就不需要傳二級指針了。?
- 雙向：每個結(jié)構(gòu)體有兩個指針，分別指向前一個結(jié)構(gòu)體和后一個結(jié)構(gòu)體。
- 循環(huán)：最后一個結(jié)構(gòu)體的指針不再指向NULL，而是指向第一個結(jié)構(gòu)體。（單向）
- 第一個結(jié)構(gòu)體的前指針指向最后一個結(jié)構(gòu)體，最后一個結(jié)構(gòu)體的后指針指向第一個結(jié)構(gòu)體（雙向）。
圖解?
2.2最常用的兩種鏈表結(jié)構(gòu)
- 更具有無頭，單雙向，是否循環(huán)組合起來有8種結(jié)構(gòu)，但最長用的還是無頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表
- 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。?
- 帶頭雙向循環(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)?
3.1結(jié)構(gòu)體創(chuàng)建
typedef int DataType;
typedef struct DListNode
{
DataType data;
DListNode* prev;
DListNode* next;
}DListNode;
3.2帶頭雙向循環(huán)鏈表的初始化?
void DListInint(DListNode** pphead)
{
*pphead = (DListNode*)malloc(sizeof(DListNode));
(*pphead)->next = (*pphead);
(*pphead)->prev = (*pphead);
}
?或者使用返回節(jié)點的方法也能實現(xiàn)初始化
DListNode* DListInit()
{
DListNode* phead = (DListNode*)malloc(sizeof(DListNode));
phead->next = phead;
phead->prev = phead;
return phead;
}
3.3創(chuàng)建新節(jié)點
DListNode* BuyDListNode(DataType x)
{
DListNode* temp = (DListNode*)malloc(sizeof(DListNode));
if (temp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
temp->prev = NULL;
temp->next = NULL;
temp->data = x;
return temp;
}
3.4尾插
void DListPushBack(DListNode* phead,DataType x)
{
DListNode* newnode = BuyDListNode(x);
DListNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
3.5打印鏈表
void DListNodePrint(DListNode* phead)
{
DListNode* cur = phead->next;
while (cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
3.6頭插
void DListNodePushFront(DListNode* phead, DataType x)
{
DListNode* next = phead->next;
DListNode* newnode = BuyDListNode(x);
next->prev = newnode;
newnode->next = next;
newnode->prev = phead;
phead->next = newnode;
}
3.7尾刪
void DListNodePopBack(DListNode* phead)
{
if (phead->next == phead)
{
return;
}
DListNode* tail = phead->prev;
DListNode* prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;
}
3.8頭刪
void DListNodePopFront(DListNode* phead)
{
if (phead->next == phead)
{
return;
}
DListNode* firstnode = phead->next;
DListNode* secondnode = firstnode->next;
secondnode->prev = phead;
phead->next = secondnode;
free(firstnode);
firstnode = NULL;
}
3.9查找data（返回data的節(jié)點地址）
DListNode* DListNodeFind(DListNode* phead, DataType x)
{
DListNode* firstnode = phead->next;
while (firstnode != phead)
{
if (firstnode->data == x)
{
return firstnode;
}
firstnode = firstnode->next;
}
return NULL;
}
3.10在pos位置之前插入節(jié)點
void DListNodeInsert(DListNode* pos, DataType x)
{
DListNode* prev = pos->prev;
DListNode* newnode = BuyDListNode(x);
newnode->next = pos;
newnode->prev = prev;
prev->next = newnode;
pos->prev = newnode;
}
3.11刪除pos位置的節(jié)點
void DListNodeErase(DListNode* pos)
{
DListNode* prev = pos->prev;
DListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
四、實現(xiàn)接口總結(jié)
- 多畫圖：能給清晰展示變化的過程，有利于實現(xiàn)編程。
- 小知識：head->next既可表示前一個結(jié)構(gòu)體的成員變量，有可表示后一個結(jié)構(gòu)體的地址。當head->next作為左值時代表的是成員變量，作右值時代表的是后一個結(jié)構(gòu)體的地址。對于鏈表來說理解這一點非常重要。
- 實踐：實踐出真知
- 帶頭雙向循環(huán)鏈表：相比于單鏈表，它實現(xiàn)起來更簡單，不用向單鏈表一樣分情況討論鏈表的長度。雖然結(jié)構(gòu)較復(fù)雜，但使用起來更簡單，更方便。 ?
五、在線oj訓(xùn)練與詳解
鏈表的中間節(jié)點（力扣）
給定一個頭結(jié)點為?head?的非空單鏈表，返回鏈表的中間結(jié)點。
如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。
輸入：[1,2,3,4,5]
輸出：此列表中的結(jié)點 3 (序列化形式：[3,4,5])
返回的結(jié)點值為 3 。 (測評系統(tǒng)對該結(jié)點序列化表述是 [3,4,5])。
注意，我們返回了一個 ListNode 類型的對象 ans，
這樣：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
來源：力扣（LeetCode）
?思路：快慢指針
取兩個指針，初始時均指向head，一個為快指針（fast）一次走兩步，另一個為慢指針（slow）一次走一步，當快指針滿足fast==NULL（偶數(shù)個節(jié)點）或者fast->next==NULL（奇數(shù)個節(jié)點）時，slow指向中間節(jié)點，返回slow即可。
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast=head;
struct ListNode* slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
到此這篇關(guān)于C語言 超詳細介紹與實現(xiàn)線性表中的帶頭雙向循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言 雙向循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C語言實現(xiàn)洗牌發(fā)牌小程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
算法無處不在，算法是程序的靈魂，而數(shù)據(jù)結(jié)構(gòu)則是程序的骨架，二者共同構(gòu)成了程序，那么如何評估算法的性能呢？理論上可以通過計算時間復(fù)雜度的方法來評估，但這是理性的認識，我們還有一種直觀的評估方法，那就是程序執(zhí)行的時間2022-08-08
這篇文章主要是想和大家一起聊聊來C++中的四種類型轉(zhuǎn)換?：const_cast、static_cast、reinterpret_cast和dynamic_cast，感興趣的可以了解一下2022-12-12
在計算機編程中,字符串處理是一項常見而重要的任務(wù),C語言的string.h頭文件提供了一系列函數(shù)和工具,用于對字符串進行操作和處理,本文將對string.h頭文件中的所有函數(shù)進行全面介紹,包括它們的功能和使用方法,以幫助大家更好地理解和利用該頭文件2023-12-12
這篇文章主要介紹了C++ 常量成員常量返回值詳解,需要的朋友可以參考下2017-06-06
單鏈表是后面要學(xué)的雙鏈表以及循環(huán)鏈表的基礎(chǔ)，要想繼續(xù)深入了解數(shù)據(jù)結(jié)構(gòu)以及C語言，我們就要奠定好這塊基石！接下來就和我一起學(xué)習(xí)吧2022-04-04
C++中malloc與free、new與delete的詳解與應(yīng)用
今天小編就為大家分享一篇關(guān)于C++中malloc與free、new與delete的詳解與應(yīng)用，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
Objective-C中使用STL標準庫Queue隊列的方法詳解
這篇文章主要介紹了Objective-C中使用STL標準庫Queue隊列的方法,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友參考下吧2024-01-01
寫一個日期計算器是一個很有現(xiàn)實意義的,比如,我想弄一個倒計時或者你女朋友問你和她認識多少天了,這就需要讓兩個日期相減,又或者和別人約定幾年以后怎么怎么樣,這就得知道那一天的日期,接下來小編借給大家介紹一下如何用C++寫一個日期計算器,感興趣的朋友可以動手嘗試2024-04-04
這篇文章主要介紹了C++中引用傳遞與指針傳遞的區(qū)別(面試常見),需要的朋友可以參考下2018-03-03