【数据结构】C语言实现双链表的基本操作

双链表及其基本操作的实现

  • 导言
  • 一、单链表与双链表
  • 二、双链表类型的创建
  • 三、双链表的初始化
  • 四、双链表的创建
  • 五、双链表的遍历
  • 六、双链表的查找
  • 七、双链表的插入
  • 八、双链表的删除
  • 结语

封面

导言

大家好,很高兴又和大家见面啦!!!

经过前面几个篇章的内容分享,相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中,咱们将介绍双链表的创建以及一些基本操作,接下来跟我一起来看看吧!

一、单链表与双链表

线性表的链式存储称为链表,链表是由数据域和指针域组成。

由一个数据域和一个指针域组成的链表我们称为单链表,单链表的指针域指向后继结点,所以我们在访问单链表时只能从前往后访问。这就导致了一个问题:我们在访问后继结点时的时间复杂度为O(1),但是在访问前驱结点时的时间复杂度却是O(n)。

为了克服单链表的这种单一访问的缺点,于是我们在单链表的结点上新增了一个指针域,使得链表上的每个结点都由一个数据域和两个指针域组成,双链表的结点结构如下所示:

双链表结点结构
这两个指针域一个指向后继结点(next),一个指向前驱结点(prior),我们将由这种结构的结点构成的链表称为双链表。

双链表和单链表一样,双链表也有带头结点的双链表与不带头结点的双链表,在没有特殊说明的情况下,我们都是以带头结点的双链表进行说明。接下来我们就来看一下与双链表相关的基本操作;

二、双链表类型的创建

我们首先来看一下双链表的类型创建的基本格式:

//双链表类型创建的基本格式
typedef struct DNode {
	ElemType data;//数据域
	struct DNode* prior, * next;//指针域
}DNode, * DLinkList;//数据类型重命名
//DNode——Double Node——强调的是双链表的结点
//DLinkList——强调的是指向双链表的指针,也就是整个双链表
//prior——在先的,在前的,先前的——指向前驱结点的指针
//next——下一个的,紧接着的,接下来的——指向后继结点的指针
//ElemType——数据元素的数据类型
//data——存储链表数据元素的变量

从格式中可以看到,其实双链表与单链表的类型创建格式是一致的,它们之间的差别有以下几点:

  1. 为了对这两种类型的链表有所区分,单链表的结点类型我们将其定义为LNode,双链表则是DNode
  2. 单链表的类型我们将其定义为LinkList,双链表则是DLinkList
  3. 在双链表中,我们定义了一个额外的指针prior用于指向前驱结点;

有了这个基本格式,我们同样还是以整型类型的数据元素为例来定义一个双链表,如下所示:

//创建双链表类型
typedef struct DNode {
	int data;
	struct DNode* prior, * next;
}DNode, * DLinkList;
int main()
{
	DLinkList L;//定义指向双链表的头指针
	return 0;
}

有了双链表的头指针,接下来我们就可以来创建双链表的头结点并将其初始化了;

三、双链表的初始化

我们先来看一下双链表初始化的基本格式:

//双链表初始化的基本格式
bool InitDLinkList(DLinkList* L)
{
	*L = (DNode*)calloc(1, sizeof(DNode));//创建头结点
	assert(*L);//如果头结点创建失败,则报错
	(*L)->prior = NULL;//初始化前驱指针
	(*L)->next = NULL;//初始化后继指针
	return true;
}

可以看到,对于双链表来说,我们在初始化头结点时不仅要将后继指针进行初始化,还要将前驱指针进行初始化,这样是为了防止这两个指针变成野指针。

  • 在单链表中有一点我们没有提到,就是我们在通过malloccalloc申请空间后一定要及时的对接收空间的指针进行检测,看是否为空指针。

  • 当空间申请失败后,这两个函数返回的就是一个空指针,所以为了避免出现问题,我们可以通过assert来进行断言,也可以通过条件语句来进行判断。

  • 对指针这一块的知识掌握的不牢固的朋友可以通过【C语言必学知识点五】指针这篇博客来复习一下指针的相关知识点

我们在对双链表初始化之后就可以来通过头插法或者尾插法来创建一个双链表了;

四、双链表的创建

由于双链表的结点结构与单链表的结点结构不同,因此我们在创建双链表时的逻辑也是稍有区别的,如下图所示:

双链表的创建
由于多了一个前驱结点,这就导致我们在创建链表时通过头插法在创建第一个表头元素与创建其他的表头元素的步骤稍有不同,如下所示;

用头插法创建第一个表头结点的步骤:

  1. 新结点的后继指针指向头结点的后继指针指向的对象,即NULL;
  2. 新结点的前驱指针指向头结点;
  3. 头结点的后继指针指向新结点;

用C语言来描述的话则是:

//头插法创建第一个表头结点的插入步骤
New_Node->next = Head->next;//新结点的后继指针指向头结点后继指针指向的对象,即NULL
New_Node->prior = Head;//新结点的前驱指针指向头结点
Head->next = New_Node;//头结点的后继指针指向新结点
  • 注:这个插入顺序要确保第3步的操作一定在第1步操作完后再执行;第2步的操作顺序可以随意放置;

用头插法创建第二个及以上的表头结点的步骤:

  1. 新结点的后继指针指向头结点的后继指针指向的对象,即表头结点;
  2. 头结点后继指针指向对象的前驱结点指向新结点;
  3. 新结点的前驱指针指向头结点;
  4. 头结点的后继指针指向新结点;

用C语言描述的话则是:

//头插法创建第二个及以上的头结点的插入步骤
New_Node->next = Head->next;//新结点的后继指针指向头结点后继指针指向的对象,即NULL
Head->next->prior = New_Node;//头指针的后继指针指向对象的前驱指针指向新结点
New_Node->prior = Head;//新结点的前驱指针指向头结点
Head->next = New_Node;//头结点的后继指针指向新结点
  • 注:这个插入顺序要确保第4步的操作一定在第1步与第2步操作完之后执行;第3步操作的顺序可以随意放置;

接下来我们来看一下在这个逻辑下的双链表的头插法的基本格式:

//头插法创建双链表的基本格式
DLinkList DList_HeadInsert(DLinkList* L)
{
	DNode* p;//指向新结点的指针
	ElemType x = 0;//接收数据元素的变量
	……;//获取需要存储的数据元素
	while (x != EOF)//通过给循环设置结束条件来控制创建的结束
	{
		p = (DNode*)calloc(1, sizeof(DNode));//创建新结点
		assert(p);//当创建新结点失败时,assert会对指针p进行报错
		if (!(*L)->next)//当头结点的后继指针指向空指针时
		{
			p->data = x;//将数据元素存储到新结点的数据域中
			p->next = (*L)->next;//新结点的后继指针指向头结点后继指针指向的对象
			p->prior = *L;//新结点的前驱指针指向头结点
			(*L)->next = p;//头结点的后继指针指向新结点
		}
		else
		{
			p->data = x;//将数据元素存储到新结点的指针域中
			p->next = (*L)->next;//新结点的后继指针指向头结点后继指针指向的对象
			(*L)->next->prior = p;//头结点的后继指针指向的对象的前驱指针指向新结点
			p->prior = *L;//新结点的前驱指针指向头结点
			(*L)->next = p;//头结点的后继指针指向新结点
		}
		……;//获取需要存储的数据元素
	}
	return (*L);//创建好链表后返回头指针
}

但是对于尾插法而言,不管是第一个结点还是最后一个结点的创建,在插入步骤上都是不影响的,因为表尾结点的后继指针肯定是指向NULL的,因此通过尾插法创建的双链表则不需要分情况讨论,对应的尾插法创建格式如下所示:

//尾插法创建双链表的基本格式
DLinkList DList_TailInsert(DLinkList* L)
{
	DNode* r = *L;//指向表尾的指针
	DNode* s;//指向新结点的指针
	ElemType x = 0;//接收数据元素的变量
	……;//获取需要存储的数据元素
	while (x != EOF)//通过给循环设置结束条件来控制创建的结束
	{
		s = (DNode*)calloc(1, sizeof(DNode));//创建新结点
		assert(s);
		s->data = x;//将数据元素存储到新结点的数据域中
		s->next = r->next;//新结点的后继指针指向表尾结点的后继指针,即NULL
		s->prior = r;//新结点的前驱指针指向表尾结点
		r->next = s;//表尾结点的后继指针指向新结点
		r = s;//表尾指针指向新结点
		……;//获取新的数据元素
	}
	return(*L);//当链表创建结束,返回头指针
}

在创建好双链表后,我们又该如何遍历双链表来访问某个结点呢?

五、双链表的遍历

在给定一个结点后要想对单链表进行遍历的话,我们只能从该结点往后遍历,但是在双链表中,我们既可以从给定结点开始往后遍历,又可以从给定结点开始往前遍历。遍历的方式也很简单,我们只需要将指向双链表的指针往我们需要遍历的方向进行移动就行,如下所示:

//给定结点指针p遍历双链表
while (p->next)//p的后继结点不为空指针
{
	p = p->next;//从结点p往后遍历
}
while (p->prior)//p的前驱结点不为空指针
{
	p = p->prior;//从结点p往前遍历
}

想要对某一个结点进行想过操作时,我们就可以通过这个遍历的方式来找到对应结点并执行相关操作。

六、双链表的查找

由于双链表是与前驱结点以及后继结点进行双向链接的,因此我们在给定双链表的一个结点后,不管是查找该结点的后继结点还是前驱结点,对应的时间复杂度都为O(1);

在未给定结点的情况下,我们要想查找对应的结点,我们同样可以通过按值查找与按位查找两种查找方式来执行,下面我们来看一下在双链表中,这两种查找方式的基本格式又是如何:

//双链表的按位查找
DNode* GetElem(DLinkList L, int i)
{
	if (i < 1)
		return NULL;//当查找的位序不合理时返回空指针
	DNode* p = L->next;//指向表头结点的指针
	int j = 1;//表头结点的位序
	while (p && j < i)//当查找结点为空指针时结束循环;当查找结点的位序与目标位序相等时结束循环
	{
		p = p->next;//继续往后遍历
		j++;
	}
	return p;//查找结束后返回指针p
}

如果是已知某一个结点的位序,需要查找另一个结点的位序,我们可以将函数的参数换成已知的结点以及需要查找的结点位序就行,这里就不再展开。下面我们来看一下按值查找的基本格式:

//双链表的按位查找
DNode* LocateElem(DLinkList L, ElemType e)
{
	DNode* p = L->next;//指向表头结点的指针
	while (p && p->data != e)//当查找结点为空指针时结束循环
	//当查找结点的数据域存储的元素与目标元素相等时结束循环
	{
		p = p->next;//继续往后遍历
	}
	return p;//查找结束后返回指针p
}

对于双链表而言,在进行查找操作时对应的时间复杂度就有以下几种情况:

  • 如果是从表头结点或者表尾结点开始进行查找的话,那对应的时间复杂度就是O(n);
  • 如果是已知结点要查找对应的前驱结点或者后继结点的话,那对应的时间复杂度就是O(1);
  • 如果是已知某一结点,需要查找位序在该结点前面或者后面的结点的话,那对应的时间复杂度就是O(n);

七、双链表的插入

双链表的插入操作也是有前插与后插操作,前插操作的逻辑与单链表一致,都是通过在指点结点的后面插入一个新的结点,再对数据域中存储的数据进行移动从而完成前插操作,下面我们先来看一下双链表前插操作的基本格式:

//双链表的前插操作
bool InsertPriorDNode(DNode* p, ElemType e)
{
	assert(p);//指针p为空指针时报错
	DNode* q = p->prior;//指针p的前驱结点
	assert(q);//指针q为空指针时报错
	DNode* s = (DNode*)calloc(1, sizeof(DNode));//创建新结点
	assert(s);//指针s为空指针时报错
	s->data = e;//将要插入的元素e放入新结点的数据域中
	s->next = p;//将新结点的后继指针指向进行前插操作的结点p
	p->prior = s;//将结点p的前驱指针指向新结点s
	q->next = s;//将前驱结点的后继指针指向新结点s
	s->prior = q;//将新结点的前驱指针执行前驱结点q
	return true;//完成前插操作后返回true
}

在双链表中进行前插操作时,我们有几点需要注意:

  1. 首先要确定该结点不是头结点,也就是该结点的前驱结点不为空指:
    • 当该结点为头结点时,不能进行前插操作,此时给予一定的信息进行提示;
    • 当该结点不为头结点时,则可以正常进行前插操作;
  2. 因为双链表结点的前驱指针直接指向的是前驱结点,因此我们不需要像单链表一样调用函数来查找前驱结点;
  3. 在进行插入操作时,前驱结点的后继指针执行新结点的操作最好放在最后一步执行;

下面我们来看一下双链表的后插操作:

//双链表的后插操作
bool InsertNextDNode(DNode* p, ElemType e)
{
	assert(p);//指针p为空指针时报错
	DNode* s = (DNode*)calloc(1, sizeof(DNode));//创建新结点
	assert(s);//指针s为空指针时报错
	s->data = e;//将要插入的数据放入新结点的数据域中
	if (p->next)//结点p的后继结点不为空指针
	{
		s->next = p->next;//将新结点的后继指针指向结点p的后继结点
		p->next->prior = s;//结点p的后继结点的前驱指针执行新结点
		s->prior = p;//新结点的前驱指针指向结点p
		p->next = s;//结点p的后继指针指向新结点
	}
	else//结点p的后继结点为空指针
	{
		s->next = p->next;//将新结点的后继指针指向结点p的后继结点
		s->prior = p;//新结点的前驱指针指向结点p
		p->next = s;//结点p的后继指针指向新结点
	}
	return true;//完成后插操作后返回true
}

在双链表中我们要执行后插操作,我们也需要注意几点:

  1. 要判断当前结点的后继结点是否为空指针,从而选择插入操作的执行步骤:
    • 当前结点的后继结点不为空指针时,需要将后继结点的前驱指针的指向对象换成新结点;
    • 当前结点的后继结点为空指针时,只需要将新结点的后继指针指向空指针就行
  2. 不管当前结点的后继结点是否为空指针,我们最好都是将当前结点的后继指针指向新结点的操作放在最后执行;

对于双链表而言,不管是前插操作还是后插操作,其对应的时间复杂度都是O(1),相比于单链表,双链表的执行效率会更高;

八、双链表的删除

如果我想删除双链表中的某个结点时,我们只需要按照以下步骤就能完成删除操作:

  1. 将当前结点的前驱结点的后继指针指向当前结点的后继结点;
  2. 将当前结点的后继结点的前驱指针指向当前结点的前驱结点;
  3. 释放当前结点的空间;

将其转换成C语言则是:

//双链表的删除操作
DNode->prior->next = DNode->next;//将前驱结点的后继指针指向后继结点
DNode->next->prior = DNode->prior;//将后继结点的前驱指针指向前驱结点
free(DNode);//释放当前结点的内存空间

如果是删除的结点为表尾结点,则我们只需要将表尾结点的前驱结点指向空指针,然后直接释放表尾结点的空间就行,转换成C语言则是如下所示:

//删除表尾结点
DNode->prior->next = NULL;//表尾结点的前驱结点的后继指针指向空指针
DNode->prior->next = DNode->next;//前驱结点的后继指针,指向后继结点,即空指针
free(DNode);//释放表尾结点的内存空间

删除表尾结点时,第一句代码与第二句代码都是可以使用的,效果都一样,二者选其一就行。下面我们将删除操作封装成一个函数的话,则对应的格式如下所示:

//双链表的删除操作
bool DeleteDNode(DNode* p)
{
	assert(p);//指针p为空指针时报错
	DNode* q = p->prior;//p的前驱结点
	assert(q);//当q为空指针时报错
	DNode* r = p->next;//p的后继结点
	if (r)//后继结点不为空指针时
	{
		q->next = r;//前驱结点指向后继结点
		r->prior = q;//后继结点指向前驱结点
		free(p);//释放结点p的内存
	}
	else
	{
		q->next = r;//前驱结点指向后继结点,即空指针
		free(p);//释放结点p的内存
	}
	return true;//完成删除操作后返回true
}

当对结点进行前删或者后删时,也是相同的逻辑,这不过在这个基础上做一点小小的变动,这里我就不展开介绍了。当我们相对整个双链表进行删除时,我们只需要重复删除表尾结点的操作即可,大家有兴趣的话可以自己尝试着编写一下;

结语

双链表的内容到这里咱们就全部介绍完了,在今天的篇章中,咱们详细介绍了双链表的创建、初始化、查找、插入、删除等基本操作,并给大家附上了对应操作的代码。希望今天的内容能够帮助大家更好的理解双链表及其基本操作。

在下一篇内容中,咱们将介绍循环链表以及静态链表的相关内容,大家记得关注哦!!!最后感谢各位的翻阅,咱们下一篇再见!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/277956.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Spire.Office for Java 8.12.0

Spire.Office for Java 8.12.0 发布。在该版本中&#xff0c;Spire.XLS for Java支持检索使用WPS工具添加的嵌入图像&#xff1b;Spire.PDF for Java 增强了从 PDF 到 SVG、PDF/A1B 和 PDF/A2A 的转换。此外&#xff0c;该版本还修复了许多已知问题。下面列出了更多详细信息。 …

算法基础day1

归并排序模版 #include <iostream> using namespace std; int n; const int N 1e610; int q[N],tmp[N]; void merge_sort(int l,int r,int q[]){if(l>r) return;int mid lr>>1;merge_sort(l,mid,q);merge_sort(mid1,r,q);//归并的的过程int k0,il,jmid1;while(…

蔓灵花组织wmRAT攻击武器对比分析

概述 蔓灵花&#xff0c;又名"Bitter"、"APT-C-08"、"T-APT-17"以及"苦象"&#xff0c;常对南亚周边及孟加拉湾海域的相关国家发起网络攻击&#xff0c;主要针对巴基斯坦和中国两国。其攻击目标主要包括政府部门、核工业、能源、国防…

openGauss学习笔记-178 openGauss 数据库运维-逻辑复制-逻辑解码-使用SQL函数接口进行逻辑解码

文章目录 openGauss学习笔记-178 openGauss 数据库运维-逻辑复制-逻辑解码-使用SQL函数接口进行逻辑解码178.1 前提条件178.2 操作步骤 openGauss学习笔记-178 openGauss 数据库运维-逻辑复制-逻辑解码-使用SQL函数接口进行逻辑解码 openGauss可以通过调用SQL函数&#xff0c;…

GLTF编辑器-位移贴图实现破碎的路面

在线工具推荐&#xff1a; 3D数字孪生场景编辑器 - GLTF/GLB材质纹理编辑器 - 3D模型在线转换 - Three.js AI自动纹理开发包 - YOLO 虚幻合成数据生成器 - 三维模型预览图生成器 - 3D模型语义搜索引擎 位移贴图是一种可以用于增加模型细节和形状的贴图。它能够在渲染时针…

PCL 空间直角坐标转大地坐标(直接求解法C++详细过程版)

目录 一、算法原理二、代码实现三、结果展示四、测试数据本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、算法原理 二、代码实现 由于此类坐标系的转换涉及到大坐标,PCL的float类型数据结构,无法保证数据精度,用…

彭涛:2023年终复盘,工作,团队,个人!

眨眼2023即将结束&#xff0c;2024即将开启&#xff0c;每年这个时候&#xff0c;都会简单总结下自己这一年&#xff0c;既是对今年的一个复盘和回顾&#xff0c;也是对新一年的向往和期待。 我的2023年&#xff0c;大概分为 「个人」&#xff0c;「家庭」&#xff0c;「团队」…

Qt篇——QwtPainter::drawPie绘制扇形

QwtPainter::drawPie(QPainter *painter, const QRectF &rect, int startAngle, int angle); 一、参数含义&#xff1a; painter&#xff1a; 重绘函数中的painter对象 rect&#xff1a; 要绘制扇形的圆的外切矩形。 startAngle: 要绘制的扇形的起始角 …

【Unity地形】使用地形工具创建场景环境-Terrain

如上图Unity的地形工具可以让我们实现创建复杂、丰富的3D室外环境。 我们创建地形很简单&#xff0c;在层级面板中右键-3Dobject-Terrain 就可以创建一个默认的地形模型&#xff01;这个模型是Unity内置的。 接下来的地形编辑功能全部集中在这个地形的组件上 主要功能如下&…

万物简单AIoT物联网平台快速开始

学物联网&#xff0c;来万物简单IoT物联网&#xff01;&#xff01; 万物简单AIoT物联网提供一站式的AI物联网的学习平台&#xff0c;以及物联网SaaS私有化部署的解决方案。从终端硬件系统、云平台到APP前端的物联网能力&#xff0c;助力企业和开发者的设备具备1分钟快速上云的…

Matplotlib找不到Times New Roman的解决方案

问题背景 在使用seaborn或者matplotlib进行论文画图的时候&#xff0c;一般都会用Times New Roman这个字体&#xff0c;但是在Linux系统里&#xff0c;经常会遇到以下的问题: findfont: Font family [Times New Roman] not found. Falling back to DejaVu Sans. 也就是说找不…

实战14 权限处理

目录 1、权限处理后端接口 1.1 SpringSecurityConfig 1.2 在控制器中加入权限控制 2、前端页面按钮权限判断 2.1 保存权限字段 2.2 编写按钮权限判断 2.3 引入按钮权限判断脚本 2.4 按钮权限判断脚本使用 3、token过期处理 3.1 编写Store代码 3.2 编写刷新token新代码…

算法设计与分析实验报告-贪心算法

校课程的简单实验报告。 算法设计与分析实验报告-递归与分治策略 算法设计与分析实验报告-动态规划算法 算法设计与分析实验报告-贪心算法 dijkstra迪杰斯特拉算法&#xff08;邻接表法&#xff09; 算法设计与分析实验报告-回溯法 算法设计与分析实验报告-分支限界法 …

基于Java车间工时管理系统(源码+部署文档)

博主介绍&#xff1a; ✌至今服务客户已经1000、专注于Java技术领域、项目定制、技术答疑、开发工具、毕业项目实战 ✌ &#x1f345; 文末获取源码联系 &#x1f345; &#x1f447;&#x1f3fb; 精彩专栏 推荐订阅 &#x1f447;&#x1f3fb; 不然下次找不到 Java项目精品实…

web等保评测需要实机查看的操作系统、服务器、数据库和应用部分

“等保测评”全称是信息安全等级保护测评。是经公安部认证的具有资质的测评机构&#xff0c;依据国家信息安全等级保护规范规定&#xff0c;受有关单位委托&#xff0c;按照有关管理规范和技术标准&#xff0c;对信息系统安全等级保护状况进行检测评估的活动。 本文陆续将遇到的…

Python教程(18)——python文件操作详解

Python文件操作 Python文件操作基础操作使用with语句管理文件处理文件操作的异常处理文件路径 文本格式和二进制格式文本格式 (Text Mode)二进制格式 (Binary Mode)例子说明 文件操作的相关函数 所谓的文件操作是指对计算机中的文件进行读取、写入、修改和删除等操作。简单来说…

安装DataEase(Linux线上安装)修改端口

问题一&#xff1a;端口更改 警告本解决方法仅仅应急&#xff0c;如果找到了更好的方法请通知我&#xff0c;感谢你的理解&#xff01;&#xff01;&#xff01; 为了让mysql与dataease的端口不发生冲突&#xff0c;将 MySQL 外部运行端口参数 ${DE_MYSQL_PORT} 改为新端口&am…

一篇文章掌握 NestJS 所有的生命周期以及生命周期的执行时机

前言 NestJS 是一个用于构建高效、可扩展的 Node.js 服务器端应用程序的框架&#xff0c;它使用 TypeScript 作为开发语言&#xff0c;也支持原生的 JavaScript。在 NestJS 中&#xff0c;生命周期事件是一个重要的概念。在我们构建和管理应用程序时&#xff0c;有时需要在特定…

JUC常用并发工具类

JUC常用并发工具类 1、什么是JUC? JUC 就是 java.util.concurrent 包&#xff0c;这个包俗称 JUC&#xff0c;里面都是解决并发问题的一些东西&#xff0c;该包的位置位于 java 下 面的 rt.jar 包下面。 2、4大常用并发工具类 2.1 CountDownLatch CountDownLatch&#x…