存储结构

查找表为线性表，其存储结构为一维结构数组，也即是顺序表，数组的每一个元素对应查找表的一个记录。为简单起见，设记录中只有一个整数关键字，存放记录的结构体类型描述如下：

	typedef struct	{	int key； /*存放关键字的成员项*/	…… /*其它成员项*/	} NODE；

顺序查找（Sequential Search） 是一种最简单的查找方法。现假设查找表中有n个记录，顺序存放在某个数组a中。顺序查找的方法为：从顺序表的一端开始，将给定值依次与数组中各个记录的关键字进行比较，若在表中找到某个记录的关键字与给定值相等，则查找成功，返回记录所在位置的下标i；若在找完表中所有记录后也未找到与给定值相等的关键字的记录，则查找失败，给出失败信息。该算法适合顺序表中记录的关键字无序的情况。

顺序查找的算法

int search(NODE a[],int n, int k)

/*在a[0]～a[n-1]中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/

{

int i=0;

while(i

i++;

if(a[i].key = =k) /*查找成功*/

return i;

else return -1; /*查找失败*/

}

在该算法中，while循环语句中包含两个判断条件，势必会影响查找的速度，因此要尽可能地减少判断条件以提高效率。这里介绍一个编程小技巧来达到这一目的。具体做法是：在顺序表的末尾设置一个监视哨a[n].key，开始查找之前，先将给定关键字的值k赋给a[n].key，这样循环中就不用判断整个表是否查找完毕。具体算法如下：

改进的顺序查找算法

	int search(NODE a[],int n, int k)	/*在a[0]～a[n-1]中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/	{	int i=0;	a[n].key=k;	while(a[i].key!=k)	i++;	if(i>=n)	return -1; /*查找成功*/	else	return i; /*查找失败*/	}

顺序查找的基本操作是关键字的比较。查找成功的最好情况是第一个记录就符合查找要求，只需进行一次比较；最坏情况是第n个记录符合查找要求，要进行n次比较。若每个记录的查找概率相等，即pi=1/n，且每次都是成功查找，则顺序查找的平均查找长度为：

对于算法8-2，查找不成功时关键字的比较次数为n＋1，顺序查找的算法时间复杂度为O（n）。