首页 > 其他分享 >【数据结构】C语言实现双链表的基本操作

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

时间：2023-12-29 20:01:02浏览次数：37  
标签：结点 指向 后继 next 双链 基本操作 C语言 指针

双链表

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


导言

大家好，很高兴又和大家见面啦！！！

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

一、单链表与双链表

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

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

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

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

这两个指针域一个指向后继结点(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;
}

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

  • 在单链表中有一点我们没有提到，就是我们在通过malloc和calloc申请空间后一定要及时的对接收空间的指针进行检测，看是否为空指针。
  • 当空间申请失败后，这两个函数返回的就是一个空指针，所以为了避免出现问题，我们可以通过assert来进行断言，也可以通过条件语句来进行判断。
  • 对指针这一块的知识掌握的不牢固的朋友可以通过【C语言总集篇】指针篇这篇博客来复习一下指针的相关知识点

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

四、双链表的创建

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

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

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

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

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

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

//双链表的后插操作
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. 要判断当前结点的后继结点是否为空指针，从而选择插入操作的执行步骤：
  • 当前结点的后继结点不为空指针时，需要将后继结点的前驱指针的指向对象换成新结点；
  • 当前结点的后继结点为空指针时，只需要将新结点的后继指针指向空指针就行
  1. 不管当前结点的后继结点是否为空指针，我们最好都是将当前结点的后继指针指向新结点的操作放在最后执行；

对于双链表而言，不管是前插操作还是后插操作，其对应的时间复杂度都是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
}

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

结语

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

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

标签：结点,指向,后继,next,双链,基本操作,C语言,指针
From： https://blog.51cto.com/u_16231477/9031176

相关文章

  • 整数除法：floor、ceil、round——《初学C语言第42天》
    //////整数除法——舍小数，取整数//1.floor()头文件<math.h>//功能：把一个小数向下取整，即如果被计算的数是2.2，那向下取整的结果就为2.000000//原型：doublefloor(doubex);//x:是需要计算的数//返回值：//   成功：返回一个double类型的数，此数默认有6位小数//   ......
  • 【数据结构】C语言实现单链表的基本操作
    单链表基本操作的实现导言大家好，很高兴又和大家见面啦！！！在上一篇中，我们详细介绍了单链表的两种创建方式——头插法与尾插法，相信大家现在对这两种方式都已经掌握了。今天咱们将继续介绍单链表的基本操作——查找、插入与删除。在开始今天的内容之前，我们先通过尾插法创建一个单链表，如......
  • 字符函数和字符串函数：memcpy、my_memcpy、memmove、my_memmove——《初学C语言第41天
    ////——————对字符进行函数操作时，函数厚的括号内需使用单引号：isspace('s')////函数     判断    如果他的参数符合下列条件就返回真（非0），不符合返回0////（判断函数是不是后续对应的参数）////注意头文件的引用////iscntrl    任何控制字符////issp......
  • #jitoa#【C语言刷题感悟】
    本博客由金陵科技学院-开放原子开源社虞博文编写1.【字母大小写转换】题目描述：输入一行字符，以回车符'\n'结束，将其中的大写字母转换为相应的小写字母后输出，小写字母转换为相应的大写字母后输出，其他字符按原样输出。如输入a时会输出A，输入B时会输出b代码实现：#include<stdio.h>#incl......
  • 【C语言数据结构】对Lua Table源码的一次劣质学习
    /*new_key*/KLcBoolKLcmCreateMapKeyValue(KLCMAP_PTRpTag,KLCTVALUE_PTRpKv){ KLcBoolkbRet =KL_FALSE; KLcBoolkbIsKvLegal =KL_FALSE; DWORDdwInsertPos =0; DWORDdwFreePos =0; DWORDdwCollisionPos =0; KLCTVALUE_PTRptMainNo......
  • 模拟实现strstr函数的代码——《初学C语言第40天》
    //////模拟实现strstr////（字符中的元素是连续存放的，所以不会存在跳动存放的情况，例如a1="ababcd"，a2="ac"此结果就是NULL）////情况1.arr1="abcd"arr2="abc"（一次匹配就找到了）////情况2.arr1="ababcd"arr2="abc"（多次匹配才能找到）//#include<stdio.h>//#in......
  • 2数据库之Mysql基本操作
                                                                                                      数据库基本类型、基本操作一.......
  • C语言： 函数 值传递 || 指针传递
    在C语言中，函数可以使用指针传递和值传递来传递参数。通常情况下，使用值传递是最常见和最简单的方式。在值传递中，函数的参数会被复制一份，然后传递给函数。这意味着在函数内对参数的修改不会对原始数据产生影响。当你只需要传递一个简单的数据类型，如整数或浮点数时，值传递是......
  • 在Linux环境下模拟实现命令解释器用c语言实现mypwd「粉丝答疑」
    Solution要在Linux环境下用C语言模拟实现一个命令解释器，包含mypwd,mymkdir,myrmdir,mycd,mylist,mycp,mydate,mycreate,mydelete,exit等基本命令，需要按照以下步骤进行：理解每个命令的功能：mypwd:显示当前工作目录。mymkdir:创建一个新目录。myrmdir:删除一个空目......
  • c语言 通过openssl进行rsa的加密和解密
    参考资料https://blog.csdn.net/enjoyinwind/article/details/23530303https://blog.csdn.net/stormbjm/article/details/46898757摘自：https://blog.csdn.net/u011983700/article/details/108240200 最近项目中需要用到RSA加密，网上这方面的资料很多，研究了一番，发现直接用open......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99