一 学习小结
本章学习查找，查找表是由同一类型的数据元素（或记录）构成的集合，根据关键字在查找表中查找得到该关键字表示的记录的信息
1. 动态查找：在查找的同时对表做出修改（如插入删除），否则为静态查找
2. ASL平均查找长度
3. 线性表的查找
①顺序查找 ASL=（n+1）/2
传统方法
int Search_Seq(SSTable ST,KeyType key) //在顺序表ST中顺序查找关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0{ for(i=ST.length;i>=1;--i) if(ST.R[i].key==key) return i; //从后往前找 return 0;} 缺点：每次都要判断整个表是否检查完毕（判断i>=1）
优化——
int Search_Seq(SSTable ST,KeyType key) //在顺序表ST中顺序查找关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0{ ST.R[0].key=key; //哨兵 for(i=ST.length;ST.R.[i]!=key;--i)//从后往前找 return i;} 若找到此时 i ∈[ 1, n ]
找不到 i = 0
②折半查找 ASL=log2(n)
前提：顺序存储，表中关键字有序排序
int Search_Bin(SSTable ST,KeyType key) //在顺序表ST中顺序查找关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0{ low=1;high=ST.length; //置查找区间初值 while(low<=high) { mid=(low+high)/2; if(key==ST.R[mid].key) return mid; //找到待查找元素 else if(key 在实际应用中，查找不到，若需要插入该记录，则 return low; 然后在最终的low之前插入（此时low>high）
4. 树表的查找
二叉排序树 递归查找 创建 插入 删除
平衡二叉树：左子树和右子树的深度之差的绝对值不超过1； 左子树和右子树也是平衡二叉树；
5. 散列表的查找
在记录的存储位置p和其关键字key之间建立一个确定的对应关系H，使p=H(key) H为散列函数
构造散列函数
原则：每个关键字只能有一个散列地址与之对应； 函数的值域需要在表长的范围内，计算出的散列地址分布均匀，尽可能减少冲突
方法：
①数字分析法——必须明确知道所有关键字每一位上的各种数字的分布情况。实际应用：同意出版社的图书，ISBN前几位相同，用数字分析法时，排除ISBN的前几位
②平方取中法——适用于 不了解关键字的所有情况，或难于直接从关键字中找到取值比较分散的几位 的情况
③折叠法——散列地址位数较少，关键字位数较多，且难于直接从关键字中找到取值比较分散的几位
④除留取余法——H(key) = key%p p一般取小于表长的最大质数
实际应用过程中，冲突很难完全避免处理冲突的方法：
① 开放地址法 Hi=(H(key)+di)%m
Ⅰ 线性探测法 di=1,2,3，……，m-1
Ⅱ 二次探测法 di=1²，-1²，2²，-2²，3²，……，+k²，-k² （k<=m/2）
Ⅲ 伪随机探测法 注意将造表时的随机序列记录，用于查表
② 链地址法
把具有相同散列地址的记录放在同一个单链表中，m个散列地址就有m个单链表，同时用HT[0…m-1]存放链表的头指针，凡是散列地址为i的记录都以结点方式插入到以HT[i]为头节点的单链表中
二 上次的目标及接下来的目标
上次希望合理分配时间保证上机实践，这次更好的协调了两边的时间
因为临近期末，接下来希望尽量在截止日期前把PTA上的自测题联系到，而不是只限于作业题，还有就是再不复习就来不及啦！！！