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

来解决冲突。假设有以下数据要插入散列表中：25、74、42、32、16、95、20、68、46、50、40、38、73、95、15、30、35、78。

首先，我们需要定义一个哈希函数，根据题目给出的公式，哈希函数为 hask(k)=k mod 18，其中 k 为要插入散列表的值。

接下来，我们使用开放地址法来解决冲突。开放地址法是指当插入的位置已经被占用时，继续向后探测，直到找到一个空位置为止。具体来说，有以下几种探测方式：

1. 线性探测法：当插入位置已经被占用时，继续向后移动一个位置，直到找到一个空位置为止。

2. 二次探测法：当插入位置已经被占用时，按照以下公式继续向后移动，直到找到一个空位置为止：hask(k)+i^2 (i=1,2,3,...)。

3. 双重哈希法：当插入位置已经被占用时，使用另外一个哈希函数继续向后探测，直到找到一个空位置为止。

在本题中，我们采用线性探测法来解决冲突。具体步骤如下：

1. 创建一个初始为空的散列表 a[18]。

2. 将数据按照哈希函数的值插入散列表中。首先，将第一个数据 25 插入散列表中，计算出它的哈希值为 7，发现位置 7 没有被占用，因此直接插入。接下来，将第二个数据 74 插入散列表中，计算出它的哈希值为 2，发现位置 2 已经被占用，因此向后探测一个位置，发现位置 3 没有被占用，因此插入到位置 3。以此类推，将所有数据插入散列表中。

3. 当需要查找某个数据时，计算出它的哈希值，然后按照哈希函数的方式向后探测，直到找到该数据或者找到一个空位置为止。

下面是完整的代码实现：

相关问题

散列表查找设散列表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。