查找的一些基本概念查找表 是由同一类型的数据元素 构成的集合,它是一种以查找为“核心”,同时包括其他运算的非常灵活的数据结构。 上面概念中的集合和数学上的定义是一致的,简单地说就是由任意一些可分辨的对象构成的整体 作为一个数学概念,集合的元素是没有任何限制。 作为一种数据结构,查找表的逻辑结构是集合,对查找表进行的操作包括 若对查找表只进行前两项操作,则称此类查找表为 静态查找表顺序表上的查找
基于上述内容引入一个新的概念,叫做 它的定义是这样的:为找到数据元素在查找表中的位置,与给定值进行比较的键值个数的期望值。 $$ASL=\sum_{r=1}^nP_iC_i$$ 其中Pi为查找第i个元素(即给定值key与顺序表中第i个元素的键值相等)的概率,且$\sum_{r=1}^nP_i=1$,Ci表示在找第i个元素时,与给定值已进行比较的键值个数。 假设顺序表为(b1,b2,b3)查找b1,b2,b3的概率分别是0.2,0.2,0.6,则顺序查找法的平均查找长度为 $0.2 * 3+0.22+0.61 = 1.6$ 即平均需要1.6 次键值与给定值的比较才能找到待查元素。 由于多种元素Pi值不好确定,所以通常让Pi概率相等,即对所有的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个数据元素的有序表(关键字即为数据元素的值) 第一步,找到查找区间,合计9个数据元素,那么[1,9]就是区间 第二步,缩小查找区间,合计4个数据元素,那么[1,4]就是区间 第三步,缩小查找区间,那么[3,4]就是区间 索引顺序表上的查找
若静态查找表用索引顺序表表示,则查找操作可用分块查找来实现,也称为 结论:
二叉排序树一棵二叉排序树(又称二叉查找树)具备如下性质
二叉排序树的案例如下图所示 关于二叉排序树,教材中涉及了部分代码,分别如下
二叉排序树的查找分析需要记住的一些小点如下 二叉排序树上的平均查找长度是介于O(n)和O($\log_2n$)之间。 以下两个树的平均查找长度分别为 散列表一些基本概念要普及一下 数据元素的键值和存储位置之间建立的对应关系H成为 常用的散列法构造散列函数的方法,了解一下
散列表的实现(自考必考,不是考代码,是考方法)线性探测法直接用例题与动画来解释吧 题目要求
线性探测法 就是 求余数,然后放到对应的位置上,如果位置上有数据元素了,那么就向后移动,移动到没有数据元素的位置上,然后占坑 平均查找长度 ASL 就是把元素查找次数加起来总和/散列表长度 = 16/11 二次探测法二次探测法,核心在于二次上,说白了,就是当你取余得到的位置由数据元素的时候,需要进行二次的偏移探测 例如,还是上述的题目,当计算到34的时候,发现位置1已经有元素了,接下来就要进行二次探测了 用1的位置分别进行+12,-12,+22,-22... 第一步,探测1+12 = 2 ,位置2是否存在元素,发现有 链地址探测法可以通过一个案例来简单说明一下 选定一个散列函数H(key) = key mod 13 ,键值为26,41,25,05,07,15,12,49,51,31,62 然后我们把求到的余数,依次对应到邻接表里面,如下图(直接截取教材图了,就不画了) 公共溢出区法(选看)更多图示: https:///r4lCXEuL 小结本章在自考或者期末考试中,核心内容是二分查找方法;二叉排序树的构建,散列表的查找方法,重点会考察线性探测法和二次探测法,重点看一下吧。 BYEBYE~ |
|