数据结构问答8
查找
1. 一些基本概念
关键字:能唯一标识该元素
查找:给定值k,在含n个元素的表中找出关键字==k的元素。找到返回其位置信息,否则返回-1。
动、静态查找表:查找同时对表进行修改(插入、删除等),相应的表为动态,否则为静态。
内、外查找:整个查找过程在内存中进行,称之为内查找;需要访问外存,则为外查找。
平均查找长度ASL:∑pici,pi:查找第i个元素的概率,一般为1/n,ci:找到第i个元素所需进行的关键字的比较次数。
2. 怎样评价一个查找算法?
答:通过平均查找长度ASL。其数量级反应了查找算法的时间复杂度。
顺序表的查找
3. 顺序查找
答:
基本思想:从表的一端开始顺序扫描顺序表,依次扫描到的元素关键字与k比较,若找到,查找成功;若扫描结束也未找到,则失败。
时间复杂度:O(n)
优点:算法简单,且对表的结构无任何要求。
缺点:查找效率低。
4. 折半查找
答:要求线性表是有序表。不适合链式存储结构的数据查找。
基本思想:在[low, high]之间查找目标关键字,每次检查mid=(low+high)/2,根据mid所指元素与目标关键字的大小调整low和high,不断缩小low和high的范围,当low>high时则查找失败。
判定树(或判定表)构造及特性:
构造:由mid所指元素将原有元素分割到左右子树中。
特性:① 折半查找的判定树是是平衡的二叉排序树(左<中<右)
② 只有最下面一层试不满的
③ 若查找表有n个关键字,则失败结点有n+1个
④ 树高h=log2(n+1)上取整,不包含失败结点
时间复杂度:O(log2n)
优点:查找效率高
缺
相关文章:
数据结构问答8
查找 1. 一些基本概念 关键字:能唯一标识该元素 查找:给定值k,在含n个元素的表中找出关键字==k的元素。找到返回其位置信息,否则返回-1。 动、静态查找表:查找同时对表进行修改(插入、删除等),相应的表为动态,否则为静态。 内、外查找:整个查找过程在内存中进行…...
行为型设计模式之观察者模式【设计模式系列】
系列文章目录 C技能系列 Linux通信架构系列 C高性能优化编程系列 深入理解软件架构设计系列 高级C并发线程编程 设计模式系列 期待你的关注哦!!! 现在的一切都是为将来的梦想编织翅膀,让梦想在现实中展翅高飞。 Now everythi…...
vue2企业级项目(四)
vue2企业级项目(四) 路由设计,过场动画设计 1、router 项目下载依赖 npm install --save vue-router3.5.3src目录下创建router/index.js import Vue from "vue"; import Router from "vue-router";Vue.use(Router);con…...
(树) 剑指 Offer 26. 树的子结构 ——【Leetcode每日一题】
❓剑指 Offer 26. 树的子结构 难度:中等 输入两棵二叉树 A 和 B,判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构) B 是 A 的子结构, 即 A 中有出现和B相同的结构和节点值。 例如: 给定的树 A: 3/ \4 5/ \1 2给定的树 B&…...
Linuxcnc-ethercat从入门到放弃(1)、环境搭建
项目开源网站 LinuxCNChttps://www.linuxcnc.org/当前release版本2.8.4 Downloads (linuxcnc.org)https://www.linuxcnc.org/downloads/可以直接下载安装好linuxcnc的实时debian系统,直接刻盘安装就可以了 安装IgH主站,网上有很多教程可供参考 git clo…...
14.Netty源码之模拟简单的HTTP服务器
highlight: arduino-light 简单的 HTTP 服务器 HTTP 服务器是我们平时最常用的工具之一。同传统 Web 容器 Tomcat、Jetty 一样,Netty 也可以方便地开发一个 HTTP 服务器。我从一个简单的 HTTP 服务器开始,通过程序示例为你展现 Netty 程序如何配置启动&a…...
万年历【小游戏】(Java课设)
系统类型 Java实现的小游戏 使用范围 适合作为Java课设!!! 部署环境 jdk1.8Idea或eclipse 运行效果 更多Java课设系统源码地址:更多Java课设系统源码地址 更多Java小游戏运行效果展示:更多Java小游戏运行效果展…...
ad+硬件每日学习十个知识点(9)23.7.20
文章目录 1.正点原子fpga开拓者无gui检查项目2.排针连接器A2541WR-XP-2P3.肖特基二极管反接在LDO的输出端,是什么用?4.在AD中如何实现批量元器件的移动?5.在PCB中,如何让元器件以任意角度旋转?6.接口设计都要做静电防护…...
ipmitool 配置BMC的ip
要使用ipmitool配置BMC的IP地址,可以按照以下步骤进行操作: 确保已安装ipmitool工具。如果尚未安装,可以使用以下命令进行安装: |复制代码 sudo yum install ipmitool连接到BMC:使用IPMI-over-LAN(通过网…...
C++设计模式::小结(creation)
creation:隐藏创建逻辑. 1) 抽象工厂模式(Abstract Factory Pattern):多层次"任选"创建对象; 实现: 1) cShape:抽象对象; cShape*:具体对象; 2) cColor:抽象对象; cColor*:具体对象; 3) cFacto…...
运维工程师第一阶段windows的学习
文章目录 计算机硬件组成计算机历史计算机硬件组成最重要的三个硬件冯诺依曼体系:组装一台电脑:虚拟机和装系统虚拟机VMware安装系统搭建局域网本地安全策略用户本地安全策略共享文件删除操作系统操作系统分类系统优化常用命令系统的启动和密码破解winodws启动过程windows系统…...
Docker复习
目录 1. Docker的理解1.1 Docker三要素 2 安装Docker2.1 安装命令2.2 配置阿里云加速器 3 Docker命令3.1 启动类命令3.2 镜像类命令 4 实战4.1 启动容器,自动创建实例4.2 查看Docker内启动的容器4.3 退出容器4.4 其他4.5 导入导出文件4.6 commit 5 Dockerfile5.1 理…...
华为OD机考--食堂供餐--带答案
题目描述: 某公司员工食堂以盒饭方式供餐。为将员工取餐排队时间降低为0,食堂的供餐速度必须要足够快。现在需要根据以往员工取餐的统计信息,计算出一个刚好能达成排队时间为0的最低供餐速度。即,食堂在每个单位时间内必须至少做出…...
C# 关于使用newlife包将webapi接口寄宿于一个控制台程序、winform程序、wpf程序运行
C# 关于使用newlife包将webapi接口寄宿于一个控制台程序、winform程序、wpf程序运行 安装newlife包 Program的Main()函数源码 using ConsoleApp3; using NewLife.Log;var server new NewLife.Http.HttpServer {Port 8080,Log XTrace.Log,SessionLog XTrace.Log }; serv…...
初识TDMQ
目录 一:需求背景二:相关文档三:验证TDMQ广播消息 一:需求背景 目前公司需要将决策引擎处理的结果, 一部分数据交给下游分析/入黑/通知等功能。因此就需要决策引擎生产结果让多方下游去消费。 而我需要实现下游的一部…...
UEditor 百度富文本编辑器使用 遇到问题
小小吐槽 碰到前后不分离项目,富文本使用的UEdtior UEditor 点击上传图片转base64 在ueditor.all.js文件中找到这个 callback()函数 这里使用根据图片的url转成base64 UEditore 粘贴图片转base64 UEditor回显图片(base64) 把ueditor.all…...
jaeger+elasticsearch(cassandra ) 单机部署以及(400)报错
Jaeger 快速体验 官网下载地址 https://www.jaegertracing.io/download/ GitHub 下载地址 https://github.com/jaegertracing/jaeger/releases 下载二进制文件压缩包后,运行解压后的 all-in-one 文件即可。 jaeger-all-in-one 采用内存存储数据,专为…...
VSCode配置之C++ SQLite3极简配置方案
背景 最近在学习《深入应用C11: 代码优化与工程级应用》,其中第13章说到SQLite库,查询网上诸多教程,发现比较容易出现bug且配置较为麻烦,故记录此次简化版方案,以供参考。 软件环境 SQLite 3.42.0 版本(仅…...
P5725 【深基4.习8】求三角形
题目描述 模仿例题,打印出不同方向的正方形,然后打印三角形矩阵。中间有个空行。 输入格式 输入矩阵的规模,不超过 9 9 9。 输出格式 输出矩形和正方形 1.题目分析 循环判断就可以解决,总的来说,是个比较简单的…...
分布式消息中间件介绍
什么是分布式消息中间件? 对于分布式消息中间件,首先要了解两个基础的概念,即什么是分布式系统,什么又是中间件。 分布式系统 “A distributed system is one in which components located at networked computers communicate an…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
