目錄
文章目錄
前言
1.結(jié)構(gòu)與優(yōu)勢(shì)
2.鏈表實(shí)現(xiàn)? ? ??
2.1 定義鏈表
2.2 創(chuàng)建頭節(jié)點(diǎn)
2.3 尾插
2.4 輸出鏈表
2.5 尾刪
2.6 頭插
2.7頭刪
2.8?節(jié)點(diǎn)個(gè)數(shù)
2.9?查找
2.10?位置插入
2.11 位置刪除
2.12 銷(xiāo)毀鏈表
?3. 源碼
總結(jié)
前言
? ? ? ? 鏈表一共有8種結(jié)構(gòu)，但最常用的就是無(wú)頭單向鏈表、和帶頭雙向循環(huán)鏈表。單鏈表的結(jié)構(gòu)存在著很多的缺陷，但它是許多數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，在刷題中經(jīng)常見(jiàn)到，而帶頭雙向循環(huán)鏈表彌補(bǔ)了單鏈表所有的缺陷，可以說(shuō)是一個(gè)完美結(jié)構(gòu)，雖然相對(duì)于單鏈表來(lái)說(shuō)結(jié)構(gòu)更復(fù)雜，但它的特性使它的實(shí)現(xiàn)邏輯較為簡(jiǎn)單，今天我就向大家一一介紹。
1.結(jié)構(gòu)與優(yōu)勢(shì)
結(jié)構(gòu)：
優(yōu)勢(shì)：
- 可以實(shí)現(xiàn)快速的插入和刪除操作：由于鏈表的特性，插入和刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)，不需要像數(shù)組一樣需要移動(dòng)其他元素。
- 可以實(shí)現(xiàn)快速的遍歷操作：雙向鏈表可以通過(guò)前向或后向的指針進(jìn)行遍歷，而不需要像單向鏈表那樣只能從頭節(jié)點(diǎn)開(kāi)始遍歷。
- 可以實(shí)現(xiàn)雙向遍歷：雙向鏈表可以通過(guò)前向和后向的指針進(jìn)行雙向遍歷，可以方便地從任意一個(gè)節(jié)點(diǎn)開(kāi)始向前或向后遍歷。
- 可以實(shí)現(xiàn)循環(huán)遍歷：由于鏈表的循環(huán)性質(zhì)，可以通過(guò)不斷移動(dòng)指針進(jìn)行循環(huán)遍歷，不需要額外的循環(huán)條件判斷。
- 可以實(shí)現(xiàn)更多高級(jí)功能：帶頭雙向循環(huán)鏈表可以實(shí)現(xiàn)更多高級(jí)功能，如反轉(zhuǎn)鏈表、查找倒數(shù)第k個(gè)節(jié)點(diǎn)等。
總結(jié)，帶頭雙向循環(huán)鏈表具有靈活性和高效性，適用于需要頻繁插入、刪除和遍歷操作的場(chǎng)景。
2.鏈表實(shí)現(xiàn)? ? ??
?2.1 定義鏈表
????????步入正題，帶頭雙向循環(huán)鏈表，首先它是雙向的，什么是雙向呢？在單鏈表定義時(shí)會(huì)有指向下一個(gè)節(jié)點(diǎn)的指針，而雙向鏈表有兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，一個(gè)指向上一個(gè)節(jié)點(diǎn)，可以實(shí)現(xiàn)前后雙向遍歷。
typedef struct ListNode
{
int data;
struct ListNode* next;//指向下一個(gè)節(jié)點(diǎn)的指針
struct ListNode* prev;//指向上一個(gè)節(jié)點(diǎn)的指針
}LN;?2.2 創(chuàng)建頭節(jié)點(diǎn)
? ? ? ? ?和無(wú)頭單向鏈表不同，帶頭雙向循環(huán)鏈表它有頭節(jié)點(diǎn)，所以在開(kāi)始執(zhí)行各操作之前，我們先創(chuàng)建一個(gè)頭節(jié)點(diǎn)并初始化。
? ? ? ? 創(chuàng)建頭節(jié)點(diǎn)需要新建一個(gè)節(jié)點(diǎn)，在其他插入接口中也需要新建節(jié)點(diǎn)，那我們就封裝一個(gè)創(chuàng)建新節(jié)點(diǎn)的函數(shù)，最后返回新建節(jié)點(diǎn)的地址。
LN* BuyListNode(Datatype x)
{
LN* newnode = (LN*)malloc(sizeof(LN));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}?????????和無(wú)頭單鏈表不同，這里帶有頭節(jié)點(diǎn)，就需要對(duì)頭節(jié)點(diǎn)進(jìn)行初始化一下，雖然在創(chuàng)建節(jié)點(diǎn)時(shí)就已經(jīng)對(duì)節(jié)點(diǎn)進(jìn)行了初始化，但頭節(jié)點(diǎn)的初始化與新建節(jié)點(diǎn)初始化需求不同，所有這里需要單獨(dú)進(jìn)行初始化初始化節(jié)點(diǎn)時(shí)可以使用雙指針，也可以直接返回頭節(jié)點(diǎn)地址。
LN* InItNode()
{
LN* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}?????????頭節(jié)點(diǎn)進(jìn)行初始化時(shí)，只需將兩個(gè)指針指向自己，然后返回頭節(jié)點(diǎn)的地址即可。
?2.3 尾插
????????建好頭節(jié)點(diǎn)后要怎么鏈接節(jié)點(diǎn)呢？我們先寫(xiě)一個(gè)尾插來(lái)體驗(yàn)一下它的便捷。在單鏈表中想要進(jìn)行尾插，還需要遍歷一遍鏈表找到尾節(jié)點(diǎn)，而帶頭雙向循環(huán)鏈表就不需要，可以通過(guò)頭節(jié)點(diǎn)直接找到尾節(jié)點(diǎn)：tail? =? phead -> prev ;頭節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)就是尾節(jié)點(diǎn)。
我們新建一個(gè)節(jié)點(diǎn)：
?????????要想插入就需要把尾節(jié)點(diǎn)的next改為新節(jié)點(diǎn)的地址，新節(jié)點(diǎn)的prev改為尾節(jié)點(diǎn)tail的地址
????????再把新節(jié)點(diǎn)的next改為頭節(jié)點(diǎn)的地址，把頭節(jié)點(diǎn)的prev改位新節(jié)點(diǎn)的地址。
?
?整體邏輯就是這樣，具體代碼如下：
void PushBack(LN* phead, Datatype x)
{
assert(phead);
LN* tail = phead->prev;
LN* newnode = BuyListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}2.4 輸出鏈表
? ? ? ? 為了便于后續(xù)的測(cè)試，我們先寫(xiě)一個(gè)函數(shù)用于輸出鏈表數(shù)據(jù)。輸出函數(shù)很簡(jiǎn)單。
void PrintList(LN* phead)
{
assert(phead);
LN* cur = phead->next;//有效節(jié)點(diǎn)不包含頭節(jié)點(diǎn)
printf("phead <->");
while (cur != phead)
{
printf(" %d <->", cur->data);
cur = cur->next;
}
}? ? ? ? ?這里需要注意的是遍歷鏈表時(shí)的循環(huán)條件，由于它是循環(huán)鏈表，所有結(jié)束條件有所變化。其次是輸出數(shù)據(jù)時(shí)不需要輸出頭節(jié)點(diǎn)的數(shù)據(jù)，頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)才是有效數(shù)據(jù)。
我們可以來(lái)測(cè)試一下：
void test1()
{
LN* plist = InItNode();
PushBack(plist, 1);
PushBack(plist, 2);
PushBack(plist, 3);
PushBack(plist, 4);
PushBack(plist, 5);
PrintList(plist);
}
int main()
{
test1();
return 0;
}?輸出效果如下：
?2.5 尾刪
????????基本邏輯理解后，可以先自主嘗試寫(xiě)一下尾刪。思路也是非常的簡(jiǎn)單，但要注意的是，有效節(jié)點(diǎn)為0的情況。把尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)next改為頭節(jié)點(diǎn)地址，頭節(jié)點(diǎn)的prev改為尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，最后釋放掉尾節(jié)點(diǎn)的空間。
void PopBack(LN* phead)
{
assert(phead);
assert(phead->next != phead);
LN* tail = phead->prev;
LN* tailprev = tail->prev;
tailprev->next = phead;
phead->prev = tailprev;
free(tail);
}2.6 頭插
????????接下來(lái)我們進(jìn)行頭插操作，我們使用的是帶頭的形式，所有這里進(jìn)行頭插時(shí)，不像單鏈表那樣需要使用二級(jí)指針，我們需要改的是頭節(jié)點(diǎn)中的內(nèi)容，所有使用一級(jí)指針就可以解決。
?????????此外頭插時(shí)一定要注意操作的次序，避免后續(xù)操作有誤。例如：
? ? ? ? 如果不提前保存第一個(gè)節(jié)點(diǎn)的地址， 就會(huì)導(dǎo)致新節(jié)點(diǎn)鏈接后續(xù)節(jié)點(diǎn)時(shí)找節(jié)點(diǎn)麻煩或出現(xiàn)錯(cuò)誤。
?正確的順序如下圖：
?代碼實(shí)現(xiàn)：
void PushFront(LN* phead,Datatype x)
{
assert(phead);
LN* newnode = BuyListNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
newnode->prev = phead;
phead->next = newnode;
}?????????當(dāng)然新手不建議這樣寫(xiě)，這樣寫(xiě)很容易把人搞暈，我們可以先保存第一個(gè)節(jié)點(diǎn)的地址，這樣就不會(huì)搞錯(cuò)。代碼如下：
void PushFront(LN* phead,Datatype x)
{
assert(phead);
LN* newnode = BuyListNode(x);
LN* first = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}2.7頭刪
? ? ? ? 這里頭刪也是非常簡(jiǎn)單，為了避免出錯(cuò)，我們可以額外創(chuàng)建兩個(gè)指針，記錄第一個(gè)節(jié)點(diǎn)和第二個(gè)節(jié)點(diǎn)，邏輯較為簡(jiǎn)單，就不再畫(huà)邏輯圖，代碼如下：
void PopFront(LN* phead)
{
assert(phead);
assert(phead->next != phead);
LN* first = phead->next;
LN* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
}需要額外注意鏈表為空的情況。
2.8?節(jié)點(diǎn)個(gè)數(shù)
????????統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)很簡(jiǎn)單，和輸出鏈表數(shù)據(jù)一樣遍歷一下鏈表統(tǒng)計(jì)鏈表個(gè)數(shù)代碼如下：
int Listsize(LN* phead)
{
assert(phead);
int sz = 0;
LN* cur = phead->next;
while (cur != phead)
{
sz++;
cur = cur->next;
}
return sz;
}?????????有人可能會(huì)想：用頭節(jié)點(diǎn)統(tǒng)計(jì)不也可以嗎？還不用額外的去寫(xiě)一個(gè)函數(shù)。初始時(shí)把頭節(jié)點(diǎn)的data初始化為0，每次插入data++。這種方式嚴(yán)格來(lái)說(shuō)是不可以的，我們?cè)趯?xiě)鏈表時(shí)每個(gè)節(jié)點(diǎn)不一定存儲(chǔ)的是整形，也可能是字符型，雖然也能計(jì)數(shù)，但如果節(jié)點(diǎn)是1000呢？數(shù)據(jù)就溢出了，所以不建議那樣寫(xiě)。
?2.9?查找
????????查找也比較簡(jiǎn)單，不再多說(shuō)，代碼如下：
LN* ListFind(LN* phead, Datatype x)
{
assert(phead);
LN* cur = phead->next;
while (cur!=phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}?2.10?位置插入
?????????帶頭雙向循環(huán)鏈表在位置插入時(shí)沒(méi)有像單鏈表那樣有位置前插入，位置后插入。這里的位置插入都是位置前插入，由于它是循環(huán)雙向的鏈表，不像單鏈表那樣不可以向前遍歷，雙向循環(huán)鏈表可以任意插入，所以位置后插入也并沒(méi)有什么意義，就統(tǒng)一默認(rèn)位置前插入。
? ? ? ? 位置插入操作和上述的插入操作很類(lèi)似，推薦額外創(chuàng)建一個(gè)指針保存節(jié)點(diǎn)信息，就可以避免操作時(shí)次序不當(dāng)造成程序錯(cuò)誤，代碼如下：
void ListInsert(LN* pos, Datatype x)
{
assert(pos);
LN* newnode = BuyListNode(x);
LN* posprev = pos->prev;
posprev->next = newnode;
newnode->prev = posprev;
newnode->next = pos;
pos->prev = newnode;
}2.11 位置刪除
????????位置刪除也一樣很簡(jiǎn)單，我們多創(chuàng)建兩個(gè)指針變量存儲(chǔ)節(jié)點(diǎn)信息，就可以有效避免次序不當(dāng)導(dǎo)致程序錯(cuò)誤的問(wèn)題。代碼如下：
void PosErase(LN* pos)
{
assert(pos);
LN* posprev = pos->prev;
LN* posnext = pos->next;
free(pos);
posprev->next = posnext;
posnext->prev = posprev;
}?2.12 銷(xiāo)毀鏈表
? ? ? ? 在鏈表使用完以后就要銷(xiāo)毀，銷(xiāo)毀也比較簡(jiǎn)單，代碼如下：
void DestoryList(LN* phead)
{
assert(phead);
LN* cur = phead->next;
while (cur != phead)
{
LN* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}?????????這樣還需要注意的一點(diǎn)，在銷(xiāo)毀鏈表的這個(gè)函數(shù)里雖然銷(xiāo)毀了頭節(jié)點(diǎn)，但是在頭節(jié)點(diǎn)創(chuàng)建之初使用了結(jié)構(gòu)體指針，在后續(xù)操作中都是通過(guò)這個(gè)指針將鏈表傳遞給函數(shù)，所以最后在調(diào)用銷(xiāo)毀鏈表函數(shù)之后要將指向頭節(jié)點(diǎn)的指針置為NULL，避免出現(xiàn)野指針。當(dāng)然這里也可以使用二級(jí)指針在函數(shù)里將這個(gè)指針置為NULL。
?3. 源碼
List.c
#include"List.h"
LN* BuyListNode(Datatype x)
{
LN* newnode = (LN*)malloc(sizeof(LN));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
LN* InItNode()
{
LN* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void PrintList(LN* phead)
{
assert(phead);
LN* cur = phead->next;
printf("phead <->");
while (cur != phead)
{
printf(" %d <->", cur->data);
cur = cur->next;
}
printf("\n");
}
void PushBack(LN* phead, Datatype x)
{
assert(phead);
LN* tail = phead->prev;
LN* newnode = BuyListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void PopBack(LN* phead)
{
assert(phead);
assert(phead->next != phead);
LN* tail = phead->prev;
LN* tailprev = tail->prev;
tailprev->next = phead;
phead->prev = tailprev;
free(tail);
}
void PushFront(LN* phead,Datatype x)
{
assert(phead);
/*LN* newnode = BuyListNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
newnode->prev = phead;
phead->next = newnode;*/
LN* newnode = BuyListNode(x);
LN* first = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
void PopFront(LN* phead)
{
assert(phead);
assert(phead->next != phead);
LN* first = phead->next;
LN* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
}
int Listsize(LN* phead)
{
assert(phead);
int sz = 0;
LN* cur = phead->next;
while (cur != phead)
{
sz++;
cur = cur->next;
}
return sz;
}
LN* ListFind(LN* phead, Datatype x)
{
assert(phead);
LN* cur = phead->next;
while (cur!=phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
void ListInsert(LN* pos, Datatype x)
{
assert(pos);
LN* newnode = BuyListNode(x);
LN* posprev = pos->prev;
newnode->next = pos;
pos->prev = newnode;
newnode->prev = posprev;
posprev->next = newnode;
}
void PosErase(LN* pos)
{
assert(pos);
LN* posprev = pos->prev;
LN* posnext = pos->next;
free(pos);
posprev->next = posnext;
posnext->prev = posprev;
}
void DestoryList(LN* phead)
{
assert(phead);
LN* cur = phead->next;
while (cur != phead)
{
LN* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}?List.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Datatype;
typedef struct ListNode
{
int data;
struct ListNode* next;
struct ListNode* prev;
}LN;
LN* BuyListNode(Datatype x);
LN* InItNode();
void PrintList(LN* phead);
void PushBack(LN* phead,Datatype x);
void PopBack(LN* phead);
void PushFront(LN* phead, Datatype x);
void PopFront(LN* phead);
LN* ListFind(LN* phead, Datatype x);
int Listsize(LN* phead);
void ListInsert(LN* pos, Datatype x);
void PosErase(LN* pos);
void DestoryList(LN* phead);?test.c
#include"List.h"
void test1()
{
LN* plist = InItNode();
PushBack(plist, 1);
PushBack(plist, 2);
PushBack(plist, 3);
PushBack(plist, 4);
PushBack(plist, 5);
PushFront(plist, 0);
PopBack(plist);
ListInsert(plist, 10);
LN* pos = ListFind(plist, 10);
ListInsert(pos, 11);
PosErase(pos);
PrintList(plist);
DestoryList(plist);
plist = NULL;
}
void test2()
{
LN* plist = InItNode();
PushBack(plist, 1);
PushBack(plist, 2);
PushBack(plist, 3);
PushBack(plist, 4);
PushBack(plist, 5);
//PushFront(plist, 0);
PopFront(plist);
PrintList(plist);
}
int main()
{
test1();
return 0;
}?文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-628165.html
總結(jié)
????????帶頭雙向循環(huán)鏈表作為一種數(shù)據(jù)結(jié)構(gòu)，在解決問(wèn)題時(shí)展現(xiàn)了其獨(dú)特的優(yōu)勢(shì)。通過(guò)快速的插入和刪除操作，以及靈活的雙向遍歷和循環(huán)遍歷能力，它為我們提供了一種高效、靈活的數(shù)據(jù)組織方式。在實(shí)際應(yīng)用中，我們可以充分發(fā)揮帶頭雙向循環(huán)鏈表的特性，優(yōu)化算法設(shè)計(jì)，提高程序的效率和可維護(hù)性。通過(guò)深入學(xué)習(xí)和掌握帶頭雙向循環(huán)鏈表，我們可以更好地解決實(shí)際問(wèn)題，提升自己的編程能力。希望本文能夠幫助讀者對(duì)帶頭雙向循環(huán)鏈表有更深入的理解，并在實(shí)踐中得到應(yīng)用。最后，感謝閱讀！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-628165.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門(mén)指南：帶頭雙向循環(huán)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
