除留取余法构造散列表–c++【做题记录】

【题目描述】

用除留取余法构造散列表，输入序列并实现查找操作。

【算法】

哈希函数使用除留余数法

若已知整个哈希表的最大长度 m，可以取一个不大于 m 的数 p，然后对该关键字 key 做取余运算，即：H（key）= key % p。 在此方法中，对于 p 的取值非常重要，由经验得知 p 可以为不大于 m 的质数或者不包含小于 20 的质因数的合数。 本题求出不大于 m 的最大质数，作为p的值。

使用开放定址法解决冲突

H（key）=（H（key）+ d）MOD m（其中 m 为哈希表的表长，d 为一个增量） 采用线性探测法，当遇到冲突时，从发生冲突位置起，每次 +1，向右探测，直到有空闲的位置为止，即d的值为1，2，3，4…。

【输入输出】

第一行输入数据的个数n和哈希表的长度m，m>2

第二行输入n个int型数据的序列，数据大于-3000，小于3000

第三行输出p值

第四行打印哈希表，表中为空的位置显示 ^

第五行输入要查找的数据

第六行输出数据在哈希表中的位置

测试数据1

7 10

13 29 27 28 26 30 38

p=7

打印哈希表28 29 30 38 ^ 26 13 27 ^ ^

输入要查找的数字27

27在哈希表中的位置是7

测试数据2

8 10

13 29 27 28 26 30 38 9

p=7

打印哈希表28 29 30 38 9 26 13 27 ^ ^

输入要查找的数字10

查找失败

【代码】

#include 
#include 
using namespace std;
#define NULLKEY -32760
bool isPrim(int num)
{
	if (num <= 1) 
		return false;
	if (num <= 3) 
		return true;
	if (num % 2 == 0 || num % 3 == 0) 
		return false;
	for (int i = 5; i * i n = n;
		this->elem = new int[size];
		this->size = size;
		for (int i = 0; i elem[i] = NULLKEY;
		}
		p = 2;
		//倒序搜索，求小于size的最大质数
		for (int i = size; i > 0; i--)
		{
			if (isPrim(i))
			{
				p = i;
				break;
			}
		}
		cout << "p=" << p <elem[hashAddress] != NULLKEY)
		{
			//利用开放定址法解决冲突
			hashAddress = (++hashAddress) % size;
		}
		this->elem[hashAddress] = data;
	}
	//哈希表的查找算法
	int search(int data)
	{
		int hashAddress = hash(data);  //求哈希地址
		while (this->elem[hashAddress] != data) //发生冲突
		{
			//利用开放定址法解决冲突
			hashAddress = (++hashAddress) % size;
			//如果查到的地址中数据位空，或者经过一圈的遍历回到查找地址时，说明查找失败
			if (this->elem[hashAddress] == NULLKEY || hashAddress == hash(data))
			{
				return -1;
			}
		}
		return hashAddress;
	}
	void displayHashTable()
	{
		for (int i = 0; i elem[i] != NULLKEY)
				cout <elem[i] << " ";
			else
				cout << "^ ";
		}
		cout <> n >> m;
	int arr[100];
	for (int i = 0; i > arr[i];
	}
	HashTable hashTable(n, m);
	//利用插入函数构建哈希表
	for (i = 0; i < n; i++)
	{
		hashTable.insert(arr[i]);
	}
	cout << "打印哈希表";
	hashTable.displayHashTable();
	cout <> num;
	//调用查找法
	result = hashTable.search(num);
	if (result != -1)
		cout << num << "在哈希表中的位置是" << result;
	else
		cout << "查找失败";
	return 0;
}