数据结构(七)——线性表的基本操作
🧑个人简介:大家好,我是尘觉,希望我的文章可以帮助到大家,您的满意是我的动力😉
在csdn获奖荣誉: 🏆csdn城市之星2名
💓csdn2023年后端赛道第第七
💓csdn2023年长沙赛道第一
💓csdn2023年大二赛道第二
💓Java全栈群星计划top前5
🤗 端午大礼包获得者
🥰阿里云专家博主
😉亚马逊DyamoDB结营
获得国家荣誉3项省级荣誉7项以及多项校院级
💕欢迎大家:这里是CSDN,我总结知识的地方,欢迎来到我的博客,感谢大家的观看🥰
如果文章有什么需要改进的地方还请大佬不吝赐教 先在次感谢啦😊
文章目录
- 数据结构(八)——线性表的基本操作
- 操作中常用的预定义常量与类型
- 初始化(分配空间;赋初值)
- 销毁线性表
- 线性表置空/清空线性表
- 求表长
- 判断线性表是否为空
- 查找算法的算法分析
- 插入算法
- 插入算法的算法分析
- 删除操作
- 删除算法分析
- 线性表的小结;
- 线性表的优缺点
- 优点
- 缺点
数据结构(八)——线性表的基本操作
操作中常用的预定义常量与类型

初始化(分配空间;赋初值)

销毁线性表

线性表置空/清空线性表

求表长

判断线性表是否为空

线性表的按值查找算法(这里我们先说最简单的顺序查找,后面就详细讲解)


查找算法的算法分析
查找算法的基本操作:将记录的关键字同给定值进行比较(L.elem==e)

比较的次数与输入的定值e有关(假设7个数字出现的概率均为1/7)
当e=a,1次;当e=b,2次;当e=c,3次;…e=g,7次
平均比较次数(1+2+3+…+7)/7=4
在查找时,为确定元素在顺序表中的位置,需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度(AverageSearch Length, ASL)。

从顺序表查找的过程可见,C取决于所查元素在表中的位置。例如,查找表中第一个记录时,仅需比较一次;而査找表中最后一个记录时,则需比较n次。一般情况下C等于i。假设每个元素的查找概率相等,即

可简化为

由此可见,顺序表按值查找算法的平均时间复杂度为O(n)。
插入算法


插入位置在最后在线性表的最后添加一个元素不需要移动直接添加
插入位置在最前在原线性表的第1个元素之前插入一个新的元素,线性表的所有元素都要移动移动次数最多
插入位置中间如上例

插入算法的算法分析

删除操作

①判断删除位置i是否合法(合法值为1≤i≤n)
②将欲删除的元素保留在e当中
③将第i+l个至第n个的元素依次向前移动一个位置(i= n时无需移动)
④表长减1

删除算法分析

线性表的小结;
查找、插入、删除的平均算法复杂度为O(n)
空间复杂度显然顺序表操作没有占用辅助空间算法的空间复杂度O(1)
线性表的优缺点
优点
存储密度大(结点本身所占用的空间/结点结构所占存储量=1)无需为表示表中元素之间的逻辑关系,而增加额外的存储空间
可以随机存取表中任意位置的元素
缺点
插入、删除某一元素需移动大量元素
当线性表长度变化较大时,难以确定存储空间的容量,数据元素的个数不能自由扩充(存储空间不灵活)
相关文章:
数据结构(七)——线性表的基本操作
🧑个人简介:大家好,我是尘觉,希望我的文章可以帮助到大家,您的满意是我的动力😉 在csdn获奖荣誉: 🏆csdn城市之星2名 …...
Python 系统学习总结(基础语法+函数+数据容器+文件+异常+包+面向对象)
🔥博客主页: A_SHOWY🎥系列专栏:力扣刷题总结录 数据结构 云计算 数字图像处理 力扣每日一题_ 六天时间系统学习Python基础总结,目前不包括可视化部分,其他部分基本齐全,总结记录࿰…...
汽车碰撞与刮伤的实用维修技术,汽车的车身修复与涂装修补教学
一、教程描述 本套汽车维修技术教程,大小7.44G,共有60个文件。 二、教程目录 01-汽车车身修复教程01-安全规则(共3课时) 02-汽车车身修复教程02-汽车结构(共3课时) 03-汽车车身修复教程03-汽车修复所使…...
网络信息安全:nginx漏洞收集(升级至最新版本)
网络&信息安全:nginx漏洞收集(升级至最新版本) 一、风险详情1.1 nginx 越界写入漏洞(CVE-2022-41742)1.2 nginx 缓冲区错误漏洞(CVE-2022-41741)1.3 nginx 拒绝服务漏洞(CNVD-2018-22806) 二、nginx升级步骤 &…...
【go从入门到精通】go包,内置类型和初始化顺序
大家好,这是我给大家准备的新的一期专栏,专门讲golang,从入门到精通各种框架和中间件,工具类库,希望对go有兴趣的同学可以订阅此专栏。 go基础 。 Go文件名: 所有的go源码都是以 ".go" 结尾&…...
【项目实战】高并发内存池(仿tcmalloc)
【项目实战】高并发内存池(仿tcmalloc) 作者:爱写代码的刚子 时间:2024.2.12 前言: 当前项目是实现一个高并发的内存池,它的原型是google的一个开源项目tcmalloc,tcmalloc全称 Thread-Caching M…...
计算机等级考试:信息安全技术 知识点一
美国联邦政府颁布数字签名标准(Digital Signature Standard,DSS)的年份是1994美国联邦政府颁布高级加密标准(Advanced Encryption Standard,AES)的年份是2001产生认证码的函数类型通常有3类:消息加密、消息认证码和哈希函数。自主访问控制,Di…...
开展庆2024年“三八”国际妇女节系列纪念活动怎样向媒体投稿?
为了向媒体投稿,庆祝2024年“三八”国际妇女节系列纪念活动,你可以遵循以下步骤: 策划与准备: 确定纪念活动的主题和目标,例如提升女性权益、表彰女性成就、促进性别平等。 策划一系列活动,如研讨会、表彰仪式、展览、讲座等,确保内容丰富多样。 准备相关的背景资料、活动介…...
SpringBoot-集成Elasticsearch
jsoup:https://jsoup.org/ 依赖 <!--解析网页--> <dependency><groupId>org.jsoup</groupId><artifactId>jsoup</artifactId><version>1.10.2</version> </dependency> <dependency><groupId>c…...
数据结构之顺序表及其实现!
目录 编辑 1. 顺序表的概念及结构 2. 接口的实现 2.1 顺序表的初始化 2.2 检查顺序表容量是否已满 2.3 顺序表的尾插 编辑 2.4 顺序表的尾删 2.5 顺序表的头插 2.6 顺序表的头删 2.7 顺序表在pos位置插入 2.8 顺序表在pos位置删除 2.9 顺序表的查找 2.10 顺…...
Vue组件间通信实践
Vue组件间通信实践 🌟 前言 欢迎来到我的小天地,这里是我记录技术点滴、分享学习心得的地方。📚 🛠️ 技能清单 编程语言:Java、C、C、Python、Go、前端技术:Jquery、Vue.js、React、uni-app、EchartsUI设…...
FISCO BCOS区块链平台上的智能合约压力测试指南
引言 在当今的分布式系统中,区块链技术因其去中心化、安全性和透明性而备受关注。随着区块链应用的不断扩展,对其性能和稳定性的要求也越来越高。因此,对区块链网络进行压力测试显得尤为重要。 目录 引言 1. 配置FISCO BCOS节点 2. 安装和…...
LabVIEW流量控制系统
LabVIEW流量控制系统 为响应水下航行体操纵舵翼环量控制技术的试验研究需求,通过LabVIEW开发了一套小量程流量控制系统。该系统能够满足特定流量控制范围及精度要求,展现了其在实验研究中的经济性、可靠性和实用性,具有良好的推广价值。 项…...
Python 爱心代码
Python爱心代码是一种用Python编程语言实现的图形化表达方式,可以通过一系列的代码来绘制出一个爱心形状。以下是一个简单的Python爱心代码示例: import turtle # 设置画布和画笔 canvas turtle.Screen() canvas.bgcolor("black") pen turt…...
linux kernel物理内存概述(五)
目录 概述 一、快速路径分配 1、get_page_from_freelist 2、rmqueue()函数 二、慢速路径分配 1、分配流程 三、direct_compact 概述 物理内存分配步骤 1、初始化,参数初始化 2、内存充足,快速分配 get_page_from_freelist 3、内存压力大,慢速…...
3分钟带你搞定电流采样电阻选型
大家好,我是砖一。 一,电流采样电阻的介绍 电流检测电路常用于高压短路保护、电机控制、DC/DC换流器、系统功耗管理、二次电池的电流管理、蓄电池管理等电流检测等场景。 比如,对于电机来说,电流检测电路是为了检测电流功能有比…...
代码随想录算法训练营Day52 | 300.最长递增子序列、674.最长连续递增序列、718.最长重复子数组
300.最长递增子序列 这题的重点是DP数组的定义,子序列必须以nums[i]为最后一个元素,这样dp数组中后面的元素才能与前面的元素进行对比 1、DP数组定义:dp[i]表示以nums[i]为最后一个元素的最长递增子序列长度 2、DP数组初始化:全部…...
一个测试OOM killer的程序未触发OOM所带来的问题
概述 我们知道,由于MMU实现了虚拟地址到物理地址的转换,所以我们在申请虚拟地址时往往可以申请一大块内存,这实际上是对资源的有效利用,毕竟只有内存真正被投入使用时(如memset)才会实际分配物理内存&…...
SanctuaryAI推出Phoenix: 专为工作而设计的人形通用机器人
文章目录 1. Company2. Main2.1 关于凤凰™ (Phoenix)2.2 关于碳™(Carbon)2.3 商业化部署2.4 关于 Sanctuary Corporation 3. My thoughtsReference彩蛋:将手机变为桌面小机器人 唯一入选《时代》杂志 2023 年最佳发明的通用机器人。 称机器人自主做家务的速度和灵…...
李沐动手学习深度学习——4.2练习
1. 在所有其他参数保持不变的情况下,更改超参数num_hiddens的值,并查看此超参数的变化对结果有何影响。确定此超参数的最佳值。 通过改变隐藏层的数量,导致就是函数拟合复杂度下降,隐藏层过多可能导致过拟合,而过少导…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...
