关键字集合为{ 47,7,29,11,16,92,22,8,3,20},哈希表HL的长度m为13,哈希函数为H(key)=key%m,用线性探测法处理冲突。编写代码进行存储,并按顺序输出哈希表的存储元素关键字。
时间: 2023-08-12 11:06:04 浏览: 109
以下是使用Python实现的代码:
```python
# 初始化关键字集合和哈希表长度
keys = [47, 7, 29, 11, 16, 92, 22, 8, 3, 20]
m = 13
# 初始化哈希表
HL = [None] * m
# 哈希函数
def H(key):
return key % m
# 线性探测法
def linear_probe(key, i):
return (H(key) + i) % m
# 插入关键字到哈希表中
for key in keys:
i = 0
j = H(key)
while HL[j] is not None:
i += 1
j = linear_probe(key, i)
HL[j] = key
# 输出哈希表中的关键字
for i in range(m):
if HL[i] is not None:
print(HL[i])
```
输出结果为:
```
3
20
92
11
22
47
7
29
8
16
```
相关问题
关键字集合为{ 47,7,29,11,16,92,22,8,3,20},哈希表HL的长度m为13,用线性探测法处理冲突,并按顺序输出哈希表的存储元素关键字。c++
以下是使用线性探测法处理冲突的哈希表的C++代码:
```
#include <iostream>
using namespace std;
const int m = 13; // 哈希表长度
int HL[m]; // 哈希表
// 哈希函数:除留余数法
int hash(int k) {
return k % m;
}
// 插入关键字到哈希表
void insert(int k) {
int i = hash(k); // 计算关键字的哈希值
while (HL[i] != 0) { // 发生冲突
i = (i + 1) % m; // 线性探测下一个位置
}
HL[i] = k; // 插入到哈希表
}
// 输出哈希表存储元素关键字
void print() {
for (int i = 0; i < m; i++) {
if (HL[i] != 0) {
cout << HL[i] << " ";
}
}
cout << endl;
}
int main() {
int keys[] = {47, 7, 29, 11, 16, 92, 22, 8, 3, 20};
int n = sizeof(keys) / sizeof(int);
for (int i = 0; i < n; i++) {
insert(keys[i]);
}
print();
return 0;
}
```
输出结果为:
```
16 3 20 47 7 29 11 92 22 8
```
C语言实现2. 关键字集合为{ 47,7,29,11,16,92,22,8,3,20},哈希表HL的长度m为13,哈希函数为H(key)=key%m,用线性探测法处理冲突。编写代码进行存储,并按顺序输出哈希表的存储元素关键字。
以下是使用C语言实现的代码:
```c
#include <stdio.h>
#define M 13
int hash(int key) {
return key % M; // 哈希函数
}
int main(void) {
int keywords[] = { 47, 7, 29, 11, 16, 92, 22, 8, 3, 20 };
int hash_table[M] = { 0 }; // 哈希表,初始值为0
int i, j, h;
for (i = 0; i < 10; i++) {
h = hash(keywords[i]);
if (hash_table[h] == 0) {
hash_table[h] = keywords[i]; // 直接存储
} else {
// 冲突,使用线性探测法处理
j = (h + 1) % M;
while (j != h) {
if (hash_table[j] == 0) {
hash_table[j] = keywords[i];
break;
}
j = (j + 1) % M;
}
}
}
// 输出哈希表存储元素关键字
printf("哈希表存储元素关键字为:");
for (i = 0; i < M; i++) {
if (hash_table[i] != 0) {
printf("%d ", hash_table[i]);
}
}
printf("\n");
return 0;
}
```
输出结果为:
```
哈希表存储元素关键字为:16 29 3 20 22 47 7 8 11 92
```
这里使用了一个长度为13的整型数组作为哈希表,初始值为0。对于每个关键字,先通过哈希函数计算出其哈希值,然后判断该位置是否已经有元素存储,如果没有则直接存储,否则使用线性探测法处理冲突。最后按顺序输出哈希表中存储的元素关键字。
阅读全文