链表的极致——带头双向循环链表

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


双向带头循环链表简介:

双向带头循环链表是链表结构最复杂,但使用最方便的链表。
链表的极致——带头双向循环链表,c语言,链表,数据结构

[图中phead表示链表的头节点(哨兵);

d1,d2等表示链表存储的数据;

d1,d2等左侧的方框存储是指向该节点的上一个节点的指针(prev),右侧方框存储指向该节点的下一个的指针(next)]


双向:

双向带头循环链表的每一个节点的指针域都有俩个指针,一个指针(prev)指向该节点的前一个节点,一个指针(next)指向它的后一个节点。
解决了单链表只能向后访问,不能向前访问的问题


带头:

特点:

  1. 双向带头循环链表的头节点(哨兵)位于第一个存储数据的链表的前一个结点

  2. 双向带头循环链表有一个头节点(哨兵),该节点无论链表是否为空它都存在

  3. 头节点(哨兵)的数据域一般不存储数据或者存储链表的信息(有几个节点等)

  4. 双向带头循环链表的头节点(哨兵)指针域的也有两个指针,且指向前一个节点的指针(prev)指向链表的最后一个节点,指向下一个节点的指针(next)指向链表的第一个节点


链表带头节点的好处:

  1. 由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个节点上的操作就和在表的其它位置上操作一致,无须对链表的第一个节点进行进行特殊处理。 不会再改变链表phead指向的位置,也就不用再函数传参时有时传phead,有时传*phead,让链表的接口函数的参数类型也统一了。
  2. 无论链表是否为空,其头指针是指向头结点的非空指针,因此空表和非空表的处理也就统一了,不需要再分情况。

循环:

特点:

  1. 双向带头循环链表的最后一个节点的指向下一个节点的指针(next)指向头节点(哨兵)
  2. 头节点(哨兵)的指向上一个节点的指针(prev)指向链表的最后一个节点
  3. 当链表为空时,只有头节点(哨兵),此时头节点(哨兵)的prev指向它自己,它的next也指向它自己

循环的好处:

  1. 尾插时不用遍历找链表的最后一个节点(尾节点),因为指向双向带头循环链表的最后一个的节点的指针被存放在头节点(哨兵)的prev中。
  2. 在进行删除操作后,能保证链表不断开
  3. 从链表中任意结点出发都能遍历整个链表。
  4. 可以实现循环遍历,即在遍历到链表末尾后能够自动回到链表头部进行下一轮遍历。

双向带头循环链表的接口函数实现

准备工作:

创建一个头文件(SList.h)两个源文件(SList.c和test.c)

  • SList.h:用于包含库函数的头文件,链表节点结构体声明,接口函数的声明等【另外两个源文件要包含SList.h这个头文件,才能使用其中的声明】
  • SList.h:用于实现单链表的接口函数
  • test.c:存放main函数,用于链表的测试

链表的极致——带头双向循环链表,c语言,链表,数据结构

上图包含了以下3个操作

1.库函数的头文件的包含:

stdio.h:输入/输出等函数
stdlib.h:动态内存申请
assert.h:报错函数assert
2.给链表节点的数据域的数据类型重命名
为什么要重命名呢?
这是为了以后如果改变了LTNoed结构体中数据存储的类型时,
不用到处改函数参数等地方的数据类型,只要改typedef后的int 为对应要改成的数据类型就可以。

3.链表节点结构体定义和重命名


初始化链表(头结点)

链表的极致——带头双向循环链表,c语言,链表,数据结构
参数设计:
无需参数,将返回值赋值给一个指针,这个指针就成为链表的phead。


尾插

链表的极致——带头双向循环链表,c语言,链表,数据结构


参数设计

LTNode*phead:
上面说了因为头指针(phead)不会改变,所以传一级指针phead即可

LTDaType x:
要插入的数据


图解

链表的极致——带头双向循环链表,c语言,链表,数据结构
链表为空的时候也不需要像单链表那样特殊考虑,这也是双向带头循环链表的好处


打印链表

链表的极致——带头双向循环链表,c语言,链表,数据结构


图解

链表的极致——带头双向循环链表,c语言,链表,数据结构


头插

链表的极致——带头双向循环链表,c语言,链表,数据结构


图解

链表的极致——带头双向循环链表,c语言,链表,数据结构


尾删

链表的极致——带头双向循环链表,c语言,链表,数据结构


图解

链表的极致——带头双向循环链表,c语言,链表,数据结构


头删

链表的极致——带头双向循环链表,c语言,链表,数据结构


图解

链表的极致——带头双向循环链表,c语言,链表,数据结构


查找

链表的极致——带头双向循环链表,c语言,链表,数据结构


随机插入

链表的极致——带头双向循环链表,c语言,链表,数据结构
随机插入的pos要配合查找函数的返回值使用·


图解

链表的极致——带头双向循环链表,c语言,链表,数据结构


随机删除

链表的极致——带头双向循环链表,c语言,链表,数据结构


图解

链表的极致——带头双向循环链表,c语言,链表,数据结构


销毁链表

链表的极致——带头双向循环链表,c语言,链表,数据结构


图解

链表的极致——带头双向循环链表,c语言,链表,数据结构


全部代码

SList.h

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDateType;

typedef struct LTNode
{
	LTDateType data;
	struct LTNode* next;
	struct LTNode* prev;
}LTNode;

//初始化链表
LTNode* ListInit(void);
//打印链表
void ListPrint(LTNode* phead);
//尾插
void ListPushBack(LTNode* phead, LTDateType x);
//头插
void ListPushFront(LTNode* phead, LTDateType x);
//尾删
void ListPopBack(LTNode* phead);
//头删
void ListPopFront(LTNode* phead);
//查找x,找到了返回指向x的结构指针,找不到返回NULL
LTNode* ListFind(LTNode* phead, LTDateType x);
//在pos之前插入数据
void ListInsert(LTNode* phead, LTNode* pos, LTDateType x);
//删除pos指向的节点
void ListEase(LTNode* phead, LTNode* pos);
//销毁链表
void ListDestory(LTNode* phead);

SList.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"

LTNode* ListInit()
{
	//哨兵位头节点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//为头结点申请空间

	phead->data = 0;//不存储链表数据(链表的长度等)时也可不初始化

	phead->next = phead;//链表为空时头结点的next指向自己
	phead->prev = phead;//链表为空时头结点的prev也指向自己

	return phead;//返回被一个节点(phead)接收
}

void ListPushBack(LTNode* phead, LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//为新节点申请空间
	if (newnode == NULL)//如果为新节点申请空间失败
	{
		printf("malloc失败");
		exit(-1);//结束程序,-1表示程序非正常结束
	}
	LTNode* tail = phead->prev;//tail指向链表的最后一个节点

	tail->next = newnode;//让新节点成为原尾节点的下一个节点

	newnode->prev = tail;//让原尾节点成为新节点的上一个节点

	phead->prev = newnode;//更新头结点中存储的尾节点

	newnode->next = phead;//让新节点的下一个节点为头结点(phead)

	newnode->data = x;//存储数据
}

void ListPrint(LTNode* phead)
{
	LTNode* cur = phead->next;//将链表的第一个节点赋值给cur

	while (cur != phead)//因为双向带头循环链表没有指向NULL的指针了,而且链表的尾节点的next指向头结点(phead)
		                //所以遍历链表结束的条件为cur==phead
	{
		printf("%d  ", cur->data);//打印节点数据域的数据
		cur = cur->next;//让cur指向下一个节点
	}
}

//头插
void ListPushFront(LTNode* phead, LTDateType x)
{
	LTNode* cur = phead->next;//让cur指向链表的第一个节点
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//为新节点申请空间

	if (newnode == NULL)//如果为新节点申请空间失败
	{
		printf("malloc失败");
		exit(-1);//结束程序,-1表示程序非正常结束
	}
	phead->next = newnode;//让头结点的下一个节点为新节点

	newnode->next = cur;//让新节点的下一个节点为原链表的第一个节点

	newnode->prev = phead;//让新节点的上一个节点为头结点

	newnode->data = x;

	cur->prev = newnode;//让原链表的第一个节点的上一个节点为新节点
}
//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead->next != phead);//链表为空时不能再删除

	LTNode* tail = phead->prev;//让tail指向尾节点

	tail->prev->next = phead;//让尾节点(tail)的前一个节点的next指向头结点,

	phead->prev = tail->prev;//让删除之前的尾节点的前一个节点成为新的尾节点

	free(tail);//释放删除之前的尾节点
}
//头删
void ListPopFront(LTNode* phead)
{
	assert(phead->next != phead);//链表为空时不能再删除

	LTNode* cur = phead->next;//让cur指向链表的第一个节点

	phead->next = cur->next;//让头节点的下一个节点为原链表第一个节点的下一个节点(原链表的第二个节点)

	cur->next->prev = phead;//让原链表的第二个节点的前一个节点为头结点

	free(cur);//释放原链表第一个节点
}
//查找x,找到了返回指向x的结构指针,找不到返回NULL
LTNode* ListFind(LTNode* phead, LTDateType x)
{
	LTNode* cur = phead->next;//让cur指向链表的第一个节点

	while (cur != phead)//因为双向带头循环链表没有指向NULL的指针了,而且链表的尾节点的next指向头结点(phead)
		                //所以遍历链表结束的条件为cur==phead
	{
		if (cur->data == x)
		{
			return cur;//找到了就直接返回
		}
		else
		{
			cur = cur->next;//让cur指向下一个节点
		}
	}
	return NULL;//找不到就返回NULL
}

//在pos之前插入数据
void ListInsert(LTNode** phead, LTNode* pos, LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)//如果为新节点申请空间失败
	{
		printf("malloc失败");
		exit(-1);//结束程序,-1表示程序非正常结束
	}
	newnode->data = x;//存放数据

	newnode->next = pos;//让新节点的下一个节点为pos指向的节点

	newnode->prev = pos->prev;//让新节点的上一个节点为pos指向节点的前一个节点

	pos->prev->next = newnode;//pos指向节点的上一个节点的下一个节点为新节点

	pos->prev = newnode;//让新节点成为pos指向节点的上一个节点
}

//删除pos指向的节点
void ListEase(LTNode* phead, LTNode* pos)
{
	assert(pos != phead);//链表为空时再不能删除

	pos->prev->next = pos->next;//让pos指向节点的前一个节点的next指向pos指向节点的下一个节点

	pos->next->prev = pos->prev;//让pos指向节点的下一个节点的prev指向pos指向节点的上一个节点

	free(pos);//释放pos指向节点
}

//销毁链表
void ListDestory(LTNode* phead)
{
	LTNode* cur = phead->next;//让cur指向链表的第一个节点

	LTNode* tmp = phead->next;

	while (cur != phead)
	{
		tmp = cur->next;//tmp指向cur的下一个节点,防止cur被释放了,找不到下一个节点了
		free(cur);
		cur = tmp;//让cur指向下一个节点
	}
	phead->prev = phead;//链表的所有节点都被释放后,头节点的prev要指向自己,让链表下一次使用时不会出错

	phead->next = phead;//链表的所有节点都被释放后,头节点的next也要指向自己
}

以上就是所有内容了,如果对你有帮助的话,可以点个赞支持一下!文章来源地址https://www.toymoban.com/news/detail-846604.html

到了这里,关于链表的极致——带头双向循环链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 链接未来:深入理解链表数据结构(二.c语言实现带头双向循环链表)

    上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表:链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)-CSDN博客 那今天接着给大家带来带头双向循环链表的实现 : 头文件DoubleList.h:用来基础准备(常量定义,typedef),链表表的基本框架

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

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

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

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

    2024年02月13日
    浏览(49)
  • 数据结构 - 链表详解(二)—— 带头双向循环链表

    链表的结构一共有 八种 :带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。 今天我们来详解带头双向循环链表 带头双向循环链表是一种数据结构,它通

    2024年04月26日
    浏览(57)
  • 【数据结构和算法】实现带头双向循环链表(最复杂的链表)

    前文,我们实现了认识了链表这一结构,并实现了无头单向非循环链表,接下来我们实现另一种常用的链表结构,带头双向循环链表。如有仍不了解单向链表的,请看这一篇文章(7条消息) 【数据结构和算法】认识线性表中的链表,并实现单向链表_小王学代码的博客-CSDN博客

    2024年01月17日
    浏览(78)
  • 数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印(基于C语言实现)

    版本: 2024年4月26日 V1.0 发布于博客园 目录 目录 双向循环链表公式 初始化双向循环链表 构建双向循环链表结点 创建一个空链表(仅头结点) 创建一个新结点 插入数据 头插 中插 尾插 删除数据 头删 中删 尾删 查询打印数据 遍历打印 测试 测试结果: 完整代码 DoubleCirLList.h

    2024年04月27日
    浏览(55)
  • 数据结构课程设计题目——链表综合算法设计、带头双向循环链表、插入、显示、删除、修改、排序

      课程设计题目1–链表综合算法设计   一、设计内容   已知简单的人事信息系统中职工记录包含职工编号(no)、职工姓名(name)、部门名称(depname)、职称(title)和工资数(salary)等信息(可以增加其他信息),设计并完成一个简单的人事信息管理系统,要求完成但不

    2024年02月08日
    浏览(64)
  • 数据结构入门(C语言版)线性表带头双向循环链表接口实现

    在上一篇博客我们讲述了链表的概念和结构,还实现了无头单向非循环链表接口写法,那么这一章节,我们来实现另一种常用的链表组成结构——带头双向循环链表。 如果对前面的链表基本概念还是不了解,可以看作者的上一篇博客: 线性表中链表介绍及无头单向非循环链

    2023年04月12日
    浏览(47)
  • 追梦之旅【数据结构篇】——详解C语言动态实现带头结点的双向循环链表结构

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年01月17日
    浏览(61)
  • 双向带头循环链表的实现

    当我们要学习和了解一个事物时,我们要做的第一步便是对这个事物有一个体的的了解。现在我们要学习双向带头循环链表的第一步也是这个,我们现在先来了解一下这种链表的结构---- 就像该图所呈现的那样,双向循环链表就是长这样。但是你可 千万不要将head当成head。  

    2024年02月05日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包