C语言双向链表的含义与链表数据操作代码详解!

这篇具有很好参考价值的文章主要介绍了C语言双向链表的含义与链表数据操作代码详解!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

引言:于本文中,我们将讲到C语言数据结构中的双向链表的含义,以及对于双向链表的增删查改函数。该函数相比于单向链表,反而还更加的简单。希望这篇文章可以对你有帮助,也希望同样热爱代码编程的你能给我支持,您的支持就是我最大的动力!
关于顺序表以及单链表等更多数据结构知识详解可前往个人主页: 计信猫

目录

一,双向链表的含义

二,双向链表结构体的定义

三,双向链表数据操作预备函数

1,双向链表初始化函数

2,双向链表打印函数

3,双向链表节点创建函数

4,双向链表查找函数

四,双向链表数据操作函数

1,双向链表尾插函数

2,  双向链表头插函数

3,双向链表尾删函数

 4,双向链表头删函数 

5,双向链表pos位置之后插入数据

6,双向链表删除pos节点函数

7,双向链表销毁函数

一,双向链表的含义

        双链表的含义为带头双向循环链表,可以由下图表示:

C语言双向链表的含义与链表数据操作代码详解!,c语言,链表,开发语言

        带头:所谓的带头,其实也就是图中的head,它也同时被称为哨兵位。我们在之前单链表中所用到的头节点其实也只是为了我们方便单链表的讲解才这么称呼的,而实际上,头节点其实就是指的图中的head,也就是哨兵位。然而哨兵位不会储存任何数据,同时它也不能改变,它在单链表中只是起着领头的作用。

        双向:双向就意味着,相较于单链表,双链表的每一个节点都会额外储存一个新的结构体地址指针,也就是pre,用于记录该节点前一个节点的地址,从而实现双向的功能。

        循环双链表中的最后一个节点会与头节点(哨兵位)首尾相连。以此形成循环功能。

二,双向链表结构体的定义

        在我们前文学习了的单链表的结构体定义之后,其实双链表的结构体定义也就十分简单了。双链表节点=所储存的数据+指向下一个节点的指针+指向上一个节点的指针

        所以我们仍然使用三文件操作法,于新的项目中创造List.h,List.c以及test.c文件

C语言双向链表的含义与链表数据操作代码详解!,c语言,链表,开发语言

        而在List.h头文件中我们便如下定义结构体:

#pragma once
//包含所会用到的头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义结构体
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;//双链表所储存的数据
	struct ListNode* next;//后一个节点的地址
	struct ListNode* pre;//前一个节点的地址
}LT;

        注:对于双向链表中,空链表意味着只有一个哨兵位,并不是全部为空! 

三,双向链表数据操作预备函数

        在真正的学习双向链表操作函数前,我们需要先学习三个预备函数,以方便我们后续的双向链表数据操作函数的实现以及检验。它们分别为双向链表的初始化函数,双向链表的打印函数,双线链表的节点创建函数以及双向链表的查找函数。

1,双向链表初始化函数

        当我们想创造一个双向链表时,则需要先创造一个哨兵位,而哨兵位的创建其实非常简单,我们只需要使用malloc函数申请一个结构体的空间就可以了。所以我们的代码如下:

//双向链表的初始化
void LTInit(LT** pphead)
{
	//给双链表创造一个哨兵位
	*pphead = (LT*)malloc(sizeof(LT));
    (*pphead)->next = (*pphead)->pre = *pphead;
}

2,双向链表打印函数

        在我们之后的代码实现中,我们便可以使用该函数来对双向链表中的数据进行打印,从而判断函数是否实现成功。

        该函数中,我们定义一个新的变量pcur来表示哨兵位之后的一个节点,之后我们使用while循环遍历链表,并且在pcur->next!=phead的条件为假的情况下跳出。所以我们的打印代码如下:

//双向链表的打印
void LTPrint(LT* phead)
{
	LT* pcur = phead->next;//创建pcur来遍历双向链表
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

3,双向链表节点创建函数

        在之后我们所要实现的头插,尾插的函数中,我们都需要先创建好一个节点,然后才能进行插入操作。而这个函数,就解决了这个问题。

        这个函数非常简单,我们所需要做的就是使用malloc函数申请一个节点的空间,再使创造出来的节点的next与pre指针全部指向自己就可以了。所以代码如下:

//双向链表节点的创建
LT* LTCreat(LTDataType x)
{
	LT* newnode = (LT*)malloc(sizeof(LT));//创建新节点
	if (newnode == NULL)//防止节点创建失败
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	//将新节点的头与尾均与自己连接
	newnode->next = newnode;
	newnode->pre = newnode;
	return newnode;
}

4,双向链表查找函数

        当我们需要查找链表中是否存在一个值x,如果有,则返回储存该数值的节点的地址;反之则返回NULL时,我们就会用到该函数。

        这也非常简单,我们只需要创建一个pcur变量,使用while循环来遍历整个链表,并在找到x值时就return pcur,如果没找到,就return NULL即可。那么我们的代码如下:

//双向链表的查找
LT* LTFind(LT* phead, LTDataType x)
{
	LT* pcur = phead->next;//创建一个pcur来遍历链表
    while (pcur != phead)
	{
        //找到了
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
    //未找到
	return NULL;
}

四,双向链表数据操作函数

        提要:1,因为我们之后所用到的函数大多不会对所用到的节点(哨兵位,pos节点)有所改变,所以我们传一级指针即可。而对于删除和摧毁函数,为减少记忆成本,保持接口一致性,我们也使用一级指针传址

1,双向链表尾插函数

        图解如下:

C语言双向链表的含义与链表数据操作代码详解!,c语言,链表,开发语言

        依据图像我们可以看出,我们创造了一个新节点之后,我们只需要先将newnode的头与尾分别与d3,head相连,之后再将phead->next赋值为newhead,d3->next赋值为newnode而比较巧妙的地方就在于d3可以使用phead直接表示,不用专门去寻找。所以我们的代码如下:

//双向链表的尾插
void LTPushBack(LT* phead, LTDataType x)
{
	assert(phead);//哨兵位不可以为空
	LT* newnode = LTCreat(x);
	//先连接newnode
	newnode->next = phead;
	newnode->pre = phead->pre;
	//再连接phead与尾节点
	phead->pre->next = newnode;
	phead->pre = newnode;
}

2,  双向链表头插函数

        图解如下:

C语言双向链表的含义与链表数据操作代码详解!,c语言,链表,开发语言

        如图所示,该函数与尾插类似,都是先创建一个新节点,后先将新节点newnodehead,d1连接,之后再将phead->next赋值为newnode,d1->pre赋值为newnode并且d1可以使用phead进行表示。所以代码如下:

//双向链表的头插
void LTPushFront(LT* phead, LTDataType x)
{
	assert(phead);//哨兵位不可以改变
	LT* newnode = LTCreat(x);
	//先连接newnode
	newnode->next = phead->next;
	newnode->pre = phead;
	//再连接phead与d1
	phead->next->pre = newnode;
	phead->next = newnode;
}

3,双向链表尾删函数

        图例如下:

C语言双向链表的含义与链表数据操作代码详解!,c语言,链表,开发语言

        根据图我们可以分析得出,想要做到尾删,我们需要先将d2phead首尾连接起来,再使用free函数去释放掉d3(也就是尾节点)的空间。如果将刚才的顺序调换,那么则可能会导致d2无法被找到的问题。所以我们的代码如下:

//双向链表的尾删
void LTDeleteBack(LT* phead)
{
	//链表必须存在且不可以为空
	assert(phead && phead->next!=phead);
	LT* del = phead->pre;//尾节点定义为del(要被删除的节点)
	del->pre->next = phead;
	phead->pre = del->pre;
	free(del);//释放掉尾节点
	del = NULL;//防止野指针的出现
}

 4,双向链表头删函数 

        图解如下:

C语言双向链表的含义与链表数据操作代码详解!,c语言,链表,开发语言

        所以如果我们想实现该函数,那我们也需要向前一个函数一样,先将pheadd2连接起来,再释放掉d1的空间。该过程不可以逆转,不然会导致d2无法找到的问题。故代码如下:

//双向链表的头删除
void LTDeleteFront(LT* phead)
{
	//链表必须存在且不可以为空
	assert(phead && phead->next != phead);
	LT* del = phead->next;
	del->next->pre = phead;
	phead->next = del->next;
	free(del);//释放掉d1
	del = NULL;//防止野指针的出现
}

5,双向链表pos位置之后插入数据

        图解如下:

C语言双向链表的含义与链表数据操作代码详解!,c语言,链表,开发语言

        所以当我们想要在pos之后插入数据时,我们需要先使用LTCreat函数创建一个节点newnode,然后再将newnode的前后指针分别赋值为pos->nextpos->next->pre,后再将pos的后指针与pos->next的前指针赋值为newnode。当然,想要找到pos,我们则需要我们前面讲到的LTFind函数。代码如下:

//双向链表pos位置之后插入数据
void LTInsertAfter(LT* pos, LTDataType x)
{
	assert(pos);//对pos有规定,不可以为空
	LT* newnode = LTCreat(x);
	//先对newnode进行操作
	newnode->next = pos->next;
	newnode->pre = pos;
	//后对另外两个节点进行操作
	pos->next->pre = newnode;
	pos->next = newnode;
}

6,双向链表删除pos节点函数

        图解如下:

C语言双向链表的含义与链表数据操作代码详解!,c语言,链表,开发语言

        老样子,我们要遵循先连后删的规律,我们要先将pos->prepos->next的两个节点首尾相连,然后再删去pos节点该函数就是如此简单。代码如下:

//双向链表删除pos节点
void LTDeletePos(LT* pos)
{
	//理论上pos不为空和phead不可以等于pos,但无phead参数,所以无法检验
	assert(pos);
	pos->next->pre = pos->pre;
	pos->pre->next = pos->next;
	//删除pos节点
	free(pos);
	pos = NULL;
}

7,双向链表销毁函数

        该函数十分的简单,我们所需要做的就是创建两个结构体指针pcurnext,分别用于while循环中遍历双向链表和记录被删除的节点的下一个节点的位置,一离开while循环,那也同时标志着双向链表被销毁。但我们也需要记住,phead指针需要在主函数(main函数)中手动置空。所以该函数的代码入下:

//双向链表的销毁
void LTDestroy(LT* phead)
{
	assert(phead);
	LT* pcur = phead->next;
	while (pcur != phead)
	{
		LT* next = pcur->next;//保存被删除节点的下一个节点的地址
		free(pcur);//释放pcur节点
		pcur = next;
	}
	pcur = NULL;
	//最后勿忘在主函数中对phead进行手动置空
}

        

         

         

         

     

         文章来源地址https://www.toymoban.com/news/detail-854564.html

         

到了这里,关于C语言双向链表的含义与链表数据操作代码详解!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构:图文详解双向链表的各种操作(头插法,尾插法,任意位置插入,查询节点,删除节点,求链表的长度... ...)

    目录 一.双向链表的概念 二.双向链表的数据结构 三.双向链表的实现 节点的插入 头插法 尾插法 任意位置插入 节点的删除 删除链表中第一次出现的目标节点 删除链表中所有与相同的节点 节点的查找 链表的清空 链表的长度 四.模拟实现链表的完整代码 前言: 在上一

    2024年02月05日
    浏览(50)
  • 【编织时空四:探究顺序表与链表的数据之旅】

    链表的分类 带头双向循环链表接口实现 顺序表和链表的区别 缓存利用率参考存储体系结构 以及 局部原理性。 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环  虽然有这么多的链表的结构,但是我们实

    2024年02月12日
    浏览(56)
  • 【编织时空三:探究顺序表与链表的数据之旅】

    链表OJ题 思路一:删除头结点时另做考虑(由于头结点没有前一个结点) 思路二:添加一个虚拟头结点,删除头结点就不用另做考虑 思路:通过三个指针的操作,每次将当前节点反转并向前移动 ​ 思路:头插法 思路:快慢指针的前进方向相同,且它们步伐的「差」是恒定

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

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

    2024年04月27日
    浏览(55)
  • [JS与链表]双向链表

    阅读本文前请先阅读 [JS与链表]普通链表_AI3D_WebEngineer的博客-CSDN博客 类的继承可以使用extends,让子类继承父类的属性和方法。 而在子类内部(构造函数constructor)必须调用super()实现继承( super()代表父类构造函数 ) 双向链表与普通链表的区别在于:普通链表的节点是链向下

    2024年02月05日
    浏览(53)
  • 基于双向链表的通讯录C语言实现

    关于双向链表的详细了解请见博主的另一篇博客,本文旨在对单链表进行应用,采用C语言编写。

    2024年04月17日
    浏览(140)
  • 数组与链表的区别

    数组是连续存储,数组在创建时需要一个整块的空间。 链表是链式存储,链表在内存空间中不一定是连续的。 数组一般创建在栈区,链表一般创建在堆区,在增加节点时需要new或malloc新节点,相较于数组长度不固定,自由度高。 数组可以通过下标随机访问,单向链表只能通

    2024年02月05日
    浏览(74)
  • 顺序表与链表的区别

    目录 一、顺序表和链表的比较 顺序表 优点: 缺点: 链表 优点 缺点 二、顺序表和链表的区别 1.顺序表和链表都具有增、删、查、改功能,但算法复杂度却不相同。 2、从数据元素存储的内存角度来看 三、顺序表与链表选取方案 顺序表的特点是逻辑上相邻数据元素,物理存

    2024年02月08日
    浏览(122)
  • c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插

    2023年04月09日
    浏览(85)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包