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

单链表基本操作的实现

  • 导言
  • 一、查找操作
    • 1.1 按位查找
      • 1.1.1 按位查找的C语言实现
      • 1.1.2 按位查找的时间复杂度
    • 1.2 按值查找
      • 1.2.1 按值查找的C语言实现
      • 1.2.2 按值查找的时间复杂度
  • 二、插入操作
    • 2.1 后插操作
    • 2.2 前插操作
  • 三、删除操作
  • 结语

封面

导言

大家好，很高兴又和大家见面啦！！！
在上一篇中，我们详细介绍了单链表的两种创建方式——头插法与尾插法，相信大家现在对这两种方式都已经掌握了。今天咱们将继续介绍单链表的基本操作——查找、插入与删除。在开始今天的内容之前，我们先通过尾插法创建一个单链表，如下所示：

//定义单链表数据类型
typedef struct LNode{
	int data;//数据域
	struct LNode* next;//指针域
}LNode, * LinkList;//结点与单链表数据类型
//初始化单链表
bool InitList(LinkList* L)//二级指针接收头指针的地址
{
	*L = (LNode*)calloc(1, sizeof(LNode));//为头结点申请空间
	if (!(*L)){
		return false;
	}
	(*L)->next = NULL;//将头结点定义域初始化为空指针，防止出现野指针
	return true;
}
//尾插法创建单链表
LinkList List_TailInsert(LinkList* L)
{
	assert(*L);//通过assert断言确保链表头指针不是空指针
	LNode* r = *L;//指向新结点的指针
	LNode* l = *L;//指向尾结点的指针
	int x = 0;//存储数据域元素的变量
	while (scanf("%d", &x) == 1)//通过scanf获取数据域存放的数据，这里采用多组输入简化代码
	{
		r = (LNode*)calloc(1, sizeof(LNode));//为新结点申请空间
		assert(r);//通过assert断言确保新结点成功申请了空间
		r->data = x;//将数据信息存放进新结点的数据域中
		r->next = l->next;//将尾节点指针域存放的地址信息存放进新结点的指针域中
		l->next = r;//将尾节点的指针域指向新节点的起始地址
		l = r;//新结点变成尾结点
	}
	return (*L);//返回链表
}
//打印链表
void Print_LinkList(LinkList L)
{
	printf("\n打印链表数据域的各个元素:>");
	LNode* p = L;//指向前一个节点的指针
	LNode* q = L;//指向后一个节点的指针
	while (q->next)//当q的指针域指向空指针时，表示q此时为表尾结点，不需要继续打印，直接退出循环
	{
		q = p->next;//将指针p的指针域存储的下一个节点的地址信息赋值给q
		printf("%d ", q->data);//此时指针q指向的需要打印的节点起始地址
		p = q;//将指针p指向已经打印过的节点
	}
	printf("\n");
}
int main()
{
	LinkList L;//指向单链表的指针L——头指针
	//初始化单链表
	if (InitList(&L)){
		L = List_TailInsert(&L);//创建单链表——尾插法
		Print_LinkList(L);//打印单链表
	}
	else{
		printf("初始化失败\n");//对初始化失败进行错误提示
	}
	return 0;
}

此时咱们就成功创建了一个顺序存放的单链表，如下图所示：
尾插法创建单链表
现在有了这个单链表后，我们就可以对其进行查找、插入与删除等操作了。那这些操作又应该如何实现呢？下面我们就来一一介绍；

一、查找操作

单链表的查找操作同样可以分为按位查找与按值查找，下面我们就来看一下这两种查找方式有什么不同。

1.1 按位查找

单链表是一个非随机存取的存储结构，因此我们想要找到位序i上的结点，只能从表头元素开始依次查找，所以在对单链表进行按位查找时会存在几种情况：

  • 需要查找的位序不合理，此时我们不能进行查找，需要给使用者一定的反馈；
  • 找到了对应位序的结点，此时我们需要将该结点返回给函数；
  • 没有找到对应位序的结点，当我们要找的结点为空指针时，说明已经将链表全部查找完，所以我们需要返回空指针；

对于这些情况，我们在编写查找功能时，就需要将这些可能发生的情况转换为代码，下面我们就来尝试一下；

1.1.1 按位查找的C语言实现

在通过C语言实现按位查找前，我们需要将自己的编写思路梳理一下：

  1. 我们在查找时需要判断该结点的位序与目标位序是否相等：
    • 相等则找到了，就不需要继续查找；
    • 小于目标位序则继续查找；
  2. 我们在查找时还需要判断查找的结点是否为空指针：
    • 不为空指针，表示还未查找完，可以继续查找；
    • 为空指针，表示已经查找完，需不要继续查找；

有了思路，我们就可以开始编写代码了，如下所示：

//按位查找
LNode* GetElem(LinkList L, int i)
{
	if (i < 1)
		return NULL;//当位序<1时，此时的位序不合理，返回空指针
	LNode* p = L->next;//寻找目标结点的指针,从表头结点开始查找
	int j = 1;//寻找的结点位序
	while (p && j < i)//当位序j与i相等时表示找到了对应的结点，退出循环；
	//当p为空指针时，表示查找完成，没有找到对应的结点，退出循环
	{
		p = p->next;//指针p指向下一个结点
		j++;//查找下一个位序
	}
	return p;//查找结束后返回指针p
}

这个代码能否实现咱们的按位查找功能呢？我们测试一下：
按位查找
可以看到我们很好的通过C语言实现了单链表的按位查找。

1.1.2 按位查找的时间复杂度

我们在进行按位查找时，查找的过程会有三种情况：

  • 最好情况，要查找的结点为表头结点，此时按位查找的时间复杂度为O(1)；
  • 最坏情况，要查找的结点为表尾结点，此时按位查找的时间复杂度为O(n)；
  • 平均情况，要查找的每个结点的概率是相同的，因此，我需要查找的次数与元素对应的位序是成正比的，所以此时按位查找的时间复杂度为O(n)；

1.2 按值查找

单链表的按值查找与按位查找的逻辑相同，都是从表头结点开始查找，只不过在查找的内容上会有区别，按位查找查找的是位序，而按值查找查找的是数据域内存储的元素。在查找的过程中也会有以下几种情况：

  • 找到了对应的值，此时我们需要将该值所在的结点返回给函数；
  • 没有找到对应的值，此时我们需要给函数返回一个空指针；

对于按值查找而言，此时我们是不需要对值的合理性进行判断的，因此我们只需要完成从表头开始查找的工作就行。

1.2.1 按值查找的C语言实现

为了更好的实现按值查找，我来梳理一下编写思路：

  1. 我们在查找的过程中需要判断查找结点的数据域与目标值是否相等：
    • 不相等，表示还未找到对应的结点，需要继续查找；
    • 相等，表示已经找到了对应的结点，可以结束查找；
  2. 我们在查找的过程中还需要判断查找的结点是否为空指针：
    • 结点为空指针，表示已经查找完所有结点，此时不需要继续查找；
    • 结点不为空指针，表示还未查找完，需要继续查找；；

有了具体的思路，我们就可以开始编写代码了：

//按值查找
LNode* LocateElem(LinkList L, int e)
{
	LNode* p = L->next;//寻找目标结点的指针，从表头结点开始寻找
	while (p && p->data != e)//当结点数据域存放的值与目标值相等时，表示找到了对应结点，退出循环
	//当p为空指针时表示查找完全部结点，没有找到对应结点，退出循环
	{
		p = p->next;//指针p指向下一个节点
	}
	return p;//完成查找后返回指针p
}

下面我们来测试一下此时能否完成按值查找的功能：
按值查找
从测试结果中我们可以看到，此时很好的完成了按值查找的功能。

1.2.2 按值查找的时间复杂度

我们在进行按值查找时，查找的过程会有三种情况：

  • 最好情况，要查找的结点为表头结点，此时按位查找的时间复杂度为O(1)；
  • 最坏情况，要查找的结点为表尾结点，此时按位查找的时间复杂度为O(n)；
  • 平均情况，要查找的每个结点的概率是相同的，因此，我需要查找的次数与元素对应的位序是成正比的，所以此时按值查找的时间复杂度为O(n)；

二、插入操作

因为单链表的各个元素是离散的分布在内存中的，因此我们想要插入新的结点时，就不需要像顺序表那样移动大量的元素，但是，我们想要插入新结点时需要先找到插入位序的前一个结点，才能将新的结点插入到单链表中，如下图所示：
插入操作
由于单链表的特性是只能从前往后查找，因此要想实现单链表的插入操作只能够借助前一个结点。

2.1 后插操作

通过上图这种方式实现的插入操作我们将其称之为后插操作。

不难发现，在带头结点的单链表中，不管是头插法创建的单链表，还是后插法创建的单链表，它们插入新结点的逻辑都是通过后插操作实现的，也就是说对于后插法的插入过程实际上就是我们前面提到的过程：

//插入操作
New_LNode->next = Ahead_LNode->next;//将前一个位序的结点的指针域指向的内容存放入新结点的指针域中
Ahead_LNode->next = New_LNode;//将新结点的位置信息存放入前一个结点的指针域中

只不过在进行后插前我们需要先通过按位查找找到前一个结点的位序，然后再进行插入操作，因此后插操作的完整流程应该是：

//插入过程
Ahead_LNode = GetElem(L, i - 1);//通过调用按位查找函数来找到位序为i-1的节点
New_LNode->next = Ahead_LNode->next;//将前一个位序的结点的指针域指向的内容存放入新结点的指针域中
Ahead_LNode->next = New_LNode;//将新结点的位置信息存放入前一个结点的指针域中

将后插操作封装为一个函数的话，我们可以编写如下代码：

//后插操作
bool InsertNextNode(LinkList L,int i, ElemType e)
{
	LNode* p = GetElem(L, i - 1);//通过按位查找找到前驱结点p
	if (!p)
		return false;//如果前驱结点为空指针，则返回false
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//为新结点申请空间
	assert(s);//如果空间申请失败，则报错
	s->data = e;//将要插入的元素存放入新结点的数据域中
	s->next = p->next;//将新结点的指针域指向前驱结点的指针域指向的空间
	p->next = s;//将新结点的地址存放入前驱结点的指针域中
	return true;//完成插入操作则返回true
}

因此这里调用了按位查找的函数，因此对于后插操作来说，此时的时间复杂度为O(n)；

下面我们思考一个问题，我们能不能在一个结点的前面进行插入操作呢？

2.2 前插操作

在单链表中，如果我们想实现在结点的前面插入一个新结点，这是不现实的，根据单链表的特性来看，我们只能够通过后插的方式来插入新结点，这样才能保证各个结点能够通过指针域的指向相互联系起来，但是我们可以换一种角度来模拟实现前插操作，如下所示：

前插操作
从图中可以看到，我们在执行前插操作的步骤是：

  1. 通过后插操作对位序i的结点后插入一个新结点，只不过插入的新结点的数据域未存放元素；
  2. 之后再将位序i结点的数据域存放的元素放入新结点中；
  3. 最后再将新的元素放入位序i的结点的数据域中；

看似我们现在完成的是完成了前插操作，实质上完成的依旧是一次后插操作。下面我们通过C语言来描述前插操作：

//前插操作
bool InsertPriorNode( LNode* p, ElemType e)//需要指向前插操作的指针p与需要插入的数据e
{
	if (!p)
		return false;//如果需要指向前插操作的指针p为空指针，则无法执行前插操作
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//插入的新结点
	assert(s);//如果新结点申请空间失败，则报错
	s->data = p->data;//将p结点的数据域中的数据放置到新结点中
	s->next = p->next;//将p结点的指针域中的数据放置到新结点中
	p->next = s;//将新结点的位置信息放置到p结点的指针域中
	p->data = e;//将需要插入的数据信息放入到p结点的数据域中
	return true;//完成插入操作后返回true
}

前插操作因为不需要进行搜索结点p的前驱结点，因此在已知结点p的情况下，前插操作的时间复杂度为O(1)；

通过前插操作与后插操作的对比我们可以看到，在已知需要执行插入操作的节点p时，前插操作通过进行数据的移动这个操作就规避了需要查找前驱结点的步骤，大幅度提高了算法的效率。

三、删除操作

在单链表中，如果我们需要删除一个元素，那我们需要执行的逻辑应该是：

  1. 找到需要删除元素的前驱结点；
  2. 修改前驱结点的指针域指向的对象；
  3. 释放需要删除元素结点的内存空间；

通过删除操作的逻辑，不难想象，因为需要通过遍历整个链表来寻找需要删除的结点的前驱结点，因此删除操作的时间复杂度为O(n)。将这个逻辑转换成C语言，则如下所示：

//删除操作
bool ListDelete(LinkList* L, int i, ElemType* e)
{
	if (i < 1)
		return false;//当位序不合法时，返回false
	LNode* p = GetElem(*L, i - 1);//通过按位查找找到前驱结点
	assert(p);//当未找到前驱结点时，将会报错
	if (!(p->next))
		return false;//如果前驱结点p为表尾结点，则无法删除位序为i的结点，因此返回false
	LNode* q = p->next;//当位序i的结点合法且存在时，将该结点的信息存放进指针q中
	*e = q->data;//将需要删除的元素存放进变量e中
	p->next = q->next;//修改前驱结点p的指针域指向的对象
	free(q);//释放删除结点的内存空间
	return true;//完成删除后返回true
}

下面我们来测试一下删除操作与插入操作，将单链表中位序为3的结点删除后在位序4处插入新的结点，如下所示：
插入与删除操作
可以看到，此时咱们已经实现了单链表的插入与删除操作。

结语

咱们今天的内容到这里就全部结束了，今天咱们详细介绍了单链表的查找、插入、删除操作的实现，希望这篇内容能够帮助大家更好的理解这些基本操作。

在下一篇内容中我们会继续介绍链表的第二种形式——双链表，大家记得关注哦！最后感谢各位的翻阅，咱们下一篇见！！！

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

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

相关文章

10 分钟了解 nextTick ，并实现简易版的 nextTick

10 分钟了解 nextTick ，并实现简易版的 nextTick

前言 在 Vue.js 中&#xff0c;有一个特殊的方法 nextTick&#xff0c;它在 DOM 更新后执行一段代码&#xff0c;起到等待 DOM 绘制完成的作用。本文会详细介绍 nextTick 的原理和使用方法&#xff0c;并实现一个简易版的 nextTick&#xff0c;加深对它的理解。 一. 什么是 n…
阅读更多...
深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第一节 理解堆与栈

深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第一节 理解堆与栈

深入浅出图解C#堆与栈 C# HeapingVS Stacking第一节 理解堆与栈 [深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第一节 理解堆与栈](https://mp.csdn.net/mdeditor/101021023)[深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第二节 栈基本工作原理](https://mp.csdn.n…
阅读更多...
Python 小程序之动态二位数组

Python 小程序之动态二位数组

动态二位数组 文章目录 动态二位数组前言一、基本内容二、代码编写三、效果展示 前言 没想出啥好点子&#xff0c;这次就给大家写个小程序&#xff0c;动态二维数组吧。 一、基本内容 程序画一个二维的方格&#xff0c;然后里面填上1-10的随机数&#xff0c;每隔一秒更新新一…
阅读更多...
网工内推 | 网络服务工程师，HCIE认证优先，带薪年假，年终奖

网工内推 | 网络服务工程师，HCIE认证优先，带薪年假，年终奖

01 高凌信息 招聘岗位&#xff1a;服务工程师&#xff08;珠海&#xff09; 职责描述&#xff1a; 1、负责华为数通&#xff08;交换机、路由器&#xff09;、IT&#xff08;服务器、存储&#xff09;等任一或多个产品领域的项目实施交付&#xff1b; 2、独立完成华为数通&…
阅读更多...
【信息安全原理】——拒绝服务攻击及防御（学习笔记）

【信息安全原理】——拒绝服务攻击及防御（学习笔记）

&#x1f4d6; 前言&#xff1a;拒绝服务攻击&#xff08;Denial of Service, DoS&#xff09;是一种应用广泛、难以防范、严重威胁网络安全&#xff08;破坏可用性&#xff09;的攻击方式。本章主要介绍DoS的基本概念、攻击原理及防御措施。 目录 &#x1f552; 1. 定义&#…
阅读更多...
Python面向对象高级与Python的异常、模块以及包管理

Python面向对象高级与Python的异常、模块以及包管理

Python面向对象高级与Python的异常、模块以及包管理 一、Python中的继承 1、什么是继承 我们接下来来聊聊Python代码中的“继承”：类是用来描述现实世界中同一组事务的共有特性的抽象模型，但是类也有上下级和范围之分，比如：生物 => 动物 => 哺乳动物 => 灵长型…
阅读更多...
【精简】解析xml文件 解决多个同名标签问题 hutool

【精简】解析xml文件 解决多个同名标签问题 hutool

一、测试XML报文用例 <?xml version"1.0" encoding"UTF-8"?> <TEST><PUB><TransSource>ERP</TransSource><TransCode>DsbrRpl</TransCode><TransSeq>202204081043</TransSeq><Version>1.0…
阅读更多...
如何使用凹凸贴图和位移贴图制作逼真的模型

如何使用凹凸贴图和位移贴图制作逼真的模型

在线工具推荐&#xff1a; 3D数字孪生场景编辑器 - GLTF/GLB材质纹理编辑器 - 3D模型在线转换 - Three.js AI自动纹理开发包 - YOLO 虚幻合成数据生成器 - 三维模型预览图生成器 - 3D模型语义搜索引擎 本教程将解释如何应用这些效应背后的理论。在以后的教程中&#xff0…
阅读更多...
【C语言】初识C语言

【C语言】初识C语言

本章节主要目的是基本了解C语言的基础知识&#xff0c;对C语言有一个大概的认识。 什么是C语言 在日常生活中&#xff0c;语言就是一种人与人之间沟通的工具&#xff0c;像汉语&#xff0c;英语&#xff0c;法语……等。而人与计算机之间交流沟通的工具则被称为计算机语言&am…
阅读更多...
任务调度-hangfire

任务调度-hangfire

目录 一、Hangfire是什么&#xff1f; 二、配置服务 1.配置Hangfire服务 2.添加中间件 3.权限控制 三、配置后台任务 1.在后台中调用方法 2.调用延时方法 3.执行周期性任务 四、在客户端上配置任务 1.在AddHangfire添加UseHangfireHttpJob方法 2.创建周期任务 3.创建只读面板 总…
阅读更多...
硅像素传感器文献调研（三）

硅像素传感器文献调研（三）

写在前面&#xff1a; 引言&#xff1a;也是先总结前人的研究结果&#xff0c;重点论述其不足之处。 和该方向联系不大&#xff0c;但还是有值得学习的地方。逻辑很清晰&#xff0c;易读性很好。 1991年—场板半阻层 使用场板和半电阻层的高压平面器件 0.摘要 提出了一种…
阅读更多...
低代码，前端工程化项目的未来

低代码，前端工程化项目的未来

一、前言 在软工圣经《人月神话》一书中&#xff0c;作者Brooks指出了软件发展的一个僵局&#xff1a;在落后的项目中增加人手&#xff0c;只会使进度更加落后。 为了更快完成项目&#xff0c;开发团队会发展的极其庞大&#xff0c;以致于所有的时间都花费在沟通和变更决策上&a…
阅读更多...
软件测试面试中90%会遇到的问题，面试前刷提高百分之60的通过率

软件测试面试中90%会遇到的问题，面试前刷提高百分之60的通过率

面试的时候&#xff0c;遇到这样的提问&#xff0c;很多人的都会感觉脑子一下一片空白&#xff0c;或者星星点点&#xff0c;不知道从何说起。 一方面不知道面试官问这个问题的意图是什么&#xff1f;也不知道他想得到的答案是什么&#xff1f; 更加不知道该从哪些方面来回答…
阅读更多...
vue3 根据用户权限控制左侧菜单和路由拦截

vue3 根据用户权限控制左侧菜单和路由拦截

目录 前言 整体思路 详细开发 1.左侧菜单的显隐控制 2.控制路由权限 补充权限控制 总结 前言 我这里是vue3开发的一个后台管理系统&#xff0c;所以涉及用户权限管理&#xff0c;以及页面权限等&#xff0c;其他模块部分可以查看专栏&#xff0c;这里只对怎么实现根据用…
阅读更多...
异步通知

异步通知

文章目录 一、异步通知1、应用场景2、执行流程&#xff08;基于读取按键值的情景&#xff09;2.1、应用程序具体做什么&#xff1f;2.2、驱动程序具体做什么&#xff1f; 三、程序1、驱动程序2、测试应用程序 三、总结 一、异步通知 1、应用场景 当应用程序不想休眠时&#x…
阅读更多...
记录一下亿级别数据入库clickhouse

记录一下亿级别数据入库clickhouse

需求背景 公司的业务主要是广告数据归因的&#xff0c;每天的pv数据和加粉数据粗粗算一下&#xff0c;一天几千万上亿是有的。由于数据量大&#xff0c;客户在后台查询时间跨度比较大的数据时&#xff0c;查询效率就堪忧。因而将数据聚合后导到clickhouse进行存储&#xff0c;…
阅读更多...
数据库系统原理例题之——SQL 与关系数据库基本操作

数据库系统原理例题之——SQL 与关系数据库基本操作

SQL 与关系数据库基本操作 第四章 SQL 与关系数据库基本操作【例题】一 、单选题二 、填空题三 、简答题四 、设计题 【答案&解析】一、单选题二、填空题三、简答题四、设计题 【延伸知识点】【延伸知识点答案&解析】 第四章 SQL 与关系数据库基本操作 【例题】 一 、…
阅读更多...
视频美颜SDK趋势畅想：未来发展方向与应用场景

视频美颜SDK趋势畅想：未来发展方向与应用场景

当下&#xff0c;视频美颜SDK正不断演进&#xff0c;本文将深入探讨视频美颜SDK的发展趋势&#xff0c;探讨未来可能的方向和广泛的应用场景。 1.深度学习与视频美颜的融合 未来&#xff0c;我们可以期待看到更多基于深度学习算法的视频美颜SDK&#xff0c;为用户提供更高质量…
阅读更多...
国标标准和行业标准使用介绍

国标标准和行业标准使用介绍

场景 我现在所在行业是交通行业&#xff0c;主要做城市交通信控相关的工作&#xff0c;后续可能会涉及高速、收费站、稽核收费等业务场景在做产品开发时&#xff0c;我们需要有一个标准可以参考&#xff0c;这些标准必须是公认的&#xff0c;这时就用到了 国家标准、行业标准等…
阅读更多...
Python流星雨完整代码

Python流星雨完整代码

文章目录 环境需求完整代码详细分析环境需求 python3.11.4PyCharm Community Edition 2023.2.5pyinstaller6.2.0（可选，这个库用于打包，使程序没有python环境也可以运行，如果想发给好朋友的话需要这个库哦~）【注】 python环境搭建请见：https://want595.blog.csdn.net/arti…
阅读更多...
最新文章

Copyright @ 2022~2023