前言：
鏈表有很多種，上一章結(jié)，我復(fù)盤了單鏈表，這一章節(jié)，主要針對雙鏈表的知識點(diǎn)進(jìn)行，整理復(fù)盤，如果將鏈表分類的話，有很多種，我就學(xué)習(xí)的方向考察的重點(diǎn)，主要針對這兩種鏈表進(jìn)行整理。
帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。帶頭雙向循環(huán)鏈表如下圖所示。?
?
目錄
1. 帶頭雙向鏈表的實(shí)現(xiàn)
?1.1封裝鏈表節(jié)點(diǎn)結(jié)構(gòu)體
1.2建立新的節(jié)點(diǎn)?
?1.3初始化鏈表
1.4尾插函數(shù)?
?1.5尾刪
?1.6頭插
1.7頭刪
1.8顯示
1.9銷毀
1.10查找
1.11插入
1.12擦除
1.13判空
?
1. 帶頭雙向鏈表的實(shí)現(xiàn)
?1.1封裝鏈表節(jié)點(diǎn)結(jié)構(gòu)體
typedef int LDataType;
typedef struct ListNode
{
LDataType data;//自身數(shù)據(jù)
struct ListNode* prev;指向前一個(gè)節(jié)點(diǎn)指針
struct ListNode* next;指向后一個(gè)節(jié)點(diǎn)指針
}LTNode;1.2建立新的節(jié)點(diǎn)?
?鏈表的增刪查改都會有新的節(jié)點(diǎn)，所以我們可以封裝一個(gè)建立節(jié)點(diǎn)的函數(shù)，具體代碼如下:
LTNode* BuyNode(LDataType x)
{
LTNode* temp = (LTNode*)malloc(sizeof(LTNode));
if (temp == NULL)
{
perror("malloc:fail");
exit(-1);
}
temp->data = x;
temp->next = NULL;
temp->prev = NULL;
return temp;
}?1.3初始化鏈表
?因?yàn)槭菐ь^節(jié)點(diǎn)，初始化會改變節(jié)點(diǎn)指向，如果按照單鏈表的操作習(xí)慣，我們可能穿指針變量的地址，用二級指針接收，但是也沒必要，我們可以讓函數(shù)返回的類型，為指針，具體代碼如下：
LTNode* ListInit()
{
LTNode* phead = BuyNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}1.4尾插函數(shù)?
?因?yàn)轭^結(jié)點(diǎn)的prev指向tail，tail的next節(jié)點(diǎn)指向head所以我們只要改變節(jié)點(diǎn)指向就可以完成尾插，如圖所示：
具體代碼如下：?
void PushBack(LTNode* pa, LDataType x)
{
assert(pa);
LTNode* newnode = BuyNode(x);
LTNode* tail = pa->prev;
tail->next = newnode;
newnode->prev = tail;
pa->prev = newnode;
newnode->next = pa;
}?1.5尾刪
?刪掉最后一個(gè)節(jié)點(diǎn)，并改變節(jié)點(diǎn)指向
具體代碼如下：
void PopBack(LTNode* pa)
{
assert(pa);
LTNode* tail = pa->prev;
LTNode* middle = tail->prev;
middle->next = pa;
pa->prev = middle;
free(tail);
tail = NULL;
}?1.6頭插
?
代碼如下：
void PushFront(LTNode* pa, LDataType x)
{
assert(pa);
LTNode* newnode = BuyNode(x);
LTNode* middle = pa->next;
newnode->next = middle;
middle->prev = newnode;
pa->next = newnode;
newnode->prev = pa;
}1.7頭刪
?代碼如下
void PopFront(LTNode* pa)
{
assert(pa);
LTNode* middle = pa->next;
LTNode* cur = middle->next;
pa->next = cur;
cur->prev = pa;
free(middle);
middle = NULL;
}1.8顯示
?增刪查改之后，需要顯示在終端，所以要有打印顯示函數(shù)
void ListPrint(LTNode* pa)
{
LTNode* cur = pa->next;
while (cur != pa)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("NULL\n");
}1.9銷毀
?在堆上創(chuàng)建的空間，使用完成后，要返還給操作系統(tǒng)。
void ListDestroy(LTNode* pa)
{
LTNode* cur = pa->next;
LTNode* prev = NULL;
while (cur != pa)
{
LTNode* prev = cur;
cur = cur->next;
free(prev);
}
free(pa);
pa->next = pa->prev = NULL;
}1.10查找
?查找指定數(shù)值得節(jié)點(diǎn)，當(dāng)查找到的時(shí)候返回該數(shù)值得地址，如果沒有查找到則返回空指針。
LTNode* ListFind(LTNode* pa, LDataType x)
{
assert(pa);
LTNode* cur = pa->next;
while (cur != pa)
{
if (cur->data != x)
{
cur = cur->next;
}
else
{
return cur;
}
}
return NULL;
}1.11插入
?在當(dāng)前節(jié)點(diǎn)的前一個(gè)位置插入節(jié)點(diǎn)
void ListInsert(LTNode* pa, LTNode* pos, LDataType x)
{
assert(pa);
assert(pos);
LTNode* newnode = BuyNode(x);
LTNode* prev = pos->prev;
newnode->next = pos;
pos->prev = newnode;
prev->next = newnode;
newnode->prev = prev;
}1.12擦除
?將當(dāng)前節(jié)點(diǎn)去除掉。文章來源：http://www.zghlxwxcb.cn/news/detail-406385.html
void ListErase(LTNode* pa, LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}1.13判空
如果頭節(jié)點(diǎn)的下個(gè)指向?yàn)樽约哼@個(gè)表達(dá)式為真的話，則返回true 否則返回false。?文章來源地址http://www.zghlxwxcb.cn/news/detail-406385.html
bool LTEmpty(LTNode* pa)
{
return pa->next == pa;
}到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-帶頭雙向循環(huán)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
