存儲結(jié)構(gòu)

查找表為線性表，其存儲結(jié)構(gòu)為一維結(jié)構(gòu)數(shù)組，也即是順序表，數(shù)組的每一個元素對應(yīng)查找表的一個記錄。為簡單起見，設(shè)記錄中只有一個整數(shù)關(guān)鍵字，存放記錄的結(jié)構(gòu)體類型描述如下：

	typedef struct
	{
	int key； /*存放關(guān)鍵字的成員項*/
	…… /*其它成員項*/
	} NODE；

順序查找

順序查找（Sequential Search）是一種最簡單的查找方法。現(xiàn)假設(shè)查找表中有n個記錄，順序存放在某個數(shù)組a中。順序查找的方法為：從順序表的一端開始，將給定值依次與數(shù)組中各個記錄的關(guān)鍵字進行比較，若在表中找到某個記錄的關(guān)鍵字與給定值相等，則查找成功，返回記錄所在位置的下標i；若在找完表中所有記錄后也未找到與給定值相等的關(guān)鍵字的記錄，則查找失敗，給出失敗信息。該算法適合順序表中記錄的關(guān)鍵字無序的情況。

順序查找的算法

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

/*在a[0]～a[n-1]中順序查找關(guān)鍵字等于k的記錄。查找成功時返回該記錄的下標，失敗時返回-1*/

{

int i=0;

while(i

i++;

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

return i;

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

}

在該算法中，while循環(huán)語句中包含兩個判斷條件，勢必會影響查找的速度，因此要盡可能地減少判斷條件以提高效率。這里介紹一個編程小技巧來達到這一目的。具體做法是：在順序表的末尾設(shè)置一個監(jiān)視哨a[n].key，開始查找之前，先將給定關(guān)鍵字的值k賦給a[n].key，這樣循環(huán)中就不用判斷整個表是否查找完畢。具體算法如下：

改進的順序查找算法

	int search(NODE a[],int n, int k)
	/*在a[0]～a[n-1]中順序查找關(guān)鍵字等于k的記錄。查找成功時返回該記錄的下標，失敗時返回-1*/
	{
	int i=0;
	a[n].key=k;
	while(a[i].key!=k)
	i++;
	if(i>=n)
	return -1; /*查找成功*/
	else
	return i; /*查找失敗*/
	}

順序查找的基本操作是關(guān)鍵字的比較。查找成功的最好情況是第一個記錄就符合查找要求，只需進行一次比較；最壞情況是第n個記錄符合查找要求，要進行n次比較。若每個記錄的查找概率相等，即pi=1/n，且每次都是成功查找，則順序查找的平均查找長度為：

對于算法8-2，查找不成功時關(guān)鍵字的比較次數(shù)為n＋1，順序查找的算法時間復(fù)雜度為O（n）。