目錄
前言
一、帶哨兵的循環雙向鏈表是什么
二、鏈表的實現
2.1規定結構體
2.2創建節點
2.3初始化
2.4打印
2.5檢驗是否為空
2.6銷毀鏈表
2.7尾插
2.8尾刪
2.9頭插
2.10頭刪
2.11尋找特定節點
2.12任意位置插入（pos前）
2.13刪除任意節點
總結
前言
前面我們學習了單鏈表的一些知識，由單鏈表引申出雙向鏈表，同時帶哨兵位或者不帶哨兵位是兩種，但大差不差，這里學習一下帶哨兵位的循環雙向鏈表。
其實有很多鏈表的結構，組成它們的也就是循環非循環，帶哨兵位不帶哨兵位，雙向還是單向。
一、帶哨兵的循環雙向鏈表是什么
無哨兵單向非循環鏈表：結構簡單，也就是我們常說的單鏈表，一般不會用來單獨存數據，實際中更多是作為其它數據的子結構，如哈希桶，圖的鄰接表等等。
而帶哨兵雙向循環鏈表：結構最復雜，一般用來單獨存儲數據，實際中使用的鏈表數據結構，都是帶哨兵（頭）雙向鏈表，另外這個結構雖然復雜，但是使用代碼實現以后會發現結構帶來很多優勢，實現反而簡單了。
二、鏈表的實現
這里我們要實現的有
//創建節點
LTNode* BuyListNode(LTDataType x)
//初始化
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//銷毀鏈表
void LTDestory(LTNode* phead);
//檢驗是否為空
bool LTEmpty(LTNode* phead)
//尾插尾刪
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
//檢驗鏈表是否為空
bool LTEmpty(LTNode* phead);
//頭插頭刪
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos之前加入一個值
void LTInsert(LTNode* pos, LTDataType x);
//刪除節點
void LTErase(LTNode* pos);
//尋找特定節點
LTNode* LTFind(LTNode* phead, LTDataType x);2.1規定結構體
要想實現一個鏈表，就要首先規定一下每一個節點的結構體組成部分，這里我們先使用結構體來定義一下。
每一個節點內包括數據域，頭指針和尾指針。
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;//頭指針struct ListNode* prev;//尾指針LTDataType data;//數據
}LTNode;基于這個結構，我們就可以實現后期的一系列操作內容，包括哨兵位的創建。
2.2創建節點
這里我們命名為BuyListNode，返回類型為結構體也就是LTNode*，通過傳入一個數據LTDataType x，從而實現對節點的創建。
LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");return NULL;}node->next = NULL;node->prev = NULL;node->data = x;return node;
}通過malloc分配一個節點的內存，然后把頭指針尾指針都賦為空，因為這里不知道頭尾指針指向誰，把傳入數據，最后返回節點。
2.3初始化
初始化就是初始化一個哨兵位節點，也就是一個頭，這里把哨兵位數據定義為-1，頭尾指針指向自己，因為這里是雙向循環鏈表，返回此節點。
//初始化
LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}2.4打印
打印這里就是不斷訪問當前節點的下一個節點，之后打印此節點的數據。
//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("head<=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}
}這里為了形象，打印出來的后面會接上一個<<=>>，來代表雙向循環鏈表。
2.5檢驗是否為空
?通過一個布爾值來檢驗是否為空，主要就是檢查哨兵位有沒有。
//檢驗是否為空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}2.6銷毀鏈表
我們用 LTDestory來作為銷毀鏈表的函數名字。實際上銷毀鏈表就是先把除了哨兵位（頭節點）以外的所有節點刪除釋放，最后再釋放哨兵位，實現是這么實現的：
//銷毀釋放
void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}先檢查是否有節點，然后把當前cur節點定義為哨兵位的下一個節點，如果cur不為哨兵位（因為是循環鏈表，所以最后肯定有一個時間，它的尾節點一定指向自己），在循環里面，先用next節點記住cur當前節點的下一個節點，然后釋放掉當前節點，再把之前定義的next賦給當前節點，就相當于cur不斷再往后走，不斷再釋放，最后到了循環結束的條件后，釋放一下哨兵位就可以實現全部釋放。
2.7尾插
這個尾插實現就基于之前創建節點的函數BuyListNode，先創建節點，找到尾節點后，再進行修改。
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;//找尾節點tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}用newnode來代表要插入的新節點，找到尾節點，因為哨兵位的頭指針指向最后一個節點，這時候把新的newnode插入到尾節點后面就可以，注意此時新的節點成為了尾節點，所以要更新一下頭尾指針的指向關系。
2.8尾刪
尾刪就是找到當前尾節點，然后把尾節點的上一個節點作為最后一個節點，更新當前節點的頭尾指針，刪除當前尾節點。
//尾刪
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);tail = NULL;}當然這里也要斷言一下，看看是否為空，為空就不需要刪除。
2.9頭插
頭插實際上就是在哨兵位的下一個節點插入，實現過程就是類似鏈表的插入一樣。
//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);phead->next->prev = newnode;newnode->next = phead->next;phead->next = newnode;newnode->prev = phead;}插入進去后更新前后指針的指向就可以。
2.10頭刪
頭刪就是指定哨兵位的下一個節點，然后這個節點的下一個節點的頭指針更新指向哨兵位，哨兵位的下一節點指向它，就然后釋放掉剛才的頭節點可以。
//頭刪
void LTPopFront(LTNode* phead)
{assert(phead);LTNode* destorynode = phead->next;phead->next->next->prev = phead;phead->next = phead->next->next;free(destorynode);destorynode = NULL;
}上面給出了頭刪的代碼。
2.11尋找特定節點
尋找特定節點，就是通過數據x尋找，之后返回一個節點的地址，這里就是通過一個循環尋找的特定節點，然后返回。
//尋找特定節點
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);//帶頭雙向循環是定不為空的LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}2.12任意位置插入（pos前）
基于之前的尋找特定的節點，以及新節點的創建，在這里對新節點進行插入，插入到pos的下一個節點，并且更新指針。
//任意位置插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}
2.13刪除任意節點
通過傳入一個pos節點，進行刪除，邏輯和前面的刪除差不多。
//刪除節點
void LTErase(LTNode* pos)
{assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);pos = NULL;
}總結
這里對循環有哨兵位雙鏈表進行基本功能的編寫和學習。
)
