教育部—微软精品课程建设项目 int location( SqList L, Elem Type& e, Status(*compare)(Elem Type, Elem Type )t k=1 p=Lelem while( k<=length & compare)(p++e))k++; if (k=Llength) return k else return o 3//location 京航空航天大学数据结构题组版权所有
int location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType)) { k = 1; p = L.elem; while ( k<=L.length && !(*compare)(*p++,e))) k++; if ( k<= L.length) return k; else return 0; } //location
教育部—微软精品课程建设项目 STele 642137881992056456807513 01234567891011 key=64 ST Length STelem 602137881992056456807513 01234567891011 key=60 STLengt 京航空航天大学数据结构题组版权所有
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.elem i 60 i key=64 key=60 i 64
教育部—微软精品课程建设项目 int Search Seq(ssTable ST, Key Type key& ∥在顺序表ST中顺序查找其关键字等于 ∥key的数据元素。若找到,则函数值为 ∥该元素在表中的位置,否则为0。 STelem[O]key=key;∥“哨兵” for (iSTlength; ST elem[i].key!=key, --i) ∥从后往前找 return 1 ∥找不到时,i为0 3// Search Seq 京航空航天大学数据结构题组版权所有
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 为确定记录在查找表中的位置,需和给定值 进行比较的关键字个数的期望值 n ASL=>PC 其中:n为表长,P为查找表中第个记录的概率, 且∑P=1,C为找到该记录时,曾和绘定 值比较过的关键字的个数 南京航空航天大学数握结构裸题组版权所有
定义： 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 ， Ci为找到该记录时，曾和给定 值比较过的关键字的个数。 分析顺序查找的时间性能 n i A PiCi SL 1 1 1 n i Pi
教育部—微软精品课程建设项目 对顺序表而言,C1=n-计+1 ASL=nP/+(n-1)P2++2Pn-+P 在等概率查找的情况下,P 顶序表查找的平均查找长度为 n+1 ASL SS m-i+1)= 京航空航天大学数据结构题组版权所有
在等概率查找的情况下， 顺序表查找的平均查找长度为： 对顺序表而言，Ci = n-i+1 n Pi 1 2 1 1 1 1 n (n i ) n ASL n i ss ASL = nP1 +(n-1)P2 + +2Pn-1+Pn