STele 642137881992056456807513 01234567891011 key=64 ST Length STelem 602137881992056456807513 01234567891011 key=60 ST Length
21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length ST.elem i 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length ST.elemi 60 i key=64 key=60 i 64
int Search Seq(ssTable St, KeyT y pe key ∥在顺序表ST中顺序查找其关键字等于 ∥key的数据元素。若找到,则函数值为 ∥该元素在表中的位置,否则为0。 STele0]key=key;∥“哨兵” for (i=STlength; ST elem[i].key: =key; ∥后往前找 return 1 ∥找不到时,i0 3// Search Sec
int Search_Seq(SSTable ST, KeyType key) { // 在顺序表ST中顺序查找其关键字等于 // key的数据元素。若找到，则函数值为 // 该元素在表中的位置，否则为0。 ST.elem[0].key = key; // “哨兵” for (i=ST.length; ST.elem[i].key!=key; --i); // 从后往前找 return i; // 找不到时，i为0 } // Search_Seq
分析顺序查找的时间性能 定义:查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置,需和给定值 进行比较的关键字个数的期望值 ASL=>PC 其中:n为表长,P为查找表中第个记录的概率, 且∑P=1,C为找到该记录时,曾和给定 值比较过的关键字的个数
定义： 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 ， Ci为找到该记录时，曾和给定 值比较过的关键字的个数。 分析顺序查找的时间性能 = = n i ASL Pi Ci 1 1 1 = = n i Pi
对顺序表而言,C=n计+1 ASL=nP,+(n-1P2++2Pn+P 在等概率查找的情况下,P= 顺序表查找的平均查找长度为 n+ ASL Ss ∑(mn-i+1)
在等概率查找的情况下， 顺序表查找的平均查找长度为： 对顺序表而言，Ci = n-i+1 n Pi 1 = 2 1 1 1 1 + = − + = = n (n i ) n ASL n i s s ASL = nP1 +(n-1)P2 + +2Pn-1+Pn
在不等概率查找的情况下,ASL~在 Pn≥Pn12≥P2≥P1 时取极小值 若査找概率无法事先测定,则查找 过程采取的改进办法是,在每次查找之 后,将刚刚查找到的记录直接移至表尾 的位置上
若查找概率无法事先测定，则查找 过程采取的改进办法是，在每次查找之 后，将刚刚查找到的记录直接移至表尾 的位置上。 在不等概率查找的情况下，ASLss 在 Pn≥Pn-1≥···≥P2≥P1 时取极小值