数据结构-->带头双向循环链表

好了，小伙伴们！！本期我们开始“带头双向循环链表”！！

很显然，这一次要涉及哨兵位了！！而在这之前，单向链表当中没有丝毫提及“哨兵位”的概念！！

其实，这是因为，带哨兵位的单向链表在实际开发和生活当中，并不常用！！

也可以说，价值不大的“带头单向链表”仅仅作为一种参考，是用来拿来练练手的！！

好的！！我们回归到本期的重点：单头双向循环链表

如图所示：

那么现在重提一下，什么是 带头双向循环链表 ？

------>结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表

另外这个结构虽然复杂，但是使用代码实现后会发现结构会带来很多优势，实现反而更简单了！！<-------

相较于“带头单向链表”而言，这种链表有很大的实用价值！！​

那就让我们进入代码环节吧！！

-----> 初建 头文件“List.h”

#include <stdio.h>
#inculde <stdlib.h>     //扩容函数malloc库
#include <assert.h>     //断言检验函数
typedef int LTDataType;
typedef struct ListNode
{
  struct ListNode* prev;    //前指针
  struct ListNode* next;    //后指针
  LTDataType data;
};

-----> 测试环节“Test.c”

#include "List.h"

void test_01()
{
  ListNode* plist = LTInitial();
  
  LTPushBack(plist, 21);
  LTPushBack(plist, 23;
  LTPushBack(plist, 24;
  LTPushBack(plist, 25);
  LTPushBack(plist, 29);    //尾插
  
  LTPrint(plist);
             
  LTPopBack(plist);
  LTPopBack(plist);        //尾删
             
  LTPrint(plist);
      
}
int main()
{
    test_01();
}

-----> 代码实现环节“List.c”

#include "List.h"

//初始化
ListNode* LTInitial()
{
  ListNode* phead = LT_BUY(-1);      //设置哨兵位
  phead ->next = phead;
  phead ->prev = phead;
  return phead;
}

//开辟空间
ListNode* LT_BUY(LTDataType x)
{
  ListNode* newnode = (ListNode*) malloc(sizeof(ListNode));
  if(newnode == NULL)
  {
    perror("malooc::fail");
    return NULL;
  }
  newnode ->next = NULL;
  newnode ->prev = NULL;
  newnode ->data = x;
  return newnode;
}

//打印
void LTPrint(LTNode* phead)
{
  printf("<=phead=>");
  LTNode* cur = phead ->next;
  while(cur != phead)
  {
      printf("<=%d=>", cur ->data);    
      cur = cur ->next;
  }
  printf("\n");
}

//布尔函数判断真假
//注意包含布尔头文件，别忘了
bool boolEmpty(LTNode* phead)
{
  if(phead == NULL )
  {
    return true;
  }
  else
    return false;
}

//尾插数据
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LT_BUY(x);
  LTNode* tail = phead ->prev;
  
  tail ->next = newnode;
  newnode ->prev = tail;
  newnode ->next = phead;
  phead ->prev = newnode;
}

//尾删数据
void LTPopBack(LTNode* phead)
{
  assert(phead);
  //还可以用布尔函数进行断言
  assert(!boolEmpty(phead));
  
  LTNode* tail = phead ->prev;
  LTNode* tailprev = tail ->prev;
  
  tailprev ->next = phead;
  phead ->prev = tailprev;
  
  free(tail);
  tail = NULL;
}

现在补充 头文件“List.h”，以及声明实现环节函数

#include <stdio.h>
#inculde <stdlib.h>     //扩容函数malloc库
#include <assert.h>     //断言检验函数
#include <stdbool.h>    //布尔函数

typedef int LTDataType;
typedef struct ListNode
{
  struct ListNode* prev;    //前指针
  struct ListNode* next;    //后指针
  LTDataType data;
};

//初始化
ListNode* LTInitial();

//开辟空间
ListNode* LT_BUY(LTDataType x);

//打印
void LTPrint(LTNode* phead);

//布尔判断真假
bool boolEmpty(LTNode* phead);

//尾插数据
void LTPushBack(LTNode* phead, LTDataType x);

//尾删数据
void LTPopBack(LTNode* phead);

经测试，执行结果如下：

本期讲解就到这里了！！

感谢小伙伴们的阅读！！

下一期将对“头插 头删”进行优化处理！！敬请期待！！