?
雙向帶頭循環(huán)鏈表簡介：
雙向帶頭循環(huán)鏈表是鏈表結構最復雜，但使用最方便的鏈表。
[圖中phead表示鏈表的頭節(jié)點（哨兵）;
d1，d2等表示鏈表存儲的數(shù)據(jù)；
d1，d2等左側(cè)的方框存儲是指向該節(jié)點的上一個節(jié)點的指針（prev），右側(cè)方框存儲指向該節(jié)點的下一個的指針（next）]
雙向：
雙向帶頭循環(huán)鏈表的每一個節(jié)點的指針域都有倆個指針，一個指針（prev）指向該節(jié)點的前一個節(jié)點，一個指針（next）指向它的后一個節(jié)點。
解決了單鏈表只能向后訪問，不能向前訪問的問題
帶頭：
特點：
-
雙向帶頭循環(huán)鏈表的頭節(jié)點（哨兵）位于第一個存儲數(shù)據(jù)的鏈表的前一個結點
-
雙向帶頭循環(huán)鏈表有一個頭節(jié)點（哨兵），該節(jié)點無論鏈表是否為空它都存在
-
頭節(jié)點（哨兵）的數(shù)據(jù)域一般不存儲數(shù)據(jù)或者存儲鏈表的信息（有幾個節(jié)點等）
-
雙向帶頭循環(huán)鏈表的頭節(jié)點（哨兵）指針域的也有兩個指針，且指向前一個節(jié)點的指針（prev）指向鏈表的最后一個節(jié)點，指向下一個節(jié)點的指針（next）指向鏈表的第一個節(jié)點
鏈表帶頭節(jié)點的好處：
- 由于開始結點的位置被存放在頭結點的指針域中,所以在鏈表的第一個節(jié)點上的操作就和在表的其它位置上操作一致,無須對鏈表的第一個節(jié)點進行進行特殊處理。 不會再改變鏈表phead指向的位置，也就不用再函數(shù)傳參時有時傳phead，有時傳*phead，讓鏈表的接口函數(shù)的參數(shù)類型也統(tǒng)一了。
- 無論鏈表是否為空，其頭指針是指向頭結點的非空指針，因此空表和非空表的處理也就統(tǒng)一了，不需要再分情況。
循環(huán)：
特點：
- 雙向帶頭循環(huán)鏈表的最后一個節(jié)點的指向下一個節(jié)點的指針（next）指向頭節(jié)點（哨兵）
- 頭節(jié)點（哨兵）的指向上一個節(jié)點的指針（prev）指向鏈表的最后一個節(jié)點
- 當鏈表為空時，只有頭節(jié)點（哨兵），此時頭節(jié)點（哨兵）的prev指向它自己，它的next也指向它自己
循環(huán)的好處：
- 尾插時不用遍歷找鏈表的最后一個節(jié)點（尾節(jié)點），因為指向雙向帶頭循環(huán)鏈表的最后一個的節(jié)點的指針被存放在頭節(jié)點（哨兵）的prev中。
- 在進行刪除操作后，能保證鏈表不斷開
- 從鏈表中任意結點出發(fā)都能遍歷整個鏈表。
- 可以實現(xiàn)循環(huán)遍歷，即在遍歷到鏈表末尾后能夠自動回到鏈表頭部進行下一輪遍歷。
雙向帶頭循環(huán)鏈表的接口函數(shù)實現(xiàn)
準備工作：
創(chuàng)建一個頭文件（SList.h）兩個源文件（SList.c和test.c）
- SList.h:用于包含庫函數(shù)的頭文件，鏈表節(jié)點結構體聲明，接口函數(shù)的聲明等【另外兩個源文件要包含SList.h這個頭文件，才能使用其中的聲明】
- SList.h：用于實現(xiàn)單鏈表的接口函數(shù)
- test.c:存放main函數(shù)，用于鏈表的測試
上圖包含了以下3個操作
1.庫函數(shù)的頭文件的包含：
stdio.h:輸入/輸出等函數(shù)
stdlib.h:動態(tài)內(nèi)存申請
assert.h:報錯函數(shù)assert
2.給鏈表節(jié)點的數(shù)據(jù)域的數(shù)據(jù)類型重命名
為什么要重命名呢？
這是為了以后如果改變了LTNoed結構體中數(shù)據(jù)存儲的類型時，
不用到處改函數(shù)參數(shù)等地方的數(shù)據(jù)類型，只要改typedef后的int 為對應要改成的數(shù)據(jù)類型就可以。
3.鏈表節(jié)點結構體定義和重命名
初始化鏈表（頭結點）
參數(shù)設計：
無需參數(shù)，將返回值賦值給一個指針，這個指針就成為鏈表的phead。
尾插
參數(shù)設計
LTNode*phead:
上面說了因為頭指針（phead）不會改變，所以傳一級指針phead即可
LTDaType x：
要插入的數(shù)據(jù)
圖解
鏈表為空的時候也不需要像單鏈表那樣特殊考慮，這也是雙向帶頭循環(huán)鏈表的好處
打印鏈表
圖解
頭插
圖解
尾刪
圖解
頭刪
圖解
查找
隨機插入
隨機插入的pos要配合查找函數(shù)的返回值使用·
圖解
隨機刪除
圖解
銷毀鏈表
圖解
文章來源：http://www.zghlxwxcb.cn/news/detail-846604.html
全部代碼
SList.h
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDateType;
typedef struct LTNode
{
LTDateType data;
struct LTNode* next;
struct LTNode* prev;
}LTNode;
//初始化鏈表
LTNode* ListInit(void);
//打印鏈表
void ListPrint(LTNode* phead);
//尾插
void ListPushBack(LTNode* phead, LTDateType x);
//頭插
void ListPushFront(LTNode* phead, LTDateType x);
//尾刪
void ListPopBack(LTNode* phead);
//頭刪
void ListPopFront(LTNode* phead);
//查找x,找到了返回指向x的結構指針，找不到返回NULL
LTNode* ListFind(LTNode* phead, LTDateType x);
//在pos之前插入數(shù)據(jù)
void ListInsert(LTNode* phead, LTNode* pos, LTDateType x);
//刪除pos指向的節(jié)點
void ListEase(LTNode* phead, LTNode* pos);
//銷毀鏈表
void ListDestory(LTNode* phead);
SList.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
LTNode* ListInit()
{
//哨兵位頭節(jié)點
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//為頭結點申請空間
phead->data = 0;//不存儲鏈表數(shù)據(jù)（鏈表的長度等）時也可不初始化
phead->next = phead;//鏈表為空時頭結點的next指向自己
phead->prev = phead;//鏈表為空時頭結點的prev也指向自己
return phead;//返回被一個節(jié)點（phead）接收
}
void ListPushBack(LTNode* phead, LTDateType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//為新節(jié)點申請空間
if (newnode == NULL)//如果為新節(jié)點申請空間失敗
{
printf("malloc失敗");
exit(-1);//結束程序，-1表示程序非正常結束
}
LTNode* tail = phead->prev;//tail指向鏈表的最后一個節(jié)點
tail->next = newnode;//讓新節(jié)點成為原尾節(jié)點的下一個節(jié)點
newnode->prev = tail;//讓原尾節(jié)點成為新節(jié)點的上一個節(jié)點
phead->prev = newnode;//更新頭結點中存儲的尾節(jié)點
newnode->next = phead;//讓新節(jié)點的下一個節(jié)點為頭結點（phead）
newnode->data = x;//存儲數(shù)據(jù)
}
void ListPrint(LTNode* phead)
{
LTNode* cur = phead->next;//將鏈表的第一個節(jié)點賦值給cur
while (cur != phead)//因為雙向帶頭循環(huán)鏈表沒有指向NULL的指針了，而且鏈表的尾節(jié)點的next指向頭結點（phead）
//所以遍歷鏈表結束的條件為cur==phead
{
printf("%d ", cur->data);//打印節(jié)點數(shù)據(jù)域的數(shù)據(jù)
cur = cur->next;//讓cur指向下一個節(jié)點
}
}
//頭插
void ListPushFront(LTNode* phead, LTDateType x)
{
LTNode* cur = phead->next;//讓cur指向鏈表的第一個節(jié)點
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//為新節(jié)點申請空間
if (newnode == NULL)//如果為新節(jié)點申請空間失敗
{
printf("malloc失敗");
exit(-1);//結束程序，-1表示程序非正常結束
}
phead->next = newnode;//讓頭結點的下一個節(jié)點為新節(jié)點
newnode->next = cur;//讓新節(jié)點的下一個節(jié)點為原鏈表的第一個節(jié)點
newnode->prev = phead;//讓新節(jié)點的上一個節(jié)點為頭結點
newnode->data = x;
cur->prev = newnode;//讓原鏈表的第一個節(jié)點的上一個節(jié)點為新節(jié)點
}
//尾刪
void ListPopBack(LTNode* phead)
{
assert(phead->next != phead);//鏈表為空時不能再刪除
LTNode* tail = phead->prev;//讓tail指向尾節(jié)點
tail->prev->next = phead;//讓尾節(jié)點（tail）的前一個節(jié)點的next指向頭結點，
phead->prev = tail->prev;//讓刪除之前的尾節(jié)點的前一個節(jié)點成為新的尾節(jié)點
free(tail);//釋放刪除之前的尾節(jié)點
}
//頭刪
void ListPopFront(LTNode* phead)
{
assert(phead->next != phead);//鏈表為空時不能再刪除
LTNode* cur = phead->next;//讓cur指向鏈表的第一個節(jié)點
phead->next = cur->next;//讓頭節(jié)點的下一個節(jié)點為原鏈表第一個節(jié)點的下一個節(jié)點（原鏈表的第二個節(jié)點）
cur->next->prev = phead;//讓原鏈表的第二個節(jié)點的前一個節(jié)點為頭結點
free(cur);//釋放原鏈表第一個節(jié)點
}
//查找x,找到了返回指向x的結構指針，找不到返回NULL
LTNode* ListFind(LTNode* phead, LTDateType x)
{
LTNode* cur = phead->next;//讓cur指向鏈表的第一個節(jié)點
while (cur != phead)//因為雙向帶頭循環(huán)鏈表沒有指向NULL的指針了，而且鏈表的尾節(jié)點的next指向頭結點（phead）
//所以遍歷鏈表結束的條件為cur==phead
{
if (cur->data == x)
{
return cur;//找到了就直接返回
}
else
{
cur = cur->next;//讓cur指向下一個節(jié)點
}
}
return NULL;//找不到就返回NULL
}
//在pos之前插入數(shù)據(jù)
void ListInsert(LTNode** phead, LTNode* pos, LTDateType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)//如果為新節(jié)點申請空間失敗
{
printf("malloc失敗");
exit(-1);//結束程序，-1表示程序非正常結束
}
newnode->data = x;//存放數(shù)據(jù)
newnode->next = pos;//讓新節(jié)點的下一個節(jié)點為pos指向的節(jié)點
newnode->prev = pos->prev;//讓新節(jié)點的上一個節(jié)點為pos指向節(jié)點的前一個節(jié)點
pos->prev->next = newnode;//pos指向節(jié)點的上一個節(jié)點的下一個節(jié)點為新節(jié)點
pos->prev = newnode;//讓新節(jié)點成為pos指向節(jié)點的上一個節(jié)點
}
//刪除pos指向的節(jié)點
void ListEase(LTNode* phead, LTNode* pos)
{
assert(pos != phead);//鏈表為空時再不能刪除
pos->prev->next = pos->next;//讓pos指向節(jié)點的前一個節(jié)點的next指向pos指向節(jié)點的下一個節(jié)點
pos->next->prev = pos->prev;//讓pos指向節(jié)點的下一個節(jié)點的prev指向pos指向節(jié)點的上一個節(jié)點
free(pos);//釋放pos指向節(jié)點
}
//銷毀鏈表
void ListDestory(LTNode* phead)
{
LTNode* cur = phead->next;//讓cur指向鏈表的第一個節(jié)點
LTNode* tmp = phead->next;
while (cur != phead)
{
tmp = cur->next;//tmp指向cur的下一個節(jié)點，防止cur被釋放了，找不到下一個節(jié)點了
free(cur);
cur = tmp;//讓cur指向下一個節(jié)點
}
phead->prev = phead;//鏈表的所有節(jié)點都被釋放后，頭節(jié)點的prev要指向自己，讓鏈表下一次使用時不會出錯
phead->next = phead;//鏈表的所有節(jié)點都被釋放后，頭節(jié)點的next也要指向自己
}
以上就是所有內(nèi)容了，如果對你有幫助的話，可以點個贊支持一下！文章來源地址http://www.zghlxwxcb.cn/news/detail-846604.html
到了這里，關于鏈表的極致——帶頭雙向循環(huán)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
