我要评论概念：哈希表是一种数据结构，它通过将键映射到数组的某个位置来存储和检索值。
第一步，首先定义节点
typedef struct node {
char *key;
int value;
struct node *next;
} node;这里，我定义的键是字符，value是整数。
第二步，自定义hash算法
int hash(char *key) {
int sum = 0;
for (int i = 0; i < strlen(key); i++) {
sum += key[i];
}
return sum;
}这里的哈希函数是一个简单的求和函数，返回的是键中的每个字符的ascii值相加的和
第三步，创建节点
node *createnode(char *key, int value) {
node *newnode = (node *)malloc(sizeof(node));
newnode->key = strdup(key);
newnode->value = value;
newnode->next = null;
return newnode;
}strdup() 函数将参数 key 指向的字符串复制到一个字符串指针上去，这个字符串指针事先可以没被初始化。在复制时，strdup() 会给这个指针分配空间，使用 malloc() 函数进行分配，如果不再使用这个指针，相应的用 free() 来释放掉这部分空间。
第四步，插入节点
void insert(node **table, char *key, int value) {
int index = hash(key) % table_size;
node *newnode = createnode(key, value);
if (table[index] == null) {
table[index] = newnode;
} else {
node *current = table[index];
while (current->next != null) {
current = current->next;
}
current->next = newnode;
}
}
之前的hash算法%table_size，得出索引，如果索引所在的位置上为null，就直接存放，否则就在当前索引的位置的next上看是否为null，这里用了while循环
第五步，搜索节点
int search(node **table, char *key) {
int index = hash(key) % table_size;
node *current = table[index];
while (current != null) {
if (strcmp(current->key, key) == 0) {
return current->value;
}
current = current->next;
}
return -1;
}搜索节点，同样使用hash函数得到索引，再用 strcmp（）函数来判断，如果为0，那就是那个值。否则就继续while循环找当前索引的下一个，因为存进去的时候就是这样存的。
第六步，删除节点
void freetable(node **table) {
for (int i = 0; i < table_size; i++) {
node *current = table[i];
while (current != null) {
node *temp = current;
current = current->next;
free(temp->key);
free(temp);
}
}
}简单遍历，然后free掉。
完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#define table_size 10
typedef struct node {
char *key;
int value;
struct node *next;
} node;
int hash(char *key) {
int sum = 0;
for (int i = 0; i < strlen(key); i++) {
sum += key[i];
}
return sum;
}
node *createnode(char *key, int value) {
node *newnode = (node *)malloc(sizeof(node));
newnode->key = strdup(key);
newnode->value = value;
newnode->next = null;
return newnode;
}
void insert(node **table, char *key, int value) {
int index = hash(key) % table_size;
node *newnode = createnode(key, value);
if (table[index] == null) {
table[index] = newnode;
} else {
node *current = table[index];
while (current->next != null) {
current = current->next;
}
current->next = newnode;
}
}
int search(node **table, char *key) {
int index = hash(key) % table_size;
node *current = table[index];
while (current != null) {
if (strcmp(current->key, key) == 0) {
return current->value;
}
current = current->next;
}
return -1;
}
void freetable(node **table) {
for (int i = 0; i < table_size; i++) {
node *current = table[i];
while (current != null) {
node *temp = current;
current = current->next;
free(temp->key);
free(temp);
}
}
}
int main() {
node **table = (node **)malloc(table_size * sizeof(node *));
for (int i = 0; i < table_size; i++) {
table[i] = null;
}
insert(table, "apple", 1);
insert(table, "banana", 2);
insert(table, "orange", 3);
printf("apple: %d\n", search(table, "apple"));
printf("banana: %d\n", search(table, "banana"));
printf("orange: %d\n", search(table, "orange"));
printf("grape: %d\n", search(table, "grape"));
freetable(table);
return 0;
}
运行结果：
发表评论