跳转至

哈希查找与增补

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

题目描述

给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表尾插入

如果首次查找失败，就把数据插入到相应的位置中

实现哈希查找与增补功能

输入

第一行输入n，表示有n个数据

第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第三行输入t，表示要查找t个数据

从第四行起，每行输入一个要查找的数据，都是正整数

输出

每行输出对应数据的查找结果，每个结果表示为数据所在位置[0，11）和查找次数，中间用空格分开

样例输入

1
2
3
4
5
6
7
8
9
6
11 23 39 48 75 62
6
39
52
52
63
63
52

样例输出

1
2
3
4
5
6
6 1
error
8 1
error
8 2
8 1

提示

解决方案

 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
#include <iostream>
#include <vector>

class HashTable {
public:
    HashTable() : hash_(P) {}
    void insert(int data) {
        int index = data % P;
        Node *ptr = &hash_[index];
        while (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = new Node();
        ptr = ptr->next;
        ptr->data = data;
    }
    void searchOrInsertThenPrint(int data) {
        int result = search(data);
        if (result == -1) {
            std::cout << "error" << std::endl;
            insert(data);
        } else {
            std::cout << data % P << ' ' << result << std::endl;
        }
    }
    int search(int data) {
        int index = data % P;
        Node *ptr = &hash_[index];
        int count = 0;
        while (ptr->next != NULL) {
            ptr = ptr->next;
            count += 1;
            if (ptr->data == data) {
                return count;
            }
        }
        return -1;
    }
private:
    static const int P = 11;
    struct Node {
        int data;
        Node *next;
        Node() : data(), next(NULL) {}
    };
    std::vector<Node> hash_;
};

int main() {
    size_t size;
    std::cin >> size;
    class HashTable hashTable;
    for (int i = 0; i < size; ++i) {
        int number;
        std::cin >> number;
        hashTable.insert(number);
    }

    size_t time;
    std::cin >> time;
    for (int i = 0; i < time; ++i) {
        int number;
        std::cin >> number;
        hashTable.searchOrInsertThenPrint(number);
    }

    return 0;
}

评论