跳转至

哈希查找与增补

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

题目描述

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

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

实现哈希查找与增补功能

输入

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

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

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

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

输出

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

样例输入

6
11 23 39 48 75 62
6
39
52
52
63
63
52

样例输出

6 1
error
8 1
error
8 2
8 1

提示

解决方案

#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;
}

评论