美文网首页
(散列法)Aizu - ALDS1_4_C

(散列法)Aizu - ALDS1_4_C

作者: Alan66 | 来源:发表于2017-08-21 16:27 被阅读0次

include<iostream>

include<cstdio>

include<cstring>

include<algorithm>

using namespace std;

define M 1046527 //设置为素数避免求模运算无法出现下标的情况

define NLL (-1)

define L 14

define ll long long int

char H[M][L];

//char 转 int
int getChar(char ch)
{
if(ch == 'A') return 1;
else if(ch == 'C') return 2;
else if(ch == 'G') return 3;
else if(ch == 'T') return 4;
else return 0;
}

//str 转int 并生成 key
ll getKey(char str[])
{
ll sum = 0, p = 1,i;
for(i = 0;i < strlen(str);i++){
sum += p*(getChar(str[i]));
p *= 5;
}
return sum;
}

int h1(int key){ return key%M; }
int h2(int key){ return 1 + (key%(M-1));}

int Find(char str[])
{
ll key,i,h;
key = getKey(str);
for(i = 0;;i++){
h = (h1(key) + i*h2(key))%M;
if(strcmp(H[h],str) == 0) return 1;
else if(strlen(H[h]) == 0) return 0;
}
return 0;
}

int Insert(char str[])
{
ll key,i,h;
key = getKey(str);
for(i = 0;;i++){
h = (h1(key) + i*h2(key)) % M;
if(strcmp(H[h],str) == 0) return 1;
else if(strlen(H[h]) == 0){
strcpy(H[h],str);
return 0;
}
}
return 0;
}

int main()
{
int i,n,h;
char str[L],com[9];
for(i = 0;i < M;i++){
H[i][0]= '\0';
}
scanf("%d",&n);
for(i = 0;i < n;i++){
scanf("%s%s",com,str);

    if(com[0] == 'i'){
        Insert(str);
    }
    else{
        if(Find(str)){
            printf("yes\n");
        }
        else printf("no\n");
    }
}
return 0;

}

相关文章

  • (散列法)Aizu - ALDS1_4_C

    include include include includ...

  • 4 查找

    静态查找 顺序查找法 折半查找法 散列 散列的概念 散列函数 冲突解决方法 散列算法设计与分析

  • 哈希表

    哈希=散列哈希法=散列法,对应的哈希表=散列表什么是哈希法?哈希法思想:首先在元素的关键字k和元素的存储位置p之间...

  • 数据结构:处理散列冲突的方法

    开放定址法: 一旦发生冲突 就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到。 再散列函数法:每...

  • 哈希(hash)(散列)算法

    [toc] 散列算法 散列函数 正整数 将整数散列使用的方法是 除留余数法 。 选择大小为 素数 M的数组,对于任...

  • 数据结构算法(十一) 之 散列表查找(哈希表)

    一、散列函数构造方法 除留取余法 对于散列表长度为 m 的散列函数公式为: f(key)= key mod p (...

  • 散列表

    散列函数将被查找的键转换为数组的索引 解决冲突的方法:拉链法和线性探测法 将整数散列最常见的方法是除留余数法,通常...

  • 散列函数(哈希函数)的设计和散列冲突解决方案

    散列函数(哈希函数)的设计有多种,我们 折叠法: 折叠法设计散列函数的基本步骤是:将数据项按照位数分为若干段...

  • 数据结构(查找-散列表(哈希表)的查找)

    1. 散列表的基本概念 元素的存储位置和其关键字之间建立某种直接关系,这就是散列查找法。 (1) 散列函数和散列地...

  • 散列表

    散列函数 除法散列法在用来设计散列函数的除法散列表中,通过取k除以m的余数,将关键字k映射到m个槽中的某一个,既散...

网友评论

      本文标题:(散列法)Aizu - ALDS1_4_C

      本文链接:https://www.haomeiwen.com/subject/fhfhdxtx.html