PTA 7-17 字符串关键字的散列映射

网友投稿 312 2022-11-27

PTA 7-17 字符串关键字的散列映射

给定一系列由大写英文字母组成的字符串关键字和素数P，用移位法定义的散列函数(将关键字Key中的最后3个字符映射为整数，每个字符占5位；再用除留余数法将整数映射到长度为P的散列表中。例如将字符串​​AZDEG​​插入长度为1009的散列表中，我们首先将26个大写英文字母顺序映射到整数0~25；再通过移位将其映射为3；然后根据表长得到，即是该字符串的散列映射位置。

发生冲突时请用平方探测法解决。

#include #include #include #include #include #include using namespace std;const int maxn = 1e6;bool vis[maxn];string s;int n, p;map m;int main() { scanf("%d %d", &n, &p); memset(vis, false, sizeof(vis)); for (int i = 1; i <= n; i++) { cin >> s; int len = s.size(); int x = 0; if (len == 1) x = (s[0]-'A'); else if (len == 2) x = 32*(s[0]-'A')+(s[1]-'A'); else { for (int j = 3; j >= 1; j--) { int t = len - j; x = x * 32 + s[t] - 'A'; } } x = x % p; if (m[s] || !vis[x]) { m[s] = x; vis[x] = true; cout << x; } else { int y; for (int j = 1; j*j < maxn; j++) { y = (x+j*j) % p; if (!vis[y]) { vis[y] = true; m[s] = y; printf("%d", y); break; } y = (x-j*j+p) % p; if (!vis[y]) { vis[y] = true; m[s] = y; printf("%d", y); break; } } } if (i < n) cout << " "; else printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：函数 文字
上一篇:将RestTemplate的编码格式改为UTF
下一篇:基于WirelessUSB LR无线的WUSB射频系统解决方案
相关文章

 发表评论

暂时没有评论，来抢沙发吧~