1．顺序查找法以及平均查找长度(ASL)的计算；
顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。
下面以顺序存储为例实现顺序查找:
typedef struct {
ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，0 号单元留空
int length; // 表的长度
} SSTable;
int Search_Seq(SSTable ST, KeyType key) {
ST.elem[0].key = key;// 设置“哨兵”
for (i=ST.length; ST.elem[i].key!=key; --i);// 从后往前找
return i;// 找不到时，i 为 0
}
就顺序查找法而言，对于 n 个数据元素的表，给定值 key 与表中第 i 个元素关键码相等，即定位第 i 个记录时，需进行 n-i+1 次关键码比较，即 Ci=n-i+1。则查找成功时，顺序查找的
平均查找长度为:
设每个数据元素的查找概率相等，即 Pi= 1/n ，则等概率情况下有
查找不成功时，关键码的比较次数总是 n+1 次。
算法中的基本工作就是关键码的比较，因此，查找长度的量级就是查找算法的时间复杂度，其为 O(n)。
顺序查找缺点是当 n 很大时，平均查找长度较大，效率低;优点是对表中数据元素的存储没有要求，顺序存储或是链式存储均可。另外，对于线性链表，只能进行顺序查找
2．折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的“判定树”的构造；
折半查找法以及平均查找长度(ASL)的计算
折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序(升序或降序)排列，也就是说折半查找只适用于对有序顺序表进行查找。折半查找的基本思想是:首先以整个查找表作为查找范围，取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成功;若给定值小于中间元素的关键码，则在中间元素的左半区继续查找;若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。
int Search_Bin ( SSTable ST, KeyType key) {
low = 1; high = ST.length; // 置区间初值
while (low <= high) {
mid = (low + high) / 2;
if(key == ST.elem[mid].key ) return mid; // 找到待查元素
else if (key < ST.elem[mid].key) )
high = mid - 1;// 继续在前半区间进行查找
else low = mid + 1;// 继续在后半区间进行查找
}
return 0;// 顺序表中不存在待查元素
}
从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续这种操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树为判定树。可以看到，查找表中任一元素的过程，即是判定树中从根到该元素结点路径上各结点关键码的比较次数，也即该元素结点在树中的层次数。对于 n 个结点的判定树，树高为 k，则有
因此，折半查找在查找成功时，所进行的关键码比较次数至多为 log2(n+1) 。 。
接下来讨论折半查找的平均查找长度。为便于讨论，以树高为k的满二叉树(n=2k-1)为例。假设表中每个元素的查找是等概率的，即 Pi=1─n ，则树的第 i 层有 2i-1 个结点，因此，折半查找的平均查找长度为:
所以，折半查找的时间效率为 O(log2n)。
查找过程对应的“判定树”的构造
如何构造二叉判定树？
3．散列(Hash)表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。
散列(Hash)表的构造
散列函数的构造
对数字的关键字可有下列散列函数的构造方法，若是非数字关键字，则需先对其进行数字化处理。
1. 直接定址法
H(key) = key 或者 H(key) = a ✖️ key + b
即取关键码的某个线性函数值为散列地址，这类函数是一一对应函数，不会产生冲突。
此法仅适合于:地址集合的大小 = = 关键字集合的大小
2. 数字分析法
假设关键字集合中的每个关键字都是由 s 位数字组成(k1, k2, ..., kn)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。
此法仅适合于:能预先估计出全体关键字的每一位上各种数字出现的频度。
3.平方取中法
若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过“平方”扩大差别，同时平方值的中间几位受到整个关键字中各位的影响。
此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。
4. 折叠法
若关键字的位数特别多，则可将其分割成几部分，然后取它们的叠加和为散列地址。可有:移位叠加和间界叠加两种处理方法。
(1)移位法:将各部分的最后一位对齐相加。
(2)间界叠加法:从一端向另一端沿各部分分界来回折叠后，最后一位对齐相加。
此方法适合于:关键字的数字位数特别多。
5. 除留余数法
H(key) = key MOD p p≤m (表长)
即取关键码除以 p 的余数作为散列地址。使用除留余数法，选取合适的 p 很重要，若散列表表长为 m，则要求 p≤m，且接近 m 或等于 m。p 一般选取质数，也可以是不包含小于 20质因子的合数。
6. 随机数法
H(key) = Random(key)，其中，Random 为伪随机函数。
通常，此方法用于对长度不等的关键字构造散列函数。
实际造表时，采用何种构造散列函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。
散列冲突的基本概念
处理散列冲突的基本方法
处理冲突的实际含义是:为产生冲突的地址寻找下一个散列地址。
1. 开放定址法
所谓开放定址法，即是由关键码得到的散列地址一旦产生了冲突，也就是说，该地址已经存放了数据元素，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。
找空散列地址方法很多，下面介绍三种:
(1)线性探测法
Hi=(Hash(key)+di) mod m ( 1≤i < m ) 其中: Hash(key)为散列函数，m 为散列表长度，di 为增量序列 1，2，......，m-1，且di=i。
这种方法的特点是:冲突发生时，顺序查看表中下一单元， 直到找出一个空单元或查遍全表。
线性探测法可能使第i 个散列地址的同义词存入第 i+1 个散列地址，这样本应存入第 i+1个散列地址的元素变成了第 i+2 个散列地址的同义词，......，因此，可能出现很多元素在相邻的散列地址上“堆积”起来，大大降低了查找效率。为此，可采用二次探测法改善“堆积”问题。
(2)二次探测法Hi=(Hash(key)±di) mod m
其中:Hash(key)为散列函数，m 为散列表长度，m 要求是某个 4k+3 的质数(k 是整数)，di 为增量序列 12，-1222，-22，......，q2，-q2 且 q≤ 12 m。
这种方法的特点是:冲突发生时，在表的左右进行跳跃式探测，比较灵活。
(3)随机探测再散列
di 是一组伪随机数列，具体实现时，应建立一个伪随机数发生器，(如 i=(i+p) % m)， 并给定一个随机数做起点。
2. 拉链法
这种方法的基本思想是将所有散列地址为i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在散列表的第 i 个单元中， 因而查找、插入和删除主要在同义词链中进行。 链地址法适用于经常进行插入和删除的情况。
散列表的查找
查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为:
对于给定值 K, 计算散列地址 i = H(K)，
若r[i] = NULL ，则查找不成功
若r[i].key = K ，则查找成功
否则求下一地址 Hi，直至 r[Hi] = NULL(查找不成功)
或 r[Hi].key = K(查找成功)为止。
散列表平均查找长度的计算
散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。
在介绍的处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。
影响产生冲突多少有以下三个因素:散列函数是否均匀;处理冲突的方法;散列表的装填因子。
分析这三个因素，尽管散列函数的“好坏”直接影响冲突产生的频度，但一般情况下，我们总认为所选的散列函数是“均匀的”，因此，可不考虑散列函数对平均查找长度的影响。就线性探测法和二次探测法处理冲突的例子看，相同的关键码集合、同样的散列函数，但在数据元素查找等概率情况下，它们的平均查找长度却不同。
α 是散列表装满程度的标志因子。由于表长是定值，α 与“填入表中的元素个数”成正比，所以，α 越大，填入表中的元素较多，产生冲突的可能性就越大;α 越小，填入表中的元素较少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是装填因子 α 的函数，只是不同处理冲突的方法有不同的函数。
散列方法存取速度快，也较节省空间，但由于存取是随机的，因此，不便于顺序查找。
网友评论