“ 查找--比较淡然的一章。”
主要知识点
查找表的检索机制
平均查找长度
折半查找表
二叉排序树
哈希表
1 查找表的检索机制
本章给出了三种类型的查找表，
第一类是线性索引，记录关键字一般按序排列，以提高检索速度。对应检索采用基于比较检索方法。
第二类是树形检索，树形的典型结构是二叉排序树，其检索的时间复杂度与树的深度同级为对数函数，其对应的检索方法是基于树表式的检索，即将带查找的表组织成树，在树形结构上实现查找。
第三类是哈希结构，根据数据的”关键值”计算数据的存储地址，哈希表既是建立表，也是查找表的方法，其对应的检索方式是”计算式”的检索。
2 平均查找长度
为决定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。
计算平均查找长度的基本公式
对于长度为n的列表，查找成功时的平均查找长度为：
ASL=P1C1 + P2C2 +……+PnCn =∑ pici
其中pi为查找列表中第i个数据元素的概率。Ci找到列表中第i二个数据元素时，已经进行过的关键字比较次数。
计算方法：
采用公式法计算（通用），也可采用手工计算方法（具体）。针对实际的具体问题计算相应的查找成功时的平均差查找长度。
3 折半查找表
折半查找法要求查找表按照顺序存储结构且按关键字有序排列。
折半查找过程中借助于折半判定树加以描述。判定树中每一结点对应表中一个记录在表中的位置序号。
折半查找算法的性能：在等概率时查找成功的平均查找长度与折半判定树的深度相关：
折半查找算法查找速度快，平均性能好，插入删除比较困难。
4 二叉排序树
二叉排序树的定义。
二叉排序树的性质：中序遍历一个二叉排序树，可以得到一个递增有序序列。
含有n个节点的二叉排序树形态不唯一，其构造与数列的的输入顺序有关。
查找过程与折半查找过程类似，在二叉排序树中查找一个记录时，其比较次数不超过树的深度。就平均性能而言，二叉排序树上的查找和折半查找相差不大。平均查找长度依然是
二叉排序树的插入，删除操作无需移动大量结点，经常变化的动态表也采用二叉排序树结构。
5 哈希表
基本思想：以元素的关键字k为自变量，通过哈希函数h，计算其存储位置p=H（k），从而实现按照关键字计算的方式建立表与查找表。哈希表的查找过程与还是表的创建过程对应一致。
哈希法主要包括1）哈希函数的构造，2)处理冲突的方法，
构造哈希函数，常用的方法有除留余数法。
处理冲突的基本方法包括性探测再散列，二次探测再散列，链地址法等。
哈希表中影响关键字比较次数的因素有三个：哈希函数，处理冲突的方法以及哈希表的装填因子。
哈希表的平均查找长度是装填因子的函数。
【例题1】1000个记录设计哈希表.假设哈希函数是均匀的，解决冲突用线性探测再散列法，并要求在等概率的情况下查找成功时的平均查找长度不超过3，查找不成功时的平均查找长度不超过13，则哈希表长度应取多大？
解：本题要求应用公式计算平均查找长度。
已知哈希函数是均匀的，且解决冲突用线性探测再散列法时，在等概率的情况下查找成功和查找不成功时的平均查找长度为
依题意有：
解的a<=0.8.取a=0.8，由于0.8=1000/m，所以m=1250
【例题2】对以下关键字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT),哈希函数为H(K)=(K中第一个字母在字母表中的序号）MOD 7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并计算出在等概率情况下，查找成功的平均查找长度和不成功的平均查找长。
解：此题主要要求掌握手工计算平均查找长度的方法，
装填因子为0.7，根据公式，装填因子 = 元素个数/表长，知哈希表长度为=7/0.7=10.
各关键字第一个字母的序号分别为19(S)，13(M)，20(T),23(W），6（F）。
建立哈希表, 成功的平均查找长度, 不成功的平均查找长度
计算各关键字的哈希地址
H(SUN)=19mod7=5;
H(MON)=13mod7=6;H(TUE)=19mod7=6;
H1(TUE)=(6+1)mod10=7;
H(WED)=23mod7=2;
H(THU)=20mod7=6 (与MON冲突)
H1(THU)=(6+1)mod10=7; (与TUE冲突)
H2(THU)=(6+2)mod10=8;
H(FRI)=6mod7=6; (与MON冲突)
H1(FRI)=(6+1)mod10=7; (与TUE冲突)
H2(FRI)=(6+2)mod10=8; (与TUE冲突)
H3(FRI)=(6+3)mod10=9;
H(SAT)=19mod7=5; (与SUN冲突)
H1(SAT)=(5+1)mod10=6; (与MON冲突)
H2(SAT)=(5+2)mod10=7; (与TUE冲突)
H3(SAT)=(5+3)mod10=8; (与THU冲突)
H4(SAT)=(5+4)mod10=9; (与FRI冲突)
H5(SAT)=(5+15)mod10=0;
由上可得构造哈希表：
0123456789SAT WED SUNMONTUETHUFRI6 1 11234按查找成功的平均查找长度：
对于SUN,查找时所需的比较次数为1
对于MON,查找时所需的比较次数为1
对于TUE,查找时所需的比较次数为2
对于WED,查找时所需的比较次数为1
对于THU,查找时所需的比较次数为3
对于FRI,查找时所需的比较次数为4
对于SAT,查找时所需的比较次数为6
根据等概率下查找成功的平均查找长度计算公式可得
计算查找不成功的平均查找长度：
哈希函数值为0时，查找不成功时的比较次数为2
哈希函数值为1时，查找不成功时的比较次数为1
哈希函数值为2时，查找不成功时的比较次数为2
哈希函数值为3时，查找不成功时的比较次数为1
哈希函数值为4时，查找不成功时的比较次数为1
哈希函数值为5时，查找不成功时的比较次数为7
哈希函数值为6时，查找不成功时的比较次数为6
由等概率下查找不成功的平均查找长度计算公式得:
【例题3】已知某哈希表的装填因子小于1，哈希函数H(key)为关键字(标识符）的第一个字母在字母表当中的序号，处理冲突的方法为线性探测开放定址法。
一， 编写按第一个字母的顺序输出哈希表中所有关键字的算法。
二，编写模拟手工计算等的概率情况下查找不成功的平均查找长度算法。
实现步骤：
1 对字母序号为i，可先从该字母序号位置开始判断该处所存的关键词是否为i；
2 如果相同，则表示该关键词为与序号i对应的关键字，输出该值；
3 若不同，则表示该关键词并非为字母序号i对应的关键字，不输出；
4 按线性探测开放定址法继续判断下一个关键词，直到值为空；
5 字母序号从1到26，持续上述步骤，则可得 个按字母序号输出的所有关键字序列。
void printword(HsahTable ht) { int i,j; for(i=1;i<=26;i++)// 字母序号从1-》26输出所有关键字序列 { j=1;// 从字母序号为i的位置开始判断 while(ht[j].key !=NULLKEY) { if(hash(ht[j].key == i)// 若该关键字的哈希地址为i，则输出该关键字 printf("%s\n",ht[j].key); j=(j+1)%m;// 按线性探测处理冲突 } } }
