查找过程:从表的一端开始逐个进行记 录的关键字和给定值的比较。 例如 找64 01234567891011 64513192137566475808892 日日回 监视哨 比较次数: 比较次数=5 查找第n个元素: 查找第n-1个元素 查找第1个元素:n 查找第个元素:n+1-i 查找失败 n+1
i 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找64 64 监视哨 i i i i 比较次数： 比较次数=5 查找第n个元素： 1 查找第n-1个元素：2 ………. 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1 查找过程：从表的一端开始逐个进行记 录的关键字和给定值的比较。 例如：
算法描述: int Search Seq ssTable ST, Key Type kval)t ∥在顺序表ST中顺序查找其关键字等于 ∥key的数据元素。若找到,则函数值为 ∥该元素在表中的位置,否则为0 STelen01.key=kval;∥设置“哨兵” for(i=sTlength; STelem[i]. key!=kval; --1); ∥从后往前找 return ∥找不到时,i为0 }∥ Search seq
int Search_Seq(SSTable ST, KeyType kval) { // 在顺序表ST中顺序查找其关键字等于 // key的数据元素。若找到，则函数值为 // 该元素在表中的位置，否则为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 ∑ P C 其中:n为表长 为查找表中第个记录的概率∑P=1 C为找到该记录时,曾和给定值比较过的 关键字的个数
顺序查找性能分析 查找算法的平均查找长度(Average Search Length)： 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值。 n i ASL PiCi 其中: n 为表长 1 Pi 为查找表中第i个记录的概率 Ci为找到该记录时，曾和给定值比较过的 关键字的个数 1 1 n i Pi
对顺序表而言,C;=n-+1 ASL=nP1+(n-1)P2++2Pn-+P 在等概率查找的情况下 顺序表查找的平均查找长度为: +1 ASL n-i+1) SS
顺序表查找的平均查找长度为： 对顺序表而言，Ci = n-i+1 2 1 1 1 1 n (n i ) n ASL n i ss ASL = nP1 +(n-1)P2 + +2Pn-1+Pn n Pi 1 在等概率查找的情况下，
在不等概率查找的情况下,ASL在 P≥P,≥…≥P,≥P 时取极小值。表中记录按查找概率由小到 达重新排列,以提高查找效率。 若查找概率无法事先测定,则查找过 程采取的改进办法是,在每次查找之后, 将刚刚查找到的记录直接移至表尾的位置
在不等概率查找的情况下，ASLss在 Pn≥Pn-1≥···≥P2≥P1 时取极小值。表中记录按查找概率由小到 达重新排列,以提高查找效率。 若查找概率无法事先测定，则查找过 程采取的改进办法是，在每次查找之后， 将刚刚查找到的记录直接移至表尾的位置 上