????????????????????????Take your time ! ????????????????????????
??個人主頁：??????大魔王??????
??所屬專欄：??魔王的修煉之路–數(shù)據(jù)結(jié)構(gòu)??
如果你覺得這篇文章對你有幫助，請在文章結(jié)尾處留下你的點贊??和關(guān)注??，支持一下博主。同時記得收藏?這篇文章，方便以后重新閱讀。
?????：櫻花掉落的速度是五厘米 那么兩顆心需要多久才能靠近——《秒速五厘米》
前言
帶頭雙向循環(huán)鏈表是性能非常好的線性表，它在增刪查改時不需要很多其他操作，直接就可以進行，雖然實現(xiàn)比其他復雜，但是如果和用起來相比，那雙向鏈表肯定是舒服的，本篇將講述帶頭雙向循環(huán)鏈表的實現(xiàn)。
本篇鏈表為雙向帶頭循環(huán)鏈表，所以會用到哨兵位頭節(jié)點，哨兵位頭節(jié)點只會用到前（最后一個結(jié)點地址）后（第二個結(jié)點，也就是存儲數(shù)據(jù)的第一個結(jié)點）結(jié)點地址，所以只存儲前后結(jié)點地址，該位置的數(shù)據(jù)成員不會用到，所以可以給隨機值。哨兵位頭結(jié)點最大的優(yōu)勢就是不需要動不動就判度是否為空這種分情況，它使得為空和不為空都能用一個代碼?？赐瓯酒銜私獾缴诒活^結(jié)點的方便。
一、創(chuàng)建結(jié)點的結(jié)構(gòu)體
我們需要讓每個結(jié)點有三個結(jié)構(gòu)體成員：前后結(jié)點地址和存儲數(shù)據(jù)的成員。
//重命名數(shù)據(jù)類型
typedef int ListNodeDate;
//創(chuàng)建結(jié)點的結(jié)構(gòu)體并重命名
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
ListNodeDate date;
}ListNode;
二、創(chuàng)建新結(jié)點
每次增加結(jié)點，都需要創(chuàng)建一個新節(jié)點（哨兵位頭節(jié)點也是這樣，只不過需要特殊初始化，下面會寫）。
//創(chuàng)建新節(jié)點
ListNode* BuyNewnode(ListNodeDate x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->next = NULL;
newnode->prev = NULL;
newnode->date = x;
return newnode;
}
三、初始化雙向鏈表（創(chuàng)建哨兵位頭節(jié)點）
哨兵位頭節(jié)點也是結(jié)點，需要先調(diào)用上面的創(chuàng)建新結(jié)點函數(shù)，然后再進行特殊的初始化：因為是雙向循環(huán)鏈表，所以要讓里面存的兩個地址都指向自己，這樣才能循環(huán)，即使沒有其他結(jié)點。
//初始化雙向鏈表（創(chuàng)建哨兵位頭節(jié)點）
ListNode* InitListNode()
{
ListNode* phead = BuyNewnode(-1);
phead->prev = phead;
phead->next = phead;
return phead;
}
四、雙鏈表銷毀
創(chuàng)建了鏈表，而且是動態(tài)開辟的，那肯定要手動釋放，當我們弄完時手動釋放申請的空間。
//雙鏈表的銷毀
void DestoryListNode(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
ListNode* next = NULL;
while (cur!=phead)
{
next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
- 注意出函數(shù)后要讓指針指向空，因為指向已經(jīng)釋放了，所以是野指針。因為傳的是自己（一級指針），而不是自己的指針（二級指針），所以在函數(shù)里無法改變實參，只能出函數(shù)后再改變指向位置。
五、判斷鏈表是否為空
后面刪除元素我們需要先判斷是否為空，如果為空（也就是只有哨兵位頭結(jié)點，沒有存儲數(shù)據(jù)的結(jié)點），那就沒有刪除的必要了。
//判斷雙向鏈表是否為空（只有哨兵位頭節(jié)點）
bool EmptyListNode(ListNode* phead)
{
if (phead->next == phead)
{
return true;
}
else
return false;
}
六、雙向鏈表打印
為了驗證代碼的正確性，需要打印出來看。
打?。簭纳诒活^結(jié)點指向的下一個結(jié)點的數(shù)據(jù)成員開始打印，直到地址又等于哨兵位頭結(jié)點，結(jié)束。
//雙向鏈表打印
void PrintListNode(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur == phead->next)
printf("<=>");
printf("%d<=>",cur->date);
cur = cur->next;
}
}
七、雙向鏈表尾插
尾插很簡單，直接改變尾部結(jié)點、尾插的節(jié)點、哨兵位頭結(jié)點三者之間的指向關(guān)系就OK了。
//雙向鏈表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x)
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newnode = BuyNewnode(x);
tail->next = newnode;
newnode->prev = tail;
phead->prev = newnode;
newnode->next = phead;
}
八、雙向鏈表尾刪
首先判斷是否為空，然后開始刪，記著釋放刪除結(jié)點的空間。
//雙向鏈表尾刪
void PopBackListNode(ListNode* phead)
{
assert(phead);
assert(!EmptyListNode(phead));
ListNode* newtail = phead->prev->prev;
free(phead->prev);
newtail->next = phead;
phead->prev = newtail;
}
九、雙向鏈表頭插
改變哨兵位頭結(jié)點、插入節(jié)點和第二個結(jié)點的指向關(guān)系。
//雙向鏈表頭插
void PushFrontListNode(ListNode* phead,ListNodeDate x)
{
assert(phead);
ListNode* plist = phead;
ListNode* newnode = BuyNewnode(x);
newnode->next = plist->next;
newnode->prev = plist;
plist->next->prev = newnode;
plist->next = newnode;
}
十、雙向鏈表頭刪
首先判斷是否為空，然后就是改變指向，釋放刪除的結(jié)點空間。
//雙向鏈表頭刪
void PopFrontListNode(ListNode* phead)
{
assert(phead);
assert(!EmptyListNode(phead));
ListNode* plist = phead;
ListNode* next = plist->next->next;
free(plist->next);
next->prev = plist;
plist->next = next;
}
十一、雙向鏈表查找
查找某個數(shù)值是否在該鏈表中，并返回其結(jié)點的地址。
//雙向鏈表查找
ListNode* FindListNode(ListNode* phead,ListNodeDate x)
{
ListNode* plist = phead->next;
assert(!EmptyListNode(plist));
while (plist != phead)
{
if (plist->date == x)
return plist;
plist = plist->next;
}
return NULL;//找不到或者空鏈表都返回NULL
}
十二、雙向鏈表插入
在pos位置前插入，也就是正常邏輯的插入，然后我們需要用到上面的那個查找函數(shù)，先查找出想要插入的位置，然后插入。
//雙向鏈表在pos前面插入
void InsertListNode(ListNode* phead,ListNodeDate x, ListNode* pos)
{
assert(phead);
assert(pos);
ListNode* ListPrev = pos->prev;
ListNode* newnode = BuyNewnode(x);
ListPrev->next = newnode;
newnode->prev = ListPrev;
newnode->next = pos;
pos->prev = newnode;
}
十三、雙向鏈表刪除
刪除并釋放某個數(shù)據(jù)所對應的結(jié)點，首先需要判斷是否為空鏈表，如果只有哨兵位頭結(jié)點肯定不能刪，所以需要判斷是否為空鏈表。
//雙向鏈表刪除pos位置結(jié)點
void EraseListNode(ListNode* phead, ListNode* pos)
{
assert(phead);
assert(pos);
assert(!EmptyListNode(phead));
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);//讓pos出函數(shù)后置空。
}
十五、總代碼
ListNode.h
ListNode.h
#pragma once
//帶頭雙向循環(huán)鏈表
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//重命名數(shù)據(jù)類型
typedef int ListNodeDate;
//創(chuàng)建結(jié)點的結(jié)構(gòu)體并重命名
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
ListNodeDate date;
}ListNode;
//創(chuàng)建新節(jié)點
ListNode* BuyNewnode(ListNodeDate x);
//初始化雙向鏈表（創(chuàng)建哨兵位頭節(jié)點）
ListNode* InitListNode();
//雙鏈表的銷毀
void DestoryListNode(ListNode* phead);
//雙向鏈表打印
void PrintListNode(ListNode* phead);
//雙向鏈表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x);
//雙向鏈表尾刪
void PopBackListNode(ListNode* phead);
//雙向鏈表頭插
void PushFrontListNode(ListNode* phead,ListNodeDate x);
//雙向鏈表頭刪
void PopFrontListNode(ListNode* phead);
//雙向鏈表查找
ListNode* FindListNode(ListNode* phead, ListNodeDate x);
//雙向鏈表在pos前面插入
void InsertListNode(ListNode* phead, ListNodeDate x, ListNode* pos);
//雙向鏈表刪除pos位置結(jié)點
void EraseListNode(ListNode* phead, ListNode* pos);
ListNode.c
ListNode.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "ListNode.h"
//創(chuàng)建新節(jié)點
ListNode* BuyNewnode(ListNodeDate x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->next = NULL;
newnode->prev = NULL;
newnode->date = x;
return newnode;
}
//初始化雙向鏈表（創(chuàng)建哨兵位頭節(jié)點）
ListNode* InitListNode()
{
ListNode* phead = BuyNewnode(-1);
phead->prev = phead;
phead->next = phead;
return phead;
}
//雙鏈表的銷毀
void DestoryListNode(ListNode* phead)
{
assert(phead);
ListNode* cur = phead;
ListNode* next = cur->next;
while (cur!=phead)
{
next = cur->next;
free(cur);
cur = next;
}
}
//判斷雙向鏈表是否為空（只有哨兵位頭節(jié)點）
bool EmptyListNode(ListNode* phead)
{
if (phead->next == phead)
{
return true;
}
else
return false;
}
//雙向鏈表打印
void PrintListNode(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur == phead->next)
printf("<=>");
printf("%d<=>",cur->date);
cur = cur->next;
}
}
//雙向鏈表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x)
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newnode = BuyNewnode(x);
tail->next = newnode;
newnode->prev = tail;
phead->prev = newnode;
newnode->next = phead;
}
//雙向鏈表尾刪
void PopBackListNode(ListNode* phead)
{
assert(phead);
assert(!EmptyListNode(phead));
ListNode* newtail = phead->prev->prev;
free(phead->prev);
newtail->next = phead;
phead->prev = newtail;
}
//雙向鏈表頭插
void PushFrontListNode(ListNode* phead,ListNodeDate x)
{
assert(phead);
ListNode* plist = phead;
ListNode* newnode = BuyNewnode(x);
newnode->next = plist->next;
newnode->prev = plist;
plist->next->prev = newnode;
plist->next = newnode;
}
//雙向鏈表頭刪
void PopFrontListNode(ListNode* phead)
{
assert(phead);
assert(!EmptyListNode(phead));
ListNode* plist = phead;
ListNode* next = plist->next->next;
free(plist->next);
next->prev = plist;
plist->next = next;
}
//雙向鏈表查找
ListNode* FindListNode(ListNode* phead,ListNodeDate x)
{
ListNode* plist = phead->next;
assert(!EmptyListNode(plist));
while (plist != phead)
{
if (plist->date == x)
return plist;
plist = plist->next;
}
return NULL;//找不到或者空鏈表都返回NULL
}
//雙向鏈表在pos前面插入
void InsertListNode(ListNode* phead,ListNodeDate x, ListNode* pos)
{
assert(phead);
assert(pos);
ListNode* ListPrev = pos->prev;
ListNode* newnode = BuyNewnode(x);
ListPrev->next = newnode;
newnode->prev = ListPrev;
newnode->next = pos;
pos->prev = newnode;
}
//雙向鏈表刪除pos位置結(jié)點
void EraseListNode(ListNode* phead, ListNode* pos)
{
assert(phead);
assert(pos);
assert(!EmptyListNode(phead));
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);//讓pos出函數(shù)后置空。
}
Test.c
Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "ListNode.h"
int main()
{
//創(chuàng)建哨兵位頭節(jié)點
ListNode* plist = InitListNode();//pointer List
//尾插尾刪打印
//PushBackListNode(plist, 0);
//PushBackListNode(plist, 1);
//PushBackListNode(plist, 2);
//PushBackListNode(plist, 3);
//PushBackListNode(plist, 4);
//PopBackListNode(plist);
//PopBackListNode(plist);
//PopBackListNode(plist);
//PrintListNode(plist);
//頭插頭刪打印
//PushFrontListNode(plist, 0);
//PushFrontListNode(plist, 1);
//PushFrontListNode(plist, 2);
//PushFrontListNode(plist, 3);
//PushFrontListNode(plist, 4);
//PopFrontListNode(plist);
//PrintListNode(plist);
//綜合驗證
PushBackListNode(plist, 0);
PushBackListNode(plist, 1);
PushBackListNode(plist, 2);
PushFrontListNode(plist, 3);
PushFrontListNode(plist, 4);
PushFrontListNode(plist, 5);
PopBackListNode(plist);
PopFrontListNode(plist);
//插入
ListNode* pos = FindListNode(plist,0);
InsertListNode(plist, 10, pos);
//刪除
pos = FindListNode(plist, 10);
EraseListNode(plist,pos);
pos = NULL;
PrintListNode(plist);
DestoryListNode(plist);
plist = NULL;
return 0;
}
十四、總結(jié)
結(jié)尾
- 博主長期更新，博主的目標是不斷提升閱讀體驗和內(nèi)容質(zhì)量，如果你喜歡博主的文章，請點個贊或者關(guān)注博主支持一波，我會更加努力的為你呈現(xiàn)精彩的內(nèi)容。
??專欄推薦
??魔王的修煉之路–C語言
??魔王的修煉之路–數(shù)據(jù)結(jié)構(gòu)初階
??魔王的修煉之路–C++
??魔王的修煉之路–Linux
更新不易，希望得到友友的三連支持一波。收藏這篇文章，意味著你將永久擁有它，無論何時何地，都可以立即找到重新閱讀；關(guān)注博主，意味著無論何時何地，博主將永久和你一起學習進步，為你帶來有價值的內(nèi)容。文章來源：http://www.zghlxwxcb.cn/news/detail-427729.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-427729.html
到了這里，關(guān)于帶頭雙向循環(huán)鏈表--數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
