|
知识路径: > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 查找 >
|
相关知识点:12个
|
|
|
|
从表中的一端开始,逐个进行记录的关键字和给定值的比较,若找到一个记录的关键字与给定值相等,则查找成功;若整个表中的记录均比较过,仍未找到关键字等于给定值的记录,则查找失败。
|
|
|
顺序查找的方法对于顺序存储和链式存储方式的查找表都适用。
|
|
|
从顺序查找的过程可见,Ci取决于所查记录在表中的位置。若需查找的记录正好是表中的第一个记录时,仅需比较一次;若查找成功时找到的是表中的最后一个记录,则需比较n次。一般情况下,Ci=n-i+1,因此在等概率情况下,顺序查找成功的平均查找长度为:
|
|
|
|
也就是说,成功查找的平均比较次数约为表长的一半。若所查记录不在表中,则至少进行n次比较才能确定失败。
|
|
|
与其他查找方法相比,顺序查找方法在n值较大时,其平均查找长度较大,查找效率较低。但这种方法也有优点,那就是算法简单且适应面广,对查找表的结构没有要求,无论记录是否按关键字有序排列均可应用。
|
|
|