数据结构与算法 查找算法

Question

对于给定的一组m个整数，采用直接定址法构造散列函数，采用线性探测法处理冲突，构造散列表，并实现对任意数的查找。(用C或者C++实现均可)

Answer 1

引自免费微信小程序：皆我百晓生

为了实现这个需求，我们将按照以下步骤进行：

1. 定义一个散列函数。
2. 实现线性探测法解决冲突。
3. 构造散列表。
4. 实现查找功能。

这里我们选择一个简单的直接定址法散列函数 h(key) = key % table_size，其中 table_size 是散列表的大小。线性探测法是在发生冲突时，从当前位置开始，向后依次检查下一个位置，直到找到一个空位为止。

下面是用 C++ 实现的代码：

#include <iostream>
#include <vector>

// 散列函数
int hashFunction(int key, int tableSize) {
    return key % tableSize;
}

// 线性探测法解决冲突
int findEmptySlot(std::vector<int>& table, int key, int tableSize, int currentPos) {
    while (table[currentPos] != -1) {
        currentPos = (currentPos + 1) % tableSize;
    }
    return currentPos;
}

// 插入元素到散列表
void insertElement(std::vector<int>& table, int key, int tableSize) {
    int index = hashFunction(key, tableSize);
    int emptySlot = findEmptySlot(table, key, tableSize, index);

    if (emptySlot == -1) {
        std::cout << "Error: Table is full.\n";
        return;
    }

    table[emptySlot] = key;
}

// 查找元素在散列表中的位置
int searchElement(const std::vector<int>& table, int key, int tableSize) {
    int index = hashFunction(key, tableSize);

    for (int i = index; ; i = (i + 1) % tableSize) {
        if (table[i] == key) {
            return i;
        } else if (table[i] == -1) {
            break;
        }
    }

    return -1;
}

int main() {
    int m;
    std::cout << "Enter the number of integers (m): ";
    std::cin >> m;

    int tableSize = m * 2; // 建议散列表大小为元素数量的2倍，以降低冲突概率

    std::vector<int> table(tableSize, -1); // 初始化散列表，所有位置标记为-1表示为空

    std::cout << "Enter " << m << " integers:\n";
    for (int i = 0; i < m; ++i) {
        int num;
        std::cin >> num;
        insertElement(table, num, tableSize);
    }

    int keyToSearch;
    std::cout << "Enter a number to search: ";
    std::cin >> keyToSearch;

    int result = searchElement(table, keyToSearch, tableSize);

    if (result != -1) {
        std::cout << "Found at position " << result << ".\n";
    } else {
        std::cout << "Not found in the table.\n";
    }

    return 0;
}

这段代码首先定义了一个散列函数 hashFunction 和一个用于线性探测法的辅助函数 findEmptySlot。然后，我们实现了插入元素到散列表的 insertElement 函数以及搜索元素的 searchElement 函数。在主函数 main 中，用户可以输入一组整数并创建散列表，接着搜索指定的整数是否存在于散列表中。注意，这里散列表的大小是元素数量的两倍，这样可以降低冲突的概率。