c语言实现HashTable

简介: 本文介绍了如何在C语言中实现哈希表(HashTable),包括定义节点结构、自定义哈希函数、创建节点、插入节点、搜索节点和删除节点的完整过程。

概念:哈希表是一种数据结构,它通过将键映射到数组的某个位置来存储和检索值。

第一步,首先定义节点

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;
}

运行结果:

目录
相关文章
|
6月前
|
存储 C语言
C语言简单实现Hashtable
hashtable是根据key查询value的一种数据结构,使用数组结构来存储所有的元素,使用一种方式将key映射到数组的不同下标,查询时key就可以直接映射到value,时间复杂度为O(1),因此,hashtable结构经常用于查询的目的。
39 0
|
23天前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
30 3
|
13天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
30 10
|
7天前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。
|
12天前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
35 7
|
12天前
|
存储 编译器 程序员
【c语言】函数
本文介绍了C语言中函数的基本概念,包括库函数和自定义函数的定义、使用及示例。库函数如`printf`和`scanf`,通过包含相应的头文件即可使用。自定义函数需指定返回类型、函数名、形式参数等。文中还探讨了函数的调用、形参与实参的区别、return语句的用法、函数嵌套调用、链式访问以及static关键字对变量和函数的影响,强调了static如何改变变量的生命周期和作用域,以及函数的可见性。
25 4
|
17天前
|
存储 编译器 C语言
C语言函数的定义与函数的声明的区别
C语言中,函数的定义包含函数的实现,即具体执行的代码块;而函数的声明仅描述函数的名称、返回类型和参数列表,用于告知编译器函数的存在,但不包含实现细节。声明通常放在头文件中,定义则在源文件中。
|
23天前
|
C语言
c语言回顾-函数递归(上)
c语言回顾-函数递归(上)
30 2
|
25天前
|
Java 编译器 C语言
【一步一步了解Java系列】:Java中的方法对标C语言中的函数
【一步一步了解Java系列】:Java中的方法对标C语言中的函数
18 3
|
28天前
|
存储 程序员 编译器
C语言——动态内存管理与内存操作函数
C语言——动态内存管理与内存操作函数