C++实现带头双向循环链表的示例详解
目录
一、双向循环链表与顺序表的区别
二、List.h
三、List.c
1、带头双向循环链表的初始化
2、带头双向循环链表的销毁
3、带头双向循环链表的打印
4、动态开辟一个节点
5、带头双向循环链表的判空
6、带头双向循环链表的尾插、尾删
7、带头双向循环链表的头插、头删
8、带头双向循环链表的长度
9、带头双向循环链表的查找、任意位置插入、删除
一、双向循环链表与顺序表的区别| 不同点 | 顺序表 | 双向带头循环链表 |
| 在内存中的存储方式 | 连续存储 | 不一定连续 |
| 随机访问 | 支持随机访问 | 不支持随访问 |
| 任意元素插入或删除 | 尾插O(1)，其他O(N)，可能需要挪动元素 | 通过修改指针指向即可 |
| 应用场景 | 元素高效存储、频繁访问 | 任意位置插入删除频繁 |
| 三级缓存命中率 | 高 | 低 |
寄存器的速度远快于主存，所以需要三级缓存先将数据取出，寄存器读取时将相邻地址的数据进行读取，所以顺序表内存地址连续的特点使其三级缓存命中率高。
双向带头循环链表虽然在链表中结构最复杂，但是解决了单链表找前一个节点需要遍历、要判断头结点是否为空的缺点。
二、List.h#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int ListDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
ListDataType data;
}ListNode;
ListNode* ListInit();//初始化
void ListDestroy(ListNode* phead);//销毁
void PrintList(ListNode* phead);//打印
bool ListEmpty(ListNode* phead);//判断链表是否为空（只有头节点）
void ListPushBack(ListNode* phead, ListDataType x);//尾插
void ListPopback(ListNode* phead);//尾删
void ListPushFront(ListNode* phead, ListDataType x);//头插
size_t ListSize(ListNode* phead);//有效节点个数
ListNode* ListFind(ListNode* phead, ListDataType x);//查找（可用于修改）
void ListInsert(ListNode* pos, ListDataType x);//pos位置插入
void ListErase(ListNode* pos);//删除pos位置
结构体内包含指向下一个节点的指针next、指向上一个节点的指针prev和本节点存储的数据data
三、List.c 1、带头双向循环链表的初始化ListNode* ListInit()//初始化，返回带哨兵位的头结点
{
ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
if (guard == NULL)
{
perror("ListInit fail:\n");
exit(-1);
}
guard->next = guard;
guard->prev = guard;
return guard;
}
malloc一个哨兵位的头结点，并将其next和prev指针置空。
2、带头双向循环链表的销毁void ListDestroy(ListNode* phead)//销毁，传一级指针调用方需要在外部将头结点指针置空
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)//释放非头结点
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);//再释放头结点
}
为了保持接口的一致性，形参用一级指针，所以需要调用者在外部对头指针置空。
先释放非头结点，再释放头结点。
3、带头双向循环链表的打印void PrintList(ListNode* phead)//打印
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("\n");
}
从头结点的next开始，遍历打印
4、动态开辟一个节点ListNode* BuyNode(ListDataType x)//动态开辟一个节点
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("BuyNode:\n");
exit(-1);
}
newnode->data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
将值放入这个节点，并将两个指针置空
5、带头双向循环链表的判空bool ListEmpty(ListNode* phead)//判断链表是否只有头节点
{
assert(phead);
return phead->next == phead;
}
只有哨兵位这一个头结点即为空
6、带头双向循环链表的尾插、尾删void ListPushBack(ListNode* phead, ListDataType x)//尾插
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newnode = BuyNode(x);
newnode->next = phead;
newnode->prev = tail;
tail->next = newnode;
phead->prev = newnode;
}
void ListPopback(ListNode* phead)//尾删
{
assert(phead);
assert(!ListEmpty(phead));
ListNode* tail = phead->prev;
ListNode* prev = tail->prev;
free(tail);
prev->next = phead;
phead->prev = prev;
}
注意尾删前需要判空
7、带头双向循环链表的头插、头删void ListPushFront(ListNode* phead, ListDataType x)//头插
{
assert(phead);
ListNode* cur = phead->next;
ListNode* newnode = BuyNode(x);
newnode->next = cur;
newnode->prev = phead;
cur->prev = newnode;
phead->next = newnode;
}
void ListPopFront(ListNode* phead)//头删
{
assert(phead);
assert(!ListEmpty(phead));
ListNode* cur = phead->next;
ListNode* next = cur->next;
free(cur);
phead->next = next;
next->prev = phead;
}
注意头删前需要判空
8、带头双向循环链表的长度size_t ListSize(ListNode* phead)//有效节点个数
{
assert(phead);
ListNode* cur = phead->next;
size_t count = 0;
while (cur != phead)
{
cur = cur->next;
++count;
}
return count;
}
循环计数即可，哨兵位不算
9、带头双向循环链表的查找、任意位置插入、删除ListNode* ListFind(ListNode* phead, ListDataType x)//查找（可用于修改）
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
void ListInsert(ListNode* pos, ListDataType x)//pos位置之前插入
{
assert(pos);
ListNode* newnode = BuyNode(x);
ListNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void ListErase(ListNode* pos)//删除pos位置
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
}
查找：遍历链表，返回第一个data==x的节点指针，查找通常配合下面两个接口使用
任意位置插入、删除：使用pos位置进行插入删除操作。
头插、头删、尾插、尾删接口可以复用上面三个接口
到此这篇关于C++实现带头双向循环链表的示例详解的文章就介绍到这了,更多相关C++带头双向循环链表内容请搜索软件开发网以前的文章或继续浏览下面的相关文章希望大家以后多多支持软件开发网！
