数据结构学习笔记（C++）：查找--顺序查找与折半（二分）查找小结

数据结构学习笔记（C++）：查找--顺序查找与折半（二分）查找小结  一、顺序查找法：         1、哨兵型         2、非哨兵型 二、折半（二分）查找法         1、递归型         2、非递归型

=================================================================》》》

 一、顺序查找法：

（1）哨兵型

int Search::sequentialSearch2(char key)
{
	int i = listLength_A;
	Alphabet[0] = key;//将哨兵设置在此处，防止数组发生越界
	while (Alphabet[i] != key)
	{
		i--;
	}
	return i;
}

（2）非哨兵型

int Search::sequentialSearch1(char key)
{
	for (int i = listLength_A; i >= 0; i--)
	{
		if (key == Alphabet[i]) return i;
	}
	return 0;
}

二、折半（二分）查找法

（1）递归型

int Search::binarySearch2(int low, int high, int key)
{
	if (low > high) return 0;
	else {
		int mid = (low + high) / 2;
		if (key < Digital[mid]) binarySearch2(low, mid - 1, key);
		else if (key > Digital[mid]) binarySearch2(mid + 1, high, key);
		else return mid;
	}
}

（2）非递归型

nt Search::binarySearch1(int key)//非递归
{
	int low, high, mid;
	low = 1; high = listLength_D;

	while (low <= high)
	{
		mid = (low + high) / 2;
		if (key < Digital[mid])
			high = mid - 1;
		else if (key > Digital[mid])
			low = mid + 1;
		else
			return mid;
	}
	return 0;
}

程序运行结果：

 

完整代码：

#include

using namespace std;

//线性表的查找;

class Search {
public:
	Search(char ch[],int nums[]);
	~Search();
public:
	int sequentialSearch1(char key);//顺序查找法1--正常遍历
	int sequentialSearch2(char key);//顺序查找法2--设置哨兵
	int binarySearch1(int key);//二分查找（折半查找）法1--非递归
	int binarySearch2(int low, int high, int key);//二分查找（折半查找）法2--递归
public:
	int listLength_A;
	int listLength_D;
	char Alphabet[100];//顺序查找案例--字母表
	int Digital[100];//折半查找案例--升序数字表
};

Search::Search(char ch[],int nums[])
{
	int i = 0;
	while (ch[i] != '')
	{
		Alphabet[i] = ch[i];
		i++;
	}
	listLength_A = i;
	
	int j = 0;
	while (j<10)
	{
		Digital[j] = nums[j];
		j++;
	}
	listLength_D = j;
}

Search::~Search()
{
	//void
}

int Search::sequentialSearch1(char key)
{
	for (int i = listLength_A; i >= 0; i--)
	{
		if (key == Alphabet[i]) return i;
	}
	return 0;
}

int Search::sequentialSearch2(char key)
{
	int i = listLength_A;
	Alphabet[0] = key;//将哨兵设置在此处，防止数组发生越界
	while (Alphabet[i] != key)
	{
		i--;
	}
	return i;
}
int Search::binarySearch1(int key)//非递归
{
	int low, high, mid;
	low = 1; high = listLength_D;

	while (low <= high)
	{
		mid = (low + high) / 2;
		if (key < Digital[mid])
			high = mid - 1;
		else if (key > Digital[mid])
			low = mid + 1;
		else
			return mid;
	}
	return 0;
}

int Search::binarySearch2(int low, int high, int key)
{
	if (low > high) return 0;
	else {
		int mid = (low + high) / 2;
		if (key < Digital[mid]) binarySearch2(low, mid - 1, key);
		else if (key > Digital[mid]) binarySearch2(mid + 1, high, key);
		else return mid;
	}
}

int main()
{
	char alphabet[30] = { ' ','a','b','c','d','e','f','g','h','i','j','k','l','m',//数组长度为27会发生数组溢出，所以要多定义一点空间保护程序运行空间
						'n','o','p','q','r','s','t','u','v','w','x','y','z' };
	
	int digital[20] = { 0,1,2,3,4,5,6,7,8,9};

	Search S(alphabet,digital);
	
	char keyA;
	cout << "输入你要查询的字母:";
	cin >> keyA;

	cout << keyA << "【非哨兵】在表中的位置是（0表示该元素在表中不存在）：" << S.sequentialSearch1(keyA) << endl;
	cout << keyA << "【哨兵】在表中的位置是（0表示该元素在表中不存在）：" << S.sequentialSearch2(keyA) << endl;

	int keyB;
	cout << "输入你要查询的数字:";
	cin >> keyB;

	cout << keyB << "【非递归】在表中的位置是（0表示该元素在表中不存在）：" << S.binarySearch1(keyB) << endl;
	cout << keyB << "【递归】在表中的位置是（0表示该元素在表中不存在）：" << S.binarySearch2(1,10,keyB) << endl;
	
	return 0;
}