大话数据结构-8.3 顺序表查找 - 高飞网

8.3 顺序表查找

2016-12-29 18:30:58.0

  顺序查找(Sequential Search)又叫线性查找,是最基本的查找技术,它的查找过程:从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定的值相等,则查找成功,找到所查找的记录;如果直到最后一个(或第一个)记录,其关键字和给定值比较都不等时,则表中没有所查的记录,查找不成功。

8.3.1 顺序查找算法

/* 顺序查找,a为数组,n为要查找的数组个数,key为要查找的关键字 */
int Sequential_Search(int *a,int n,int key)
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(a[i]==key)
		{
			return i;
		}
	}
	return 0;
}

8.3.2 顺序表查找优化

    上面的查找算法,每次循环都要判断是否越界,即i<=n,事实上,可以通过设计哨兵,来去掉这个判断。

/* 有哨兵的顺序查找 */
int Sequential_Search(int *a,int n,int key)
{
	int i = n;/* 循环从数组尾部开始 */
	a[0] = key;/*设置a[0]为关键字值,称之为"哨兵"*/
	while(a[i]!=key)
	{
		i--;
	}
	return i;
}

    这种在查找方向的尽头设置“哨兵”免去了查找过程中每次比较后都要判断查找位置是否越界的小技巧,在总数据较多时,效率提高很大。
    该算法的时间复杂度为O(n),缺陷在于当n很大小,效率低下。