顺序检索

    当我们对所检索序列中元素的分布一无所知或元素本身就是随机分布的时候，顺序检索是常用的方法。

    常用的返回值策略是，若用数组array，从下标0开始存储元素，检索成功则返回相应下标，失败则返回-1。另一种返回策略是：若从下标1开始存储元素，0号位置作为sentinel(哨兵)，返回0则表示检索失败。使用这种返回策略会减少循环条件的判断，提高效率。直接看代码

#include<iostream>
using namespace std;
class Elem
{
private:
	int key;
public:
	void setKey(int key)
	{
		this->key = key;
	}
	int getKey()
	{
		return key;
	}
};
int find(int *array, int n, int key)
{
	if (array && n > 1)
	{
		Elem* arr = new Elem[n+1];
		int i;
		for (int i = 0; i < n; i++)
			arr[i + 1].setKey(array[i]);
		//0号位置作为sentinel
		arr[0].setKey(key);
		i = n;
		//查找
		while (arr[i].getKey() != key)
			i--;
		return i;
	}
	return 0;
}
int main()
{
	cout << "------顺序检索---by David---" << endl; 
	int array[] = { 1, 2, 3, 4, 5, 6 };
	int n = sizeof(array) / sizeof(array[0]);
	cout << "原序列" << endl;
	int i;
	for ( i = 0; i < n; i++ )
		cout << array[i] << " ";
	cout << endl << endl; 
	//第一次查找 
	int key = 1;
	cout << "待查找的关键字是 " << key << endl;
	int index = find(array, n, key);
	if (index)
		cout << "查找到的位置是 " << index << endl;
	else
		cout << "查找失败！" << endl;
	cout << endl; 
	//第二次查找 
	key = -1;
	cout << "待查找的关键字是 " << key << endl;
	index = find(array, n, key);
	if (index)
		cout << "查找到的位置是 " << index << endl;
	else
		cout << "查找失败！" << endl;	
	system("pause");
	return 0;
}

小结

把0号位置作为哨兵，从后往前检索，可能代码并不简练，但思想值得借鉴。

专栏目录

• 数据结构与算法
• c指针