跳转至

DS哈希查找—二次探测再散列

时间限制: 1 Sec 内存限制: 128 MB

题目描述

定义哈希函数为H(key) = key%11。输入表长（大于、等于11），输入关键字集合，用二次探测再散列构建哈希表，并查找给定关键字。

输入

测试次数t

每组测试数据格式如下：

哈希表长m、关键字个数n

n个关键字

查找次数k

k个待查关键字

输出

对每组测试数据，输出以下信息：

构造的哈希表信息，数组中没有关键字的位置输出NULL

对k个待查关键字，分别输出：

0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）

样例输入

1
2
3
4
5
6
7
8
1
12 10
22 19 21 8 9 30 33 4 41 13
4
22
15
30
41

样例输出

1
2
3
4
5
22 9 13 NULL 4 41 NULL 30 19 8 21 33
1 1 1
0 3
1 3 8
1 6 6

提示

解决方案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <vector>

class HashTable {
public:
    explicit HashTable(size_t size) : hash_(size, -1) {}
    void setFromCin() {
        size_t length;
        std::cin >> length;
        for (int i = 0; i < length; ++i) {
            int number, index = 0;
            std::cin >> number;
            int position = number % P;
            int sign = 1;
            while (hash_[position] != -1) {
                position = number % P + index * index * sign;
                sign = -sign;
                if (sign == 1) {
                    index += 1;
                }
                if (position > static_cast<int>(hash_.size())) {
                    position = position - static_cast<int>(hash_.size());
                } else if (position < 0) {
                    position = position + static_cast<int>(hash_.size());
                }
            }
            hash_[position] = number;
        }
        std::cout << hash_.front();
        for (int i = 1; i < hash_.size(); ++i) {
            if (hash_[i] == -1) {
                std::cout << " NULL";
            } else {
                std::cout << ' ' << hash_[i];
            }
        }
        std::cout << std::endl;
    }
    void searchAndPrint(int data) {
        int result = 1, count = 0, index = 0, sign = -1;
        int position = data % P + index * index;
        while (count += 1, hash_[position] != data) {
            if (count == hash_.size() || hash_[position] == -1) {
                result = 0;
                break;
            }
            sign = -sign;
            if (sign == 1) {
                index += 1;
            }
            position = data % P + index * index * sign;
            if (position > static_cast<int>(hash_.size())) {
                position = position - static_cast<int>(hash_.size());
            } else if (position < 0) {
                position = position + static_cast<int>(hash_.size());
            }
        }
        std::cout << result << ' ' << count;
        if (result == 1) {
            std::cout << ' ' << position + 1;
        }
        std::cout << std::endl;
    }
private:
    static const int P = 11;
    std::vector<int> hash_;
};

int main() {
    size_t ctrl;
    std::cin >> ctrl;
    while (ctrl--) {
        size_t size;
        std::cin >> size;
        class HashTable hashTable(size);
        hashTable.setFromCin();

        int time;
        std::cin >> time;
        while (time--) {
            int number;
            std::cin >> number;
            hashTable.searchAndPrint(number);
        }
    }

    return 0;
}

评论