用c写出散列查找的代码实现,并在重要代码旁添加注释
时间: 2024-02-05 21:13:13 浏览: 55
用c语言设计查找算法
下面是使用C语言实现散列查找的代码,注释已经添加在重要代码旁边:
```c
#include<stdio.h>
#include<stdlib.h>
#define SIZE 10 //散列表的大小
struct node {
int data;
struct node *next;
};
struct node *hash_table[SIZE]; //散列表
//计算散列值
int hash_func(int data) {
return data % SIZE;
}
//插入数据
void insert(int data) {
int pos = hash_func(data); //计算散列值
struct node *new_node = (struct node*) malloc(sizeof(struct node)); //分配新节点内存空间
new_node->data = data;
new_node->next = NULL;
if(hash_table[pos] == NULL) { //如果这个位置没有数据,则直接插入
hash_table[pos] = new_node;
} else { //如果这个位置已经有数据,则采用链式结构
struct node *tmp = hash_table[pos];
while(tmp->next != NULL) { //遍历链表,找到最后一个节点
tmp = tmp->next;
}
tmp->next = new_node; //将新节点插入到链表的末尾
}
}
//查找数据
struct node* search(int data) {
int pos = hash_func(data); //计算散列值
struct node *tmp = hash_table[pos];
while(tmp != NULL) { //遍历链表,查找与data相等的节点
if(tmp->data == data) {
return tmp; //找到了,返回节点指针
}
tmp = tmp->next;
}
return NULL; //没找到,返回NULL
}
//打印所有数据
void print() {
printf("散列表中的数据:\n");
for(int i=0; i<SIZE; i++) {
printf("%d: ", i);
struct node *tmp = hash_table[i];
while(tmp != NULL) {
printf("%d ", tmp->data);
tmp = tmp->next;
}
printf("\n");
}
}
int main() {
//初始化散列表
for(int i=0; i<SIZE; i++) {
hash_table[i] = NULL;
}
//插入数据
insert(10);
insert(20);
insert(30);
insert(40);
insert(50);
//查找数据
struct node *data1 = search(20);
if(data1 != NULL) {
printf("查找到数据:%d\n", data1->data);
} else {
printf("未找到数据!\n");
}
//打印所有数据
print();
return 0;
}
```
在这个代码中,我们使用了一个结构体来表示一个节点,该节点包含了数据以及指向下一个节点的指针。我们使用一个指针数组来表示散列表,每个数组元素都指向一个链表的头节点。如果一个位置没有数据,则该位置的指针为NULL。
插入数据时,我们先计算出数据的散列值,然后判断该位置是否已经有数据,如果没有则直接插入,如果有则采用链式结构将新数据插入到链表的末尾。
查找数据时,我们先计算出数据的散列值,然后遍历该位置的链表,查找与数据相等的节点。
最后,我们还实现了一个打印所有数据的函数,用于检查散列表中的数据是否正确。
阅读全文