数据结构——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; }