第九章查找表9.1静态查找表9.2动态查找表9.3哈希表及其香找中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 1 中国科学技术大学 第九章 查找表 • 9.1静态查找表 • 9.2动态查找表 • 9.3哈希表及其查找
查找表：一由同一类元素或记录构成的集合。对数据元素间的关系未作限定。对查找表的操作有一查找某个“特定”白的元素是否在表中。一查找某个“特点”的元素的各种属性。一在查找表中插入一个元素。一在查找表中删除一个元素静态查找表、动态查找表关键字数据元素中的某个数据项值。可以表示一个数据元素，如可以唯一一表示，则为主关键字（primarykey）。查找根据给定的某个值，在查找表中确定一个关键字等于给定值的数据元素。若找到表示查找成功，返回该元素详细信息或在查找表中的位置：否则返回NULL2中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 2 中国科学技术大学 • 查找表： – 由同一类元素或记录构成的集合。对数据元素间的关系未作限定。 • 对查找表的操作有 – 查找某个“特定”的元素是否在表中。 – 查找某个“特点”的元素的各种属性。 – 在查找表中插入一个元素。 – 在查找表中删除一个元素 • 静态查找表、动态查找表 • 关键字 – 数据元素中的某个数据项值。可以表示一个数据元素，如可以唯一 表示，则为主关键字（primary key）。 • 查找 – 根据给定的某个值，在查找表中确定一个关键字等于给定值的数据 元素。若找到表示查找成功，返回该元素详细信息或在查找表中的 位置；否则返回NULL
9.1静态查找表9.1.1顺序查找typdef struct:ElemType*elem,//元素存储空间，0单元保留intlength;//表长度↓SSTable;查找成功和失败平均查找长度一查找过程中先后和给定值进行比较的关键字的个数的期望值ASL=ZP,C ZP,=1 i=1,2,...C,= n - i+ 1 P,=1/nASLss = 1/nZ (n - i+ 1 ) =(n+1)/23中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 3 中国科学技术大学 9.1静态查找表 9.1.1顺序查找 typdef struct{ ElemType *elem; //元素存储空间，0单元保留 int length; //表长度 }SSTable; • 查找成功和失败 • 平均查找长度 – 查找过程中先后和给定值进行比较的关键字的个数 的期望值 ASL＝∑PiCi ∑Pi＝1 i＝1，2，.n Ci＝n－i＋1 Pi＝1/n ASLss＝1/n∑（n－i＋1）=(n+1)/2
9.1.2折半查找折半查找（binarySearch）：二分查找·例8.2利用二分查找在顺序有序表中查找。- 算法8.2 Int Search Bin(SStable ST,KeyType kval)- ASLbs = （n + 1) /nlog(n+1)-1中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 4 中国科学技术大学 9.1.2折半查找 • 折半查找（binary Search）：二分查找。 • 例8.2 利用二分查找在顺序有序表中查找。 – 算法8.2 Int Search_Bin(SStable ST,KeyType kval) –ASLbs＝（n＋1）/nlog(n+1)-1
S丫二分查找平均查找长度（假设满二叉树）ASLhs= (n+1)/nlog(n+1)-1ASLbs=(20+21*2+...+2h-1*h)Pi= 1 Zti * 2i-1 (n=2h-1)2i=t+1令: S=Zhi* 2i-1=2hi* 2i-2-2 Zh-1(t + 1)2t-1=22-1 t * 2t-1+2h-1 2t-1=2(2ht * 2t-1 - h * 2h-1)+Zh-1 2t=2(S - h * 2h-1) + 2h - 1所以: S =h * 2h - 2h + 1 =(n + 1)log2(n+ 1) -nb==s = n+1log2(n+ 1) -1EASLh5vpb@ustc.edu.cn中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 二分查找平均查找长度（假设满二叉树） ASLbs＝（n＋1）/nlog(n+1)-1 ASLbs=(2 0+2 1*2+.+2 h-1*h)Pi=