采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为多少
(1+n)/2
(1+2+3+...+n)/n = (1+n)/2
对于任意一个序列以及一个给定的元素,将给定元素与序列中元素依次比较,直到找出与给定关键字相同的元素,或者将序列中的元素与其都比较完为止。
顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L 1≤i≤n 其中,L是元素占用存储单元的长度。
扩展资料:
删除L的第i个数据元素,并用e返回其值。
Status ListDelete(SqList &L,int i,ElemType &e) // 算法2.5
{ // 初始条件:顺序线性表L已存在,1≤i≤ListLength(L)
// 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1
ElemType *p,*q;
if(i<1||i>L.length) // i值不合法
return ERROR;
p=L.elem+i-1; // p为被删除元素的位置
e=*p; // 被删除元素的值赋给e
q=L.elem+L.length-1; // 表尾元素的位置
for(++p;p<=q;++p) // 被删除元素之后的元素左移
*(p-1)=*p;
L.length--; // 表长减1
return OK;
}
(1+2+3+...+n)/n = (1+n)/2
所以答案为(1+n)/2
失败的平局查找次数:(0+1+2+...+n-1)/n=(n-1)/2