【自考】数据结构第六章查找，期末不挂科指南，第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}^nfrac{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）然后在块内顺序查找

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

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

二叉排序树

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

若它的左子树不空，则左子树上所有结点的键值均小于它的根结点键值；
若它的右子树不空，则右子树上所有结点的键值均小于它的根结点键值；
根的左、右子树也分别为二叉排序树。

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

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

二叉排序树上的查找
二叉排序树上的插入

二叉排序树的查找分析

需要记住的一些小点如下

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

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

散列表

一些基本概念要普及一下

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