4，双向带头循环链表
目录
1，双向带头循环链表的定义
带头双向循环链表：结构复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向链表。
2，双向带头循环链表的实现
A，函数的声明
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int LTDataType;
typedef struct ListNode//带头双向循环链表
{
struct ListNode* prev;
struct ListNode* next;
LTDataType data;
}LTNode;
//void ListInit(ListNode** pphead);//无返回值初始化
//链表初始化/开辟节点/打印链表/遍历长度
LTNode* ListInit();
LTNode* BuyNode(LTDataType x);
void ListPrint(LTNode* phead);
int ListSize(LTNode* phead);
//尾插/头插/尾删/头删/间插/间删
void ListPushBack(LTNode* phead, LTDataType x);
void ListPushFront(LTNode* phead, LTDataType x);
void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);
void ListInsertAfter(LTNode* pos, LTDataType x);
void ListErase(LTNode* pos);
//查找/销毁
LTNode* ListFind(LTNode* phead, LTDataType x);
void ListDestory(LTNode* phead);B，函数的定义
LTNode* BuyNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
}
LTNode* ListInit()
{
LTNode* phead = BuyNode(-1);
phead->prev = phead;
phead->next = phead;
return phead;
}
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyNode(x);
LTNode* next = phead->next;
phead->next = newnode;
newnode->next = next;
newnode->prev = phead;
next->prev = newnode;
}
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailprev = tail->prev;
free(tail);
tailprev->next = phead;
phead->prev = tailprev;
}
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* next = phead->next;
LTNode* nextnext = next->next;
free(next);
phead->next = nextnext;
nextnext->prev = phead;
}
void ListInsertAfter(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyNode(x);
LTNode* posprev = pos->prev;
posprev->next = newnode;
newnode->prev = posprev;
newnode->next = pos;
pos->prev = newnode;
}
void ListErase(LTNode* pos)
{
assert(pos);
assert(pos->next != pos);
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
free(pos);
posprev->next = posnext;
posnext->prev = posprev;
}
LTNode* ListFind(LTNode* phead, LTDataType x)
{
assert(phead);
assert(phead->next != phead);
LTNode* cur = phead->next;
while (cur->data != x)
{
cur = cur->next;
if (cur == phead)
{
printf("没找到");
break;
}
}
return cur;
}
int ListSize(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
int size = 0;
while (phead)
{
size++;
cur = cur->next;
}
return size;
}
void ListDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
int size = 0;
while (cur != phead)
{
LTNode* next = cur->next;
ListErase(cur);
cur = next;
}
free(phead);
phead = NULL;
}原文地址：https://blog.csdn.net/m0_65148485/article/details/144323558
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！