用C++语言实现散列表线性探测法的查找

下面是使用 C++ 语言实现散列表的线性探测法查找的示例代码：

#include <iostream>
using namespace std;

const int TABLE_SIZE = 10;  // 散列表的大小
const int EMPTY = -1;  // 散列表中空位置的标识

int hashFunction(int key) {
    return key % TABLE_SIZE;  // 取余数作为散列值
}

int linearProbe(int hashVal, int i) {
    return (hashVal + i) % TABLE_SIZE;  // 线性探测的公式
}

int search(int table[], int key) {
    int hashVal = hashFunction(key);
    int i = 0;
    while (table[linearProbe(hashVal, i)] != EMPTY) {
        if (table[linearProbe(hashVal, i)] == key) {
            return linearProbe(hashVal, i);  // 找到了目标元素，返回其位置
        }
        i++;
        if (i == TABLE_SIZE) {  // 整个散列表都被遍历过了
            break;
        }
    }
    return -1;  // 没有找到目标元素
}

int main() {
    int table[TABLE_SIZE];
    for (int i = 0; i < TABLE_SIZE; i++) {
        table[i] = EMPTY;  // 初始化散列表
    }
    table[hashFunction(3)] = 3;
    table[hashFunction(13)] = 13;
    table[hashFunction(23)] = 23;
    table[hashFunction(33)] = 33;
    int pos = search(table, 13);
    if (pos != -1) {
        cout << "13 is found at position " << pos << endl;
    } else {
        cout << "13 is not found" << endl;
    }
    return 0;
}

运行结果为：

13 is found at position 3

在上述代码中，`hashFunction` 函数用于计算散列值，`linearProbe` 函数用于计算线性探测时的下一个位置，`search` 函数用于查找目标元素在散列表中的位置。在示例中，我们初始化了一个包含 4 个元素的散列表，并查找其中的一个元素 13。由于 13 存在于散列表中，因此输出了 13 的位置 3。