查找
查找方法
- 顺序查找
- 折半查找
- 分块查找
平均查找长度 ASL（Average Search Length ）
所有查找过程中进行关键字比较次数的平均值
数学定义为：$ASL=\sum _{i=1}^n P_i C_i$
n是查找长度，$P_i$是查找第i个元素的概率，$C_i$是找到第i个元素所需进行比较次数
顺序查找
适用于无序的表，挨个查找1
2
3
4
5
6
7
8
9typedef struct {
ElemType *elem; //元素存储空间基址
int TableLen;//表长
}SSTable;
int Search_Seq(SSTable ST,ElemType key){
ST.elem[0]=key; //哨兵
for(i=ST.TableLen;ST.elem[i]!=key;--i); //从后往前找到i为0时退出for循环
return i;
}
平均查找长度：
折半查找
折半查找其实就是把查找表分成两半，然后在这两半里面继续分…1
2
3
4
5
6
7
8
9
10int BinarySearch(SeqList L;ElemType key){
int low=0,high=L.TableLen-1,mid;
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;
}
折半查找的过程可以用二叉树来描述，这个二叉树叫判定树，用折半查找到给定值的比较次数不会超过数的高度,即$\left \lceil log_2 (n+1) \right \rceil$
平均查找长度：
$ASL_{success}=log_2 (n+1)-1$
分块查找
分块查找又称索引查找，吸取了折半查找和顺序查找的优点，块内元素可以无序，但是块之间是有序的。
示意图：
索引表
| 24 | 54 | 78 | 88 |
|---|---|---|---|
| 1 | 7 | 10 | 13 |
查找表：
| 24* | 21* | 6* | 11* | 8* | 22* |
|---|---|---|---|---|---|
平均查找长度：
$ASL=L_I+L_S$
$L_I$ 和 $L_S$分别为索引查找和块内查找的平均查找长度
①若干将长度为n的产值表均匀分b块，每块s个记录，在等概率的情况下块内使用顺序查找那么平均查找长度为：$ASL=L_I+L_S=\frac{b+1}{2}+\frac{s+1}{2}$
②此时若$s=\sqrt{n}$,则平均查找长度取最小值：$\sqrt{n}+1$;若对索引表采用折半查找时，则平均查找长度为：$ASL=L_I+L_S=\left \lceil log_2(b+1)+\frac{s+1}{2} \right \rceil$
B树 & B+树
B树，又称多路平衡查找树,B树中所有节点的孩子节点数的最大值称为B数的阶，通常用m表示。一颗m阶的树或为空树，或为满足如下特性的树:
1、树中每个节点至多有m颗子树（即至多含有m-1个关键字）。
2、若根节点不是终端节点，则至少有两颗子树（至少一个关键字）。
3、除根节点外的所有非叶子节点至少有$\left \lceil m/2 \right \rceil$颗子树（即至少含有$\left \lceil m/2 \right \rceil-1$个关键字）。
4、所有的叶节点都出现在同一层次上，并且不带信息（实际这些节点并不存在，指向这些节点的指针为空）。
B树是所有节点的平衡因子均
等于0的多路查找树
B树的高度（磁盘存储次数）
首先应该明确B树的高度不包括最后的不带任何信息的叶子节点那一层。
如果$n\geq 1$，则对任意一颗包含n个关键字、高度为h、阶数为m的B树：
有一棵树的高度：$h\geq log_m(n+1)$
如果让每个节点中的关键字个数达到最少则高度为：$h\leq log_{\left \lceil m/2 \right \rceil}(((n+1)/2)+1)$
B树的大部分操作所需的磁盘存取次数与B树的高度成正比
散列(Hash)表
散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。
散列函数块内会把两个或两个以上的不同关键字映射到同一个地址，这种情况称“冲突”,这些发生碰撞的不同关键字称为“同义词”。
散列表 是根据关键字而直接进行访问的数据结构。
散列函数的构造遵循规则
1.均匀分布,少冲突
2.计算简单,查找快
1.直接地址法
散列函数： H(key)=a*key+b
特点: 计算简单，不会产生冲突，适合连续存储的情况，但如果关键字分布不连续，空位较多，将造成存储空间浪费。
2.除留余数法
散列函数：H(key)=key%p
特点：简单、常用，使用关键是选好p，尽量减少冲突3.数字分析法
设关键字是r进制数，而r个数码在各个位置上出现的频率不一定相同，在某些位上经常出现，则应选取数码分布较为均匀的若干位作为散列地址。
4.平方取中法
顾名思义，取关键字的平方值的中间几位作为散列地址:$10^{k-1} \leq n \leq 10^k $(其中n为集合中元素个数)
5.折叠法
将关键字分割成位数相同的几部分（最后一部分可以短一点），然后取这几部分的叠加作为散列地址。
处理冲突的方法
1.开地址法（闭散列法）
数学递推公式
$H_i=((H(key)+d_i)\%m)$
式中,$i=1,2,3,…,k(k \geq m-1 )$;m表示散列表表长；$d_i$为增量序列。
1） 线性探测法
不多说，冲突就往后挪，挪到有位置，停止
2） 平方探测法
当 $d_i = 1^2,-1^2,2^2,-2^2,…,k^2,-k^2,$其中$k \leq m/2 $，m必须是一个可以表示成4k+3的质数，又称二次探测法
3)再散列法
当 $d_i=Hash_2(Key)$, 如果第一个散列函数Hash(key)得到的地址发生冲突时，利用第二个散列函数计算该关键字的地址增量。再散列法经过m-1次探测会遍历表中的所有的位置，回到$H_0$位置。
4)伪随机序列法（简答题）
当$d_i$=伪随机序列，称为伪随机序列法。
注意在开放地址的情形下，不能随便物理删除所有元素，因为若删除元素将会截断其他具有相同散列地址元素的查找地址。所以若想删除一个元素时，给它做一个删除标记，进行逻辑删除。但副作用是，执行多次删除后，散列表表面上看起来很满，实际上有许多位置没用利用，因此需要定期维护散列表，要把删除标记的元素物理删除。
2.拉链法
假设散列地址为i的同义词链表的头指针存放在散列表的第i个单元中，因而查找、插入、删除都在同义词链中进行。
散列查找及性能分析
散列表的查找过程与构造散列表的过程基本一致。
装填因子：散列表的装填因子一般记为$\alpha$,定义为一个表的装满程度，即：
$\alpha =\frac{n}{m}$ 其中n为表中记录数，m为散列表长度。