数据结构篇_知识点板块_第七章查找

2022年05月11日 阅读数:3
这篇文章主要向大家介绍数据结构篇_知识点板块_第七章查找,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
  • 数据结构篇为本人考研时所写笔记,包括知识点和编程思想两大板块,笔记内容依据王道数据结构考研书所写,但比书本上知识更加生动形象,愿本篇章能对您有所帮助

7、查找

(一)基本查找方法

  1. 基本概念:

① 查找表(又称查找结构):用于查找的数据集合算法

②  静态查找表(顺序查找,折半查找,分块查找):不须要进行动态插入或删除的查找表编程

③  动态查找表(二叉排序树,二叉平衡树,B-,B+):与上反之(不要被动态静态误导了,并非链表和顺序表的意思)数组

④ 关键字:数据元素中惟一标识该元素的某个数据项的值,基于关键字查找结果是惟一的安全

⑤ 一次查找长度:须要比较的关键字次数数据结构

⑥ 平均查找长度(ASL):全部查找过程当中进行关键字比较次数的平均值函数

  1. 通常线性表顺序查找:

① 哨兵:将值a赋给查找表中最后一个元素,则在for循环中中间判断条件是判断是否等于a而没必要判断数组是否会越界性能

②  哨兵好处:避免不少没必要要的判断语句,从而提升程序的效率优化

③ ASL:编码

(1) 查找成功时平均长度:3d

(2) 查找成功时平均长度(等几率时):ASL=(n+1)/2

(3) 查找不成功时平均长度:n+1

④ 注意对线性的链表只能进行顺序查找

⑤ 顺序表查找指的是在顺序存储结构上进行查找(错)(顺序存储指的就是数组之的数据结构,可是 顺序表并不必定是用数组实现的,例如链表即也可在链式存储结构上实现)

  1. 有序线性表顺序查找(通常线性表顺序查找的一种优化):

① 概念:查找以前知道表的关键字(数值)是有序的

② 有序线性表的断定树:

(1) 树中圆形结点:有序线性表中存在的元素

(2) 树中矩形结点:失败结点;如有n个结点,则相应有n+1个查找失败结点(即相似于二叉数查找失败时所画的空结点)

③ 时间复杂度:O(n)

④ ASL:

(1) 查找成功时平均长度与通常线性表同样

(2) 查找不成功时平均长度(等几率时):n/2 + n/(n+1)(到达失败结点的长度等于父结点所在层数)

  1. 通常线性表顺序查找的另外一种优化:当被查几率不等时把被查几率大的放在靠前的位置(相似于哈夫曼编码的思想),但这会时ASL_不成功增大,故怎么优化还应依状况而定

  2. 折半查找(二分查找):

① 折半查找断定树(二叉数):

(1) 断定树:将折半查找过程用二叉树来描述(折半查找的性能分析能够用二叉断定树来衡量)

(2) 断定树是一颗平衡二叉树

(3) 圆形结点:表示一个记录

(4) 结点中的值:该记录的关键字值

(5) 方形结点:树最下面的叶结点,表示查找不成功的状况

(6) 查找成功时:查找长度为根节点到目标结点

查找失败时:查找长度为根节点到对应失败结点的父结点

(7) 左结点值<根值<右结点值(同二叉排序树)

(8) 如有序序列有n个元素,则对应断定树有n个圆形非叶结点和n+1个方形叶结点

(9) 注意:

​ (1 当向下取整(mid=(low+high)/2):断定树必须右子树结点数-左子树结点数=0/1

​ (2 当向上取整(mid=(low+high)/2):断定树必须左子树结点数-右子树结点数=0/1(考试时看清是向上仍是向下取整

(10) 在查找不成功时和给定值进行关键字的比较次数最多为树的高度

② 要求必须是顺序存储结构且元素按关键字有序排列

③ 时间复杂度:O(log_2 n)

④ ASL:

(1) 查找成功时:
(h不包括失败结点)

  1. K分查找:

  2. 分块查找(索引顺序查找):

① 基本思想:将查找表分为若千子块。块内的元素能够无序,但块之间是有序的,即第一个块中的最大关键字小于第二个块中的全部记录的关键字,第二个块中的最大关键字小于第三个块中的全部记录的关键字,以此类推。再创建一个索引表,索引表中的每一个元素含有各块的最大关键字和各块中的第一个元素的地址,索引表按关键字有序排列

② 分块查找的过程分为两步:

(1) 第一步是在索引表中肯定待查记录所在的块,能够顺序查找或折半查找索引表

(2) 第二步是在块内顺序查找(由于可能无序故只能顺序查找)

③ ASL:

(1) ASL=索引查找平均长度(L_I)+块内查找平均长度(L_S)

(2) 长度为n的查找表均匀地分为b块,每块有s个记录:

​ (1 等几率都使用顺序查找:
(若s=
,则min(ASL)=
+1(求导取极值得出的))

​ (2 索引表用折半查找:

​ (3 当都用折半查找时效率最高,具体数据看题(时间效率介于顺序查找和二分查找之间)

  1. 若查找表是动态表,则通常用链式存储较方便
优势 缺点 适用于
通常线性表顺序查找有序表的顺序查找 ① 对数据元素存储和表中记录的有序性没要求② 顺序存储或链式存储皆可 当数值较多时,平均查找长度大 长度较小的表和查找较少但改动较多的表
折半查找 查找效率高 要求必须是顺序存储结构且元素按关键字有序排列 一经创建就不多改动又常常须要查找的线性表
分块查找 ① 在表中插入或删除记录时只要在该记录所属块内操做② 块内记录存放随意故易插入和删除 要增长一个辅助数组的存储空间 有分块特色的记录(如学生登记表可按系号分块)

(二)B树(多路平衡查找树)和B+树

考前结合王道选择看一下

1)B树

  1. 阶:B树(能够为空树)中全部结点的孩子个数最大值

  2. B树为知足下列特性的m叉树:

① 树中每一个结点至多有m棵子树,即至多含有m-1个关键字。

② 若根结点不是终端结点,则至少有两棵子树(保证绝对平衡,即没高度差)

③ 除根结点外的全部非叶结点至少有向上取整(m/2)棵子树,即至少含有向上取整(m/2)-1个关键字

④ 综上:

(1) 根结点的子树数∈[2,m]

(2) 关键字数∈[1,m-1]

(3) 其余结点的子树数∈[向下取整(m/2),m]

(4) 关键字数∈[向下取整(m/2)-1,m-1]

⑤ 结点中的关键字是有序的,且结点知足:子树0<关键字1<子树1<关键字2...(即左结点值<根值<右结点值)

⑥ 全部的叶结点都出如今同一层次上,而且不带信息(能够视为外部结点或相似于折半查找断定树的杳找失败结点,实际上这些结点不存在,指向这些结点的指针为空)

⑦ 对于任一结点,全部子树高度都相同

⑧ n个关键字的B树必有n+1个叶子结点

⑨ 综上所述B树是全部结点的平衡因子均等于0的多路平衡查找树,与③都是为了保证查找效率

(外部结点又称叶子结点/失败结点,外部结点上面一层的结点又称终端结点)

  1. 计算B树高度时应注意是否包括最后的叶子结点

  2. 对于n>=1,包含n个关键字,高度为h,阶数为m的B树:

① 

② 

2)B+树

  1. B+树需知足如下条件:

① 每一个分支结点最多有m棵子树(孩子结点)

② 非叶根结点至少有两棵子树,其余每一个分支结点至少有向下取整(m/2)棵子树

③ 结点的子树个数与关键字个数相等

④ 全部叶结点包含所有关键字及指向相应记录的指针,叶结点中将关键字按大小顺序排列而且相邻叶结点按大小顺序相互连接起来

⑤ 全部分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针

  1. 不管查找成功与否,每次查找都是一条从根结点到叶结点的路径(即都要走到最小面),由于只有底层结点才包含信息,故对于B+树而言只有查找到最下面一层结点才是成功的
B树与B+树主要差异
m阶B树 m阶B+树
类比 二叉查找树的进化-->m叉查找树 分块查找的进化-->多级分块查找
关键字与分叉 n个关键字对应n+1个分叉(子树) n个关键字对应n个分叉
结点包含的信息 全部结点中都包含记录的信息 n个关键字对应n个分叉只有最下层叶子结点才包含记录的信息(可以使树更矮)
查找方式 不支持顺序查找。查找成功时,可能停在任何一层结点,查找速度“不稳定” 支持顺序查找。查找成功或失败都会到达最下一层结点,查找速度“稳定”
相同点 除根节点外,最少向下取整(m/2)个分叉(确保结点不要太空)任何一个结点的子树都要同样高(确保“绝对平衡")

3)B-树(多路平衡查找树)

  1. 适合在磁盘等直接存取设备上组织动态的查找表

(三)散列表

  1. 典型的空间换时间的算法

  2. 基本概念:

① 散列函数(又称哈希函数):一个把查找表中的关键字映射成该关键字对应的地址的函数

② 散列表(又称哈希表):根据关键字而直接进行访问的数据结构(散列表创建了关键字和存储地址之间的一种直接映射关系)

③ 冲突:当两个或两个以上不一样关键字映射到同一地址(解决冲突的经常使用方法是:线性探测法,多重散列法,链地址法)

④ 冲突解决技术能够分为两类:开散列方法(也称为拉链法/链地址法)和闭散列方法(也称为开地址方法)。这两种方法的不一样之处在于:开散列法把发生冲突的关键码存储在散列表主表以外,而闭散列法把发生冲突的关键码存储在表中另外一个槽内

⑤ 线性探测是出现冲突后开始向后探测一个位置,因此从第二个关键字若和第一个冲突时映射时要作1次探测

⑥ 同义词:发现碰撞的不一样关键字

  1. 时间复杂度(理想状况):O(1)(哈希表的查找效率主要取决于哈希表造表时所选取的哈希函数和处理冲突的方法)

  2. 散列表和索引表的区别:

(1) 散列存储是直接将关键字的值作一个映射到存储地址

(2) 索引存储则是另外使用关键字来构建一个索引表

A. 散列函数的构造

  1. 构造散列函数需注意:

① 散列函数的定义域必须包含所有须要存储的关键字,而值域的范围则依赖于散列表的大小或地址范围。

② 散列函数计算出来的地址应该能等几率、均匀地分布在整个地址空间中,从而减小冲突的发生

③ 散列函数应尽可能简单,可以在较短的时间内计算出任一关键字对应的散列地址

  1. 散列函数选择两条标准:简单和均匀

  2. 一些函数分析:

① 不能看成散列函数,由于该函数的返回值不肯定,这样没法进行正常的查找(并非随机就是好)

② :可以做为散列函数,但不是一个好的散列函数,由于全部关键字都映射到同一位置,形成大量的冲突机会。

a. 直接地址法

  1. 直接取关键字的某个线性函数值为散列地址,散列函数为

  2. 适合关键字的分布基本连续的状况;若关键字分布不连续,空位较多,则会形成存储空间的浪费

b. 除数余数法

  1. 通常取不大于表长但最接近或等于表长的质数p(又称素数(不能被除自身和1外的数整除)(合数是指在大于1的整数中除了能被1和自己整除外,还能被其余数(0除外)整除的数。与之相对的是质数,而1既不属于质数也不属于合数)),散列函数为

  2. 此方法关键是取好P

c. 数字分析法

  1. 设关键字是r进制数(如十进制数),而r个数码在各位上出现的频率不必定相同,可能在某些位上分布均匀一些,每种数码出现的机会均等:而在某些位上分布不均匀,只有某几种数码常常出现,此时应选取数码分布较为均匀的若干位做为散列地址

  2. 这种方法适合于己知的关键字集合,若更换了关键字,则须要从新构造新的散列函数

d. 平方取中法

  1. 取关键字的平方值的中间几位做为散列地址,具体取几位视状况而定

  2. 适合用于数据量过大的状况

B. 处理冲突方法

  1. 要彻底(不是安全)避免冲突需知足:

① 关键字集合U不大于散列表长m

② 选择合适的散列函数(例如选择
就不合适)

a. 开放地址法

  1. 数学递推公式:
    )

  2. di通常有四种取法:

① di中i表示当前元素H(key)冲突后依次H(key)+di(从0开始)比较后的冲突次数,如若分别与H(key)+0、一、-1位置冲突共冲突三次则下一次即为H(key)+d3=H(key)+4(以平方探测法为例)

② 线性探测法:

(1) di=0,1,2...

(2) 空位置的判断也要算成一次比较

(3) 缺点:易形成大量元素的散列地址“汇集”(或堆积(由同义词之间或非同义词之间发生冲突(不是仅同义词之间)))(对存储效率、散列函数、装填因子均不会有影响,但会直接影响平均查找长度)起来,减低查找效率

(4)

③ 平方探测法(二次探测法):(2021考了)

(1) di=0,1,-1,4,-4...

(2)

④ 再散列法(双散列法、再哈希法)

(1) 除了原始散列函数H(key)外,多准备几个散列函数,当散列函数冲突时,用下一个散列函数计算一个新地址,直到不冲突为止

⑤ 伪随机序列法:

(1) di=伪随机序列

  1. 注意:在开放定址的情形下,不能随便物理删除表中的已有元素,由于若删除元素,则会截断其余具备相同散列地址的元素的查找地址。所以,要删除一个元素时,可给它作一个删除标记,进行逻辑删除。但这样作的反作用是:执行屡次删除后,表面上看起来散列表很满,实际上有许多位置未利用,所以须要按期维护散列表,要把删除标记的元素物理删除。

b. 拉链法(连接法,chaining)

  1. 将全部同义词存储在一个线性链表中,这个线性链表由其散列地址惟一标识

  2. 适用于常常进行插入和删除的状况

  3. 若限定在链首插入,则插入任一个元素的时间是相同的

  4. 注意:有的教材会把“空指针”的判断算做一次比较,具体参考真题是怎么计算的

开放地址法和拉链法比较
开放地址法 拉链法
放置位置 将全部结点均存放在散列中 将互为同义词的结点链成一个单链表,而将此表的头指针放在散列表中(因此拉链法的图结点不在散列表中)
优势 拉链法相比较下的优势:① 简单无堆积② 动态申请表长③ 空间可节省(α可大于1(开放地址法为减小冲突要求α较小))
缺点 拉链法缺点:① 当结点规模较小时,指针域要占用额外空间,此时仍是开放地址法省空间

C.散列查找及性能分析

  1. 散列表的查找效率取决于三个因素:散列函数、处理冲突的方法和装填因子

  2. 装填因子(通常记为α):定义一个表的装满程度()

  3. 散列表的平均查找长度依赖于散列表的装填因子α,而不直接依赖于n或m

  4. α越大,表示装填的记录越“满”,发生冲突的可能性越大,反之发生冲突的可能性越小

(四)ASL综述

  1. 设一个查找集合中已有n个数据元素,每一个元素的查找几率为p_i,查找成功的数据比较次数为G (i=1, 2,…, n);不在此集合中的数据元素分布在由这n个元素的间隔构成的n+1个子集合内,每一个子集合元素的查找几率为q_j,查找不成功的数据比较次数为c_j(j=0, 1,…,n)。所以,对某一特定查找算法的查找成功的ASL和查找失败的ASL,是综合考虑仍是分开考虑呢?

答:

  1. 上述两种考虑的计算结果是不一样的,考试中必定要仔细阅读题目的要求,以避免失误

  2. 散列表平均查找成功长度除以排序个数,平均查找失败长度除以散列表长度