数据结构——C语言实现带头双向循环链表

数据结构——C语言实现带头双向循环链表
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了，比单链表实用的多。
图示：

ListNode.h文件：

#include<stdio.h>
typedef struct ListNode
{
 DataType _data;
 struct ListNode* _next;
 struct ListNode* _prev;
}ListNode;
typedef struct List
{
 struct ListNode* _head;
}List;
void ListInit(List* plist);//初始化带头双向循环链表
void ListDestory(List* plist);//销毁
ListNode* CreatListNode(DataType x);//
void ListPushBack(List* plist, DataType x);//尾插
void ListPopBack(List* plist);//尾删
void ListPushFront(List* plist, DataType x);//头插
void ListPopFront(List* plist);//头删
void ListInsert(List* plist,ListNode* pos, DataType x);//在pos前面插入
void ListErase(List* plist,ListNode* pos); // 删除pos位置的结点
void ListPrint(List* plist);
void testList();

ListNode.c文件：

#include"ListNode.h"
#include<assert.h>
#include<malloc.h>
//初始化链表
void ListInit(List* plist)
{
 assert(plist);
 plist->_head = CreatListNode(0);
 //仅有头结点时前驱结点和后继结点均指向自身
 plist->_head->_next = plist->_head;
 plist->_head->_prev = plist->_head;
}
//销毁链表
void ListDestory(List* plist)
{
 assert(plist);
 ListNode* cur=plist->_head->_next;
 while (cur != plist->_head)
 {
  ListNode* next = cur->_next;
  //遍历释放空间
  free(cur);
  //释放空间后将其置为空
  cur = next;
 }
 //最后释放头结点
 free(plist->_head);
 plist->_head = NULL;
}
//生成新结点
ListNode* CreatListNode(DataType x)
{
//分配空间
 ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
 //为新结点赋值
 newNode->_data = x;
 newNode->_next = newNode->_prev = NULL;
 return newNode;
}
//尾插
void ListPushBack(List* plist, DataType x)
{
 assert(plist);
 ListNode* newNode = CreatListNode(x);
 ListNode* tail = plist->_head->_prev;
 tail->_next = newNode;
 newNode->_next = plist->_head;
 newNode->_prev = tail;
 plist->_head->_prev = newNode;
}
//尾删
void ListPopBack(List* plist)
{
 assert(plist);
 ListNode* prev, * tail;
 //判断是否为头结点
 if (plist->_head == plist->_head->_next)
 {
  return;
 }
 tail = plist->_head->_prev;
 prev = tail->_prev;
 prev->_next = plist->_head;
 plist->_head->_prev = prev;
 free(tail);
 tail = NULL;
}
//头插
void ListPushFront(List* plist, DataType x)
{
 assert(plist);
 ListNode* newNode = CreatListNode(x);
 ListNode* next = plist->_head->_next;
 plist->_head->_next = newNode;
  newNode->_prev = plist->_head;
 newNode->_next = next;
 next->_prev = newNode;
}
//头删
void ListPopFront(List* plist)
{
 assert(plist);
 ListNode* next = plist->_head->_next;
 ListNode* nextnext=next->_next;
 //判断是否为头结点
 if (plist->_head == plist->_head->_next)
 {
  return;
 }
 plist->_head->_next = nextnext;
 nextnext->_prev = plist->_head;
 free(next);
 next = NULL;
}
//在pos位置前面插入
void ListInsert(List* plist, ListNode* pos, DataType x)
{
 assert(plist && pos);
 ListNode* prev = pos->_prev;
 ListNode* newNode = CreatListNode(x);
 prev->_next = newNode;
 newNode->_prev = prev;
 newNode->_next = pos;
 pos->_prev = newNode;
}
//删除pos位置的结点
void ListErase(List* plist,ListNode* pos)
{
 assert(plist && pos);
 ListNode* prev, * next;
 //判断是否为头结点
 if (plist->_head == pos)
 {
  return;
 }
 prev = pos->_prev;
 next = pos->_next;
 prev->_next = next;
 next->_prev = prev;
 free(pos);
 pos = NULL;
}
//打印链表
void ListPrint(List* plist)
{
 assert(plist);
 ListNode* cur = plist->_head->_next;
 while (cur != plist->_head)
 {
    printf("%d->", cur->_data);
    cur = cur->_next;
 }
 printf("\n");
}
//测试
void testList()
{
 List list;
 ListInit(&list);
 ListPushBack(&list, 1);
 ListPushBack(&list, 2);
 ListPushBack(&list, 3);
 ListPushBack(&list, 4);
 ListPushFront(&list, 1);
 ListPushFront(&list, 2);
 ListPushFront(&list, 3);
 ListPushFront(&list, 4);
 ListPrint(&list);
 ListPopBack(&list);
 ListPopFront(&list);
 ListPrint(&list);
 ListDestory(&list);
 ListPrint(&list);

main.c文件

int main()
{
 testList();
 return 0;
}