内容:编写一个程序 exp9-5.c cpp 实现哈希表的相关运算,并完成以下功能。 (1)建立关键字序列(16,74,60,43,54,90,46,31,29,88,77)对应的哈希表A[0..12],哈希函数为 H(k)=k%p,并采用开放地址法中的线性探测法解决冲突。 (2)在上述哈希表中查找关键字为29的记录。 (3)在上述哈希表中删除关键字为77的记录,再将其插入。
时间: 2024-03-11 10:46:54 浏览: 59
很抱歉,我无法编写和运行程序。但是,我可以提供伪代码来帮助你理解哈希表的相关操作。
建立哈希表:
```
#define SIZE 13
int A[SIZE] = {0}; // 初始化哈希表为0
int H(int key) {
return key % SIZE; // 哈希函数,对于关键字key,返回其余数
}
void insert(int key) {
int index = H(key);
int i = 0;
while (A[(index + i) % SIZE] != 0) { // 线性探测法,探测下一个空位置
i++;
}
A[(index + i) % SIZE] = key; // 插入关键字
}
void print() {
for (int i = 0; i < SIZE; i++) {
printf("%d ", A[i]); // 输出哈希表
}
printf("\n");
}
int main() {
int keys[] = {16,74,60,43,54,90,46,31,29,88,77};
for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
insert(keys[i]); // 建立哈希表
}
print(); // 输出哈希表
return 0;
}
```
查找关键字:
```
int search(int key) {
int index = H(key);
int i = 0;
while (A[(index + i) % SIZE] != key && A[(index + i) % SIZE] != 0) { // 线性探测法,查找关键字
i++;
}
if (A[(index + i) % SIZE] == key) {
return (index + i) % SIZE; // 返回关键字所在位置
} else {
return -1; // 关键字不存在
}
}
int main() {
int keys[] = {16,74,60,43,54,90,46,31,29,88,77};
for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
insert(keys[i]);
}
print();
int index = search(29); // 查找关键字29
printf("Index of 29: %d\n", index);
return 0;
}
```
删除和插入关键字:
```
void delete(int key) {
int index = search(key); // 先查找关键字所在位置
if (index != -1) {
A[index] = 0; // 删除关键字
}
}
int main() {
int keys[] = {16,74,60,43,54,90,46,31,29,88,77};
for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
insert(keys[i]);
}
print();
int index = search(77); // 查找关键字77
printf("Index of 77: %d\n", index);
delete(77); // 删除关键字77
insert(77); // 插入关键字77
print();
return 0;
}
```
希望这些伪代码能够帮助你理解哈希表的相关操作。
阅读全文