【数据结构】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的指针域存储的下一个节点的地址信息赋值给qprintf("%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);//通过按位查找找到前驱结点pif (!p)return false;//如果前驱结点为空指针，则返回falseLNode* 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;//当位序不合法时，返回falseLNode* p = GetElem(*L, i - 1);//通过按位查找找到前驱结点assert(p);//当未找到前驱结点时，将会报错if (!(p->next))return false;//如果前驱结点p为表尾结点，则无法删除位序为i的结点，因此返回falseLNode* q = p->next;//当位序i的结点合法且存在时，将该结点的信息存放进指针q中*e = q->data;//将需要删除的元素存放进变量e中p->next = q->next;//修改前驱结点p的指针域指向的对象free(q);//释放删除结点的内存空间return true;//完成删除后返回true
}

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

结语

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

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

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

代码随想录二刷 ｜ 二叉树 ｜ 最大二叉树

代码随想录二刷 ｜ 二叉树 ｜ 最大二叉树

代码随想录二刷 &#xff5c; 二叉树 &#xff5c; 最大二叉树 题目描述解题思路代码实现 题目描述 654.最大二叉树 给定一个不重复的整数数组 nums 。 最大二叉树可以用下面的算法从 nums 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最大值。递归地在最大值 左…
阅读更多...
SpringSecurity6 | 默认用户生成(上)

SpringSecurity6 | 默认用户生成(上)

✅作者简介：大家好，我是Leo，热爱Java后端开发者，一个想要与大家共同进步的男人😉😉 🍎个人主页：Leo的博客 💞当前专栏： Java从入门到精通 ✨特色专栏： MySQL学习 🥭本文内容：SpringSecurity6 | 默认用户生成(上) 📚个人知识库： [Leo知识库]https://gaozim…
阅读更多...
基于STM8S103F3P6的超声波测距仪设计

基于STM8S103F3P6的超声波测距仪设计

大三的时候给大四学长做的毕业设计题目 文章目录 1 绪论1.1 设计背景1.2 设计的主要任务 2 超声波测距基本理论及总体架构2.1 基本知识2.1.1 超声波特性2.1.2 超声波传感器2.1.3 超声波测距原理 2.2 总体架构2.2.1 设计原则2.2.2 总体方案介绍 2.3 主要器件选择与介绍2.3.1 主控…
阅读更多...
网盘项目话术（0.5w字精选）

网盘项目话术（0.5w字精选）

功能结构图 数据库设计总结 该项目主要就是对文件的操作&#xff0c;file表&#xff0c;file_share表。 file表主要字段&#xff1a;id&#xff0c;用户id&#xff0c;父级目录id&#xff0c;文件的地址&#xff0c;文件的封面图片地址&#xff0c;创建和修改时间。 file_sha…
阅读更多...
react 之 美团案例

react 之 美团案例

1.案例展示 2.环境搭建 克隆项目到本地&#xff08;内置了基础静态组件和模版&#xff09; git clone http://git.itcast.cn/heimaqianduan/redux-meituan.git 安装所有依赖 npm i 启动mock服务&#xff08;内置了json-server&#xff09; npm run serve 启动前端服务 npm…
阅读更多...
Translation翻译插件

Translation翻译插件

Translation插件是为IntelliJ IDEA开发的&#xff0c;因此只能在IntelliJ IDEA中使用。但是&#xff0c;如果你需要在其他软件中进行翻译&#xff0c;可以考虑使用其他的翻译工具或服务。例如&#xff0c;一些在线翻译网站&#xff08;如Google翻译、百度翻译等&#xff09;提供…
阅读更多...
VScode——下载、安装、配置C/C++环境（windows）

VScode——下载、安装、配置C/C++环境（windows）

一.快速下载 还在因为vscode官方下载慢而头疼嘛&#xff0c;按这个步骤来直接起飞兄弟萌 首先进入vscode官方网站然后选择对应版本下载然后进入浏览器下载页面复制下载链接粘贴到地址栏 将地址中的/stable前换成vscode.cdn.azure.cn 即可实现超速下载 下面是一个国内镜像的下…
阅读更多...
mysql原理--MySQL基于规则的优化

mysql原理--MySQL基于规则的优化

设计 MySQL 的大叔依据一些规则&#xff0c;竭尽全力的把一些很糟糕的语句转换成某种可以比较高效执行的形式&#xff0c;这个过程也可以被称作 查询重写 &#xff08;就是人家觉得你写的语句不好&#xff0c;自己再重写一遍&#xff09;。 1.条件化简 我们编写的查询语句的搜…
阅读更多...
vue虚拟列表展示

vue虚拟列表展示

效果图 <template><!-- 总体高度区域 --><divref"listWrap"class"m-container"scroll"scrollListener"><div:style"handleContainerHeight()"><!-- 可视区域 --><divclass"m-area":style&…
阅读更多...
打地鼠游戏来了

打地鼠游戏来了

主要利用js鼠标点击事件和window.setInterval&#xff08;&#xff09;回调函数来进行实现的. 源码获取方式&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1eW9qvX3zFH9qlH82-I4yOA 提取码&#xff1a;1233
阅读更多...
中间件系列 - Redis入门到实战(原理篇)

中间件系列 - Redis入门到实战(原理篇)

前言 学习视频&#xff1a; 黑马程序员Redis入门到实战教程&#xff0c;深度透析redis底层原理redis分布式锁企业解决方案黑马点评实战项目 中间件系列 - Redis入门到实战 本内容仅用于个人学习笔记&#xff0c;如有侵扰&#xff0c;联系删除 学习目标 Redis数据结构Redis网…
阅读更多...
Matlab：非线性规划

Matlab：非线性规划

1、语法&#xff1a; xfmincon(fun,x0,A,b) xfmincon(fun,x0,A,b,Aeq,beq) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) xfmincon(problem) [x,fval]fmincon(___) [x,fval,exitflag,…
阅读更多...
搭建FTP服务器详细介绍

搭建FTP服务器详细介绍

一.FTP简介 &#xff11;.&#xff11;什么是FTP &#xff11;.&#xff12;FTP服务器介绍 &#xff11;.&#xff13;FTP服务器优缺点 二.FTP服务器的搭建与配置 2.1 开启防火墙 2.2创建组 2.3创建用户 2.4安装FTP服务器 2.5配置FTP服务器 &#xff12;.&#xff…
阅读更多...
日常中msvcp120.dll丢失五种解决方法

日常中msvcp120.dll丢失五种解决方法

在日常使用电脑的过程中&#xff0c;我们可能会遇到一些错误提示&#xff0c;其中之一就是“msvcp120.dll丢失”。那么&#xff0c;msvcp120.dll到底是什么&#xff1f;它的作用又是什么呢&#xff1f;为什么会出现丢失的情况呢&#xff1f;本文将为您详细介绍msvcp120.dll的相…
阅读更多...
无法连接虚拟机设备 ide1：0，因为主机上没有相应的设备。您要每次在开启此虚拟机时都尝试连接此虚拟设备吗？

无法连接虚拟机设备 ide1：0，因为主机上没有相应的设备。您要每次在开启此虚拟机时都尝试连接此虚拟设备吗？

Vmware报错&#xff1a; 报错原因&#xff1a; ide1:0一般是虚拟机的光驱&#xff0c;配置选项是“使用物理驱动器”&#xff0c;而宿主机可能没有安装光驱&#xff0c;故无法从驱动器上寻找 .ISO 系统文件。 解决方法: 右键点击对应的虚拟机&#xff0c;再点击“设置”按钮。…
阅读更多...
百度每天20%新增代码由AI生成，Comate SaaS服务8000家客户 采纳率超40%

百度每天20%新增代码由AI生成，Comate SaaS服务8000家客户 采纳率超40%

12月28日&#xff0c;由深度学习技术及应用国家工程研究中心主办的WAVE SUMMIT深度学习开发者大会2023在北京召开。百度首席技术官、深度学习技术及应用国家工程研究中心主任王海峰现场公布了飞桨文心五载十届最新生态成果&#xff0c;文心一言最新用户规模破1亿&#xff0c;截…
阅读更多...
轻量应用服务器与云服务器CVM对比——腾讯云

轻量应用服务器与云服务器CVM对比——腾讯云

腾讯云轻量服务器和云服务器CVM该怎么选&#xff1f;不差钱选云服务器CVM&#xff0c;追求性价比选择轻量应用服务器&#xff0c;轻量真优惠呀&#xff0c;活动 https://curl.qcloud.com/oRMoSucP 轻量应用服务器2核2G3M价格62元一年、2核2G4M价格118元一年&#xff0c;540元三…
阅读更多...
❀My学习小记录之算法❀

❀My学习小记录之算法❀

目录 算法:) 一、定义 二、特征 三、基本要素 常用设计模式 常用实现方法 四、形式化算法 五、复杂度 时间复杂度 空间复杂度 六、非确定性多项式时间&#xff08;NP&#xff09; 七、实现 八、示例 求最大值算法 求最大公约数算法 九、分类 算法:) 一、定义 …
阅读更多...
dvwa问题篇 -- dvwa出现数据库无法访问的时候，Could not connect to the MySQL service. -- 小黑解决教程

dvwa问题篇 -- dvwa出现数据库无法访问的时候，Could not connect to the MySQL service. -- 小黑解决教程

各位小伙伴初次玩dvwa会出现各种问题&#xff0c;本来想把一些问题直接总结写一篇dvwa文章来着&#xff0c;但因为都是关键字搜索&#xff0c;所以将一些问题都拆分出来&#xff0c;以便大家方便查类似问题。&#xff08;大家有遇到不一样的问题欢迎投稿&#xff01;&#xff0…
阅读更多...
VSCode 如何安装插件的历史版本

VSCode 如何安装插件的历史版本

背景 在日常开发过程中&#xff0c;我们可能会遇到新版VSCode插件存在问题&#xff0c;无法正常工作的情况。这种情况下&#xff0c;一种可行的解决方案就是安装插件的历史版本。VSCode 插件默认安装的都是插件最新的版本&#xff0c;例如下面 vscode-styled-compoents 插件 本…
阅读更多...
最新文章

Copyright @ 2022~2023