数据结构实验之查找五：平方之哈希表

冷不防 2022-06-12 03:57 150阅读 0赞

Think:  
1知识点：哈希表+平方探测方法  
2反思：使用变量时选择清晰的命名，保证后续使用时逻辑清晰

[建议参考博客][Link 1]

[SDUT题目链接][SDUT]

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main(){
        int hash[504], pos[504];
        int n, p, i, k, kk, tp;
        while(scanf("%d %d", &n, &p) != EOF){
            tp = 0;
            memset(hash, -1, sizeof(hash));
            for(i = 0; i < n; i++){
                scanf("%d", &k);
                kk = k % p;
                if(hash[kk] == -1){
                    hash[kk] = k;
                }
                else {
                    int sym = 1;
                    int j = 1;
                    int tmp = kk;
                    while(hash[tmp] != -1){
                        tmp = (kk + sym*(j*j)) % p;
                        sym = -sym;
                        if(sym == 1)
                            j++;
                    }
                    hash[tmp] = k;
                    kk = tmp;
                }
                pos[tp++] = kk;
            }
            for(i = 0; i < tp; i++){
                printf("%d%c", pos[i], i == tp-1? '\n': ' ');
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 208KB
    Submit time: 2017-07-14 21:16:07
    ****************************************************/

[Link 1]: http://blog.csdn.net/gd_vip/article/details/52280083
[SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3377.html