数据结构问答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…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
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 抗噪声…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
