图书管理(Loj0034)+浅谈哈希表

图书管理

题目描述

图书管理是一件十分繁杂的工作,在一个图书馆中每天都会有许多新书加入。为了更方便的管理图书(以便于帮助想要借书的客人快速查找他们是否有他们所需要的书),我们需要设计一个图书查找系统。

该系统需要支持 2 种操作:

  1. add(s) 表示新加入一本书名为 s 的图书。
  2. find(s) 表示查询是否存在一本书名为 s 的图书。

输入格式

第一行包括一个正整数 n,表示操作数。 以下 n 行,每行给出 2 种操作中的某一个指令条,指令格式为:

add s
find s

在书名 s 与指令(addfind)之间有一个隔开,我们保证所有书名的长度都不超过 200。可以假设读入数据是准确无误的。

输出格式

对于每个 find(s) 指令,我们必须对应的输出一行 yes 或 no,表示当前所查询的书是否存在于图书馆内。

注意:一开始时图书馆内是没有一本图书的。并且,对于相同字母不同大小写的书名,我们认为它们是不同的。

样例

样例输入

4
add Inside C#
find Effective Java
add Effective Java
find Effective Java

样例输出

no
yes

数据范围与提示

n≤30000

借这个题说几件事情

(1)输入

我们发现书名中间是有空格的,cin和scanf一旦遇到空格就会断开

所以这里要用gets()(详见代码)

(2)双hash

通常来说,hash发生碰撞的概率比较大,所以我们可以分别取两个乘数和模数,只有两个hash值均相等时才说两个数相等。这样可以大大减少碰撞的概率。

(3)哈希表

一种数据结构。查找hash表的时间近似于O(n),十分便捷。

比如我们如果要存一个数组并查找

如果用朴素的A[1……n]来存储

即使用二分查找也要O(logN)

如果用hash的思想,可以将hash值相同的几个数用链表存在一起,每个hash值开一个链表(其实就是邻接表

这个东西就叫哈希表

图书管理(Loj0034)+浅谈哈希表

如图,这是一个模数为16的哈希表(实际上将16选为模数并不合适)

储存和查找的期望复杂度为O(1),实际的复杂度取决于链表长度(也就是你选的模数好不好、数据友善不友善),可以看成一个常数

给出代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ULL unsigned long long
#define P 37
#define P2 97
#define MOD 100003
#define MOD2 100009
using namespace std; inline int read()
{
int f=,x=;
char ch=getchar();
while(ch<'' || ch>'') {if(ch=='-') f=-; ch=getchar();}
while(ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
} int n,cnt;
int v[MOD2+],head[MOD2+],nxt[MOD2+];
char a[],c[];
int i,j; void add(int x1,int x2)//哈希表(怎么看都是邻接表……)
{
v[++cnt]=x2;
nxt[cnt]=head[x1];
head[x1]=cnt;
return ;
} bool check(int x1,int x2)
{
for(int k=head[x1];k!=-;k=nxt[k])
{
if(v[k]==x2) return ;
}
return ;
} int main()
{
memset(head,-,sizeof(head));
n=read();
for(i=;i<=n;i++)
{
scanf("%s",a);
gets(c);
int len=strlen(c);
int sum1=,sum2=;
for(j=;j<len;j++)
{
sum1=(sum1*P+c[j])%MOD;
sum2=(sum2*P2+c[j])%MOD2;//使用双hash值,减少碰撞概率
}
if(a[]=='a') add(sum1,sum2);
else
{
if(check(sum1,sum2))
printf("yes\n");
else
printf("no\n");
} }
return ;
}

哈希表(标准答案)

此外还有其他方法:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ULL unsigned long long
#define P 1000000007
using namespace std; inline int read()
{
int f=,x=;
char ch=getchar();
while(ch<'' || ch>'') {if(ch=='-') f=-; ch=getchar();}
while(ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
} int n,cnt;
ULL v[];
char a[],c[];
int i,j; void add(int x)
{
v[++cnt]=x;
} bool check(int x)
{
for(int k=;k<=cnt;k++)
{
if(v[k]==x) return ;
}
return ;
} int main()
{
n=read();
for(i=;i<=n;i++)
{
scanf("%s",a);
gets(c);
int len=strlen(c);
ULL sum=;
for(j=;j<len;j++)
{
sum=sum*P+c[j];
}
if(a[]=='a') add(sum);
else
{
if(check(sum))
printf("yes\n");
else
printf("no\n");
} }
return ;
}

朴素hash(容易被卡+TLE)

石乐志的尝试↓:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std; inline int read()
{
int f=,x=;
char ch=getchar();
while(ch<'' || ch>'') {if(ch=='-') f=-; ch=getchar();}
while(ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
} int n,tot;
char a[],s[];
int ts[][];
bool book[];
int i,j; void make_trie()
{
int len=strlen(s),u=;
for(int k=;k<len;k++)
{
int c=s[k];
if(!ts[u][c])
ts[u][c]=++tot;
u=ts[u][c];
}
book[u]=;
} bool find_trie()
{
int len=strlen(s),u=;
for(int k=;k<len;k++)
{
int c=s[k];
if(!ts[u][c]) return ;
u=ts[u][c];
}
if(book[u]) return ;
else return ;
} int main()
{
n=read();
for(i=;i<=n;i++)
{
scanf("%s",a);
gets(s);
if(a[]=='a')
{
make_trie();
}
else
{
if(find_trie())
printf("yes\n");
else
printf("no\n");
}
}
return ;
}

Trie(华丽丽的RE&MLE)

本文部分图片来源于网络

部分内容参考《信息学奥赛一本通.提高篇》第二部分第一章 哈希和哈希表

若需转载,请注明https://www.cnblogs.com/llllllpppppp/p/9746749.html

~祝大家编程顺利~

上一篇:JAVA类的创建: 创建JAVA的类 ,JAVA的字段,JAVA类的方法


下一篇:python学习之老男孩python全栈第九期_day001作业