Process of search compare the keyword of record with the giving value one by one from the beginning of table For example 找 64 1234567891011 64513192137566475808892 监视哨 比较次数 比较次数=5 查找第n个元素:1 查找第n-1个元素:2 查找第1个元素 查找第个元素:n+1i 查找失败: 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 Process of search：compare the keyword of record with the giving value one by one from the beginning of table. For example：
Description of the algorithm int Search Seq ssTable ST, KeyType kval)t ∥/在顺序表ST中顺序查找其关键字等于 ∥/key的数据元素。若找到,则函数值为 ∥/该元素在表中的位置,否则为0。 STele[o]key=kval;∥/设置“哨兵 for i=ST length; STelem[]. keyl=kval; --iB ∥/从后往前找 return I; ∥/找不到时,为0 1// 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 Description of the algorithm：
Implementation in C int Search Seq(sstable st, Key Type key) {∥/在顺序表ST中顺序查找其关键字等于key 的数据元素。若找到,则函数值为 ∥/该元素在表中的位置,否则为0。算法9.1 STele[0]key=key;∥哨兵 for(i-ST length; !EQ(STelem[i key, key); --1 ∥从后往前找 return 1;∥/找不到时,i为0
Implementation in C int Search_Seq(SSTable ST,KeyType key) • { // 在顺序表ST中顺序查找其关键字等于key 的数据元素。若找到，则函数值为 • // 该元素在表中的位置，否则为0。算法9.1 • int i; • ST.elem[0].key=key; // 哨兵 • for(i=ST.length;!EQ(ST.elem[i].key,key);--i); • // 从后往前找 • return i; // 找不到时，i为0 • }
performance analysis of the sequential search Average Search Length To ascertain the position of record in the table, and the expect number of keyword comparing with the giving value ASL ∑ n :table leng i=1 P: is the probability of the ith record in the table ∑P C; is the comparing number of keyword
performance analysis of the sequential search Average Search Length： To ascertain the position of record in the table, and the expect number of keyword comparing with the giving value = = n i ASL Pi Ci 1 n :table length Pi is the probability of the ith record in the table Ci is the comparing number of keyword 1 1 = = n i Pi
In terms of sequential lists, Ci=n-i+1 ASL=nP1+(n-1)P2++2Pn-1+P In the case of search at the same probability the asl of the sequential search is n+1 ASL 1n-i+ SS 1 2
the ASL of the sequential search is： In terms of sequential lists，Ci = n-i+1 2 1 1 1 1 + = − + = = n (n i ) n ASL n i s s ASL = nP1 +(n-1)P2 + +2Pn-1+Pn n Pi 1 = In the case of search at the same probability