C语言编程数据结构带头双向循环链表全面详解

目录
  • 前言
  • 一、什么是带头循环双向链表
  • 二、链表初始化
  • 三、链表接口函数
    • 1.尾插
    • 2.头插
    • 3.头删
    • 4.尾删
    • 5.任意位置插入数据
    • 6.任意位置删除数据
  • 四、打印链表
  • 总结

前言

上一篇数据结构专栏:C语言数据结构单链表接口函数全面讲解教程

我们介绍了单链表的各个接口函数,大家可能会发现单链表存在一些缺陷:比如它一个节点要存储数据+下一个节点地址,占用的空间要远多于顺序表;并且由于单链表是无法从后往前找的,如果你想进行尾删这样的操作,你必须从第一个节点往后找,你的时间复杂度一定是O(n)。

为了解决上面的一些缺陷,我们今天来介绍带头双向循环链表

一、什么是带头循环双向链表

这种链表会有一个哨兵位head节点指向d1,然后d1指向d2…这和单链表非常相似。
但和单链表最大的区别就是:这种链表的每个节点不仅会存储下一个节点地址而且会存储上一个节点的地址,然后尾节点会存储一个指向哨兵位head的地址,然后哨兵位head会存储一个指向尾结点的地址。
具体代码如下:

typedef int LTDataType;//万一以后需要改链表数据类型,可以直接在这里更改(int)
typedef struct ListNode
{
	struct ListNode*next;
	struct ListNode*prev;
	LTDataType data;
}ListNode;//结构体重命名

示例:pandas 是基于NumPy 的一种工具,该工具是为了解决数据分析任务而创建的。

二、链表初始化

类似于上图的效果,刚开始创建只有一个节点,它储存的前地址和后地址都指向自己

代码如下(示例):

#include<stdlib.h>//malloc函数头文件
ListNode* BuyListNode(LTDataType x)//创建一个节点
{
	ListNode*newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
ListNode* ListInit()//链表初始化
{
	ListNode*phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

ps:这里ListInit函数用的是返回值的方法,你也可以用二级指针传参来进行初始化操作

三、链表接口函数

1.尾插

我们以上图为例,原先链表的head节点的前驱指向3,然后3的后驱指向head节点,那在3后面怎么进行尾插呢?由于head节点里存放了3节点的地址,所以我们可以直接找到3节点,找到之后怎么办?把head节点的前驱改成4节点地址,3节点后驱改为4节点地址,最后4节点后驱指向head节点。如下图:

代码如下(示例):

#include<assert.h>//assert函数头文件
void ListPushBack(ListNode*phead, LTDataType x)//尾插
{
    assert(phead);//对传过来的指针进行断言,因为你要进行尾插至少得有个头节点啊
    //如果传过来的是空指针会进行报错
	ListNode*tail = phead->prev;
	ListNode*newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->data = phead;
	phead->prev = newnode;
}

2.头插

如上图,先要在head和d1之间进行头插,怎么操作?非常简单,思路和尾插一模一样
head的后驱指向newnode,newnode的前驱和后驱分别指向phead和d1,d1前驱指向newnode如下图:

代码如下(示例):

void ListPushFront(ListNode*phead,LTDataType x)
{
	assert(phead);
	ListNode*first = phead->next;
	ListNode*newnode = BuyListNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

注意!!!这里是先定义了一个first来存放d1这个地址,如果不事先定义的话,phead->next = newnode;head不再存储d1地址,你就找不到d1了。当然了,如果你就是不想先定义一个first来存放d1地址也可以。怎么做呢?“先连后断”,newnode后驱先接上d1节点,然后你head节点后驱接上newnode。

3.头删

头删也是和前面两个类似的思想

头删也就是把d1节点删掉,我们定义2个指针分别指向d1和d2,然后把head节点后驱接指向d2,d2前驱指向head即可,如下图:

代码如下(示例):

void ListPopFront(ListNode*phead)
{
	assert(phead);
	ListNode*first = phead->next;
	ListNode*second = first->next;
	phead->next = second;
	second->prev = phead;
}

4.尾删

现在要删除d3这个节点,我们定义一个tail和prev指针分别指向d3和d2,然后把d2后驱接上head,head前驱接上d2即可,如下图:

代码如下(示例):

void ListPopBack(ListNode*phead)
{
	assert(phead);
	assert(phead->next != phead);//要进行尾删至少保证有一个节点可删(非head节点)
	ListNode*tail = phead->prev;//头节点前驱指向尾部
	ListNode*prev = tail->prev;//通过尾部得到d2地址
	prev->next = phead;//d2后驱head节点
	phead->prev = prev;//head前驱指向d2节点
}

5.任意位置插入数据

要在某个位置前插入数据,你需要先找到那个位置在哪里,我们先写一个查找函数

怎么个找法呢?很简单,定义一个cur指针,然后从d1开始遍历看有没有我们想要找的数据,遍历到head节点结束。
代码如下(示例):

ListNode* ListFind(ListNode*phead, LTDataType 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, LTDataType x)
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

两个函数一起调用也是很简单的,比如我现在要在链表里数据3的位置前插入300,下面两行代码即可完成两个函数的运用。

ListNode*pos = ListFind(plist, 3);
ListInsert(pos, 300);

ps:这里找到所需位置指针,你如果需要,也可以通过该指针对该位置的值进行修改,比如(返回的指针)->data=n

6.任意位置删除数据

现在要删除pos位置的数据,怎么操作?非常简单!定义一个prev指向pos前一个节点,定义一个next指向pos后一个节点,然后prev和next连起来即可,如图:

代码如下(示例):

void ListErase(ListNode*pos)//指定位置删除
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);//prev和next连起来了,pos就可以被释放掉了
}

四、打印链表

以上图为例:要打印一个链表,head节点是不需要打印的,我们只需要打印存储实际数据的d1,d2,d3即可,定义一个变量cur,让它从d1开始遍历,到head节点结束即可。
代码如下(示例):

void ListPrint(ListNode*phead)
{
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		printf("%d\n", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

总结

本文介绍了带头循环双向链表,包括其定义、各个接口函数、及其遍历打印。虽然是链表中最复杂的结构,但它的代码操作却是最简单的,希望通过今天的学习读者能有所收获~更多关于带头双向循环链表数据结构的资料请关注我们其它相关文章!

(0)

相关推荐

  • C语言 超详细介绍与实现线性表中的带头双向循环链表

    目录 一.本章重点 二.带头双向循环链表介绍 2.1什么是带头双向循环链表? 2.2最常用的两种链表结构 三.带头双向循环链表常用接口实现  3.1结构体创建 3.2带头双向循环链表的初始化  3.3创建新节点 3.4尾插 3.5打印链表 3.6头插 3.7尾删 3.8头删 3.9查找data(返回data的节点地址) 3.10在pos位置之前插入节点 3.11删除pos位置的节点 四.实现接口总结 五.在线oj训练与详解 一.本章重点 带头双向循环链表介绍 带头双向循环链表常用接口实现 实现接

  • C语言超详细讲解数据结构中双向带头循环链表

    目录 一.概念 二.必备工作 2.1.创建双向链表结构 2.2.初始化链表 2.3.动态申请节点 2.4.打印链表 2.5.销毁链表 三.主要功能 3.1.在pos节点前插入数据 尾插 头插 3.2.删除pos处节点数据 尾删 头删 3.3.查找数据 四.总代码 List.h 文件 List.c 文件 Test.c 文件 五.拓展 一.概念 前文我们已经学习了单向链表,并通过oj题目深入了解了带头节点的链表以及带环链表,来画张图总体回顾下: 在我们学习的链表中,其实总共有8种,都是单双向和带不带

  • C语言实现带头双向循环链表的接口

    本文实例为大家分享了C语言实现带头双向循环链表的接口,供大家参考,具体内容如下 各函数功能如下 申请空间 ListNode* BuyListNode(LTDataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->next = NULL; node->prev = NULL; node->data = x; return node; } 初始化 ListNode* ListInit() { ListN

  • C语言手把手带你掌握带头双向循环链表

    目录 前言 带头双向循环链表的结构 代码操作 前言 关于链表这一块,写了多篇博客,学习了顺序表.单链表.及其一些练习题 顺序表:传送门:顺序表 单链表:传送门:单链表1   链表2 链表OJ:传送门:链表OJ 今天,我又来水一水博客, 介绍关于双链表. 带头双向循环链表的结构 实际上,单链表也存在一个比较大的缺陷: 1.不能从后往前遍历 2.无法找到前驱 除了单链表之外,我们自然还有双向链表,我们要说的就是带头双向循环链表,简单理解为:带头结点的,有两个方向的.循环的.结构图如下: 结构虽然比较

  • C语言详解如何实现带头双向循环链表

    目录 创建链表存储结构 创建结点 链表的初始化 双向链表的打印 双向链表尾插 双向链表尾删 双向链表头插 双向链表头删 双向链表查找 双向链表pos前插入结点 双向链表删除pos位置的结点 双向链表的销毁 顺序表和链表的区别 2022042311415360.{C}{C}png" /> 创建链表存储结构 我们需要创建一个结构体来存储一个链表结点的相关信息. typedef int ListDataType;//将ListDataType先定义为int类型,根据需要可以改为不同的类型 //创

  • C语言实现带头双向循环链表

    目录 前言 1. 创建结构体 2.malloc新节点 3.创建哨兵位节点 4.尾插 5.打印 6.尾删 7.头插 8.在指定位置pos的前面进行插入 9. 删除指定位置pos节点 10.销毁链表 前言 在实际生活中最常用的就是这两种链表.无头单向非循环链表.和带头双向循环链表.无头单向非循环链表:结构简单,一般不会单独用来存数据.实际中更多是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.另外这种结构在笔试面试中出现很多.带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数

  • C语言编程数据结构带头双向循环链表全面详解

    目录 前言 一.什么是带头循环双向链表 二.链表初始化 三.链表接口函数 1.尾插 2.头插 3.头删 4.尾删 5.任意位置插入数据 6.任意位置删除数据 四.打印链表 总结 前言 上一篇数据结构专栏:C语言数据结构单链表接口函数全面讲解教程 我们介绍了单链表的各个接口函数,大家可能会发现单链表存在一些缺陷:比如它一个节点要存储数据+下一个节点地址,占用的空间要远多于顺序表:并且由于单链表是无法从后往前找的,如果你想进行尾删这样的操作,你必须从第一个节点往后找,你的时间复杂度一定是O(n).

  • C语言编程C++编辑器及调试工具操作命令详解

    目录 一.GCC编译器 1.GNU工具 2.GCC简介 3.GCC编译器的版本 4.gcc所支持后缀名解释 5.编译器的主要组件 6.GCC的基本用法和选项 7.GCC的错误类型及对策 8.GCC编译过程 条件编译 二.GDB调试工具 1.Gdb调试流程: 2.进入代码调试模式后 一.GCC编译器 1.GNU工具 编译工具:把一个源程序编译成为一个可执行程序. 调试工具:能对执行程序进行源码及汇编级调试. 软件工程工具:用于协助多人开发或大型软件项目的管理,如make.CVS.Subvision

  • python双向循环链表实例详解

    使用python实现双向循环链表,供大家参考,具体内容如下 双向循环链表: 将所有的数据存放到节点中,每一个节点相连接,首尾链接,每一个节点中有一个数据存储区,和两个链接区,一个链接前一个节点,一个链接下一个节点 双向链表操作 1.链表是否为空2.链表的长度3.遍历链表4.链表头部添加元素5.链表尾部添加元素6.链表指定位置添加元素7.链表删除节点8.查找节点是否存在 代码实现 # Functions  函数声明 class Node():     """实例化节点类&quo

  • golang编程开发使用sort排序示例详解

    golang sort package: https://studygolang.com/articles/3360 sort 操作的对象通常是一个 slice,需要满足三个基本的接口,并且能够使用整数来索引 // A type, typically a collection, that satisfies sort.Interface can be // sorted by the routines in this package. The methods require that the /

  • C语言中带头双向循环链表基本操作的实现详解

    目录 一.概念与结构 二.基本操作的实现 1.创建结点 2.初始化链表 3.打印链表 4.尾插 5.尾删 6.头插 7.头删 8.查找某个数并返回其指针 9.在某个位置之前插入 10.删除某个位置 11.判断链表是否为空 12.计算链表中有效值的个数 13.销毁链表 三.测试代码 一.概念与结构 无头单向非循环链表结构简单,一般不会单独用来存数据.实际中更多的是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.而带头双向循环链表的结构较为复杂,一般用在单独存储数据.实际中使用的链表数据结构,都

  • C语言带头双向循环链表的示例代码

    目录 前言 结构分析 链表的基本操作实现 创建节点 初始化链表 链表销毁 打印链表 链表尾插 链表尾删 链表头插 链表头删 链表查找 链表pos位置前面去插入 删除pos位置 链表判空 代码复用 总代码及头文件 前言 对于链表来说,不只有单链表这一个品种: 链表有很多种形态 按方向分:单向.双向 按带不带头:带头.不带头 按循环:循环.不循环 1.单向或则双向: 2.带头或者不带头: 3.循环或者不循环: 组合排列一下的话,链表一共有8种形态!!! 今天我们就来学习一下结构最复杂的带头双向循环链

  • C++零基础精通数据结构之带头双向循环链表

    目录 与单链表的区别 代码的实现 接口 节点的构造 初始化链表 开辟节点 销毁链表 打印链表 尾插链表 尾删链表 头插链表 头删链表 查找链表 链表pos位置的删除 总结 与单链表的区别 单向/双向 单向:只有一个next指针,只指向下一位元素 双向:有两个指针,指向上一位和下一位元素,寻找前一节点和后一节点很便利 带头/不带头 带头:在本来的头结点之前还有一个哨兵卫节点作为头节点,它的址域指针指向头节点,值域不做使用 不带头:没有哨兵卫头节点,在尾删尾插等问题中要考虑头结点的情况(局限) 循环

随机推荐