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

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...