数据结构——查找(线性表的查找与树表的查找)
目录
1.查找
1.查找的基本概念
1.在哪里找?
2.什么查找?
3.查找成功与否?
4.查找的目的是什么?
5.查找表怎么分类?
6.如何评价查找算法?
7.查找的过程中我们要研究什么?
2.线性表的查找
1.顺序查找
代码示例:
1.顺序查找的改进
代码示例:
2.顺序查找的性能分析与特点
2.折半查找
代码示例:
1.折半查找的性能分析与特点
3.分块查找(索引顺序查找)
1.分块查找性能分析与优缺点
3.树表的查找
1.二叉排序树
1.二叉排序树的存储结构
代码示例:
2.二叉排序树的递归查找
代码示例:
3.二叉排序树的查找分析
平衡二叉树
4.二叉排序数的操作-插入
5.二叉排序树的操作-删除
4.总的代码
1.查找

1.查找的基本概念
1.在哪里找?

2.什么查找?

3.查找成功与否?

4.查找的目的是什么?

5.查找表怎么分类?

6.如何评价查找算法?

7.查找的过程中我们要研究什么?

2.线性表的查找

1.顺序查找


代码示例:
typedef struct {int key;
}elem;typedef struct {elem *r;int len;
}sstable;sstable st;int search_seq(sstable st,int key) {for(int i = st.len; i >= 1; --i) {if(st.r[i].key == key) return i;return 0;}
}

1.顺序查找的改进




代码示例:
int Search_seq(sstable st,int key) {st.r[0].key = key;int i;for(i = st.len; st.r[i].key != key; --i);return i;
}

2.顺序查找的性能分析与特点




2.折半查找




代码示例:
int search_bin(sstable st,int key) {int low = 1;int high = st.len;while(low <= high) {int mid = (low + high) / 2;if(st.r[mid].key == key) return mid;else if(key < st.r[mid].key)high = mid - 1;else low = mid + 1;}return 0;
}



1.折半查找的性能分析与特点



3.分块查找(索引顺序查找)


1.分块查找性能分析与优缺点



3.树表的查找

1.二叉排序树




1.二叉排序树的存储结构

代码示例:
typedef struct {int key;
}elemtype;typedef struct bstnode {elemtype data;struct bstnode *lchild, *rchild;
}bstnode,*bstree;bstree t;
2.二叉排序树的递归查找


代码示例:
bstree searchbst(bstree t,int key) {if((!t) || key == t -> data.key) return t;else if(key < t -> data.key)return searchbst(t -> lchild,key);else return searchbst(t -> rchild,key);
}
3.二叉排序树的查找分析



平衡二叉树

4.二叉排序数的操作-插入





5.二叉排序树的操作-删除







4.总的代码
#include<bits/stdc++.h>
using namespace std;typedef struct {int key;
}elem;typedef struct {elem *r;int len;
}sstable;sstable st;int search_seq(sstable st,int key) {for(int i = st.len; i >= 1; --i) {if(st.r[i].key == key) return i;return 0;}
}int Search_seq(sstable st,int key) {st.r[0].key = key;int i;for(i = st.len; st.r[i].key != key; --i);return i;
}int search_bin(sstable st,int key) {int low = 1;int high = st.len;while(low <= high) {int mid = (low + high) / 2;if(st.r[mid].key == key) return mid;else if(key < st.r[mid].key)high = mid - 1;else low = mid + 1;}return 0;
}typedef struct {int key;
}elemtype;typedef struct bstnode {elemtype data;struct bstnode *lchild, *rchild;
}bstnode,*bstree;bstree t;bstree searchbst(bstree t,int key) {if((!t) || key == t -> data.key) return t;else if(key < t -> data.key)return searchbst(t -> lchild,key);else return searchbst(t -> rchild,key);
}int main() {return 0;
}
相关文章:
数据结构——查找(线性表的查找与树表的查找)
目录 1.查找 1.查找的基本概念 1.在哪里找? 2.什么查找? 3.查找成功与否? 4.查找的目的是什么? 5.查找表怎么分类? 6.如何评价查找算法? 7.查找的过程中我们要研究什么? 2.线性表…...
MySQL入门学习-深入索引.组合索引
在 MySQL 中,组合索引(也称为复合索引)是在多个列上创建的索引。以下是关于组合索引的详细信息: 一、组合索引的概念: - 组合索引是基于多个列创建的索引结构。它可以提高在这些列上进行查询的效率。 二、深入理解组…...
RABBITMQ的本地测试证书生成脚本
由于小程序要求必须访问wss的接口,因此需要将测试环境也切换到https,看了下官方的文档 RabbitMQ Web STOMP Plugin | RabbitMQ里面有这个信息 然后敲打GPT一阵子,把要求输入几个来回,得到这样一个脚本: generate_cer…...
记录些Redis题集(4)
Redis 通讯协议(RESP) Redis 通讯协议(Redis Serialization Protocol,RESP)是 Redis 服务端与客户端之间进行通信的协议。它是一种二进制安全的文本协议,设计简洁且易于实现。RESP 主要用于支持客户端和服务器之间的请求响应交互…...
JVM:垃圾回收器
文章目录 一、介绍二、年轻代-Serial垃圾回收器三、老年代-SerialOld垃圾回收器四、年轻代-ParNew垃圾回收器五、老年代-CMS(Concurrent Mark Sweep)垃圾回收器六、年轻代-Parllel Scavenge垃圾回收器七、Parallel Old垃圾回收器八、G1垃圾回收器 一、介…...
Golang | Leetcode Golang题解之第228题汇总区间
题目: 题解: func summaryRanges(nums []int) (ans []string) {for i, n : 0, len(nums); i < n; {left : ifor i; i < n && nums[i-1]1 nums[i]; i {}s : strconv.Itoa(nums[left])if left < i-1 {s "->" strconv.It…...
单目3D和bev综述
文章目录 SOTA2D 检测单目3d检测3d bev cam范式1 Transformer attention is all you need 20172 ViT vision transformer ICLR 2021google3 swin transformer 2021 ICCV bestpaper MS4 DETR 20205 DETR3D 20216 PETR 20227 bevformerLSSbevdetcaddn指标 mAP NDS标注:…...
每日Attention学习11——Lightweight Dilated Bottleneck
模块出处 [TITS 23] [link] [code] Lightweight Real-Time Semantic Segmentation Network With Efficient Transformer and CNN 模块名称 Lightweight Dilated Bottleneck (LDB) 模块作用 改进的编码器块 模块结构 模块代码 import torch import torch.nn as nn import to…...
EM32DX-E4 IO 扩展模块
输入:0x6000-01 // 输入 0-15 6020H——00H IN0 计数【0~7】 ——01H IN0_SetCountMode S32 r/w 初始值默认为 0 设置 IN0 的计数方式:0 电平下 降沿,1 电平上升沿, 2 电平任意沿 ——02H IN0_Set…...
【数据结构与算法】选择排序篇----详解直接插入排序和哈希排序【图文讲解】
欢迎来到CILMY23的博客 🏆本篇主题为:【数据结构与算法】选择排序篇----详解直接插入排序和哈希排序 🏆个人主页:CILMY23-CSDN博客 🏆系列专栏:Python | C | C语言 | 数据结构与算法 | 贪心算法 | Linux…...
SpringBoot实战:多表联查
1. 保存和更新公寓信息 请求数据的结构 Schema(description "公寓信息") Data public class ApartmentSubmitVo extends ApartmentInfo {Schema(description"公寓配套id")private List<Long> facilityInfoIds;Schema(description"公寓标签i…...
解决mysql,Navicat for MySQL,IntelliJ IDEA之间中文乱码
使用软件版本 jdk-8u171-windows-x64 ideaIU-2021.1.3 mysql-essential-5.0.87-win32 navicat8_mysql_cs 这个问题我调试了好久,网上的方法基本上都试过了,终于是解决了。 三个地方结果都不一样。 方法一 首先大家可以尝试下面这种方法:…...
虚拟环境操作
1、对虚拟环境的操作 查看虚拟环境列表 conda env list 创建虚拟环境 conda create -n 虚拟环境名称 python3.x 激活虚拟环境 conda activate 虚拟环境名称 退出虚拟环境 conda deactivate 删除虚拟环境 conda remove -n 虚拟环境名称 all 2、对虚拟环境下的包的操作…...
企业网三层架构
企业网三层架构:是一种层次化模型设计,旨在将复杂的网络设计分成三个层次,每个层次都着重于某些特定的功能,以提高效率和稳定性。 企业网三层架构层次: 接入层:使终端设备接入到网络中来,提供…...
node.js的安装及学习(node/nvm/npm的区别)
一、什么是node、nvm和npm 1.Node.js node.js 一种Javascript编程语言的运行环境,能够使得javascript能够脱离浏览器运行。以前js只能在浏览器(也就是客户端)上运行,node.js将浏览器中的javascript运行环境进行封装的,…...
性能优化篇:用WebSocket替代传统的http轮循
当我还是初级菜鸟时,我只会写定时器定时调用接口,发起http请求,定时轮训请求接口,返回最新数据,定时器开启的多了还会引起页面卡顿的性能问题,虽然及时销了但还是会影响流畅问题。然后技术leader一声令下说改成websoket的请求方式,为什么这么做呢?下面来谈谈WebSocket相…...
virtualbox的ubuntu默认ipv4地址为10.0.2.15的修改以及xshell和xftp的连接
virtualbox安装Ubuntu后,默认的地址为10.0.2.15 我们查看virtualbox的设置发现是NAT 学过计算机网络的应该了解NAT技术,为了安全以及缓解ip使用,我们留了部分私有ip地址。 私有IP地址网段如下: A类:1个A类网段&…...
Codeforces Round 957 (Div. 3)(A~D题)
A. Only Pluses 思路: 优先增加最小的数,它们的乘积会是最优,假如只有两个数a和b,b>a,那么a 1,就增加一份b。如果b 1,只能增加1份a。因为 b > a,所以增加小的数是最优的。 代码: #include<bi…...
fedora 40 安装拼音输入法
仅做参考,一般主流linux版本在安装完成后,都会自带中文输入法。而需要配置中文输入法的小众发行版往往软件仓库自带的依赖不全。 1,sudo dnf install ibus 2,sudo dnf install im-chooser 3,sudo dnf install ibus-libpinyin 4,在终端输入im-choose…...
Chromium CI/CD 之Jenkins实用指南2024-如何创建新节点(三)
1. 前言 在前一篇《Jenkins实用指南2024-系统基本配置(二)》中,我们详细介绍了如何对Jenkins进行基本配置,包括系统设置、安全配置、插件管理以及创建第一个Job。通过这些配置,您的Jenkins环境已经具备了基本的功能和…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
