算法:查找

算法

  • 1. 顺序查找和折半查找
    • 1.1 顺序查找
    • 1.2 折半查找
    • 1.3 索引顺序查找
  • 2. 树表查找
    • 2.1 查找
    • 2.2 插入
  • 3. 哈希表及哈希查找
    • 3.1 哈希造表
    • 3.2 处理冲突
      • 开放定址法
      • 链地址法
    • 3.3 哈希查找

查找是非数值数据处理中一种基本运算,查找运算的效率与查找表所采用的数据结构和查找方法密切相关。查找表是指由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系,可以将查找表构造为静态的或者动态的。
根据对表中数据的处理有:

  1. 静态查找表:不进行修改表结构的操作。如查询某个特定的数据元素是否在查找表中;检索某个特定的数据元素的属性。
  2. 动态查找表:是动态变化的,除了查询和检索,对查找表要进行的操作有:插入一个数据元素和删除一个数据元素。

表中数据的查找通过关键码进行区分。关键码是数据元素(或记录)的某个数据项的值,用它来识别(标识)这个数据元素(或记录)。主关键码是指能唯一标识一个数据元素的关键码。次关键码是指能标识多个数据元素的关键码。
查找算法的基本操作:将记录的关键码与给定值进行比较。
对于含有n个记录的表,查找成功时的平均查找长度定义为:
A S L = ∑ i = 1 n P i C i ASL=\sum_{i=1}^nP_iC_i ASL=i=1nPiCi
P i P_i Pi为表中第i个记录进行查找的概率,且 ∑ i = 1 n P i = 1 \sum_{i=1}^nP_i=1 i=1nPi=1 C i C_i Ci为找到表中其关键码与给定值相等的记录时和给定值已进行过比较的关键码个数。

1. 顺序查找和折半查找

当仅在查找表中进行查找运算而不修改查找表时,可先构造一个静态查找表,然后进行顺序查找或折半查找等操作。

1.1 顺序查找

顺序查找的方法对于顺序查找和链式查找存储方式的线性表都适用。
在等概率情况下,顺序查找成功的平均查找长度是:
A S L s s = ∑ i = 1 n P i C i = 1 n ∑ i = 1 n ( n − i + 1 ) = n + 1 2 ASL_{ss}=\sum_{i=1}^nP_iC_i=\frac{1}{n} \sum_{i=1}^n(n-i+1)=\frac{n+1}{2} ASLss=i=1nPiCi=n1i=1n(ni+1)=2n+1

成功查找的平均比较次数约为表长的一半。若所查记录不在表中,则至少进行n次比较才能确定查找失败。与

  • 缺点:顺序査找方法在"值较大时,其平均查找长度较大,查找效率较低。
  • 优点:算法简单且适应面广,对查找表的存储结构没有要求,无论记录是否按关键码有序排列均可应用。

1.2 折半查找

折半查找也称为二分查找,该方法是将给定值与中间位置记录的关键码比较,若相等,则查找成功:若不等,则缩小范围,直至新的査找区间中间位置记录的关键码等于给定值或者查找区间没有元素时(表明查找不成功)为止。

  • 使用范围:表中的元素已经按关键码排序。
  1. 整型数组折半查找
int Bsearsh_1(int r[], int low, int high, int key)
/*元素存储在r[low, high],用折半查找的方法在数组r中找值为key的元素*/
/*若找出则返回元素的下标,否则返回-1*/
{int mid;while(low<=high){mid=(low+high)/2;if(key==r[mid]) return mid;else if(key<r[mid]) high = mid-1;else low=high+1;}return -1;
}
  1. 整型数组折半查找递归算法
int Bsearsh_rec(int r[], int low, int high, int key)
{int mid;if(low<high){mid=(low+high)/2;if(key==r[mid]) return mid;else if(key<r[mid]) return  Bsearsh_rec(r, low, mid-1, key);else return  Bsearsh_rec(r, mid+1, high, key);}return -1;
}

折半查找可以理解为折半查找树。以当前查找区间的中间位置上的记录为根,左子表和右子表中的记录分贝作为根的左子树和右子树结点。
在这里插入图片描述
具有n个结点的判定树的高度为 [ l o g 2 n ] + 1 [log_2n]+1 [log2n]+1,所以折半查找在查找成功时和给定值进行比较的关键码个数至多为 [ l o g 2 n ] + 1 [log_2n]+1 [log2n]+1
折半查找的平均查找长度为:
A S L b s = ∑ j = 1 n P i C i = 1 n ∑ j = 1 n j × 2 j − 1 = n + 1 n l o g 2 ( n + 1 ) − 1 ASL_{bs}=\sum_{j=1}^nP_iC_i=\frac{1}{n}\sum_{j=1}^nj\times2^{j-1}=\frac{n+1}{n}log_2(n+1)-1 ASLbs=j=1nPiCi=n1j=1nj×2j1=nn+1log2(n+1)1
当n值较大时,
A S L b s ≈ l o g 2 ( n + 1 ) − 1 ASL_{bs} \approx log_2(n+1)-1 ASLbslog2(n+1)1

  • 折半查找的效率很高,但是查找表需要采用顺序存储并且关键码要有序排列。折半查找适用于查找不易变动,且又经常进行查找的情况。

1.3 索引顺序查找

在这里插入图片描述
在分块查找过程中,首先将查找表分成若干块,每一块中关键码不一定有序,但块之间是有序的,即后一块中所有记录的关键码均大于前一个块中最大的关键码。此外,还建立了一个’索引表”,索引表的元素按关键码有序排列。因此,查找过程分为两步:第-步在索引表中确定待查记录所在的块;第二步在块内顺序查找。
平均查找长度为:
A S L b s = 1 2 ( n s + s ) + 1 ASL_{bs} = \frac{1}{2}(\frac{n}{s}+s)+1 ASLbs=21(sn+s)+1
其中,b为分的块数;s为每块内的元素数量。当s取 n \sqrt{n} n 时, A S L b s ASL_{bs} ASLbs取最小值 n + 1 \sqrt{n}+1 n +1

2. 树表查找

将查找表组织为一种树状结构时,则为树表查找。
非空的二叉查找树中左子树上所有结点的关键码均小于根结点的关键码,右子树上所有结点的关键码均大于根结点的关键码,因此,可将二叉查找树看成是一个有序表,其查找过程与折半查找过程相似。
二叉树数据结构及存储

typedef struct Tnode{int key;struct Tnode *lchild,*rchild;
}BSTnode,*Bitree;

2.1 查找

Bitree searchBST(Bitree root, int thekey, Bitree *father)
/*在root指向根的二叉查找树中查找键值为key的结点*/
/*若找到则返回所指向的节点指针,否则返回NULL,并向father带回父节点的指针*/
{	Bitree p=root; *father = NULL;While(p&&p->key!=thekey){*father = p;if(thekey<p->key) p=p->lchild;else p=p->rchild;}return p;
}

2.2 插入

构造二叉树:关键码序列 { 46 , 25 , 54 , 13 , 29 , 91 } \{46,25,54,13,29,91\} {46,25,54,13,29,91},则其构造的过程为:
在这里插入图片描述
代码实现:
二叉查找树的插入是不断向下延展的,不会在中间结点位置插入。
此代码是在查找的基础之上进行的实现。

Bitree insertBST(Bitree *root, int newkey)
/*在*root指向根的二叉查找树中插入一个键值为newkey的结点,若插入成功则返回0,否则返回-1*/
{	Bitree s,p,father;s = (BSTnode *)malloc(sizeof(BSTnode));if(!s) return -1;s->key = newkey;s->lchild =NULL;s->rchild = NULL;P = searchBST(*root,newkey,&father);  //查找插入位置if(p) return -1;                      //键值为newkey的结点已在树中,不再插入if(!father) *root=s;                  //若为空树,键值为newkey的结点为树根else if(newkey <father->key) father->lchild = s;else  father->rchild = s;return 0;
}

另外,由于一棵二叉查找树的形态完全由输入序列决定,所以在输入序列已经有序的情况下,所构造的二又查找树是一棵单枝树。从二又查找树的查找过程可知,这种情况下的査找效率和顺序查找的效率相当。

3. 哈希表及哈希查找

与散列表结合使用。

顺序查找、折半查找和二叉查找表的存储位置和关键码之间不存在确定的关系,查找过程要通过系列对关键码的比较后才能确定记录在表中的位置。
理想情况是依据记录的关键码直接得到其对应的存储位置,即要求记录的关键码与其存储位置之间存在一一对应关系,从而快速地找到记录。

3.1 哈希造表

根据设定的哈希函数 Hash(key)和处理冲突的方法,将一组关键码映射到一个有限的连续的地址集(区间)上,并以关键码在地址集中的“像”作为记录在表中的存储位置,这种表称为哈希表,这一映射过程称为哈希造表或散列,所得的存储位置称为哈希地址或散列地址。

利用哈希函数来对应关键码和存储位置,必须做到一一对应,每次映射的结果是统一的
采用哈希法需要解决两个问题:

  1. 哈希函数的构造;
  2. 冲突的解决。
  • 冲突
    对于某个哈希函数 Hash 和两个关键码 K 1 K_1 K1 K 2 K_2 K2,如果 K 1 ≠ K 2 K_1 \ne K_2 K1=K2,而 H a s h ( K 1 ) = H a s h ( K 2 ) Hash(K_1)=Hash(K_2) Hash(K1)=Hash(K2),则称出现了冲突,对该哈希函数来说, K 1 K_1 K1 K 2 K_2 K2称为同义词。

3.2 处理冲突

处理冲突就是为出现冲突的关键码找到另一个空的哈希地址。
常见的处理冲突的方法有开放定址法、链地址法(拉链法)、再哈希法、建立公共溢出区法等,在处理冲突的过程中,可能得到一个地址序列,记为 H i ( i = 1 , 2 , . . . , k ) H_i(i=1,2,...,k) Hi(i=1,2,...,k)

开放定址法

H i = ( H a s h ( k e y ) + d i ) % m i = 1 , 2 , . . . , k ( k ≤ m − 1 ) \begin{matrix} H_i=(Hash(key)+d_i)\%m & i=1,2,...,k(k\le{m-1}) \end{matrix} Hi=(Hash(key)+di)%mi=1,2,...,k(km1)
其中,Hash(key)为哈希函数;m为哈希表的表长; d i d_i di为增量序列。常见增量序列有:

  1. d i = 1 , 2 , . . . , m − 1 d_i=1,2,...,m-1 di=1,2,...,m1,称为线性探测再散列。
  2. d i = 1 2 , − 1 2 , 2 2 , − 2 2 , 3 2 , . . . , − k 2 ( k ≤ m 2 ) d_i=1^2,-1^2,2^2,-2^2,3^2,...,-k^2(k\le{\frac{m}{2}}) di=12,12,22,22,32,...,k2(k2m),称为二次探测再散列。
  3. d i = 伪随机序列 d_i=伪随机序列 di=伪随机序列,称为随机探测再散列。

最简单的就是进行线性探测,发生冲突时顺序的存储到下一个单元进行探测,直到找到空闲的地址。
在这里插入图片描述
在这里插入图片描述
线性探测法可能使第i个哈希地址的同义词存入第 +1 个哈希地址,这样本应存入第 i+1个哈希地址的元素变成了第 i+2 个哈希地址的同义词,……,因此,可能出现很多元素在相邻的哈希地址上“聚集”起来的现象,大大降低了查找效率。为此,可采用二次探测法或随机探测再散列法,以降低“聚集”现象。

链地址法

链地址法是一种经常使用且很有效的方法。它将具有相同哈希函数值的记录组织成一个链表,当链域的值为 NUIL 时,表示已没有后继记录。
例如,哈希表表长为 11、哈希函数为 H a s h ( k e y ) = k e y m o d 11 Hash(key)=key \mod 11 Hash(key)=keymod11,对于关键码序列 47,34,13,12,52,38,33,27,3,使用链地址法构造的哈希表。
在这里插入图片描述

3.3 哈希查找

在线性探测法解决冲突的哈希表中进行查找的过程如下:

  1. 先根据哈希函数计算出元素的哈希地址。
  2. 若是空单元,说明查找不成功,可结束查找:若不是空单元,则与该单元中的元素进行比较。
  3. 若相等,则查找成功并结束查找,否则,计算出下一个哈希地址,转(2)。

在用链地址法解决冲突构造的哈希表中查找元素,就是根据哈希函数得到元素所在链表的头指针,然后在链表中进行顺序查找即可。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1746.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Istio基本概念及部署

一、Istio架构及组件 Istio服务网格在逻辑上分为数据平面和控制平面。 控制平面&#xff1a;使用全新的部署模式&#xff1a;Istiod&#xff0c;这个组件负责处理Sidecar注入&#xff0c;证书颁发&#xff0c;配置管理等功能&#xff0c;替代原有组件&#xff0c;降低复杂度&…

OpenCV视觉分析之目标跟踪(8)目标跟踪函数CamShift()使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 找到物体的中心、大小和方向。 CamShift&#xff08;Continuously Adaptive Mean Shift&#xff09;是 OpenCV 中的一种目标跟踪算法&#xff0…

gradlew命令打包报错:malformed input off : 50, length : 1

Execution failed for task :app:mapǧ&#xfffd;&#xfffd;Ѫսƪ_officialOfficialReleaseSourceSetPaths. > Could not resolve all files for configuration :app:ǧ&#xfffd;&#xfffd;Ѫսƪ_officialOfficialReleaseRuntimeClasspath. > Failed to trans…

[云] 大数据分析栈(Big Data Analytics Stack)+ Apache Hadoop分布式文件系统(HDFS)+Apache Spark

任务概述 本次作业旨在帮助你理解大数据分析栈&#xff08;Big Data Analytics Stack&#xff09;的工作原理&#xff0c;并通过实际操作加深认识。你将搭建Apache Hadoop分布式文件系统&#xff08;HDFS&#xff09;作为底层文件系统&#xff0c;并将Apache Spark作为执行引擎…

ESP8266 自定义固件烧录-Tcpsocket固件

一、固件介绍 固件为自定义开发的一个适配物联网项目的开源固件&#xff0c;支持网页配网、支持网页tcpsocket服务器配置、支持串口波特率设置。 方便、快捷、稳定&#xff01; 二、烧录说明 固件及工具打包下载地址&#xff1a; https://download.csdn.net/download/flyai…

新能源汽车空调压缩机:科技驱动的冷暖核心

一、新能源汽车空调系统概述 新能源汽车空调系统在车辆中起着至关重要的作用&#xff0c;它直接影响着驾乘人员的舒适度。新能源汽车空调系统主要由制冷系统、加热系统、送风系统、操纵控制系统和空气净化系统等组成。 制冷系统通常由电动压缩机、冷凝器、压力传感器、电子膨…

Leetcode 213. 打家劫舍 II 动态规划

原题链接&#xff1a;Leetcode 213. 打家劫舍 II class Solution { public:int rob(vector<int>& nums) {int n nums.size();if (n 1)return nums[0];if (n 2)return max(nums[0], nums[1]);// 如果偷了第一家&#xff0c;就不能偷最后一家int dp[n - 1];dp[0] …

助力AI智能化时代:全国产化飞腾FT2000+/64+昇腾310B服务器主板

在信息技术快速发展的今天&#xff0c;服务器作为数据处理和存储的核心设备&#xff0c;肩负着越来越重要的使命。全国产化的服务器主板&#xff0c;采用飞腾FT2000/64核处理器&#xff0c;搭配华为昇腾310的AI芯片&#xff0c;提供卓越的性能与可靠性。 核心配置&#xff0c;强…

IO 多路复用技术:原理、类型及 Go 实现

文章目录 1. 引言IO 多路复用的应用场景与重要性高并发下的 IO 处理挑战 2. IO 多路复用概述什么是 IO 多路复用IO 多路复用的优点与适用场景 3. IO 多路复用的三种主要实现3.1 select3.2 poll3.3 epoll三者对比 4. 深入理解 epoll4.1 epoll 的三大操作4.2 epoll 的核心数据结构…

大学英语神器:让GPT帮助你攻克完型填空和阅读理解

这里写目录标题 0、前言一、再来十篇完型填空和阅读理解第一部分&#xff1a;操作指南1.访问链接&#xff1a;ChatGPT 4o国内直接访问地址&#xff1a;https://share.xuzhugpt.cloud/2.上plus的车 第二部分&#xff1a;实操展示①完型填空②阅读理解 二、用户体验 0、前言 学习…

masm汇编debug调试1~100求和

计算123...100并把结果放到寄存器AX里 assume cs:codecode segment start:mov ax,0mov cx,100 s:add ax,cxloop smov ax,4c00hint 21hcode ends end start 效果演示&#xff1a;

LeetCode3226题. 使两个整数相等的位更改次数(原创)

【题目描述】 给你两个正整数 n 和 k。 你可以选择 n 的 二进制表示 中任意一个值为 1 的位&#xff0c;并将其改为 0。 返回使得 n 等于 k 所需要的更改次数。如果无法实现&#xff0c;返回 -1。 示例 1&#xff1a; 输入&#xff1a; n 13, k 4 输出&#xff1a; 2 解释&am…

ubuntu 异常 断电 日志 查看

sudo less /var/log/syslog 搜 Linux version

Python:入门基础

目录 常量和表达式 变量 变量的语法 变量的类型 动态类型特性 注释的使用 输入和输出 通过控制台输出 通过控制台输入 运算符 算术运算符 关系运算符 逻辑运算符 赋值运算符 常量和表达式 print是Python中的一个内置函数&#xff0c;使用print函数可以将数据打印…

ChatGPT 高级语音模式已登陆 Windows 和 Mac 平台,对话更自然

OpenAI ChatGPT 高级语音模式已登陆 Windows 和 Mac 平台&#xff0c;对话更自然&#xff0c;拟态更逼真 OpenAI 于10月31日正式宣布&#xff0c;ChatGPT 的高级语音模式&#xff08;Advanced Voice Mode&#xff0c;简称 AVM&#xff09;现已登陆 Windows 和 Mac 平台。基于最…

【深度学习】InstantIR:图片高清化修复

InstantIR——借助即时生成参考的盲图像修复新方法 作者:Jen-Yuan Huang 等 近年来,随着深度学习和计算机视觉技术的飞速发展,图像修复技术取得了令人瞩目的进步。然而,对于未知或复杂退化的图像进行修复,仍然是一个充满挑战的任务。针对这一难题,研究者们提出了 Insta…

【深度学习】实验 — 动手实现 GPT【三】:LLM架构、LayerNorm、GELU激活函数

【深度学习】实验 — 动手实现 GPT【三】&#xff1a;LLM架构、LayerNorm、GELU激活函数 模型定义编码一个大型语言模型&#xff08;LLM&#xff09;架构 使用层归一化对激活值进行归一化LayerNorm代码实现scale和shift 实现带有 GELU 激活的前馈网络测试 模型定义 编码一个大…

信息抽取与知识图谱技术在医疗领域中的应用

​快瞳AI开放平台支持多种输入格式&#xff0c;如电子病历、临床数据和医学文献等&#xff0c;可以将这些信息快速转换为结构化数据&#xff0c;包括自动360度不同角度的旋转识别、自动校准弯曲透视、光照不均、手写叠加处理等&#xff0c;提升数据的可操作性和可检索性。通过我…

SpringCloudAlibaba实战入门之OpenFeign高级用法(十)

在上一篇中我们简单了解了OpenFeign的简单使用,本篇是承接上一篇的高级使用拓展内容。 一、@FeignClient 标签的常用属性 @FeignClient 注解是 Spring Cloud OpenFeign 中用于声明一个 Feign 客户端的核心注解。它可以用来指定服务的名称、配置类、负载均衡策略等。下面是 @…

DBeaver 数据库安装及破解个人使用 不同版本不同jdk

DBeaver DBeaver 分为 **Lite、Enterprise、Ultimate&#xff08;功能最全&#xff09;、Community&#xff0c;**其中Community免费使用&#xff0c;但是功能不言而喻&#xff0c;具体差异自行去官网对比。 安装 DBeaver 到官网下载即可 https://dbeaver.io/download/ 激活 D…