数据结构-2.7.单链表的查找与长度计算

注:本文只探讨"带头结点"的情况(查找思路类似循环找到第i-1 个结点的代码)
一.按位查找:
1.代码演示:
版本一:
#include<stdio.h>
#include<stdlib.h>
//定义单链表结点类型
typedef struct LNode
{int data; //每个结点存放一个数据元素struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;
//初始化一个单链表(带头结点)
bool InitList(LinkList &L)
{L = (LNode *)malloc( sizeof(LNode) ); //分配一个头结点if(L==NULL) //代表内存不足,分配失败-->意味着带头结点的单链表无法创建 {return false;}else{L -> next = NULL; //头结点之后暂时还没有节点,所以指向NULLreturn true; }
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L)
{if(L->next==NULL) //头结点之后如果指向NULL,代表没有数据 {return true;}else{return false;}
}
//按位查找,返回第i个元素(带头结点即第0个结点)
LNode * GetElem(LinkList L,int i)
{if(i<0){return NULL;}LNode *p; //指针p指向当前扫描到的结点 int j=0; //当前p指向的是第几个结点:j为0代表头结点 p=L; //L指向头结点,头结点是第0个结点(不存数据)while(p!=NULL && j<i) //循环找到第i个结点 {p = p->next;j++;} return p;
}
int main()
{//声明一个指向单链表的指针LinkList L;//初始化一个空表InitList(L); return 0;
}
版本二:王道书版本
#include<stdio.h>
#include<stdlib.h>
//定义单链表结点类型
typedef struct LNode
{int data; //每个结点存放一个数据元素struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;
//初始化一个单链表(带头结点)
bool InitList(LinkList &L)
{L = (LNode *)malloc( sizeof(LNode) ); //分配一个头结点if(L==NULL) //代表内存不足,分配失败-->意味着带头结点的单链表无法创建 {return false;}else{L -> next = NULL; //头结点之后暂时还没有节点,所以指向NULLreturn true; }
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L)
{if(L->next==NULL) //头结点之后如果指向NULL,代表没有数据 {return true;}else{return false;}
}
//按位查找,返回第i个元素(带头结点即第0个结点)
LNode * GetElem(LinkList L,int i)
{int j=1; //代表p结点刚开始指向第一个结点(不是头结点) LNode *p=L->next;if(i==0){return L; //返回头结点 }if(i<1){return NULL;}while(p!=NULL && j<i) //循环找到第i个结点 {p = p->next;j++;} return p;
}
int main()
{//声明一个指向单链表的指针LinkList L;//初始化一个空表InitList(L); return 0;
}

2.返回第0个元素即头结点:

3.返回的结点大于链表的长度:
while循环进行到第5次时p指向NULL,不满足下一次循环条件,跳出while循环,此时返回的p为NULL:代表查找失败

最终可知当i值不合法时即i为负数或者i值大于链表长度时最终都返回NULL,因此只需要判断返回结果是否为NULL即可
得知是否查找成功。
4.返回的结点在链表内:

a.计算时间复杂度需要要查找的元素在合法范围内。
b.平均时间复杂度是指此次输入的i值它取的合法范围内的任何一个数字的概率都等可能的情况,
具体的算法和顺序表的按位查找的分析方法一样。
5.封装:
案例一:GetElem用来获取第i个结点,传入参数i-1即可找到第i-1个结点

案例二:后插操作的加入

右下角的InsertNextNode函数中需要一个if(p==NULL)进行是否为空指针的判断,因为如果传入GetElem函数的i值不合法即i-1也不合法,会导致p为NULL即空指针:

二.按值查找:
1.代码演示:
按值查找操作只能从第一个结点开始循环依次向后查找:
#include<stdio.h>
#include<stdlib.h>
//定义单链表结点类型
typedef struct LNode
{int data; //每个结点存放一个数据元素struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;
//初始化一个单链表(带头结点)
bool InitList(LinkList &L)
{L = (LNode *)malloc( sizeof(LNode) ); //分配一个头结点if(L==NULL) //代表内存不足,分配失败-->意味着带头结点的单链表无法创建 {return false;}else{L -> next = NULL; //头结点之后暂时还没有节点,所以指向NULLreturn true; }
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L)
{if(L->next==NULL) //头结点之后如果指向NULL,代表没有数据 {return true;}else{return false;}
}
//按值查找,找到数据域等于e的结点
LNode * LocateElem(LinkList L,int e)
{LNode *p= L->next; //L代表头结点,L->next就是第一个节点,此时p就是第一个结点 //从第一个结点开始查找数据域为e的结点(头结点不存数据,所以不从头结点开始)while(p != NULL && p->data != e){p = p->next;}//找到后返回该节点指针,否则返回NULLreturn p;
}
int main()
{//声明一个指向单链表的指针LinkList L;//初始化一个空表InitList(L); return 0;
}
平均时间复杂度为O(n)。
2.图解:
例一:
p为第一个节点,第一次循环时p不为NULL且p内部的值不为8,符合循环条件,指向p = p->next即向后指一个元素:

第二次循环时p内部的值为8,不符合循环条件,跳出while循环:

例二:


最终返回NULL,代表不存在数据域为6的结点。
3.如果要找的数据域元素不是基本数据类型如结构体类型,就需要复杂的判断:
如结构体(struct)类型要用到运算符"."访问每一个成员变量来比较。
三.求单链表的长度:

四.总结:

相关文章:
数据结构-2.7.单链表的查找与长度计算
注:本文只探讨"带头结点"的情况(查找思路类似循环找到第i-1 个结点的代码) 一.按位查找: 1.代码演示: 版本一: #include<stdio.h> #include<stdlib.h> //定义单链表结点类型 typedef struct LNo…...
iotop 命令:磁盘IO监控和诊断
一、命令简介 iotop命令用于监视磁盘I/O,实时显示每个进程或线程的读写速率等信息。非常适合用于诊断系统中的I/O瓶颈。 安装 iotop 在大多数Linux发行版中,iotop可能不是预装的。可以使用包管理器来安装它。 例如,在…...
解锁编程新境界:GitHub Copilot 让效率翻倍
Number.1:工具介绍 功能特点: 智能代码生成与补全:通过学习大量代码库和开发者的编码风格,能根据上下文自动推断可能的代码补全选项,甚至可以自动完成函数定义、循环结构等复杂代码片段。例如,当编写一个算…...
爱普生相机SD卡格式化后数据恢复指南
我借了朋友的爱普生相机,想查看一下内存,哎呀,一不小心按错了,竟然执行了格式化操作,这可真是太让人郁闷了,这还有机会挽救数据吗?心塞,求帮助! 随着数码摄影的普及&am…...
【数据结构】排序算法---基数排序
文章目录 1. 定义2. 算法步骤2.1 MSD基数排序2.2 LSD基数排序 3. LSD 基数排序动图演示4. 性质5. 算法分析6. 代码实现C语言PythonJavaCGo 结语 ⚠本节要介绍的不是计数排序 1. 定义 基数排序(英语:Radix sort)是一种非比较型的排序算法&…...
二叉树(下)
目录 判断树是否相同 判断树是不是另一棵树的子树 二叉树翻转 判断平衡二叉树 二叉树层序遍历 这篇主要提供一些关于二叉树例题的讲解,如果对二叉树及其基本操作有疑问的可以转至: 二叉树(上)-CSDN博客二叉树(中&…...
计算机网络33——文件系统
1、chmod 2、chown 需要有root权限 3、link 链接 4、unlink 创建临时文件,用于非正常退出 5、vi vi可以打开文件夹 ../是向外一个文件夹 6、ls ls 可以加很多路径,路径可以是文件夹,也可以是文件 ---------------------------------…...
算法:76.最小覆盖子串
题目 链接:leetcode链接 思路分析(滑动窗口) 还是老样子,连续问题,滑动窗口哈希表 令t用的hash表为hash1,s用的hash表为hash2 利用hash表统计窗口内的个字符出现的个数,与hash1进行比较 选…...
DNS服务
一.DNS介绍 DNS应用层协议 Domain Name System 域名系统 作用:实现域名解析,解析主机名所对应的IP地址, 在网络环境中设备与设备之间要想相互通信只能依赖IP地址,DNS服务器的作用是实现域名解析。 如上图所示,DNS存…...
STM32 HAL freertos零基础(九)任务通知
1、任务通知 任务通知用于任务之间同步和通信。任务通知允许一个任务向另一个任务发送一个32位的值,并可以选择是否唤醒正在等待通知的任务。这使得任务之间的同步更加简单和灵活。 任务通知功能: 发送通知:一个任务可以向另一个任务发送一个32位的值。 接收通知:接收任…...
Qt+FFmpeg开发视频播放器笔记(三):音视频流解析封装
音频解析 音频解码是指将压缩的音频数据转换为可以再生的PCM(脉冲编码调制)数据的过程。 FFmpeg音频解码的基本步骤如下: 初始化FFmpeg解码器(4.0版本后可省略): 调用av_register_all()初始化编解码器。 调用avcodec_register_all()注册所有编解码器。 打开输入的音频流:…...
从黎巴嫩电子通信设备爆炸看如何防范网络电子袭击
引言: 在当今数字化时代,电子通信设备已成为我们日常生活中不可或缺的一部分。然而,近期黎巴嫩发生的电子设备爆炸事件提醒我们,这些设备也可能成为危险的武器。本文将深入探讨电子袭击的原理、防范措施,以及网络智能…...
【Verilog学习日常】—牛客网刷题—Verilog快速入门—VL16
使用8线-3线优先编码器Ⅰ实现16线-4线优先编码器 描述 ②请使用2片该优先编码器Ⅰ及必要的逻辑电路实现16线-4线优先编码器。优先编码器Ⅰ的真值表和代码已给出。 可将优先编码器Ⅰ的代码添加到本题答案中,并例化。 优先编码器Ⅰ的代码如下: module…...
12 - TCPServer实验
在上一章节中,我们学习了TCPClient通信测试的相关知识。接下来,本章节将以此为基础,构建一个基础性的TCPServer连接机制,该机制将利用之前所建立的WIFI网络连接。为方便演示,我们将借助网络调试助手工具进行数据的发送…...
Explain执行计划
Explain执行计划 explain可以帮助开发人员分析SQL问题,explain用于显示MySQL如何使用SQL执行计划,可以帮助开发人员写出更优化的查询语句。使用方法就是在查询语句前加上explain关键字。 执行添加上explain关键字的语句可以看到一个列表: 其…...
ARM/Linux嵌入式面经(三六):中科曙光
文章目录 1.AD转换,怎么在项目中运用2.项目中的通信网络介绍一下通信网络介绍1. 通信网络类型2. 通信网络特点3. 应用场景4. 关键技术5. 项目中的具体应用和实现方式模拟面试官追问3.socketSocket介绍深度拓展与追问深度拓展可能的追问4.进程间通信方式进程间通信方式介绍总结…...
Python和C++气候模型算法模型气候学模拟和统计学数据可视化及指标评估
🎯要点 贝叶斯推理气候模型辐射对流及干湿能量平衡模型时间空间气象变化预测模型评估统计指标气象预测数据变换天气和气象变化长短期影响预估降低气候信息尺度评估算法气象行为模拟:碳循环、辐射强迫和温度响应温室气体排放碳循环温室诱导气候变化评估气…...
鸿蒙开发城市联动选择弹框
鸿蒙开发城市联动选择弹框 城市联动选择弹框不容易,在Android那边也是不容易。选择某个省份时,城市要对得上,切换得及时 一、思路: 关键用Provide和Consume互相监听对方的变化 二、效果图: 三、视频效果࿱…...
css 控制虚线刻度尺寸
文章目录 css效果 css <div style"width: 100%; height: 1px;background-image: linear-gradient(to right, #545454 0%, #545454 80%, transparent 5%);background-size: 15px 10px;background-repeat: repeat-x; margin: 0 auto;"></div>效果...
NLP三天入门大模型,我领先你好几个版本了
大模型时代下,nlp初学者需要怎么入门? 入门姿势简单粗暴:打一些必要的基础就跑步进入Transformera 大模型时代,传统的算法,像分词、词性标注,被替代得非常厉害,在入门阶段没必要花费太多精力在传统算法上面。 数学和…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
