带头双向循环链表
- 带头双向循环链表的优点
1.支持任意位置时间复杂度为O(1)的插入和删除。
2.按照需求申请释放空间,无需担心空间不够用,无需担心浪费。
3.带头可以省去链表为空时的判断,可以使代码更加简约
- 带头双向循环链表的缺点
1.不可以进行下标随机访问。
2.缓存利用率低
带头双向循环链表是线性表的一种,带头双向循环链表是链式存储的线性表,不同于顺序表,链表在内存空间中不连续。
带头:带头就是带哨兵位,可以省链表为空时进行的判断。
双向:由结构体内的next指针下一条数据进行链接,由prev对前一条数据进行链接🧐。
循环:以循环方式进行链接,头的(前一个)prev是尾,尾的next(后一个)是头。
PS:需要源码直接通过目录跳转到最后
带头双向循环链表主体结构
默认大小与扩容大小还有类型都可以是任意大小或类型
typedef int DListDataType; //数据类型
typedef struct ListNode
{
DListDataType data;
struct ListNode* prev; //指针指向前一个结点
struct ListNode* next; //指针指向后一个结点
}LTNode;
带头双向循环链表操作函数介绍
- LTNode* InitLTNode(); //链表初始化
- void ListInsert(LTNode* pos, DListDataType x); //任意位置插入
- void ListPushBack(LTNode* phead, DListDataType x); //尾插
- void ListPushFront(LTNode* phead, DListDataType x); //头插
- void print(LTNode* phead); //输出链表
- void ListErase(LTNode* pos); //任意位置删除
- void ListPopBack(LTNode* phead); //尾删
- void ListPopFront(LTNode* phead); //头删
- LTNode* LTModify(LTNode* phead, DListDataType x); //修改指定结点
- LTNode* LTFind(LTNode* phead, DListDataType x); //查找指定结点
- void LTDestory(LTNode* phead); //销毁链表
为了代码方便阅读,将带头双向循环链表操作函数全部放在LinkedList.c文件中,将头文件放在LinkedList.h,测试文件test.c 😮
带头双向循环链表操作函数实现
为了方便调试,建议每写完1-2个函数就进行测试,初始化之后,首先实现print函数可以方便我们进行调试。
带头双向循环链表的初始化函数:
LTNode* Phead = InitLTNode(); //初始化哨兵位
LTNode* BuyNewNode(DListDataType x) //开辟一个新结点
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
LTNode* InitLTNode()
{
LTNode* phead = BuyNewNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
必须先进行初始化哨兵位,将哨兵位指向自己形成循环
打印函数
先写出打印函数,方便进行调试
void print(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("head");
while (cur!=phead)
{
printf("->%d", cur->data);
cur = cur->next;
}
printf("\n");
}
带头双向循环链表插入函数:
指定结点后插入和查找函数
两个函数可以配合使用,使用LTFind查找到需要插入的位置,然后使用ListInsert进行更改
LTNode* LTFind(LTNode* phead, DListDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
LTNode* BuyNewNode(DListDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
void ListInsert(LTNode* pos,DListDataType x)
{
assert(pos);
LTNode* newnode = BuyNewNode(x);
LTNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
头插
头插将新结点插入到哨兵位后面的结点
这里面有一种简单的写法,就是直接复用ListInsert,将哨兵位后面的结点传过去,也是头插的效果
void ListPushFront(LTNode* phead, DListDataType x)
{
assert(phead);
//第一种方法
//ListInsert(phead->next,x);
//第二种方法
LTNode* newnode = BuyNewNode(x);
LTNode* secound = phead->next;
newnode->next = secound;
secound->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
尾插
从最后一个结点后面插入新结点
尾插也可以复用ListInsert函数
- 尾插也会用到申请新结点的函数,这里不重复了
void ListPushBack(LTNode* phead, DListDataType x)
{
assert(phead);
//第一种办法
//ListInsert(phead,x);
//第二种办法
LTNode* newnode = BuyNewNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
带头双向循环链表删除函数
指定结点删除
删除指定结点,配合STFInd使用,将指定节点前一个结点的next连接到指定结点后一个结点,再将指定结点后面结点的prev连接到指定指定结点前一个结点。
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
头删
记得进行断言,当只有一个哨兵位时与头结点为空都无法进行删除
可以对STErase进行复用
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead != phead->next);
//第一种方法
//ListErase(phead->next);
//第二种
LTNode* secound = phead->next;
phead->next = secound->next;
secound->next->prev = phead;
free(secound);
}
尾删
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(phead != phead->next);
//第一种方法
//ListErase(phead->prev);
//第二种方法
LTNode* tail = phead->prev;
phead->prev = tail->prev;
tail->prev->next = phead;
free(tail);
}
带头双向循环链表修改函数
配合LTFind函数使用
LTNode* LTFind(LTNode* phead, DListDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
LTNode* LTModify(LTNode* phead, DListDataType x)
{
LTNode* pos = LTFind(phead, x);
int y;
scanf("%d", &y);
pos->data = y;
}
销毁带头双向循环链表
将每个结点依次释放。最后将哨兵位释放。
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur!=phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
源代码文件
🌞🌞为了使代码更有阅读性,我们不建议把所有函数写在一个文件里,所以这里分成三个文件,模块化管理
test.c
测试文件
#include "DList.h"
void test1()
{
LTNode* Phead = InitLTNode();
ListPushBack(Phead, 666);
ListPushBack(Phead, 777);
ListPushBack(Phead, 9999);
ListPushBack(Phead, 888);
print(Phead);
ListPopBack(Phead);
print(Phead);
ListPopFront(Phead);
print(Phead);
ListPopFront(Phead);
ListPopFront(Phead);
print(Phead);
ListPushFront(Phead,111);
print(Phead);
ListPushFront(Phead, 112);
print(Phead);
LTDestory(Phead);
Phead = NULL;
}
int main()
{
test1();
}
DList.c
i将所有函数封装在此文件下
#include "DList.h"
LTNode* BuyNewNode(DListDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
LTNode* InitLTNode()
{
LTNode* phead = BuyNewNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void ListInsert(LTNode* pos,DListDataType x)
{
assert(pos);
LTNode* newnode = BuyNewNode(x);
LTNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void ListPushBack(LTNode* phead, DListDataType x)
{
//ListInsert(phead,x);
assert(phead);
LTNode* newnode = BuyNewNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void ListPushFront(LTNode* phead, DListDataType x)
{
//ListInsert(phead->next,x);
assert(phead);
LTNode* newnode = BuyNewNode(x);
LTNode* secound = phead->next;
newnode->next = secound;
secound->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
void ListPopBack(LTNode* phead)
{
//ListErase(phead->prev);
assert(phead);
assert(phead != phead->next);
LTNode* tail = phead->prev;
phead->prev = tail->prev;
tail->prev->next = phead;
free(tail);
}
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead != phead->next);
//ListErase(phead->next);
LTNode* secound = phead->next;
phead->next = secound->next;
secound->next->prev = phead;
free(secound);
}
void print(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("head");
while (cur!=phead)
{
printf("->%d", cur->data);
cur = cur->next;
}
printf("\n");
}
LTNode* LTFind(LTNode* phead, DListDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
LTNode* LTModify(LTNode* phead, DListDataType x)
{
LTNode* pos = LTFind(phead, x);
int y;
scanf("%d", &y);
pos->data = y;
}
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur!=phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
DLlist.h
将主程序所需要的函数全部在头文件中声明,增加代码阅读性文章来源:https://www.toymoban.com/news/detail-438244.html
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
typedef int DListDataType;
typedef struct ListNode
{
DListDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
LTNode* InitLTNode();
void ListInsert(LTNode* pos, DListDataType x);
void ListPushBack(LTNode* phead, DListDataType x);
void ListPushFront(LTNode* phead, DListDataType x);
void print(LTNode* phead);
void ListErase(LTNode* pos);
void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);
LTNode* LTModify(LTNode* phead, DListDataType x);
LTNode* LTFind(LTNode* phead, DListDataType x);
void LTDestory(LTNode* phead);
撒花
这就是实现带头双向循环链表的全部内容了,创作不易,还请各位小伙伴多多点赞👍关注收藏⭐,以后也会更新各种关于c语言,数据结构的博客,撒花!文章来源地址https://www.toymoban.com/news/detail-438244.html
到了这里,关于【数据结构】线性表——带头双向循环链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!