前言
??前面我們學(xué)習(xí)了單鏈表的實(shí)現(xiàn)，我們發(fā)現(xiàn)它在進(jìn)行從后往前查找的時(shí)候有很大的不便，為了解決這個(gè)問(wèn)題，雙向鏈表油然而生。它可以很好的解決單鏈表無(wú)法從后往前查找的困難。
雙向鏈表的結(jié)構(gòu)
??如圖所示，它是有兩個(gè)指針域，一個(gè)指向后一個(gè)結(jié)點(diǎn)，一個(gè)指向前一個(gè)結(jié)點(diǎn)。它存儲(chǔ)了前一個(gè)結(jié)點(diǎn)的地址與后一個(gè)結(jié)點(diǎn)的地址，所以可以很方便的進(jìn)行向前遍歷或者向后遍歷。同時(shí)它還是一個(gè)循環(huán)鏈表，可以通過(guò)第一個(gè)結(jié)點(diǎn)直接找到最后一個(gè)結(jié)點(diǎn)。
功能的解析及實(shí)現(xiàn)
1. 雙向鏈表的創(chuàng)建
??就像前文所說(shuō)，它包含了兩個(gè)指針域和一個(gè)數(shù)據(jù)域，用來(lái)存放它前一個(gè)結(jié)點(diǎn)的地址和后一個(gè)結(jié)點(diǎn)的地址以及本身的數(shù)據(jù)。
typedef struct LTNode
{
LTDataType data;
struct LTNode* prev;
struct LTNode* next;
}LTNode;
2. 創(chuàng)建頭節(jié)點(diǎn)（初始化）
??此次雙向鏈表的結(jié)構(gòu)我是采用了帶頭結(jié)點(diǎn)的結(jié)構(gòu)，好處就是頭節(jié)點(diǎn)是malloc出來(lái)的，是在堆區(qū)上存放，不會(huì)因?yàn)槌隽撕瘮?shù)就被銷毀，也意味著后續(xù)的各種操作我們只需要傳遞一級(jí)指針就會(huì)有實(shí)現(xiàn)單鏈表時(shí)傳遞二級(jí)指針的效果。
LTNode* ListInit()
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if (phead == NULL)
{
return NULL;
}
phead->prev = phead;
phead->next = phead;
return phead;
}
3. 創(chuàng)建新結(jié)點(diǎn)
??每次插入新的數(shù)據(jù)都需要開辟新的結(jié)點(diǎn)，因此把它單獨(dú)拿出來(lái)放到一個(gè)函數(shù)中實(shí)現(xiàn)。
LTNode* BuyListNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
return NULL;
}
newnode->data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
4. 尾插
??因?yàn)槭茄h(huán)鏈表，我們可以通過(guò)第一個(gè)頭節(jié)點(diǎn)直接找到尾結(jié)點(diǎn)，而在連接的時(shí)候，需要將新結(jié)點(diǎn)分別連接到頭節(jié)點(diǎn)的prev以及尾結(jié)點(diǎn)的next，同時(shí)自身的prev存放尾結(jié)點(diǎn)的地址，next存放頭節(jié)點(diǎn)的地址。如圖：
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyListNode(x);
newnode->data = x;
newnode->next = phead;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
}
5. 尾刪
??在創(chuàng)建頭節(jié)點(diǎn)時(shí)，我們是將頭節(jié)點(diǎn)的prev與next都指向了它自身，因此我們可以通過(guò)頭節(jié)點(diǎn)的next指向的是不是自身來(lái)判斷是否為存放了數(shù)據(jù)。(頭節(jié)點(diǎn)自身不存放數(shù)據(jù))。與尾插類似，如圖：
void ListPopBack(LTNode* phead)
{
assert(phead);
if (phead->next == phead)//判斷鏈表是否存放了數(shù)據(jù)
{
return;
}
LTNode* tail = phead->prev;
LTNode* prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;
}
6. 頭插
??與尾插類似，只不過(guò)這個(gè)放到了最前面。在尾插是我們是有tail與phead來(lái)與新結(jié)點(diǎn)連接，頭插也一樣。先保存當(dāng)前的第一個(gè)結(jié)點(diǎn)地址，然后再將新結(jié)點(diǎn)連接到頭節(jié)點(diǎn)與原第一個(gè)結(jié)點(diǎn)的中間即可。
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* next = phead->next;//保存當(dāng)前的第一個(gè)結(jié)點(diǎn)地址
LTNode* newnode = BuyListNode(x);
newnode->prev = phead;
phead->next = newnode;
newnode->next = next;
next->prev = newnode;
}
7. 頭刪
??我們只需要保存第一個(gè)結(jié)點(diǎn)與第二節(jié)結(jié)點(diǎn)的地址，然后在將第二個(gè)與頭節(jié)點(diǎn)連接，再釋放掉第一個(gè)結(jié)點(diǎn)即可。同時(shí)還需要判斷鏈表是否為空(即有沒有元素存放其中)。
void ListPopFront(LTNode* phead)
{
//assert(phead->next != phead); //暴力解決
//溫和解決
if (phead->next == phead)
{
return;
}
LTNode* prev = phead->next;
LTNode* next = prev->next;
phead->next = next;
next->prev = phead;
free(prev);
prev = NULL;
}
8. 查找
??依次遍歷鏈表即可，從phead開始，一直到再次遇到phead結(jié)束（循環(huán)鏈表）。
LTNode* ListFind(LTNode* phead, LTDataType x)
{
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
printf("該元素不存在\n");
return NULL;
}
9. 在pos位置前插入
??與頭插相似，這里只需要用prev保存pos位置的前一個(gè)結(jié)點(diǎn)地址，然后將新結(jié)點(diǎn)與prev與pos相連接即可。
void ListInsert(LTNode* pos, LTDataType x)
{
LTNode* prevPos = pos->prev;
LTNode* newnode = BuyListNode(x);
newnode->next = pos;
pos->prev = newnode;
newnode->prev = prevPos;
prevPos->next = newnode;
}
10. 刪除pos位置的結(jié)點(diǎn)
??保存pos的前一個(gè)結(jié)點(diǎn)地址與后一個(gè)結(jié)點(diǎn)地址，然后將彼此相連接，然后free掉pos結(jié)點(diǎn)就完成了。
void ListErase(LTNode* pos)
{
LTNode* nextPos = pos->next;
LTNode* prevPos = pos->prev;
nextPos->prev = prevPos;
prevPos->next = nextPos;
free(pos);
pos = NULL;
}
11. 銷毀
??動(dòng)態(tài)開辟的結(jié)點(diǎn)在最后結(jié)束時(shí)都需要進(jìn)行釋放，防止出現(xiàn)內(nèi)存泄漏。用cur保存當(dāng)前準(zhǔn)備要釋放的結(jié)點(diǎn)，用next保存cur的下一個(gè)結(jié)點(diǎn)，釋放完cur后，再將cur指向next，進(jìn)行循環(huán)。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-434446.html
void ListDestroy(LTNode* phead)
{
LTNode* cur = phead;
LTNode* next = cur->next;
while (cur)
{
free(cur);
cur = NULL;
if (cur != NULL)
{
cur = next;
next = next->next;
}
}
}
代碼實(shí)現(xiàn)
1.ListNode.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;
typedef struct LTNode
{
LTDataType data;
struct LTNode* prev;
struct LTNode* next;
}LTNode;
// 創(chuàng)建返回鏈表的頭結(jié)點(diǎn).
LTNode* ListInit();
// 雙向鏈表銷毀
void ListDestroy(LTNode* phead);
// 雙向鏈表打印
void ListPrint(LTNode* phead);
// 雙向鏈表尾插
void ListPushBack(LTNode* phead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(LTNode* phead);
// 雙向鏈表頭插
void ListPushFront(LTNode* phead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(LTNode* phead);
// 雙向鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x);
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(LTNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(LTNode* pos);
2. ListNode.c
#include"ListNode.h"
LTNode* BuyListNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
return NULL;
}
newnode->data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
LTNode* ListInit()
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if (phead == NULL)
{
return NULL;
}
phead->prev = phead;
phead->next = phead;
return phead;
}
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyListNode(x);
newnode->data = x;
newnode->next = phead;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
}
void ListPrint(LTNode* phead)
{
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void ListPopBack(LTNode* phead)
{
assert(phead);
if (phead->next == phead)
{
return;
}
LTNode* tail = phead->prev;
LTNode* prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;
}
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* next = phead->next;
LTNode* newnode = BuyListNode(x);
newnode->prev = phead;
phead->next = newnode;
newnode->next = next;
next->prev = newnode;
}
void ListPopFront(LTNode* phead)
{
//assert(phead->next != phead); //暴力解決
//溫和解決
if (phead->next == phead)
{
return;
}
LTNode* prev = phead->next;
LTNode* next = prev->next;
phead->next = next;
next->prev = phead;
free(prev);
prev = NULL;
}
LTNode* ListFind(LTNode* phead, LTDataType x)
{
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
printf("該元素不存在\n");
return NULL;
}
void ListInsert(LTNode* pos, LTDataType x)
{
LTNode* prevPos = pos->prev;
LTNode* newnode = BuyListNode(x);
newnode->next = pos;
pos->prev = newnode;
newnode->prev = prevPos;
prevPos->next = newnode;
}
void ListErase(LTNode* pos)
{
LTNode* nextPos = pos->next;
LTNode* prevPos = pos->prev;
nextPos->prev = prevPos;
prevPos->next = nextPos;
free(pos);
pos = NULL;
}
void ListDestroy(LTNode* phead)
{
LTNode* cur = phead;
LTNode* next = cur->next;
while (cur)
{
free(cur);
cur = NULL;
if (cur != NULL)
{
cur = next;
next = next->next;
}
}
}
3. test.c
#include"ListNode.h"
void test()
{
LTNode* phead = ListInit();
if (phead == NULL)
{
return;
}
ListPushBack(phead, 1);//測(cè)試:尾插
ListPushBack(phead, 2);
ListPushBack(phead, 3);
ListPushBack(phead, 4);
ListPrint(phead);
ListPopBack(phead);//測(cè)試:尾刪
ListPopBack(phead);
ListPopBack(phead);
ListPrint(phead);
ListPopBack(phead);//測(cè)試:如果鏈表為空繼續(xù)刪除會(huì)不會(huì)報(bào)錯(cuò)
ListPopBack(phead);
ListPushBack(phead, 1);//尾插一個(gè)數(shù)據(jù)來(lái)對(duì)比頭插
ListPushFront(phead, 1);//測(cè)試:頭插
ListPushFront(phead, 2);
ListPushFront(phead, 3);
ListPushFront(phead, 4);
ListPrint(phead);
ListPopFront(phead);//測(cè)試:頭刪
ListPopFront(phead);
ListPopFront(phead);
ListPrint(phead);
ListPopFront(phead);//測(cè)試:如果鏈表刪除完畢，繼續(xù)刪除會(huì)不會(huì)報(bào)錯(cuò)
ListPopFront(phead);
ListPopFront(phead);
ListPrint(phead);
ListPushBack(phead, 1);//插入新元素進(jìn)行后續(xù)測(cè)試
ListPushBack(phead, 2);
ListPushBack(phead, 3);
ListPushBack(phead, 4);
ListPrint(phead);
ListFind(phead, 5);
LTNode* pos = ListFind(phead, 2);//測(cè)試:在2前面插入數(shù)字5
ListInsert(pos, 5);
ListPrint(phead);
pos = ListFind(phead, 2);//測(cè)試:刪除結(jié)點(diǎn)2
ListErase(pos);
ListPrint(phead);
ListDestroy(phead);//測(cè)試:銷毀鏈表
}
int main()
{
test();
return 0;
}
總結(jié)
??總體而言難度不大，并且雙向鏈表解決了單鏈表的很多問(wèn)題，值得好好學(xué)習(xí)一下。并且在這里總結(jié)一下數(shù)據(jù)結(jié)構(gòu)中形參能對(duì)實(shí)參產(chǎn)生影響的三種方式：二級(jí)指針，頭節(jié)點(diǎn)（在堆區(qū)），返回值。
??雙向循環(huán)鏈表就先告一段落了，如果發(fā)現(xiàn)文章哪里有問(wèn)題可以在評(píng)論區(qū)提出來(lái)或者私信我嗷。接下來(lái)我會(huì)繼續(xù)學(xué)習(xí)棧與隊(duì)列，開啟新的篇章，那么本期就到此結(jié)束，讓我們下期再見！！覺得不錯(cuò)可以點(diǎn)個(gè)贊以示鼓勵(lì)喔?。?span toymoban-style="hidden">文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-434446.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)篇三：雙向循環(huán)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
