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)


相关推荐

  • linux文件共享 samba_文件共享服务

    linux文件共享 samba_文件共享服务Samba是在Linux和UNIX系统上实现SMB协议的一个免费软件,由服务器及客户端程序构成;SMB(ServerMessagesBlock,信息服务块)是一种在局域网上共享文件和打印机的一种通信协议,它为局域网内的不同计算机之间提供文件及打印机等资源的共享服务;SMB协议是客户机/服务器型协议,客户机通过该协议可以访问服务器上的共享文件系统,

  • IDEA中web项目如何部署到Tomcat上[通俗易懂]

    IDEA中web项目如何部署到Tomcat上[通俗易懂]IDEA中web项目的创建与如何部署到Tomcat

    2022年10月31日
  • idea安装配置tomcat_eclipse中配置tomcat

    idea安装配置tomcat_eclipse中配置tomcat我看到很多博文介绍使用maven配置tomcat,那种方法我没有尝试,不过社区版其实是有tomcat的->SmartTomcat。打开IDEA,Crtl+Alt+S或者File->setting在设置里面的plugins插件里面,搜索tomcat就能看到了,点击Install进行安装即可。安装好之后,重启IDEA工具,然后点击IDEA右上角的Addconfiguratio…

  • BindingNavigator控件[通俗易懂]

    BindingNavigator控件[通俗易懂]WinForm之中BindingNavigator控件的使用在微软WinForm中,BindingNavigator控件主要用来绑定数据。可以将一个数据集合与该控件绑定,以进行数据联动的显示效果。如图下图所示:那么,下面我们就来用BindingNavigator控件做一下上图所示的效果。分析:该案例以BindingNavigator控件为主线,我们定义一个实体类

  • Java实现判断闰年

    Java实现判断闰年Java实现闰年判断需求分析:年份如果满足以下两个条件中的其中一个则可将其年份判断位闰年一、能被4整除,但不能被100整除,就是闰年;二、能被400整除,也是闰年;需求实现方案一:使用if的嵌套实现packagecom.qingsu.basis;importjava.util.Scanner;publicclassProcessControl{ publicstaticvoidmain(String[]args){ //判断闰年 //1.能被4整除

  • ubuntu安装教程_ubuntu docker安装

    ubuntu安装教程_ubuntu docker安装卸载docker1.删除某软件,及其安装时自动安装的所有包sudoapt-getautoremovedockerdocker-cedocker-enginedocker.iocontainerdrunc2.删除docker其他没有没有卸载dpkg-l|grepdockerdpkg-l|grep^rc|awk'{print$2}’|sudoxargsdpkg-P#删除无用的相关的配置文件3.卸载没有删除的docker相关插件(…

发表回复

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

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