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)文章
下面通過判斷一個數(shù)是偶數(shù)還是奇數(shù)來展示交互遞歸的應(yīng)用，并且此題突出了遞歸跳躍的信任的重要性,需要的朋友可以參考下2012-11-11
C/C++中接收return返回來的數(shù)組元素方法示例
return是C++預(yù)定義的語句，它提供了種植函數(shù)執(zhí)行的一種放大，最近學(xué)習(xí)中遇到了相關(guān)return的內(nèi)容，覺著有必要總結(jié)一下，這篇文章主要給大家介紹了關(guān)于C/C++中如何接收return返回來的數(shù)組元素的相關(guān)資料，需要的朋友可以參考下。2017-12-12
C語言 詳細分析結(jié)構(gòu)體的內(nèi)存對齊
C 數(shù)組允許定義可存儲相同類型數(shù)據(jù)項的變量，結(jié)構(gòu)是 C 編程中另一種用戶自定義的可用的數(shù)據(jù)類型，它允許你存儲不同類型的數(shù)據(jù)項，本篇讓我們來了解C 的結(jié)構(gòu)體內(nèi)存對齊2022-03-03
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單的通訊錄，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-02-02
這篇文章主要介紹了C語言實現(xiàn)計算樹的深度的方法,針對數(shù)據(jù)結(jié)構(gòu)中樹進行操作的方法,在算法設(shè)計中比較常見,需要的朋友可以參考下2014-09-09
當我們編寫C++代碼時，經(jīng)常需要使用頭文件來引入一些常用的函數(shù)、類或者變量，如果一個頭文件被重復(fù)包含，就會導(dǎo)致編譯錯誤或者運行時錯，為了避免發(fā)生，我們需要使用預(yù)處理指令來防止頭文件被重復(fù)包含，常用的預(yù)處理指令有#pragma once和#ifndef,需要的朋友可以參考下2023-05-05
future和promise的作用是在不同線程之間傳遞數(shù)據(jù)，這篇文章主要為大家詳細介紹了C++中future和promise的具體使用，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-05-05
內(nèi)聯(lián)函數(shù)inline與宏定義深入解析
類的內(nèi)斂函數(shù)是一個真正的函數(shù)。使用內(nèi)聯(lián)函數(shù)inline可以完全取代表達式形式的宏定義2013-09-09
C語言的getc()函數(shù)和gets()函數(shù)的使用對比
這篇文章主要介紹了C語言的getc()函數(shù)和gets()函數(shù)的使用對比,從數(shù)據(jù)流中一個是讀取字符一個是讀取字符串,需要的朋友可以參考下2015-08-08
指針提供了對地址操作的一種方法，因此，使用指針可使得?C?語言能夠更高效地實現(xiàn)對計算機底層硬件的操作。另外，通過指針可以更便捷地操作數(shù)組。在一定意義上可以說，指針是?C?語言的精髓2022-04-04