请用C语言实现hash链表的构建
时间: 2023-08-15 15:42:47 浏览: 18
以下是一个简单的C语言实现哈希链表的构建的示例代码,仅供参考:
```c
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 10
typedef struct node {
int key;
int value;
struct node* next;
} Node;
typedef struct hash_table {
Node* table[HASH_SIZE];
} HashTable;
int hash(int key) {
return key % HASH_SIZE;
}
void put(HashTable* ht, int key, int value) {
int index = hash(key);
Node* node = ht->table[index];
while (node) {
if (node->key == key) {
node->value = value;
return;
}
node = node->next;
}
node = (Node*)malloc(sizeof(Node));
node->key = key;
node->value = value;
node->next = ht->table[index];
ht->table[index] = node;
}
int get(HashTable* ht, int key) {
int index = hash(key);
Node* node = ht->table[index];
while (node) {
if (node->key == key) {
return node->value;
}
node = node->next;
}
return -1;
}
void print_hash_table(HashTable* ht) {
for (int i = 0; i < HASH_SIZE; i++) {
printf("index %d: ", i);
Node* node = ht->table[i];
while (node) {
printf("(%d, %d) ", node->key, node->value);
node = node->next;
}
printf("\n");
}
}
int main() {
HashTable ht;
for (int i = 0; i < HASH_SIZE; i++) {
ht.table[i] = NULL;
}
put(&ht, 1, 10);
put(&ht, 11, 20);
put(&ht, 21, 30);
put(&ht, 2, 40);
put(&ht, 12, 50);
put(&ht, 22, 60);
printf("get(1) = %d\n", get(&ht, 1));
printf("get(11) = %d\n", get(&ht, 11));
printf("get(21) = %d\n", get(&ht, 21));
printf("get(2) = %d\n", get(&ht, 2));
printf("get(12) = %d\n", get(&ht, 12));
printf("get(22) = %d\n", get(&ht, 22));
print_hash_table(&ht);
return 0;
}
```
在这个示例中,我们定义了一个哈希表结构体`HashTable`和一个链表结构体`Node`。`HashTable`中包含一个长度为`HASH_SIZE`的指向`Node`结构体的指针数组,每个指针指向哈希表中一个链表的头节点。`Node`结构体包含一个键值对和一个指向下一个节点的指针。
我们通过hash函数计算键的哈希值,并将键值对插入到哈希表中。当需要查询一个键值对时,我们通过哈希值找到对应的链表,并在链表中查找对应的节点。
该示例中的哈希表使用的是链表法解决哈希冲突的方式。当哈希值相同的键值对需要插入到同一个链表中时,我们将新的键值对插入到链表头部,这样就可以在O(1)时间内完成插入操作。
相关推荐















