【题目描述】
用除留取余法构造散列表，输入序列并实现查找操作。
【算法】
哈希函数使用除留余数法
若已知整个哈希表的最大长度 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 <iostream>
#include <math.h>
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 <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
class HashTable
{
private:
int* elem; //数据元素存储地址，动态分配数组
int size; //哈希表长度
int n; //当前元素个数
int p; //哈希函数的除数
public:
HashTable(int n, int size)
{
this->n = n;
this->elem = new int[size];
this->size = size;
for (int i = 0; i < size; i++)
{
this->elem[i] = NULLKEY;
}
p = 2;
//倒序搜索，求小于size的最大质数
for (int i = size; i > 0; i--)
{
if (isPrim(i))
{
p = i;
break;
}
}
cout << "p=" << p << endl;
}
int hash(int data)
{
return data % p;
}
//哈希函数除留取余法，可用于构造哈希表，用开放性定址法线性探测解决冲突
void insert(int data)
{
int hashAddress = hash(data);
//发生冲突
while (this->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 < size; i++)
{
if (this->elem[i] != NULLKEY)
cout << this->elem[i] << " ";
else
cout << "^ ";
}
cout << endl;
}
};
int main()
{
int i,result;
int n, m;
cin >> n >> m;
int arr[100];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
HashTable hashTable(n, m);
//利用插入函数构建哈希表
for (i = 0; i < n; i++)
{
hashTable.insert(arr[i]);
}
cout << "打印哈希表";
hashTable.displayHashTable();
cout << "输入要查找的数字";
int num;
cin >> num;
//调用查找法
result = hashTable.search(num);
if (result != -1)
cout << num << "在哈希表中的位置是" << result;
else
cout << "查找失败";
return 0;
}
