查找基本概念和顺序表查找

查找基本概念和顺序表查找

基本概念：
1、查找表：是由同一元素或记录构成的集合
2、关键字：数据元素中某个数据项的值
3、主关键字：唯一标识某个记录的关键字
4、次关键字：无法唯一标识某个记录的关键字
5、静态查找表：只做查找操作的查找表
6、动态查找表：对查找表进行插入或者删除操作

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

顺序查找算法一、

/*
 * 顺序查找，a 为数组， n为要查找的数组个数（长度）， key为要查找的关键字
 * 注意：a[0]号单元留空，所以循环的部分略有不同
 */
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;
}

顺序鼻查找优化算法：
由于每次循环都需要对i是否越界进行判断，判断其是否溢出数组。可以采用一个更好的办法，设置一个哨兵，可以解决这个问题，此时的a[0]就可以派上用场。

int Sequential_Search2(int * a , int n, int key)
{
	a[0] = key;  //设置a[0]为哨兵
	int i = n;    //循环从数组尾部开始
	while(a[i] != key)
		i--;
	return i;  // 返回0，则说明查找失败
}

适用于小型数组。