HNU 13064 Cuckoo for Hashing解题报告 North America

题目大意:使用两个哈希表来解决哈希冲突的问题。假如现在有两个哈希表分别为:H1,H2 ,大小分别为:n1,n2;现有一数据X需要插入,其插入方法为:

1、计算index1 = X MOD N1,  若哈希表H1的index1位置没有保存数据,则直接将X保存到H1得index1;否则,若哈希表H1的index1位置已经保存有数据X1,则将原来已保存的数据X1进行缓存,然后将X插入H1的index1的位置。

2、将上一步缓存的X1插入到哈希表H2,首先计算index2=X1 MOD N2,若H2的index2没有保存数据,则直接将X1保存至index2,;否则,缓存原来在H2中index2的数据X2,然后将X1保存到H2的index2中。

3、将上一步得X2重新插入到哈希表H1中,依次类推。

样例输入输出

Sample Input
5 7 4
8 18 29 4
6 7 4
8 18 29 4
1  2
1
2
0 0 0
Sample Output
Case 1:
Table 1
3:8
4:4
Table 2
1:29
4:18
Case 2:
Table 1
0:18
2:8
4:4
5:29
Case 3:
Table 1
0:2
Table 2
1:1
解题思路:

1、创建两个新的空哈希表,对于每个需要插入的数据分别进行处理。

2、对于每一个需要插入的数据,根据两个哈希表以上的性质,进行插入。

代码如下:

<span style="font-size:18px;">#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int t1[1002],t2[1002];
int flag;
/*flag==0, the operation in the table1
  flag==1, the operation in the table2
  when the collision occur, it will 
  */
void insert(int n1, int n2, int value)
{
    int index, hel, tmp;
    switch (flag)
    {
        case 0:            //in the table1
            hel = value%n1;
            if(t1[hel] != 0)
            {
                flag = 1;
                tmp = t1[hel];
                t1[hel] = value;
                insert(n1, n2, tmp);
            }
            else {
                t1[hel] = value;
            }
            break;
        case 1:            //in the table2;
            hel = value%n2;
            if(t2[hel] != 0)
            {
                flag=0;
                tmp = t2[hel];
                t2[hel] = value;
                insert(n1, n2, tmp);
            }
            else{
                t2[hel] = value;
            }
            break;
    }
}
int main()
{
    int n1,n2,m,count;
    int i,value,f;
    
    count = 0;
    while(scanf("%d%d%d",&n1,&n2,&m)==3)
    {
        if(!n1 && !n2 && !m)
            break;
        memset(t1,0,sizeof(t1));
        memset(t2,0,sizeof(t2));
        for(i=0; i<m; i++)
        {
            scanf("%d",&value);
            flag = 0;
            insert(n1, n2, value);
            
        }
        printf("Case %d:\n",++count);
        f=0;
        for(i=0; i<n1; i++)
        {
            if(t1[i] != 0)
            {
                if(0 == f)
                {
                    printf("Table 1\n");
                    f = 1;
                }
                printf("%d:%d\n",i,t1[i]);
            }
        }
        f=0;
        for(i=0; i<n2; i++)
            if(t2[i] != 0)
            {
                if(0 == f)
                {
                    printf("Table 2\n");
                    f=1;
                }
                printf("%d:%d\n",i,t2[i]);
            }
    }
    return 0;
}</span>


更多相关文章
  • 题目大意:输入一个偶数(x<32),输出这个偶数是由哪两个素数相加所得. 比如:一个偶数26,它可以是3+23,7+19,13+13,这些素数相加所得. 输入输出样例: Sample Input 3 4 26 100 Sample Output 4 has 1 representation(s ...
  • Problem B:Cuckoo for HashingAn integer hash table is a data structure that supports insert, delete and lookup of integer values inconstant time. Tradi
  • 题意和解决回路匹配的思路如同hdu3488 (这里我第一次想到最短路,但是对于有回路这个不知道怎么处理,后来看了别人的解题报告才知道KM匹配,但是看到KM之后就自己想...想了很久....还是不知道回路这个地方怎么匹配......其实应该这样来想....总共有N个城市....如果是要形成回路..那么 ...
  • http://poj.org/problem?id=1173 发现此题资料甚少,斗胆第一次写一份解题报告[题意]     输入 n(代表二进制位数) k(代表黑条白条总共有几条,条形码是以黑条开始的,再白黑交替出现) m(代表每条最多占多少个二进制位)     输出这种模式的条形码的有多少个?    ...
  • The form belonging to the Diesel's court case is totally distinct in addition to being very unlikely to find
  • Regionals 2013 :: North America
    Regionals 2013 :: North America - Southeast USA It Takes a Village As a Sociologist, you are studying a certain kingdom. This kingdom has a capitol ci ...
  • 2015 UESTC Winter Training #6Regionals 2010  North America
    2015 UESTC Winter Training #6 Regionals 2010 >> North America - Rocky Mountain   A - Parenthesis 给一个长度不多于1的表达式,只包含小写字母,加法运算,省略乘号的乘法运算和括号,输出去掉多余括 ...
  • 本题大意: 用天平对一物品进行称重,现有重量不同的砝码,砝码的重量分别为:1,3,9,27,..,3^n.(n<20) 天平的右侧放砝码,左侧放物品或物品和砝码,使得左右两边的重量相等. 现有一个物品,计算左右两边应当分别放多少个多大的砝码才能使得天平平衡. 例如:现在有一个重量为21的物品, ...
一周排行
  • 按照官方文档操作,但是windows下有些不同,它不认识单引号',因此如果这样操作,就会报错: C:\Users\neusoft>curl localhost:9200/b1/b2/1 -d {"na ...
  • 异常描述:执行以下的addAsHaveParentId2方法出现此异常: /*--类Dept.Dept.hbm.xml有parentId属性(数据库中有此列)-*/ @Test//添加一级部门--success(pa ...
  • HDU 3667 費用流 拆邊 Transportation
    题意: 有N个城市,M条有向道路,要从1号城市运送K个货物到N号城市. 每条有向道路< ...
  • 在安装Ubuntu的时候,记得选上LAMP Server,如果想要SSH登陆,记得也选上OpenSSH.安装完成后,就可以进行Cacti的安装了,到它的主页下载最新的版本吧,如果你想用其他版本的也可以.我装的是0.8
  • 恢复内容开始 DDOS是分布式拒绝访问服务攻击,就是海量的向服务器发起request,而服务器难以区分这些request哪些是真实请求.只能都进行回应, 于是服务器的带宽被榨干,无法相应,使得正常的访问也被拒绝.   ...
  • Configuring Your RHEL Firewall For Webmin 本文以RHEL6.1为实例,详细讲述了Webmin在RHEL6.1中的安装和配置过程. 着重描述了防火墙规则的设置. Many op
  • 原创技术贴:手机,Ipad Android 安卓系统翻墙教程 根据全球著名调查机构Gartner提供的数据,安卓系统在智能手机市场的占有率在2011年第三季度达到52.5%,去年同期为25.3%. 安卓系统毫无疑问是
  • 比大小 时间限制:3 ms    内存限制:65535 KB 难度:2   描述 给你两个很大的数,你能不能判断出他们两个数的大小呢? 比如123456789123456789要大于-123456   输入每组测试数
  • 监控memcache的运行状态有好几种实现方式.在这里我只介绍用Nagios-Plugins-Memcached 进行监控memcached. 该插件是用prel 进行开发的所以系统上必须要安装Perl 环境,并且同
  • OTG
    OTG技术就是在没有Host的情况下,实现设备间的数据传送.例如数码相机直接连接到打印机上,通过OTG技术,连接两台设备间的USB口,将拍出的相片立即打印出来:也可以将数码照相机中的数据,通过OTG发送到USB接口的