大家好,又见面了,我是你们的朋友全栈君。
题目描述
定义哈希函数为H(key) = key%11。输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。
输入
测试次数t
每组测试数据格式如下:
哈希表长m、关键字个数n
n个关键字
查找次数k
k个待查关键字
输出
对每组测试数据,输出以下信息:
构造的哈希表信息,数组中没有关键字的位置输出NULL
对k个待查关键字,分别输出:
0或1(0—不成功,1—成功)、比较次数、查找成功的位置(从1开始)
样例输入
1
12 10
22 19 21 8 9 30 33 4 41 13
4
22
15
30
41
样例输出
22 9 13 NULL 4 41 NULL 30 19 8 21 33
1 1 1
0 3
1 3 8
1 6 6
思路:
取key的方式:先取余,若不冲突则直接存,若冲突则加上偏移量(1²,-1²,2²,-2²……),然后在长为m的hash表中循环滚动,最后确定key
key第一次取value%11
如果位置冲突,key取:value % 11 + 1²,如果key超过hash表的长度m,key取key-m,如果key的值为负,key取key+m
如果位置冲突,key取:value % 11 + (-1²),如果key超过hash表的长度m,key取key-m,如果key的值为负,key取key+m
如果位置冲突,key取:value % 11 + (2²),如果key超过hash表的长度m,key取key-m,如果key的值为负,key取key+m
如果位置冲突,key取:value % 11 + (-2²),如果key超过hash表的长度m,key取key-m,如果key的值为负,key取key+m
以此类推下去取key
code:
#include <iostream>
using namespace std;
void test()
{
int m,n;
cin>>m>>n;
int *hashh;
hashh = new int [m];
for(int i=0;i<m;i++)
hashh[i]=-100000;
int value,key,flag,temp_key,d,symb,num;
for(int i=0;i<n;i++) //建hash表
{
cin>>value;
key=value%11;
temp_key=key;
d=1; //偏移量
symb=1; //符号
num=0; //hash次数
while(1)
{
if(hashh[temp_key]==-100000)
{
hashh[temp_key]=value;
break;
}
else
{ //滚动取key
num++;
temp_key=key+symb*(d*d); //更新key
symb*=-1; //更新符号
if(num%2==0) //每2次需要更新1次偏移量
d++;
if(temp_key>m) //key超过hash表长度
temp_key -= m;
else if(temp_key <0) //key的值为负数
temp_key += m;
}
}
}
for(int i=0;i<m;i++)
{
if(hashh[i] == -100000)
cout<<"NULL";
else
cout<<hashh[i];
if(i != m-1)
cout<<' ';
}
cout<<endl;
int search_num,search_time;
cin>>search_num;
for(int i=0;i<search_num;i++) //查找
{
search_time=0;
cin>>value;
key=value%11;
temp_key=key;
d=1;
symb=1;
flag=0;
num=0;
while(1)
{
search_time++;
if(hashh[temp_key]==value)
{
flag=1;
cout<<1<<' '<<search_time<<' '<<temp_key+1<<endl;
break;
}
else
{ //和建表一样的更新方法
if(hashh[temp_key]==-100000)
break;
num++;
temp_key=key+symb*(d*d);
symb*=-1;
if(num%2==0)
d++;
if(temp_key>m)
temp_key -= m;
else if(temp_key <0)
temp_key += m;
if(num>m/2)
break;
}
}
if(flag==0)
cout<<0<<' '<<search_time<<endl;
}
delete[] hashh;
}
int main()
{
int t;
cin >> t;
while (t--)
{
test();
}
return 0;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/146468.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...