c语言哈希表查找(线性探查法)输入不大于m的n个不为0(0表示空值)的数,用线性探查法解决冲突构造散列表。输入一个值key,在散列表中查找key位置。代码
时间: 2023-12-19 17:15:43 浏览: 89
好的,以下是一个使用C语言实现的哈希表(线性探查法)的代码,可以供你参考:
```c
#include <stdio.h>
#include <stdlib.h>
#define EMPTY 0
#define DELETED -1
typedef struct {
int key;
int value;
} HashTableEntry;
typedef struct {
int size;
HashTableEntry *table;
} HashTable;
HashTable *createHashTable(int size) {
HashTable *ht = (HashTable*) malloc(sizeof(HashTable));
ht->size = size;
ht->table = (HashTableEntry*) calloc(size, sizeof(HashTableEntry));
return ht;
}
void destroyHashTable(HashTable *ht) {
free(ht->table);
free(ht);
}
int hash(int key, int size) {
return key % size;
}
int linearProbe(int key, int size, int i) {
return (hash(key, size) + i) % size;
}
void insert(HashTable *ht, int key, int value) {
int i, index;
for (i = 0; i < ht->size; i++) {
index = linearProbe(key, ht->size, i);
if (ht->table[index].key == EMPTY || ht->table[index].key == DELETED) {
ht->table[index].key = key;
ht->table[index].value = value;
return;
}
}
}
int search(HashTable *ht, int key) {
int i, index;
for (i = 0; i < ht->size; i++) {
index = linearProbe(key, ht->size, i);
if (ht->table[index].key == key) {
return index;
} else if (ht->table[index].key == EMPTY) {
return -1;
}
}
return -1;
}
void printHashTable(HashTable *ht) {
int i;
for (i = 0; i < ht->size; i++) {
printf("%d: %d\n", ht->table[i].key, ht->table[i].value);
}
}
int main() {
int n, m, i, key, value;
HashTable *ht;
printf("Enter the size of the hash table: ");
scanf("%d", &m);
ht = createHashTable(m);
printf("Enter the number of keys: ");
scanf("%d", &n);
printf("Enter the keys and values:\n");
for (i = 0; i < n; i++) {
scanf("%d %d", &key, &value);
insert(ht, key, value);
}
printf("Enter the key you want to search: ");
scanf("%d", &key);
i = search(ht, key);
if (i != -1) {
printf("Key %d is found at position %d.\n", key, i);
} else {
printf("Key %d is not found.\n", key);
}
printHashTable(ht);
destroyHashTable(ht);
return 0;
}
```
在这个代码中,我们定义了一个哈希表的结构体`HashTable`,并使用`createHashTable`函数创建一个指定大小的哈希表。`insert`函数用于向哈希表中插入一个键值对,`search`函数用于在哈希表中查找一个特定的关键字,并返回它在哈希表中的位置。最后,我们使用`printHashTable`函数打印哈希表中所有的键值对,并使用`destroyHashTable`函数释放哈希表的内存。
希望这个回答能够帮助到你,如果你还有其他问题,请继续提问。
阅读全文