hash表c语言链地址法
时间: 2023-10-26 07:02:18 浏览: 45
哈希表是一种数据结构,用于实现字典或映射。哈希表使用哈希函数将键映射到存储桶中,以便快速查找值。链地址法是哈希表的一种实现方式,它使用链表来解决哈希冲突的问题。下面是使用链地址法实现哈希表的C语言代码示例:
首先,定义一个哈希表节点的结构体:
```
typedef struct HashNode{
int key;
int value;
struct HashNode* next;
}HashNode;
```
哈希表节点包含键值对和一个指向下一个节点的指针。
接着,定义一个哈希表的结构体:
```
typedef struct HashTable{
int size;
HashNode** table;
}HashTable;
```
哈希表包含一个大小和一个指向指针数组的指针。
接下来,实现哈希函数,将键映射到存储桶中:
```
int hash(int key, int size){
return key % size;
}
```
这里使用取模运算将键映射到存储桶中。
然后,实现哈希表的初始化函数:
```
HashTable* createHashTable(int size){
HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
ht->size = size;
ht->table = (HashNode**)malloc(sizeof(HashNode*) * size);
for(int i = 0; i < size; i++){
ht->table[i] = NULL;
}
return ht;
}
```
这里使用malloc动态分配哈希表和指针数组的内存空间,并将指针数组中的元素初始化为NULL。
接下来,实现插入操作:
```
void insert(HashTable* ht, int key, int value){
int index = hash(key, ht->size);
HashNode* node = (HashNode*)malloc(sizeof(HashNode));
node->key = key;
node->value = value;
node->next = ht->table[index];
ht->table[index] = node;
}
```
这里首先使用哈希函数计算键的索引,然后创建一个新的哈希节点并将其插入到链表的头部。
最后,实现查找操作:
```
int search(HashTable* ht, int key){
int index = hash(key, ht->size);
HashNode* node = ht->table[index];
while(node != NULL){
if(node->key == key){
return node->value;
}
node = node->next;
}
return -1;
}
```
这里首先使用哈希函数计算键的索引,然后遍历该索引处的链表,查找对应的键值对。如果找到,则返回其值,否则返回-1。
以上就是使用链地址法实现哈希表的C语言代码示例。