首页 > 编程语言 >数据结构·查找算法

数据结构·查找算法

时间:2024-06-04 16:26:04浏览次数:21  
标签:10 frac -- mid 算法 查找 数据结构 ASL

查找

1.顺序查找

一般表

(1)代码

typedef struct{
    ElemType *elem;
    int tableLen;
}SSTable;

int searchSeq(SSTable ST, ElemType key){
    ST.elem[e] = key;   //设置哨兵
    for(int i = 0; i<ST.tableLen; i++)
        return i;   //存在返回, 不存在返回1
}

(2)设置哨兵:可以不必判断是否越界,注意数据下表从1开始
(3)ASL
$$
如果不能知道查找概率,可先对记录的查找概率进行排序,是表中的记录按查找概率从小到大\
ASL_{success} = \sum_{i=1}^{n} P_i(n-i+1) = \frac{n+1}{2}\
ASL_{unsuccess} = n+1\
$$
(4)优缺点
优点:对数据的存储无要求,顺序存储或者链式存储皆可
缺点:当n较大,平均查找长度较大,效率低

有序表

graph LR id1((10))--id2((20)) id1((10)).--infinity,10 id2((20))--id3((30)) id2((20)).--infinity,20 id3((30))--id4((40)) id3((30)).--infinity,30 id4((40))--id5((50)) id4((40)).--infinity,40 id5((50))--id6((60)) id5((50)).--infinity,50 id6((60))--60,= id6((60)).--infinity,60

(1)一旦查到某个元素大于该元素便停止查找
(2)方框是虚构的节点,查找长度=方框上的圆环
(3)ASL
$$
ASL_{success} = \sum_{i=1}^{n} P_i(n-i+1) = \frac{n+1}{2}\
ASL_{unsuccess} = \sum_{j=1}^{n} Q_j(l_j-1) = \frac{1+2+...+n+n}{n+1} = \frac{n}{2} + \frac{n}{n+1}\
$$

折半查找(二分查找)

graph LR id29((29))--id37((37))--id41((41))--id43((43)) id43((43))--43,+infinity id43((43))--37,43 id37((37))--id32((32))--id33((33)) id32((32))--29,32 id33((33))--33,37 id33((33))--32,33 id13((13))--id16((16))--id19((19))--19,29 id19((19))--16,19 id29((29))--id13((13))--id7((7))--id10((10))--10,13 id10((10))--7,10 id7((7))---infinity,7

(1)仅适用于顺序表
(2)代码

int binarySearch(SeqList L, ElemType key){
    int low, high, mid = 0, L.tableLen, 0;
    while(low <= high){
        mid = (low + high) / 2;
        if(L.elem[mid] == key)
            return mid;
        else if(L.elem[mid]  key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

(3)ASL
$$
ASL = \frac{1}{n}\sum_{i=1}^{n} l_i = \frac{1}{n}(11+22+...+h*2^{h-1}) = \frac{n+1}{n} log_2(n+1)-1 = log_2(n+1)-1\
h=[log_2(n+1)](向上取整)
$$

查找11

low=7, high=43, mid=29
11<29
graph 7--low 10 13 16 19 29--mid 32 33 37 41 43--high
low=7, high=mid-1=19, mid=13
11<13
graph 7--low 10 13--mid 16 19--high 29 32 33 37 41 43
low=7, high=mid-1=7, mid=10
117
graph 7--low--mid 10--high 13 16 19 29 32 33 37 41 43
low=mid+1=10, high=10, mid=10
1010 ×
graph 7 10--low--mid--high 13 16 19 29 32 33 37 41 43
没找到,停在low

分块查找

(1)将查找表分为若干子块,块内可以无序,但块之间有序的

graph id24((24))--id((索引块24,54,78,88)) id21((21)) id6((6)) id11((11)) id8((8)) id22((22)) id32((32))--id((索引块24,54,78,88)) id31((31)) id54((54)) id72((72))--id((索引块24,54,78,88)) id61((61)) id78((78)) id88((88))--id((索引块24,54,78,88)) id83((83))

(2)ASL
$$
n:长度\
b:分块个数\
s:每块s个记录\
P:等概率\
ASL = L_I+L_S = \frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}\
s=\sqrt{n},ASL=\sqrt{n}+1\
采用折半查找:ASL=L_I+L_S=[log_2(b+1)]+\frac{s+1}{2}(向上取整)
$$

B树(多路平衡查找树)

$$
m阶B树或空树\
每棵子树至多m棵子树,最多包含m-1个关键字\
若根节点不是终端节点,至少两棵子树\
除根结点外所有非叶节点至少[\frac{m}{2}](向上取整)棵子树(关键字)\
$$

graph id[22]--id0[5,11] id[22]--id1[36,45] id0[5,11]--id00[1,3] id0[5,11]--id01[6,8,9] id0[5,11]--id02[13,15] id1[36,45]--id10[30,35] id1[36,45]--id11[40,42] id1[36,45]--id12[47,48,50,56]

标签:10,frac,--,mid,算法,查找,数据结构,ASL
From: https://www.cnblogs.com/blueflylabor/p/18231128

相关文章

  • 数据结构·查找算法
    查找1.顺序查找一般表(1)代码typedefstruct{ElemType*elem;inttableLen;}SSTable;intsearchSeq(SSTableST,ElemTypekey){ST.elem[e]=key;//设置哨兵for(inti=0;i<ST.tableLen;i++)returni;//存在返回,不存在返回1}(2)设......
  • 基于Java+Dijkstra算法的地铁线路换乘最短路径项目(免费提供全部源码)
    下载地址如下:基于Java+Dijkstra算法的地铁线路换乘最短路径项目(免费提供全部源码)资源-CSDN文库项目介绍背景随着城市化进程的不断推进,地铁已成为现代大城市公共交通系统的核心组成部分。地铁线路的日益复杂和站点的不断增加,使得乘客在出行时面临换乘路线选择的困扰。为了提......
  • 多源最短路径算法–Floyd算法
    多源最短路径算法–Floyd算法Floyd算法是为了求出每一对顶点之间的最短路径它使用了动态规划的思想,将问题的求解分为了多个阶段先来个例子,这是个有向图Floyd算法的运行需要两个矩阵最短路径矩阵从当前这个状态看各顶点间的最短路径长度例如初始状态可以看出这是该......
  • Transgaga——人脸与猫脸之间互相转换算法解析
    1.概述虽然pix2pix作为风格转换模型被提出,但它依赖于成对的数据集。与之相比,CycleGAN通过引入循环损失,实现了无需配对数据的风格转换。不过,CycleGAN在处理需要大幅几何变化的风格转换时表现不佳,仅在如马和斑马这类颜色变化的场景中有效。2018年,MUNIT利用变分自编码器(VAE)......
  • 飞睿uwb定位tag防丢器,蓝牙智能防丢器原理,支持苹果IOS的本地防丢查找
    在当今这个快节奏的社会,人们的注意力经常被各种琐事分散,丢三落四的情况时有发生。随着科技的发展,智能防丢器应运而生,成为帮助我们解决这一烦恼的助手。今天,我们就来深入探讨一款备受瞩目的智能防丢产品——飞睿UWB定位Tag防丢器,它不仅结合了新的蓝牙技术,还拥有自己的APP,支持苹......
  • 经纬恒润成功研发LRR610雷达先进算法!
        好消息!经纬恒润搭载Arbe芯片组的LRR6104D成像雷达算法开发出先进的后点云算法,并已圆满完成集成工作,这标志着智能驾驶感知系统迈向了一个新的里程碑。     经纬恒润自主开发的成像雷达算法,可以有效地跟踪数百个运动和静止目标,输出可行驶区域和道路边界,仅基于......
  • 数据结构第四篇【再谈泛型】
    数据结构第四篇【再谈泛型】泛型泛型类的使用泛型的上界泛型方法通配符通配符上界通配符下界......
  • 【算法】字符串函数
    今天讲讲字符串函数。//C++标凇库提供了丰富的字符串操作函数,下面介绍一些常用的函数。//备注:位置可以看成是字符串的下标,从0开始//获取字符串长度//使用length或size函数来获取字符串的长度。#include<iostream>#include<string>#include<algorithm>#include<......
  • 【会议征稿,IEEE出版】第二届算法、图像处理与机器视觉国际学术会议(AIPMV2024,7月12-14)
    2024年镇江市计算机科学技术大会暨第二届算法、图像处理与机器视觉国际学术会议(AIPMV2024)将于2024年7月12日-14日在江苏镇江召开。会议主要围绕算法、图像与视觉处理等研究领域展开讨论,为从事算法、图像与视觉处理研究的专家学者、工程技术人员、技术研发人员提供一个分享......
  • 【耗时8个小时整理】硬核集成算法,学习完你会哭着感谢自己!
    纯 干 货目录纯 干 货1、Bagging(自举汇聚法)2、Boosting(提升法)3、Stacking(堆叠法)4、Voting(投票法)5、深度学习集成今天给大家带来的是「集成算法」的全部整理!其实今儿的一些内容比较好理解~集成算法(EnsembleLearning)是一种将多个弱学习器......