当前位置: 首页 > news >正文

数据结构问答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并发线程编程 设计模式系列 期待你的关注哦&#xff01;&#xff01;&#xff01; 现在的一切都是为将来的梦想编织翅膀&#xff0c;让梦想在现实中展翅高飞。 Now everythi…...

vue2企业级项目(四)

vue2企业级项目&#xff08;四&#xff09; 路由设计&#xff0c;过场动画设计 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. 树的子结构 难度&#xff1a;中等 输入两棵二叉树 A 和 B&#xff0c;判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构) B 是 A 的子结构&#xff0c; 即 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系统&#xff0c;直接刻盘安装就可以了 安装IgH主站&#xff0c;网上有很多教程可供参考 git clo…...

14.Netty源码之模拟简单的HTTP服务器

highlight: arduino-light 简单的 HTTP 服务器 HTTP 服务器是我们平时最常用的工具之一。同传统 Web 容器 Tomcat、Jetty 一样&#xff0c;Netty 也可以方便地开发一个 HTTP 服务器。我从一个简单的 HTTP 服务器开始&#xff0c;通过程序示例为你展现 Netty 程序如何配置启动&a…...

万年历【小游戏】(Java课设)

系统类型 Java实现的小游戏 使用范围 适合作为Java课设&#xff01;&#xff01;&#xff01; 部署环境 jdk1.8Idea或eclipse 运行效果 更多Java课设系统源码地址&#xff1a;更多Java课设系统源码地址 更多Java小游戏运行效果展示&#xff1a;更多Java小游戏运行效果展…...

ad+硬件每日学习十个知识点(9)23.7.20

文章目录 1.正点原子fpga开拓者无gui检查项目2.排针连接器A2541WR-XP-2P3.肖特基二极管反接在LDO的输出端&#xff0c;是什么用&#xff1f;4.在AD中如何实现批量元器件的移动&#xff1f;5.在PCB中&#xff0c;如何让元器件以任意角度旋转&#xff1f;6.接口设计都要做静电防护…...

ipmitool 配置BMC的ip

要使用ipmitool配置BMC的IP地址&#xff0c;可以按照以下步骤进行操作&#xff1a; 确保已安装ipmitool工具。如果尚未安装&#xff0c;可以使用以下命令进行安装&#xff1a; |复制代码 sudo yum install ipmitool连接到BMC&#xff1a;使用IPMI-over-LAN&#xff08;通过网…...

C++设计模式::小结(creation)

creation:隐藏创建逻辑. 1) 抽象工厂模式&#xff08;Abstract Factory Pattern&#xff09;:多层次"任选"创建对象; 实现: 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 启动容器&#xff0c;自动创建实例4.2 查看Docker内启动的容器4.3 退出容器4.4 其他4.5 导入导出文件4.6 commit 5 Dockerfile5.1 理…...

华为OD机考--食堂供餐--带答案

题目描述&#xff1a; 某公司员工食堂以盒饭方式供餐。为将员工取餐排队时间降低为0&#xff0c;食堂的供餐速度必须要足够快。现在需要根据以往员工取餐的统计信息&#xff0c;计算出一个刚好能达成排队时间为0的最低供餐速度。即&#xff0c;食堂在每个单位时间内必须至少做出…...

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

目录 一&#xff1a;需求背景二&#xff1a;相关文档三&#xff1a;验证TDMQ广播消息 一&#xff1a;需求背景 目前公司需要将决策引擎处理的结果&#xff0c; 一部分数据交给下游分析/入黑/通知等功能。因此就需要决策引擎生产结果让多方下游去消费。 而我需要实现下游的一部…...

UEditor 百度富文本编辑器使用 遇到问题

小小吐槽 碰到前后不分离项目&#xff0c;富文本使用的UEdtior UEditor 点击上传图片转base64 在ueditor.all.js文件中找到这个 callback()函数 这里使用根据图片的url转成base64 UEditore 粘贴图片转base64 UEditor回显图片&#xff08;base64&#xff09; 把ueditor.all…...

jaeger+elasticsearch(cassandra ) 单机部署以及(400)报错

Jaeger 快速体验 官网下载地址 https://www.jaegertracing.io/download/ GitHub 下载地址 https://github.com/jaegertracing/jaeger/releases 下载二进制文件压缩包后&#xff0c;运行解压后的 all-in-one 文件即可。 jaeger-all-in-one 采用内存存储数据&#xff0c;专为…...

VSCode配置之C++ SQLite3极简配置方案

背景 最近在学习《深入应用C11: 代码优化与工程级应用》&#xff0c;其中第13章说到SQLite库&#xff0c;查询网上诸多教程&#xff0c;发现比较容易出现bug且配置较为麻烦&#xff0c;故记录此次简化版方案&#xff0c;以供参考。 软件环境 SQLite 3.42.0 版本&#xff08;仅…...

P5725 【深基4.习8】求三角形

题目描述 模仿例题&#xff0c;打印出不同方向的正方形&#xff0c;然后打印三角形矩阵。中间有个空行。 输入格式 输入矩阵的规模&#xff0c;不超过 9 9 9。 输出格式 输出矩形和正方形 1.题目分析 循环判断就可以解决&#xff0c;总的来说&#xff0c;是个比较简单的…...

分布式消息中间件介绍

什么是分布式消息中间件&#xff1f; 对于分布式消息中间件&#xff0c;首先要了解两个基础的概念&#xff0c;即什么是分布式系统&#xff0c;什么又是中间件。 分布式系统 “A distributed system is one in which components located at networked computers communicate an…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...

Canal环境搭建并实现和ES数据同步

作者&#xff1a;田超凡 日期&#xff1a;2025年6月7日 Canal安装&#xff0c;启动端口11111、8082&#xff1a; 安装canal-deployer服务端&#xff1a; https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...

路由基础-路由表

本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中&#xff0c;往往存在多个不同的IP网段&#xff0c;数据在不同的IP网段之间交互是需要借助三层设备的&#xff0c;这些设备具备路由能力&#xff0c;能够实现数据的跨网段转发。 路由是数据通信网络中最基…...