当前位置: 首页 > 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…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...