一个简单的顺序查找

Posted on 2006-08-30 16:03 樱木 阅读(153) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构

实现一个最简单的顺序查找算法,如下所示:
template<class Record, class Key>
int sequential_search( Record *r, const int & size, const Key & k )
{
 for(int i=0; i<size; i++)
  if( r[i] == k )
   return i;
 return -1;
}
有几点需要注意的:
1)如果在数组的最低或最高单元加上一个哨兵元素(sentinel),则可以在每次迭代中少一个判断(i<size),因为总会遇到相同的节点。
2)在仅考虑搜索成功以及等概率搜索的前提下,顺序查找的的关键字比较次数为n*(n+1)/2。
3)常见搜索算法的时间复杂度是以关键字比较的次数来进行度量的。
4)与二分搜索不同,顺序搜索可以针对无序表进行。
5)顺序查找的搜索树是一颗单链树,有n+1个叶子节点,其中n个成功节点,1个失败节点。

只有注册用户登录后才能发表评论。