个人主页：欢迎大家光临——>沙漠下的胡杨

  各位大帅哥，大漂亮

 如果觉得文章对自己有帮助

 可以一键三连支持博主

 你的每一分关心都是我坚持的动力

 

 ☄： 本期重点：双向带头循环链表的实现

  希望大家每天都心情愉悦的学习工作。 

 ☄： 本期重点：双向带头循环链表的实现

链表的8种结构：

双向带头循环的实现：

头文件的创建和初始化：

源文件：函数接口的实现

创建新的节点：

链表的初始化：

链表的打印：

链表的尾插：

 链表的头插：

链表的尾删：

链表的头删：

判断链表的是否为空：

链表的长度：

链表的销毁：

如何10分钟之内写出一个链表呢？

在pos位置之前插入x

删除pos位置的结点：

整体代码展示

头文件：

函数实现的源文件：

带头双向循环链表总结：

链表的8种结构：

链表的属性上大体分为：单向和双向，带头和不带头，循环和不循环，这3个属性，一共6中，我们排列组合之后就是8种结构。

 其中我们最常用的就是中的两种，一个是之前已经讲过的单链表---->单链表的讲解   

下面我们就看下个链表的另一个常用的结构,也是链表的终极形态啦，叫双向带头循环结构：

 我们可以看到这个链表每个结点上都有4个关系线，比起单链表要麻烦多了，但是虽然结构麻烦，但是使用时很方便哦。

双向带头循环的实现：

头文件的创建和初始化：

首先，我们创建链表时，要先明白这个链表的结构，它有前指针和后指针，和存放数据的区域，所以我们应该如下创建：

typedef int LTDataType;//类型重命名，方便修改数据类型typedef struct ListNode{struct ListNode *next;//前指针struct ListNode *prev;//后指针LTDataType data;}LTNode;//链表重命名

还有要用的头文件

#pragma once//防止头文件重复包含#define  _CRT_SECURE_NO_WARNINGS//禁止4996报错#include #include #include //使用布尔值引用的头文件#include //断言头文件

下面是函数的接口

LTNode* BuyListNode(LTDataType x);//创建结点LTNode* ListInit();//初始化void ListPrint(LTNode *phead);//打印void ListPushBack(LTNode *phead, LTDataType x);//尾插void ListPushFront(LTNode *phead, LTDataType x);//头插void ListPopBack(LTNode *phead);//尾删void ListPopFront(LTNode *phead);//头删bool ListEmpty(LTNode* phead);//判断链表是否为空// 在pos位置之前插入xvoid ListInsert(LTNode* pos, LTDataType x);//  删除pos位置的节点void ListErase(LTNode* pos);int ListSize(LTNode* phead);//求链表的长度void ListDestroy(LTNode* phead);//链表的销毁

源文件：函数接口的实现

我们一个个来看下函数接口的实现：

创建新的节点：

LTNode* BuyListNode(LTDataType x)//创建结点{    //开辟新的节点 LTNode * newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");//开辟失败结束程序exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;//最后返回节点。}

首先我们使用返回值的方式，不像单链表一样使用二级指针的形式，是因为双向带头循环链表的头结点不会改变，所以没必要使用二级指针。我们单单使用返回值就可以啦。

 

链表的初始化：

LTNode* ListInit()//初始化{    //创建头结点，赋值可以随意。LTNode *phead = BuyListNode(-1);phead->next = phead;//把前后指针都指向自己phead->prev = phead;return phead;//返回头结点，初始化完成。}

在链表初始化时，我们其实只是创建了一个头结点，把它的前后指针都指向自己，进而完成后续的操作，这里我们保证链表的整体统一，所以也使用了返回值的形式。

链表的打印：

void ListPrint(LTNode *phead)//打印{assert(phead);//断言节点不为空    //保存下一个结点，进行遍历LTNode *cur = phead->next;    //从头结点的下一个开始遍历，到头结点结束while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");}

在链表的打印中，我们要注意的是，这个链表是循环的链表，所以不可以指直接遍历，否则会导致链表死循环，所以我们从链表的头结点的下一个结点进行遍历，到链表的头结点结束，刚好把链表遍历一遍。

 

链表的尾插：

void ListPushBack(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; }

上面的链表的尾插，其实就是找到链表的头结点的后指针，进而找到尾节点，在创建一个新节点，然后把他们连接起来就好啦。示意图如下（图画的确实有点丑啦）

 

 链表的头插：

void ListPushFront(LTNode *phead, LTDataType x)//头插{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->next;//找到第一个节点phead->next = newnode;newnode->prev = phead;newnode->next = tail;tail->prev = newnode;}

头插和尾插大同小异，头插我们要先找出第一个节点，就是头结点的后指针，然后我们进行插入连接就好啦，图示和尾插类似。

 

 

链表的尾删：

void ListPopBack(LTNode *phead)//尾删{assert(phead);assert(!ListEmpty(phead));//判断链表不为空LTNode* tail = phead->prev;//保存尾节点tail->prev->next = phead;phead->prev = tail->prev;free(tail);tail = NULL;}

链表的尾删也不难，我们先找到尾节点，接着我们对节点进行修改，把尾节点的前一个的后指针连接到头结点，接着把头结点的前指针，连接到尾节点的前一个，最后free掉尾节点，把尾节点置NULL。

 

链表的头删：

void ListPopFront(LTNode *phead)//头删{assert(phead);assert(!ListEmpty(phead));LTNode* tail = phead->next;tail->next->prev = phead;phead->next = tail->next;free(tail);tail = NULL;}

头删和尾删基本一样，就删除的结点不一样，我们只需要找到第一个结点就可以啦。

 

判断链表的是否为空：

bool ListEmpty(LTNode* phead)//判断链表是否为空{assert(phead);return phead->next == phead;//判断是否为空}

我们一般判断链表为空时，我们采用的是 if 语句条件判断，看是否phead->next == phead这样进行判断，我们可以直接用 phead->next == phead 这个表达式的结果进行判断。

 

链表的长度：

int ListSize(LTNode* phead)//求链表的长度{int size = 0;LTNode *cur = phead->next;while (cur != phead){size++;cur = cur->next;}return size;}

这个求链表的长度和打印链表的思路一致，我们不能直接遍历，所以我们保存头结点的下一个，然后进行遍历，一直到链表的头结点处遍历结束，最后我们返回size就可以啦。

 

链表的销毁：

void ListDestroy(LTNode* phead)//链表的销毁{assert(phead);LTNode *cur = phead->next;while (cur != phead){ //头删前，要先保存下一个的结点。LTNode* next = cur->next;ListPopFront(cur);cur = next;}free(phead);}

链表的销毁中最值得注意的就是，我们在删除链表时必须要把删除前的下一个进行保存，这样不会导致访问不到，删除完成后，我们还要删除链表的头结点。

如何10分钟之内写出一个链表呢？

下面就进入最精华的部分，10分钟以内写出一个链表的关键：

// 在pos位置之前插入xvoid ListInsert(LTNode* pos, LTDataType x);//  删除pos位置的节点void ListErase(LTNode* pos);

关于上面两个函数的实现，就可以帮助我们同时写出 头删头插和尾删尾插 。

 

在pos位置之前插入x

void ListInsert(LTNode* pos, LTDataType x){assert(pos);//断言pos不为NULLLTNode* tail = pos->prev;//找到pos结点的前一个。LTNode* newnode = BuyListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = pos;pos->prev = newnode;}

我们先判断pos不为NULL，然后找到pos结点的前一个，接着创建一个新节点，然后把这三个结点（pos   pos->prev   newnode ）进行连接就好啦。

 

删除pos位置的结点：

void ListErase(LTNode* pos){assert(pos);LTNode* tailnext = pos->next;//找到pos的下一个结点LTNode* tailprev = pos->prev;//找到pos的前一个结点tailprev->next = tailnext;tailnext->prev = tailprev;free(pos);pos = NULL;}

我们先找到pos的前 后 结点，接着我们进行连接这两个结点（pos->next pos->prev），最后free 掉pos结点，把pos结点处置为NULL。

整体代码展示

头文件：

#pragma once#define  _CRT_SECURE_NO_WARNINGS#include #include #include #include typedef int LTDataType;//类型重命名，方便修改数据类型typedef struct ListNode{struct ListNode *next;//前指针struct ListNode *prev;//后指针LTDataType data;}LTNode;//链表重命名LTNode* BuyListNode(LTDataType x);//创建结点LTNode* ListInit();//初始化void ListPrint(LTNode *phead);//打印void ListPushBack(LTNode *phead, LTDataType x);//尾插void ListPushFront(LTNode *phead, LTDataType x);//头插void ListPopBack(LTNode *phead);//尾删void ListPopFront(LTNode *phead);//头删bool ListEmpty(LTNode* phead);//判断链表是否为空// 在pos位置之前插入xvoid ListInsert(LTNode* pos, LTDataType x);//  删除pos位置的节点void ListErase(LTNode* pos);int ListSize(LTNode* phead);//求链表的长度void ListDestroy(LTNode* phead);//链表的销毁

函数实现的源文件：

#include "List.h"LTNode* BuyListNode(LTDataType x)//创建结点{LTNode * newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}LTNode* ListInit()//初始化{LTNode *phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;}void ListPrint(LTNode *phead)//打印{assert(phead);LTNode *cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");}void ListPushBack(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;ListInsert(phead->prev, x);}void ListPushFront(LTNode *phead, LTDataType x)//头插{assert(phead);//LTNode* newnode = BuyListNode(x);//LTNode* tail = phead->next;//phead->next = newnode;//newnode->prev = phead;//newnode->next = tail;//tail->prev = newnode;ListInsert(phead->next, x);}void ListPopBack(LTNode *phead)//尾删{assert(phead);assert(!ListEmpty(phead));//LTNode* tail = phead->prev;////tail->prev->next = phead;//phead->prev = tail->prev;//free(tail);//tail = NULL;ListErase(phead->prev);}void ListPopFront(LTNode *phead)//头删{assert(phead);assert(!ListEmpty(phead));//LTNode* tail = phead->next;//tail->next->prev = phead;//phead->next = tail->next;//free(tail);//tail = NULL;ListErase(phead->next);}bool ListEmpty(LTNode* phead)//判断链表是否为空{assert(phead);return phead->next == phead;}// 在pos位置之前插入xvoid ListInsert(LTNode* pos, LTDataType x){assert(pos);LTNode* tail = pos->prev;LTNode* newnode = BuyListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = pos;pos->prev = newnode;}//  删除pos位置的节点void ListErase(LTNode* pos){assert(pos);LTNode* tailnext = pos->next;LTNode* tailprev = pos->prev;tailprev->next = tailnext;tailnext->prev = tailprev;free(pos);pos = NULL;}int ListSize(LTNode* phead)//求链表的长度{int size = 0;LTNode *cur = phead->next;while (cur != phead){size++;cur = cur->next;}return size;}void ListDestroy(LTNode* phead)//链表的销毁{assert(phead);LTNode *cur = phead->next;while (cur != phead){LTNode* next = cur->next;ListErase(cur);cur = next;}free(phead);}

带头双向循环链表总结：

总的来说，这个链表的功能已经十分强大了，如果单独使用链表，我们就一般使用这个链表，虽然链表的结构上复杂些，但是我们写好以后的效率方面很高。在函数的接口方面，其实只要把任意位置的删除和插入写好，这个链表就完成了一大半了，所以在10分钟写一个链表是我完全OK的哦。

今天是小胡杨停更20天的首作，未来一个月还是要日更的。