7-12 哈希查找的平均查找长度

对于给定的关键字序列，求采用哈希查找时查找成功和查找失败的平均查找长度。哈希函数：H(key) = key % K，其中K为某个不大于哈希表长M的整数。采用线性探测再散列处理冲突。

输入格式:

测试数据有多组，处理到文件尾。对于每组测试，第一行输入关键字个数n（n≤100）、表长M（n<M≤2n）和K；第二行输入n个整型关键字。

输出格式:

对于每组测试，输出查找成功和查找失败时的平均查找长度，之间以一个空格间隔，结果保留2位小数。

输入样例:

4 5 5
10 6 4 15
11 18 16
10 24 32 17 31 30 46 47 40 63 49

输出样例:

1.50 3.00
2.09 2.94

来源：

[1] 黄龙军, 等. 数据结构与算法, 上海:上海交通大学出版社, 2022.7. ISBN: 9787313269881
[2] 黄龙军, 等. 数据结构与算法（Python版）,上海: 上海交通大学出版社, 2023. ISBN: 9787313280732

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <stdio.h>

int a[222], k, m, n;

int hash(int x) {
    return x % k;
}

int find(int x, int v) {
    int key = hash(x), pos = key, i;
    for (i = 0; i < m; i++) {
        pos = (key + i) % m;
        if (a[pos] == -1) {
            if (v) {
                a[pos] = x;
            }
            return i + 1;
        } else if (a[pos] == x) {
            return i + 1;
        }
    }
    return m; 
}

double failLength() {
    int len = 0, ct = 0;
    for (int i = 0; i < k; i++) {
        int key = i, pos = key;
        for (int j = 0; j < m; j++) {
            pos = (key + j) % m;
            if (a[pos] == -1) {
                len += j + 1;
                ct++;
                break;
            }
        }
    }
    return (double)len / ct;
}

int main() {
    int t;
    while (scanf("%d%d%d", &n, &m, &k) == 3) {
        for (int i = 0; i < m; i++) {
            a[i] = -1;
        }
        double su = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &t);
            su += find(t, 1);
        }
        double fa = failLength(); 

        printf("%.2f %.2f\n", su / n, fa);
    }
    return 0;
}