DS哈希查找—二次探测再散列

DS哈希查找—二次探测再散列题目描述定义哈希函数为H(key)=key%11。输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。输入测试次数t每组测试数据格式如下:哈希表长m、关键字个数nn个关键字查找次数kk个待查关键字输出对每组测试数据,输出以下信息:构造的哈希表信息,数组中没有关键字的位置输出NULL对k个待查关键字,分别输出:…

大家好,又见面了,我是你们的朋友全栈君。

题目描述

定义哈希函数为H(key) = key%11。输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。

输入

测试次数t

每组测试数据格式如下:

哈希表长m、关键字个数n

n个关键字

查找次数k

k个待查关键字

输出

对每组测试数据,输出以下信息:

构造的哈希表信息,数组中没有关键字的位置输出NULL

k个待查关键字,分别输出:

010—不成功,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账号...

(0)


相关推荐

  • preparedStatement和Statement区别「建议收藏」

    preparedStatement和Statement区别「建议收藏」原文:https://blog.csdn.net/xuebing1995/article/details/72235380  一、概念PreparedStatement是用来执行SQL查询语句的API之一,Java提供了Statement、PreparedStatement和CallableStatement三种方式来执行查询语句,其中Statement用于通用查询,Prep…

  • win10应用商店错误代码0x8000FFFF_错误代码0xc000007b

    win10应用商店错误代码0x8000FFFF_错误代码0xc000007b控制面板内打开网络和Internet Internet选项 连接 设置 自动检测设置

  • Idea实现WebService实例

    Idea实现WebService实例因为工作需要,数据传输部分需要使用webservice实现,经过两天的研究,实现了一个简单的例子,具体方法如下。首先需要新建一个项目,如图:下一步点击finish,然后会生成一个webservice项目,在HelloWorld类里面写自己的方法,在file下编译一下这个类,不编译,idea会提示不通过,编译后需要将为该服务发布WSDL文件,此文件必须生成,如下图:选择需要发

  • 组装服务器注意事项

    最近做虚拟化工作需要,为公司组装了一台服务器。把过程经验介绍一下:推荐:http://www.cnblogs.com/roucheng/p/texiao.html

    2021年12月27日
  • 对全连接层(fully connected layer)的通俗理解

    对全连接层(fully connected layer)的通俗理解我的机器学习教程「美团」算法工程师带你入门机器学习已经开始更新了,欢迎大家订阅~任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习小组“,沙雕博主在线答疑~此外,公众号内还有更多AI、算法、编程和大数据知识分享,以及免费的SSR节点和学习资料。其他平台(知乎/B站)也是同名「图灵的猫」,不要迷路哦~定义…

  • Gstreamer中加入�x265编解码器

    Gstreamer中加入�x265编解码器

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号