菜鸟天堂

实现一个最简单的顺序查找算法，如下所示：
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个失败节点。