@算法81 int Search Seq (ssTable st, KeyType kval) ∥在顺序表ST中顺序查找其关键字等于kva的 数据元素。 数据结 ∥若找到,则函数值为该元素在表中的位置 否则为0。 STelem[o key = kval; ∥设置"哨兵 for(i-sTlength; ST. ikey !=kval; -i) ∥从后往前查找 return i: ∥找不到时,i为0 }∥ Search Seq 计算机教研宦 第11页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第11页 算法8.1 int Search_Seq (SSTable ST, KeyType kval) { // 在顺序表ST中顺序查找其关键字等于kval的 数据元素。 // 若找到，则函数值为该元素在表中的位置， 否则为0。 ST.elem[0].key = kval; // 设置"哨兵" for (i=ST.length; ST.elem[i].key != kval; --i); // 从后往前查找 return i; // 找不到时，i为0 } // Search_Seq
@分析顺序查找的时间性能 ·定义:查找算法的平均查找长度( Average Search Length) 为确定记录在查找表中的位置,需和给定值进行比较的 关键字个数的期望值 数据结 ASL=∑PC 其中:m为表长,P为查找表中第个记录的概率,且∑P=1 C为找到该记录时,曾和给定值比较过的关键字的个数 计算机教研宦 第12页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第12页 分析顺序查找的时间性能 • 定义： 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值进行比较的 关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率，且 ， Ci为找到该记录时，曾和给定值比较过的关键字的个数。 = = n i ASL Pi Ci 1 1 1 = = n i Pi
对顺序表而言,C=m-i+l ASL=nP+(-DP2+……+2Pmn+Pn 在等概率查找的情况下 顺序表查找的平均查找长度为 ASL I ∑mn-i+1 n 计算机教研宦 第13页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第13页 对顺序表而言，Ci = n-i+1 ASL = nP1 +(n-1)P2 +…… +2Pn-1+Pn 在等概率查找的情况下， n Pi 1 = 顺序表查找的平均查找长度为： 2 1 1 1 1 + = − + = = n (n i ) n ASL n i s s
@8.12折半查找(二分查找) 若以有序表表示静态查找表,则查找过程可以基于“折 半”进行。 查找过程:每次将待查记录所在区间缩小一半 算法实现 数据结 设表长为n,bow、high和mid分别指向待查元素所在 区间的上界、下界和中点k为给定值 初始时,令low=1,high=n,mid(ow+high)2」 让k与mid指向的记录比较 若k= rmid. key,查找成功 若k<r|mid]key, 则则 high=mid-1 若k> tImid. key, low=mid+1 重复上述操作,直至w>high时,查找失败 计算机教研宦 第14页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第14页 8.1.2 折半查找（二分查找） • 若以有序表表示静态查找表，则查找过程可以基于“折 半”进行。 • 查找过程：每次将待查记录所在区间缩小一半 • 算法实现 – 设表长为n，low、high和mid分别指向待查元素所在 区间的上界、下界和中点,k为给定值 – 初始时，令low=1,high=n,mid=(low+high)/2 – 让k与mid指向的记录比较 • 若k==r[mid].key，查找成功 • 若k<r[mid].key，则high=mid-1 • 若k>r[mid].key，则low=mid+1 – 重复上述操作，直至low>high时，查找失败
例如:key=64的查找过程如下 STength STele 0513192137566475808892 01234567891011 low high low指示查找区间的下界 high指示查找区间的上界 mid =(low+high)/2
05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elem ST.length 例如: key=64 的查找过程如下： low high mid low mid high mid low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2