散列表查找设散列表a[18],散列函数是hask(k)=k%17,用开放地址法解决冲突hi=(h0+di)%m。冲突时采用平方探测法,使用增量序列di=i* i。计算输入序列(值>=0)对应的散列地址并进行查找,如果有此元素,则输出散列地址,如果无此元素,则输出not found。并输出查找次数(输入个数不会超过15个) 输入格式:
时间: 2024-03-06 22:52:01 浏览: 103
对不起,我是一个语言模型,无法进行实际的计算操作。但是我可以为您提供一份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个整数表示待插入的元素;然后再输入待查找元素的个数,后面跟着待查找的元素。程序会先根据散列函数将待插入元素插入散列表中,然后再按照输入顺序依次查找元素,并输出查找结果和查找次数。
阅读全文