设计一个程序,运用C语言,实现哈希表的相关运算 1.建立含有十一个整数的哈希表(数据自行设计),表长为13, A[0...12],哈希函数为H(K)=key mod P,并采用线性探测法解决冲突。 2.对该哈希表进行查找成功的数据测试 3.对该哈希表进行删除操作 4.对该哈希表进行插入操作(查找失败后进行插入)
时间: 2024-03-15 09:46:09 浏览: 82
好的,以下是针对您的问题的答案:
```c
#include <stdio.h>
#include <stdlib.h>
// 哈希表长度
#define HASH_TABLE_SIZE 13
// 哈希表元素
typedef struct {
int key;
} HashTableItem;
// 哈希表
HashTableItem hashTable[HASH_TABLE_SIZE];
// 哈希函数
int hashFunction(int key) {
return key % HASH_TABLE_SIZE;
}
// 插入元素
void insert(int key) {
int index = hashFunction(key);
while (hashTable[index].key != 0 && hashTable[index].key != key) {
index = (index + 1) % HASH_TABLE_SIZE;
}
hashTable[index].key = key;
}
// 查找元素
int search(int key) {
int index = hashFunction(key);
while (hashTable[index].key != 0) {
if (hashTable[index].key == key) {
return index;
}
index = (index + 1) % HASH_TABLE_SIZE;
}
return -1;
}
// 删除元素
void delete(int key) {
int index = search(key);
if (index != -1) {
hashTable[index].key = 0;
}
}
int main() {
// 初始化哈希表
for (int i = 0; i < HASH_TABLE_SIZE; i++) {
hashTable[i].key = 0;
}
// 待插入的数据
int data[] = {12, 3, 27, 8, 9, 11, 13, 7, 4, 23, 35};
// 插入数据
for (int i = 0; i < sizeof(data) / sizeof(data[0]); i++) {
insert(data[i]);
}
// 查找数据
int key = 11;
int index = search(key);
if (index == -1) {
printf("数据 %d 不存在\n", key);
} else {
printf("数据 %d 的索引为 %d\n", key, index);
}
// 删除数据
delete(key);
printf("数据 %d 已被删除\n", key);
// 插入数据
key = 10;
index = search(key);
if (index == -1) {
insert(key);
printf("数据 %d 已插入\n", key);
} else {
printf("数据 %d 已存在\n", key);
}
return 0;
}
```
上述代码中,我们使用了一个哈希表 `hashTable` 来表示哈希表,元素类型为 `HashTableItem`,其中包含一个整数关键字 `key`。我们使用 `hashFunction(key)` 函数来计算哈希值,并使用线性探测法解决冲突。具体来说,我们将待插入数据 `key` 的哈希值 `index` 计算出来,如果 `hashTable[index].key` 已经被占用了,就继续往下找,直到找到一个空位。
查找元素时,我们使用 `search(key)` 函数来查找关键字 `key` 是否存在于哈希表中。具体来说,我们计算关键字 `key` 的哈希值 `index`,并从 `hashTable[index]` 开始往下找,直到找到一个空位或者找到关键字 `key`。
删除元素时,我们使用 `delete(key)` 函数来删除关键字 `key` 在哈希表中的元素。具体来说,我们先使用 `search(key)` 函数查找关键字 `key` 的索引 `index`,如果找到了就将 `hashTable[index].key` 设为0,表示该位置上的数据已被删除。
插入元素时,我们首先使用 `search(key)` 函数查找关键字 `key` 是否已经存在于哈希表中。如果不存在,就使用 `insert(key)` 函数将关键字 `key` 插入到哈希表中。如果已经存在,就输出提示信息。
在 `main` 函数中,我们首先初始化哈希表,然后插入数据。接着,我们分别测试查找、删除、插入操作,并输出相应的提示信息。
阅读全文