专栏首页Python3爬虫100例教程【自考】数据结构第六章查找,期末不挂科指南,第10篇

【自考】数据结构第六章查找,期末不挂科指南,第10篇

查找的一些基本概念

查找表 是由同一类型的数据元素 构成的集合,它是一种以查找为“核心”,同时包括其他运算的非常灵活的数据结构。

上面概念中的集合和数学上的定义是一致的,简单地说就是由任意一些可分辨的对象构成的整体

作为一个数学概念,集合的元素是没有任何限制。

作为一种数据结构,查找表的逻辑结构是集合,对查找表进行的操作包括 查找表中的某一元素读取表中特定数据元素插入和删除一个数据元素等。

若对查找表只进行前两项操作,则称此类查找表为 静态查找表。 若在查找过程中,向表中插入不存在的数据元素,或者从表中删除某个数据元素,则称此类查找表为动态查找表

静态查找表

顺序表上的查找

具体的代码就不实现了,有兴趣的可以自行查阅,主要说的是概念与逻辑

对于查找运算,其基本操作是“数据元素的键值与给定值的比较”,所以通常用“数据元素的键值与给定值的比较次数”作为衡量查找算法好坏的依据,称上述比较次数为查找长度。但是查找长度与键值在顺序表中的位置有关,且差别很大。例如,若键值在顺序表的第n个位置上,则查找长度为1,而如果键值在顺序表的第1个位置上,查找长度为n。

基于上述内容引入一个新的概念,叫做“查找成功时的平均查找长度(记作ASL)”

它的定义是这样的:为找到数据元素在查找表中的位置,与给定值进行比较的键值个数的期望值。 当查找表有n个元素时,有

$$ASL=\sum_{r=1}^nP_iC_i$$

其中P~i~为查找第i个元素(即给定值key与顺序表中第i个元素的键值相等)的概率,且$\sum_{r=1}^nP_i=1$,C~i~表示在找第i个元素时,与给定值已进行比较的键值个数。

假设顺序表为(b~1~,b~2~,b~3~)查找b~1~,b~2~,b~3~的概率分别是0.2,0.2,0.6,则顺序查找法的平均查找长度为 $0.2 * 3+0.22+0.61 = 1.6$ 即平均需要1.6 次键值与给定值的比较才能找到待查元素。

由于多种元素P~i~值不好确定,所以通常让P~i~概率相等,即对所有的i,有 $P_i =\frac{1}{n}$,并在此假设下确定查找算法的平均查找长度。

$$ASL=\sum_{r=1}^nP_iC_i=\sum_{r=1}^n\frac{1}{n}*(n-i+1)=\frac{n+1}{2}$$

上述内容记住结论即可。

有序表上的查找

如果顺序表中数据元素是按照键值大小的顺序排列的,则称为有序表。

这种存储结构,查找运算可以用效率更高的二分查找法

直接看例题即可

现在有一个含有9个数据元素的有序表(关键字即为数据元素的值) (10,13,17,20,30,55,68,89,95)用二分查找算法查找key=17的过程

第一步,找到查找区间,合计9个数据元素,那么[1,9]就是区间 (1+9)/ 2 = 5 找到位置5的数据元素30,30>17 进入第二步

第二步,缩小查找区间,合计4个数据元素,那么[1,4]就是区间 (1+4)/ 2 = 2.5 去尾法 等于2 找到位置2的数据元素13,13<17 进入第三步

第三步,缩小查找区间,那么[3,4]就是区间 (3+4) / 2 = 3.5 去尾法 等于3 找到位置3的数据元素17,正好是待查元素,查找成功,返回结果为mid=3

索引顺序表上的查找

索引顺序表由两部分组成:一个索引表和一个顺序表 其中 顺序表在组织形式上与普通的顺序表完全相同,而索引表本身在组织形式上也是一个顺序表。 索引表通过索引将顺序表分割为若干块,而顺序表呈现出“按块有序”的形式

若静态查找表用索引顺序表表示,则查找操作可用分块查找来实现,也称为 索引顺序查找。 分为两步进行: (1)先确定待查数据元素所在的块 (2)然后在块内顺序查找

结论: 静态查找表 有顺序查找、二分查找、分块查找 三种特点分别为:

  1. 顺序查找效率最低但限制最少
  2. 二分查找效率最高,但限制最多
  3. 分块查找介于上述二者之间

二叉排序树

一棵二叉排序树(又称二叉查找树)具备如下性质

  1. 若它的左子树不空,则左子树上所有结点的键值均小于它的根结点键值;
  2. 若它的右子树不空,则右子树上所有结点的键值均小于它的根结点键值;
  3. 根的左、右子树也分别为二叉排序树。

二叉排序树的案例如下图所示

关于二叉排序树,教材中涉及了部分代码,分别如下

  1. 二叉排序树上的查找
  2. 二叉排序树上的插入

二叉排序树的查找分析

需要记住的一些小点如下

二叉排序树上的平均查找长度是介于O(n)和O($\log_2n$)之间。

以下两个树的平均查找长度分别为

散列表

一些基本概念要普及一下

数据元素的键值和存储位置之间建立的对应关系H成为散列函数, 用键值通过散列函数获取存储位置的这种存储方式构造的存储结构成为散列表,这一映射过程称为散列 如果选定了某个散列函数H及其对应的散列表L,则对每个数据元素X,函数值H(H.Key)就是X在散列表L中的存储位置,这个存储位置也称为散列地址。

常用的散列法

构造散列函数的方法,了解一下

  1. 数字分析法
  2. 除留余数法
  3. 平方取中法
  4. 基数转换法

散列表的实现(自考必考,不是考代码,是考方法)

线性探测法

直接用例题与动画来解释吧

题目要求

设散列表长度为11,散列函数H(key) = key mod 11(mod为求余运算),给定的健值序列为(3,12,13,27,34,22,38,25),试画出采用线性探测法解决冲突时所构造的散列表,并求出在等概率的情况下查找成功时的平均查找长度。

线性探测法 就是 求余数,然后放到对应的位置上,如果位置上有数据元素了,那么就向后移动,移动到没有数据元素的位置上,然后占坑

平均查找长度 ASL 就是把元素查找次数加起来总和/散列表长度 = 16/11

二次探测法

二次探测法,核心在于二次上,说白了,就是当你取余得到的位置由数据元素的时候,需要进行二次的偏移探测

例如,还是上述的题目,当计算到34的时候,发现位置1已经有元素了,接下来就要进行二次探测了

用1的位置分别进行+1^2^,-1^2^,+2^2^,-2^2^...

第一步,探测1+1^2^ = 2 ,位置2是否存在元素,发现有 第二步,探测1-1^2^ = 0,位置0是否存在元素,发现无,那么好,把34放在位置0那里,假设位置0也有元素了 第三步,探测1+2^2^ = 5,位置5是否存在元素,发现无,把34放过去。

链地址探测法

可以通过一个案例来简单说明一下

选定一个散列函数H(key) = key mod 13 ,键值为26,41,25,05,07,15,12,49,51,31,62

然后我们把求到的余数,依次对应到邻接表里面,如下图(直接截取教材图了,就不画了)

公共溢出区法(选看)

更多图示: https://dwz.cn/r4lCXEuL

小结

本章在自考或者期末考试中,核心内容是二分查找方法;二叉排序树的构建,散列表的查找方法,重点会考察线性探测法和二次探测法,重点看一下吧。

BYEBYE~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【自考】数据结构第三章,栈、队列、数组,期末不挂科指南,第3篇

    栈(Stack)是运算受限的线性表,这种线性表上的插入和删除操作限定在表的一端进行

    梦想橡皮擦
  • Python爬虫入门教程 61-100 写个爬虫碰到反爬了,动手破坏它!

    当你兴冲冲的打开一个网页,发现里面的资源好棒,能批量下载就好了,然后感谢写个爬虫down一下,结果,一顿操作之后,发现网站竟然有反爬措施,尴尬了。

    梦想橡皮擦
  • Python爬虫入门教程 48-100 使用mitmdump抓取手机惠农APP-手机APP爬虫部分

    mitmdump是mitmproxy的命令行接口,比Fiddler、Charles等工具方便的地方是它可以对接Python脚本。 有了它我们可以不用手动截获和...

    梦想橡皮擦
  • 数据结构:图文详解 - 动态查找、静态查找、散列查找

    对于二分查找存在一定的优 & 缺点,所以衍生出2种二分查找的变式方法:插值查找 & 斐波那契查找。具体如下:

    Carson.Ho
  • 算法与数据结构(九) 查找表的顺序查找、折半查找、插值查找以及Fibonacci查找(Swift版)

    今天这篇博客就聊聊几种常见的查找算法,当然本篇博客只是涉及了部分查找算法,接下来的几篇博客中都将会介绍关于查找的相关内容。本篇博客主要介绍查找表的顺序查找、折半...

    lizelu
  • 9.2 静态查找表

    1、顺序查找(Sequential Search)的查找过程为:从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,...

    闫小林
  • 文件查找

    文件查找:locate, find 实时查找:遍历所有文件进行条件匹配 非实时查找:根据索引查找 locate...

    零月
  • Linux中find命令用法全汇总,看完就没有不会用的!

    糖豆贴心提醒,本文阅读时间7分钟 Linux 查找命令是Linux系统中最重要和最常用的命令之一。查找用于根据与参数匹配的文件指定的条件来搜索和查找文件和目录...

    小小科
  • Linux中find命令用法全汇总,看完就没有不会用的!

    Linux 查找命令是Linux系统中最重要和最常用的命令之一。查找用于根据与参数匹配的文件指定的条件来搜索和查找文件和目录列表的命令。查找可以在各种条件下使用...

    小小科
  • 算法图解|简单查找和二分查找算法

    AI深度学习求索

扫码关注云+社区

领取腾讯云代金券