题目描述
定义哈希函数为H(key) = key%11,输入表长(大于、等于11)。输入关键字集合,用线性探测再散列构建哈希表,并查找给定关键字。
--程序要求--
若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件,不看代码,作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
测试次数t
每组测试数据为:
哈希表长m、关键字个数n
n个关键字
查找次数k
k个待查关键字
输出
对每组测试数据,输出以下信息:
构造的哈希表信息,数组中没有关键字的位置输出NULL
对k个待查关键字,分别输出:0或1(0—不成功,1—成功)、比较次数、查找成功的位置(从1开始)
样例输入
1 12 10 22 19 21 8 9 30 33 4 15 14 4 22 56 30 17
样例输出
22 30 33 14 4 15 NULL NULL 19 8 21 9 1 1 1 0 6 1 6 2 0 1
提示
#include<iostream>
using namespace std;
#define INF -9999
int main()
{
int T;
cin>>T;
while(T--)
{
int m,n;
cin>>m>>n;
int *array=new int[m];
for(int i=0;i<m;i++)
array[i]=INF;
for(int i=0;i<n;i++)
{
int num;
cin>>num;
if(array[num%11]==INF)
{
array[num%11]=num;
}
else
{
int di=0;
while(true)
{
if(array[(num%11+di)%m]==INF)
{
array[(num%11+di)%m]=num;
break;
}
else
di++;
}
}
}
for(int i=0;i<m;i++)
{
if(array[i]!=INF)
cout<<array[i];
else
cout<<"NULL";
if(i!=m-1)
cout<<" ";
}
cout<<endl;
int K;
cin>>K;
while(K--)
{
int di=0;
int C;
cin>>C;
int times=0;
while(true)
{
times++;
if(array[(C%11+di)%m]==C)
{
cout<<"1"<<" "<<times<<" "<<(C%11+di)%m+1<<endl;
break;
}
else if(di==m||array[(C%11+di)%m]==INF)
{
cout<<"0"<<" "<<times<<endl;
break;
}
else
di++;
}
}
delete []array;
}
return 0;
}
原文链接: https://www.cnblogs.com/SZU-DS-wys/p/12183039.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/191872
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!