【数据结构】线性表——带头双向循环链表

这篇具有很好参考价值的文章主要介绍了【数据结构】线性表——带头双向循环链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


带头双向循环链表

  • 带头双向循环链表的优点

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;

【数据结构】线性表——带头双向循环链表

带头双向循环链表操作函数介绍

  1. LTNode* InitLTNode(); //链表初始化
  2. void ListInsert(LTNode* pos, DListDataType x); //任意位置插入
  3. void ListPushBack(LTNode* phead, DListDataType x); //尾插
  4. void ListPushFront(LTNode* phead, DListDataType x); //头插
  5. void print(LTNode* phead); //输出链表
  6. void ListErase(LTNode* pos); //任意位置删除
  7. void ListPopBack(LTNode* phead); //尾删
  8. void ListPopFront(LTNode* phead); //头删
  9. LTNode* LTModify(LTNode* phead, DListDataType x); //修改指定结点
  10. LTNode* LTFind(LTNode* phead, DListDataType x); //查找指定结点
  11. 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

将主程序所需要的函数全部在头文件中声明,增加代码阅读性

#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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构---带头双向循环链表

    什么是双向带头循环链表? 上面简单的一个非空 带头循环双向链表逻辑图 如何定义一个双向链表? 根据图和代码可以看双向链表就是单链表的每个结点中,在设置一个指向前驱节点的指针 简单认识之后,对他进行初始化(申请一个头节点,让前驱和后驱指针都指向自己) 代码

    2024年02月07日
    浏览(69)
  • 【数据结构】带头双向循环链表

      🧑‍🎓 个人主页:简 料   🏆 所属专栏:C++   🏆 个人社区:越努力越幸运社区   🏆 简       介: 简料简料,简单有料~在校大学生一枚,专注C/C++/GO的干货分享,立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

    2024年01月16日
    浏览(79)
  • 数据结构-带头双向循环链表

    前言: 链表有很多种,上一章结,我复盘了单链表,这一章节,主要针对双链表的知识点进行,整理复盘,如果将链表分类的话,有很多种,我就学习的方向考察的重点,主要针对这两种链表进行整理。 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用

    2023年04月09日
    浏览(50)
  • 【数据结构】实现带头双向循环链表

    之前我们已经学习了单链表,有了单链表的基础,现在开始学习带头双向循环链表~ 结构最复杂 ,一般用在单独存储数据。 实际中使用的链表数据结构,都是带头双向循环链表 。另外这个结构虽然结构复杂,但是使用代码实现以后会发现 结构会带来很多优势 ,实现反而简单

    2024年02月10日
    浏览(46)
  • 数据结构_带头双向循环链表

    相较于之前的顺序表和单向链表,双向链表的逻辑结构稍微复杂一些,但是在实现各种接口的时候是很简单的。因为不用找尾,写起来会舒服一点。(也可能是因为最近一直在写这个的原因) 在实现接口的时候,除了没有找尾,其他的操作和单向链表是差不多的,这里就不多

    2024年04月14日
    浏览(63)
  • 数据结构之带头双向循环链表

    目录 链表的分类 带头双向循环链表的实现 带头双向循环链表的结构 带头双向循环链表的结构示意图 空链表结构示意图 单结点链表结构示意图  多结点链表结构示意图 链表创建结点 双向链表初始化 销毁双向链表 打印双向链表  双向链表尾插 尾插函数测试 双向链表头插

    2024年02月08日
    浏览(74)
  • 【数据结构】带头双向循环链表及其实现

    目录 1.带头双向循环链表 2.带头双向循环链表实现 2.1初始化 2.2销毁 2.3头插 2.4链表打印 2.5头删数据 2.6尾插数据 2.7尾删数据 2.8链表判空  2.9查找一个数据 2.10在pos位置前插入数据 2.11删除pos位置 2.12求链表的长度 2.顺序表和链表的比较 我们已经实现了无头单向循环链表 带头双

    2024年02月10日
    浏览(45)
  • 数据结构-带头双向循环链表的实现

    前言           带头双向循环链表是一种重要的数据结构,它的结构是很完美的,它弥补了单链表的许多不足,让我们一起来了解一下它是如何实现的吧!         它的节点中存储着数据和两个指针,一个 指针_prev 用来记录前一个节点的地址,另一个指针 _next 用来记录后一

    2024年02月13日
    浏览(49)
  • 数据结构入门指南:带头双向循环链表

    目录 文章目录 前言 1.结构与优势 2.链表实现       2.1 定义链表 2.2 创建头节点 2.3 尾插 2.4 输出链表 2.5 尾删 2.6 头插 2.7头删 2.8 节点个数 2.9 查找 2.10 位置插入 2.11 位置删除 2.12 销毁链表  3. 源码 总结         链表一共有8种结构,但最常用的就是无头单向链表、和带头

    2024年02月14日
    浏览(51)
  • 【数据结构】双向带头循环链表的实现

    前言:在前面我们学习了顺序表、单向链表,今天我们在单链表的基础上进一步来模拟实现一个带头双向链表。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博主和博主一起学习!一起努力! 带头双向循环链

    2024年01月15日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包