实验8-选做题(1) 散列表查找设散列表a[18],散列函数是hask(k)=k,用开放地址法

散列表查找是一种常见的数据结构操作，可以快速地查找特定的元素。开放地址法是一种常见的解决哈希冲突的方法，它的基本思想是在哈希表中寻找空槽位，将冲突的元素插入到空槽位中，从而解决冲突。

针对您的问题，我假设您需要实现一个使用开放地址法的散列表查找算法，其散列函数为hask(k)=k mod 18，您可以按照以下步骤进行实现：

1. 定义散列表a[18]，并初始化为-1，表示所有槽位都是空的。
2. 定义散列函数hask(k)=k mod 18，用于将关键字k映射到散列表中的槽位。
3. 实现查找算法。对于给定的关键字k，首先计算它的散列地址h=hask(k)，然后从散列地址h开始向后遍历散列表，直到找到一个空槽位或者槽位中的元素等于k为止。如果找到了空槽位，则说明关键字k不存在于散列表中；否则，找到了相应的元素，返回它的下标即可。
4. 实现插入算法。对于给定的关键字k，首先计算它的散列地址h=hask(k)，然后从散列地址h开始向后遍历散列表，直到找到一个空槽位或者槽位中的元素等于k为止。如果找到了空槽位，则将关键字k插入到该槽位中；否则，说明散列表已满，无法插入新元素。

需要注意的是，开放地址法有多种不同的实现方式，比如线性探测、二次探测、双重散列等，您可以根据具体的需求选择不同的实现方式。另外，由于开放地址法容易产生聚集现象，导致性能下降，因此在实际应用中需要结合具体情况进行调整和优化。

相关问题

散列表查找设散列表a[18]，散列函数是hask(k)=k%17，用开放地址法解决冲突hi=(h0+di)%m。冲突时采用平方探测法，使用增量序列di=i* i。计算输入序列(值>=0)对应的散列地址并进行查找，如果有此元素，则输出散列地址，如果无此元素，则输出not found。并输出查找次数（输入个数不会超过15个） 输入格式:

对不起，我是一个语言模型，无法进行实际的计算操作。但是我可以为您提供一份C++示例代码，您可以参考其中的数据结构和算法实现。

#include <iostream>
using namespace std;

const int m = 18;
int a[m];

int hask(int k) {
    return k % 17;
}

int find(int key) {
    int h0 = hask(key);
    int h = h0;
    int i = 1;
    while (a[h] != -1 && a[h] != key) {
        h = (h0 + i * i) % m;
        i++;
    }
    if (a[h] == key) {
        return h;
    } else {
        return -1;
    }
}

int main() {
    for (int i = 0; i < m; i++) {
        a[i] = -1;
    }
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int h = hask(x);
        int j = 1;
        while (a[h] != -1) {
            h = (h + j * j) % m;
            j++;
        }
        a[h] = x;
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int h = find(x);
        if (h == -1) {
            cout << "not found" << endl;
        } else {
            cout << h << endl;
        }
        cnt += i + 1;
    }
    cout << "查找次数：" << cnt << endl;
    return 0;
}

输入格式为：首先输入待插入元素的个数n，接下来n个整数表示待插入的元素；然后再输入待查找元素的个数，后面跟着待查找的元素。程序会先根据散列函数将待插入元素插入散列表中，然后再按照输入顺序依次查找元素，并输出查找结果和查找次数。

C语言代码实现，设散列表a[18]，散列函数是hask(k)=k%17，用开放地址法解决冲突hi=(h0+di)%m。冲突时，使用增量序列di=5i。计算输入序列(值>=0)对应的散列地址值。（输入个数不会超过15个）

以下是C语言代码实现：

#include <stdio.h>

#define M 18

int hask(int k) {
    return k % 17;
}

int open_addressing(int a[], int k) {
    int h = hask(k);
    if (a[h] == -1) {
        a[h] = k;
        return h;
    }
    int i = 1;
    while (1) {
        int hi = (h + 5 * i) % M;
        if (a[hi] == -1) {
            a[hi] = k;
            return hi;
        }
        i++;
    }
}

int main() {
    int a[M];
    for (int i = 0; i < M; i++) {
        a[i] = -1;
    }

    int n;
    printf("请输入数字个数：");
    scanf("%d", &n);

    printf("请输入%d个数字：\n", n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        int h = open_addressing(a, x);
        printf("%d ", h);
    }

    return 0;
}

程序首先定义了散列表 `a`，并且定义了散列函数 `hask(k)`。然后定义了开放地址法解决冲突的函数 `open_addressing`，该函数接收一个散列表和一个数字 `k`，并根据散列函数计算出 `k` 对应的散列地址。如果该地址没有被占用，则直接将 `k` 存储在该地址中，并返回该地址。如果该地址已经被占用，则使用增量序列 `di=5i`，不断计算下一个地址，直到找到一个空闲地址并将 `k` 存储在该地址中，并返回该地址。

在 `main` 函数中，程序首先初始化散列表 `a`，将每个元素都设置为 `-1`。然后程序让用户输入数字个数 `n`，并让用户输入 `n` 个数字。对于每个数字，程序调用 `open_addressing` 函数计算出它对应的散列地址，并打印该地址。最终程序返回 0。