【数据结构】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;//新结点的后继指针指向表尾结点的后继指针,即NULLs->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;//将新结点的后继指针指向进行前插操作的结点pp->prior = s;//将结点p的前驱指针指向新结点sq->next = s;//将前驱结点的后继指针指向新结点ss->prior = q;//将新结点的前驱指针执行前驱结点qreturn 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;//新结点的前驱指针指向结点pp->next = s;//结点p的后继指针指向新结点}else//结点p的后继结点为空指针{s->next = p->next;//将新结点的后继指针指向结点p的后继结点s->prior = p;//新结点的前驱指针指向结点pp->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
}

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

结语

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

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

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【adb】--- win10 配置 adb环境 超详细 (持续更新中)

在编程的艺术世界里&#xff0c;代码和灵感需要寻找到最佳的交融点&#xff0c;才能打造出令人为之惊叹的作品。而在这座秋知叶i博客的殿堂里&#xff0c;我们将共同追寻这种完美结合&#xff0c;为未来的世界留下属于我们的独特印记。 【adb】--- win10 配置 adb环境 超详细 &…

解决Qt“报无法定位程序输入点xxx于动态连接库“问题

今天&#xff0c;在使用QtVS2019编译工程时&#xff0c;弹出"无法定位程序输入点xxx于动态链接库"问题&#xff0c;如图(1)所示&#xff1a; 图(1) 报"无法定位程序输入点xxx于动态链接库"问题 出现这种问题的原因有很多&#xff1a; (1) 工程Release/Deb…

低代码选型注意事项

凭借着革命性的生产力优势&#xff0c;低代码技术火爆了整个IT圈。面对纷繁复杂的低代码和无代码产品&#xff0c;开发者该如何选择&#xff1f; 在研究低代码平台的年数上&#xff0c;本人已有3年&#xff0c;也算是个低代码资深用户了&#xff0c;很多企业面临低代码选型上的…

iOS 开发设计 App 上架符合要求的截图

1. 真机运行截屏 2. 可以在 Apple developer 官网 Design 下找到 iPhone 边框 https://developer.apple.com/design/resources/ 不用这个边框也行&#xff0c;可以参考已上架 App 的图片框 3. 使用 Procreate&#xff08;PhotoShop&#xff09;创建符合要求的画布大小 4. 导入…

听GPT 讲Rust源代码--src/tools(27)

File: rust/src/tools/clippy/clippy_lints/src/methods/suspicious_to_owned.rs 文件rust/src/tools/clippy/clippy_lints/src/methods/suspicious_to_owned.rs的作用是实施Clippy lint规则&#xff0c;检测产生潜在性能问题的字符转换代码&#xff0c;并给出相关建议。 在Rus…

智能优化算法应用:基于袋獾算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于袋獾算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于袋獾算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.袋獾算法4.实验参数设定5.算法结果6.参考文献7.MA…

【UE5.1】程序化生成Nanite植被

目录 效果 步骤 一、下载Gaea软件和树林资产 二、使用Gaea生成贴图 三、 生成地形 四、生成草地 五、生成树林 六、生成湖泊 七、其它功能介绍 7.1 调整树林生成的面积 7.2 让植物随风飘动 7.3 玩家和植物互动 7.4 雪中树林 7.5 环境音效 效果 步骤 一、下载Ga…

HBase 集群搭建

文章目录 安装前准备兼容性官方网址 集群搭建搭建 Hadoop 集群搭建 Zookeeper 集群解压缩安装配置文件高可用配置分发 HBase 文件 服务的启停启动顺序停止顺序 验证进程查看 Web 端页面 安装前准备 兼容性 1&#xff09;与 Zookeeper 的兼容性问题&#xff0c;越新越好&#…

信息泄露总结

文章目录 一、备份文件下载1.1 网站源码1.2 bak文件泄露1.3 vim缓存1.4 .DS_Store 二、Git泄露2.1 git知识点2.1 log2.2 stash 三、SVN泄露3.1 SVN简介3.2 SVN的文件3.3 SVN利用 四、Hg泄露 一、备份文件下载 1.1 网站源码 常见的网站源码备份文件后缀&#xff1a; tartar.gz…

非阻塞 IO(NIO)

文章目录 非阻塞 IO(NIO)模型驱动程序应用程序模块使用 非阻塞 IO(NIO) 上一节中 https://blog.csdn.net/tyustli/article/details/135140523&#xff0c;使用等待队列头实现了阻塞 IO 程序使用时&#xff0c;阻塞 IO 和非阻塞 IO 的区别在于文件打开的时候是否使用了 O_NONB…

深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第五节 引用类型复制问题及用克隆接口ICloneable修复

深入浅出图解C#堆与栈 C# Heaping VS Stacking 第五节 引用类型复制问题及用克隆接口ICloneable修复 [深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第一节 理解堆与栈](https://mp.csdn.net/mdeditor/101021023)[深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第二节…

spdlog中的异步日志方案

日志方案 同步日志方案&#xff1a;立即输出日志记录的方案才能继续执行其他任务。 异步日志方案&#xff1a;先抛出一个日志记录的任务到某个地方&#xff0c;不马上执行打印也不影响往下执行其他任务。 二者关键区别是产生日志记录并调用相关的日志任务接口之后&#xff0…

【Kafka】Kafka客户端认证失败:Cluster authorization failed.

背景 kafka客户端是公司内部基于spring-kafka封装的spring-boot版本&#xff1a;3.xspring-kafka版本&#xff1a;2.1.11.RELEASE集群认证方式&#xff1a;SASL_PLAINTEXT/SCRAM-SHA-512经过多年的经验&#xff0c;以及实际验证&#xff0c;配置是没问题的&#xff0c;但是业务…

【JVM】虚拟机的组成+字节码文件组成+类的生命周期

什么是JVM&#xff1f; JVM 本质上是一个运行在计算机上的程序&#xff0c;他的职责是运行Java字节码文件。 JVM的功能 1.解释和运行&#xff1a;对字节码文件中的指令实时的解释成机器码让计算机执行。 2.内存管理&#xff1a;自动为对象、方法等分配内存&#xff0c;自动…

平升电子水库监管平台SQL注入漏洞复现

0x01 产品简介 唐山平升电子水库监管平台通过实时监测、数据分析、预警系统和远程控制等功能&#xff0c;为水库管理部门提供了一种全面、高效的数字化解决方案&#xff0c;帮助他们更好地管理和监控水库&#xff0c;确保水库的安全运行。 0x02 漏洞概述 唐山平升电子水库监…

sqlite3 c++ VS编译生成静态库

官网 https://www.sqlite.org/download.html 下载sqlite-amalgamation和x86版本下载sqlite-dll-win32-x86、x64位版本sqlite-dll-win64-x64 解压 SQLITE-AMALGAMATION包含 shell.csqlite3.csqlite3.hsqlite3ext.hsqlite-dll-win32-x86包含 sqlite3.def sqlite3.dll建立一个空…

Prometheus-JVM

一. JVM监控 通过 jmx_exporter 启动端口来实现JVM的监控 Github Kubernetes Deployment Java 服务&#xff0c;修改 wget https://repo1.maven.org/maven2/io/prometheus/jmx/jmx_prometheus_javaagent/0.19.0/jmx_prometheus_javaagent-0.19.0.jar# 编写配置文件&#xff0…

limit查询报错问题

分页时候 limit 后面的公式是 (pageNum-1)*pageSize,pageSize 但是在数据库查询时候 当然在.XML中也不能像下面这么写,如果要计算 在业务层或者控制层计算好再传值进来

c++ / day01

1. 整理思维导图 2. 定义自己的命名空间myspace&#xff0c;并在myspace中定义一个字符串&#xff0c;实现求字符串大小的函数。 代码 #include <iostream>using namespace std;namespace myns {unsigned long long strlen(string s){return s.length();}}int main() {…

Chatgpt如何共享可以防止封号!

ChatGPT 是一个基于 GPT-3.5/GPT-4 模型的对话系统&#xff0c;它主要用于处理自然语言对话。通过训练模型来模拟人类的语言行为&#xff0c;ChatGPT 可以通过文本交流与用户互动。每个新版本的 GPT 通常都会在模型规模、性能和其他方面有一些改进。在目前免费版GPT-3.5 中&…