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

数据结构—线性表的查找

7.查找

《数据结构与算法分析》 思维导图复习_ManLok.的博客-CSDN博客

7.1查找的基本概念

问题:在哪里找?——查找表

查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的结构。

问题:什么查找?——根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或(记录)

关键字:用来标识一个数据元素(或记录)的某个数据项的值

  • 主关键字 可唯一地标识一个记录的关键字时主关键字;

  • 次关键字 反之,用以识别若干记录的关键字是次关键字。

问题:查找成功否?——根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或(记录)

  • 若查找表中存在这样一个记录,则称“查找成功”。

    • 查找结果给出整个记录的信息,或指示该记录在查找表中的位置;
  • 否则称“查找不成功”。

    • 查找结果给出“空记录”或“空指针”。

问题:查找目的是什么?

对查找表经常进行的操作:

  1. 查询某个 “特定的” 数据元素是否在查找表中;
  2. 检索某个 “特定的” 数据元素的各种属性;
  3. 在查找表中插入一个数据元素;
  4. 删除查找表中的某个数据元素。

问题:查找表怎么分类?

查找表可分为两类:

  • 静态查找表:
    • 仅作 “查询” (检索)操作的查找表。
  • 动态查找表:
    • 作 “插入” 和 “删除” 操作的查找表。
    • 有时在查询之后,还需要将 “查询” 结果为 “不在查找表中” 的数据元素插入到查找表中;或者,从查找表中删除其 “查询” 结果为 “在查找表中” 的数据元素,此类表为动态查找表。

问题:如何评价查找算法?

查找算法的评价指标:

​ 关键字的平均比较次数,也称平均查找长度 ASL(Average Search Length)

数据结构:二叉查找树 BST 平均查找长度 ASL 的计算_asl数据结构_寒泉Hq的博客-CSDN博客

问题:查找过程中我们要研究什么?

​ 查找的方法取决于查找表的结构,即表中数据元素是依何种关系组织在一起的。

​ 由于对查找表来说,在集合中查询或检索一个 “特定的” 数据元素时。若无规律可循,只能对集合中的元素——加以辨认直至找到为止。

​ 而这样的 “查询” 或 “检索” 是任何计算机应用系统中使用频度都很高的操作,因此设法提高查找表的查找效率,是本章讨论问题的出发点。

​ 为提高查找效率,一个办法就是在构造查找表时,在集合中的数据元素之间人为地加上某种确定的约束关系。

​ 研究查找表的各种组织方法及其查找过程的实施。

7.2线性表的查找

7.2.1顺序查找

应用范围

  • 顺序表或线性链表表示的静态查找表
  • 表内元素之间无序

数据元素类型定义:

typedef struct{KeyType key;//关键字域......//其他域
}ElemType;
typedef struct{//顺序表结构类型定义ElemType *R;//表基址int length;
}SSTable;
SSTable ST;//定义顺序表ST

在顺序表ST中查找值为key的数据元素,从最后一个元素开始比较

img

int Search_Seq(SSTable ST,KeyType key){for(i=ST.length;i>=1;--i)if(ST.R[i].key) return i;return 0;
}

其他形式:

int Search_Seq(SSTable ST,KeyType key){for(i=ST.length;ST.R[i].key!=key;--i)if(i<=0) break;if(i>0) return i;else return 0;
}

或者:

int Search_Seq(SSTable ST,KeyType key){for(i=ST.length;ST.R[i].key!=key&&i>0;--i);if(i>0) return i;else return 0;
}

改进:把待查找关键字key存入表头(“哨兵”、“监视哨”),从后往前逐个比较,可免去查找过程中每一部都要检测是否查找完毕,加快速度。

img

int Search_Seq(SSTable ST,KeyType key){ST.R[0].key=key;for(i=ST.length;ST.R[i].key!=key;--i);return i;
}

当ST.length较大时,此改进能使进行一次查找所需的平均时间几乎减少一半。

时间效率分析:比较次数与key位置有关:

  • 查找第i个元素,需要比较n-i+1次
  • 查找失败,需要比较n+1次

1.记录的查找的概率不相等时如何提高查找效率?

​ 查找表存储记录原则——按查找概率高低存储:

​ 1)查找概率越高,比较次数越少;

​ 2)查找概率越低,比较次数越多。

2.记录的查找概率无法测定时如何提交查找效率?

​ 方法——按查找概率动态调整记录顺序:

​ 1)在每个记录中设一个访问频度域;

​ 2)始终保持记录按非递增有序的次序排列;

​ 3)每次查找后均将刚查到的记录直接移至表头。

顺序查找表的特点

​ 优点:算法简单,逻辑次序无要求,且不同存储结构均适用。

​ 缺点:ASL太长,时间效率太低。

7.2.2折半查找

折半查找:每次将待查记录所在区间缩小一半。

折半查找(折半查找定义+折半查找过程+折半查找算法实现+折半查找判定树+折半查找ASL+折半查找性能T(n))_xyl-CSDN博客_折半查找asl

mid = (low + high)/2
key<mid 则:high = mid - 1
key>mid 则:low = mid + 1
key == mid,找到
high<low,结束

折半查找算法:(非递归算法)

  • 设表长为 n,low、high 和 mid分别指向待查元素所在区间的上界、下界和中点,key为给定的要查找的值:
  • 初始时,令low=1,high=n,mid=[(low+high)/2]
  • 让k与mid指向的记录比较
    • 若key==R[mid].key,查找成功
    • 若key<R[mid].key,则high=mid-1
    • 若key>R[mid].key,则low=mid+1
  • 重复上述操作,直至low>high时,查找失败
int Search_Bin(SSTable ST,KeyType key){low=1;high=ST.length;//置区间初值while(low<=high){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;//顺序表中不存在待查元素
}

折半查找:递归算法

int Search_Bin(SSTable ST,keyType key,int low,int high){if(low>high) return 0;//查找不到时返回0mid=(low+high)/2;if(key==ST.elem[mid].key) return mid;else if(key<ST.elem[mid].key)......//递归,在前半区间进行查找else ......//递归,在后半区间进行查找
}

折半查找的性能分析—判定树

折半查找(折半查找定义+折半查找过程+折半查找算法实现+折半查找判定树+折半查找ASL+折半查找性能T(n))_xyl-CSDN博客_折半查找asl

考研之数据结构026_算法查找_折半查找(重要)分块查找_折半查找判定树的特点_BigTree的学习之路的博客-CSDN博客

折半查找优点:效率比顺序查找高。

折半查找缺点:只适用于有序表,且限于顺序存储结构(对线性链表无效)。

7.2.3分块查找

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

条件:

  1. 将表分成几块,且表或者有序,或者分块有序;若i<j,则第j块中所有记录的关键字均大于第i块中的最大关键字。
  2. 建立“索引表”(每个结点含有最大关键字域和指向本块第一个结点的指针,且按关键字有序)。

数据结构之分块查找_AAS48的博客-CSDN博客

查找过程:先确定待查记录所在快(顺序或折半查找),再在块内查找(顺序查找)。

分块查找优点:插入和删除比较容易,无需进行大量移动。

分块查找缺点:要增加一个索引表的存储空间并对初始索引表进行排序运算。

适用情况:如果线性表既要快速查找又经常动态变化,则可采用分块查找。

查找方法比较

顺序查找折半查找分块查找
ASL最大最小中间
表结构有序表、无序表有序表分块有序
存储结构顺序表、线性链表顺序表顺序表、线性链表

相关文章:

数据结构—线性表的查找

7.查找 7.1查找的基本概念 问题&#xff1a;在哪里找&#xff1f;——查找表 查找表是由同一类型的数据元素&#xff08;或记录&#xff09;构成的集合。由于“集合”中的数据元素之间存在着松散的关系&#xff0c;因此查找表是一种应用灵便的结构。 问题&#xff1a;什么查找&…...

EndNote(一)【界面+功能介绍】

EndNote界面&#xff1a; 顶上小图标的介绍&#xff1a; ①&#xff1a;同步 ②&#xff1a;分享 ③&#xff1a;检索全文 对于第三个&#xff08;检索全文的功能&#xff09;&#xff1a; &#xff08;不做任何操作的情况下的界面&#xff0c;检索全文的按钮是灰的&…...

JWT令牌验证

目录 一、JWT介绍 二、安装依赖 三、登陆接口 1、令牌工具类 2、接口代码 四、说明 一、JWT介绍 JWT全称&#xff1a;JSON Web Token &#xff08;官网&#xff1a;JSON Web Tokens - jwt.io&#xff09; 定义了一种简洁的、自包含的格式&#xff0c;用于在通信双方以json…...

【微信小程序】下拉刷新功能实现

微信小程序开发系列 文章目录 前言一、onPullDownRefresh函数二、实现1.开启下拉刷新2.监听下拉事件 前言 在开发微信小程序中经常会需要下拉页面进行更新要页面数据的功能&#xff0c;微信小程序提供了onPullDownRefresh函数。该函数作用是监听用户下拉动作。 一、onPullDown…...

三角函数与圆,角度和弧度 (草稿,建设中)

目录 1 三角函数与圆&#xff0c;角度和弧度 1.1 三角形 1.2 圆形 2 角度 3 弧度 rad 4 角度&#xff0c;弧度的换算 2 三角函数 1 三角函数与圆&#xff0c;角度和弧度 1.1 三角形 角度弧长sin()cos()tan() 1.2 圆形 半径&#xff0c;周长&#xff0c;弧长半径面积 …...

AIGC 施展“物理魔法”,3D视觉突破“精度极限”

点击关注 文&#xff5c;姚悦&#xff0c;编&#xff5c;王一粟 “没有艺术&#xff0c;全是物理&#xff01;物理让你快乐&#xff0c;不是吗&#xff1f;” 近日&#xff0c;在世界计算机图形会议 SIGGRAPH 2023 上&#xff0c;英伟达创始人、CEO 黄仁勋宣布&#xff0c;将…...

redis 哨兵模式

目录 一、什么是哨兵模式 二、配置哨兵 三、启动哨兵 四、验证哨兵 五、复制延时 六、选举策略 一、什么是哨兵模式 哨兵也叫 sentinel&#xff0c;它的作用是能够在后台监控主机是否故障&#xff0c;如果故障了根据投票数自动将从库转换为主库。 二、配置哨兵 首先停止…...

java八股文面试[java基础]——String StringBuilder StringBuffer

String类型定义&#xff1a; final String 不可以继承 final char [] 不可以修改 String不可变的好处&#xff1a; hash值只需要算一次&#xff0c;当String作为map的key时&#xff0c; 不需要考虑hash改变 天然的线程安全 知识来源&#xff1a; 【基础】String、StringB…...

[oneAPI] 基于BERT预训练模型的命名体识别任务

[oneAPI] 基于BERT预训练模型的命名体识别任务 Intel DevCloud for oneAPI 和 Intel Optimization for PyTorch基于BERT预训练模型的命名体识别任务语料介绍数据集构建使用示例 命名体识别模型前向传播模型训练 结果 参考资料 比赛&#xff1a;https://marketing.csdn.net/p/f3…...

SSL证书如何使用?SSL保障通信安全

由于SSL技术已建立到所有主要的浏览器和WEB服务器程序中&#xff0c;因此&#xff0c;仅需安装数字证书或服务器证书就可以激活功能了。SSL证书主要是服务于HTTPS&#xff0c;部署证书后&#xff0c;网站链接就由HTTP开头变为HTTPS。 SSL安全证书主要用于发送安全电子邮件、访…...

postgresql 的递归查询

postgresql 的递归查询功能很强大&#xff0c;可以实现传统 sql 无法实现的事情。那递归查询的执行逻辑是什么呢&#xff1f;在递归查询中&#xff0c;我们一般会用到 union 或者 union all&#xff0c;他们两者之间的区别是什么呢&#xff1f; 递归查询的执行逻辑 递归查询的…...

Go语言进阶:函数、指针、错误处理

一、函数 函数是基本的代码块&#xff0c;用于执行一个任务。 Go 语言最少有个 main() 函数。 你可以通过函数来划分不同功能&#xff0c;逻辑上每个函数执行的是指定的任务。 函数声明包括函数名﹑形式参数列表﹑返回值列表&#xff08;可省略&#xff09;以及函数体。 fun…...

最强自动化测试框架Playwright(30)-JS句柄

在 Playwright 中&#xff0c;JSHandle 是一个表示浏览器中 JavaScript 对象的类。它提供了与网页中的 JavaScript 对象进行交互和操作的方法。 可以通过调用 Playwright中的 evaluateHandle 或 evaluate 方法来获取 JSHandle from playwright.sync_api import sync_playwrig…...

Ctfshow web入门 命令执行RCE篇 web29-web77 与 web118-web124 详细题解 全

Ctfshow 命令执行 web29 pregmatch是正则匹配函数&#xff0c;匹配是否包含flag&#xff0c;if(!preg_match("/flag/i", $c))&#xff0c;/i忽略大小写 可以利用system来间接执行系统命令 flag采用f*绕过&#xff0c;或者mv fl?g.php 1.txt修改文件名&#xff0c…...

【C++ STL之map,set,pair详解】

目录 一.map映射1.简介2.包含头文件及其初始化3.基本操作4.用迭代器正反遍历5.添加元素的四种方式6.元素的访问7.对比unordered_map&#xff0c;multimap 二.set集合1.简介2.包含头文件及其初始化3.基本操作4.元素的访问5.set&#xff0c;multiset&#xff0c;unordered_set&am…...

Python LEGB规则解析与应用

引言 推荐阅读 AI文本 OCR识别最佳实践 AI Gamma一键生成PPT工具直达链接 玩转cloud Studio 在线编码神器 玩转 GPU AI绘画、AI讲话、翻译,GPU点亮AI想象空间 资源分享 「java、python面试题」来自UC网盘app分享&#xff0c;打开手机app&#xff0c;额外获得1T空间 http…...

气象监测站:用科技感知气象变化

气象监测站是利用科学技术感知当地小气候变化情况的气象观测仪器&#xff0c;可用于农业、林业、养殖业、畜牧业、环境保护、工业等多个领域&#xff0c;提高对环境数据的利用率&#xff0c;促进产业效能不断提升。 气象监测站主要由气象传感器、数据传输系统、电源系统、支架…...

Linux debian12解压和压缩.rar文件教程

一、Debian12安装rar命令 sudo apt install rar二、使用rar软件 1.解压文件 命令格式&#xff1a; rar x 文件名.rar实例测试&#xff1a; [rootdoudou tmp]# rar x test.rar2.压缩文件 test是一个文件夹 命令格式&#xff1a; rar a 文件名.rar 文件夹名实例测试&#x…...

探析国际大文件传输的花费与降低开销的小妙招

随着全球化的不断发展&#xff0c;跨国企业日益增多&#xff0c;因此国外大文件传输也日益普遍。在这种背景下&#xff0c;国外大文件传输方式的需求也相应增加。本文旨在深入分析国外大文件传输的成本&#xff0c;并提出有效降低这些成本的方法。 一、国外大文件传输成本分析 …...

Linux中shell脚本——for、while循环及脚本练习

目录 一.for循环 1.1.基本格式 1.2.类C语言格式 二.while循环 2.1.基本格式 2.2.死循环语句 三.跳出循环 3.1.continue跳出循环 3.2.break跳出循环 四.常用循环 4.1.循环打印九九乘法表 4.2.循环ping测试某个网段网络连通性 4.3.while死循环实现猜数字游戏 4.4.数…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题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 位数字。 输…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...