题目描述
定义哈希函数为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
代码
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#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; }View Code
标签:11,hash,哈希,temp,value,key,散列,DS From: https://www.cnblogs.com/kuailest/p/16977346.html