在 C 语言中实现字典
Jinku Hu
2023年10月12日
本文将演示关于如何在 C 语言中实现字典的多种方法。
使用 hcreate、hsearch 和 hdestroy 在 C 语言中实现字典功能
一般来说，C 标准库不包含内置的字典数据结构，但 POSIX 标准规定了哈希表管理例程，可以利用这些例程来实现字典功能。即：hcreate、hsearch 和 hdestroy 提供了创建哈希表、在表中插入项、在表中搜索项以及对整个数据结构进行重新分配等功能。尽管实现的功能是最基本的，但它可以解决很多问题场景。
首先，需要调用 hcreate 函数来创建一个给定最大元素数的哈希表，该表作为唯一的参数传递。需要注意的是，在 hcreate 调用后，容量是不能修改的，因此，用户需要在代码结构中考虑这个问题。一旦创建了表，就可以调用 hsearch 函数向其中添加元素。它需要 2 个参数；第一个参数的类型是 ENTRY，定义为 struct，其中 char*为键，void*为对应的数据。第二个参数的类型是 ACTION，本质上是一个 enum，由 FIND 和 ENTER 两个元素组成。后面的值用来指示对表进行什么操作。
#include <search.h>
#include <stdio.h>
#include <stdlib.h>
static char *companies[] = {"Intel", "AMD", "ARM", "Apple",
"Marvell", "Qualcomm", "IBM", "Nvidia"};
static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
"ThunderX2", "Kryo", "z15", "Ampere"};
int main(void) {
ENTRY e;
ENTRY *ep;
const size_t capacity = sizeof companies / sizeof companies[0];
hcreate(capacity);
for (size_t i = 0; i < capacity - 2; i++) {
e.key = companies[i];
e.data = (void *)uarch[i];
ep = hsearch(e, ENTER);
if (ep == NULL) {
fprintf(stderr, "entry failed\n");
exit(EXIT_FAILURE);
}
}
e.key = "Intel";
ep = hsearch(e, FIND);
printf("%s -> %s\n", e.key, (char *)ep->data);
hdestroy();
exit(EXIT_SUCCESS);
}
输出：
Intel -> Willow Cove
注意，这些代码示例演示了用明文表示的键/值对，但用户可以使用哈希算法来创建键并将其存储在表中。在本例中，我们使用简单的迭代向表中添加了 6 个元素，并跳过了最后两个元素。不过接下来的 for 循环，会查询原始数组中的每一个元素，并打印出相应的数据。
hdestroy 函数是用来释放哈希表内存的，但它并不释放 ENTRY 对象中的缓冲区，这些对象通常是由用户创建的。因此，如果这些对象中的指针指向动态内存，调用者要负责为它们保留句柄，并在程序退出前进行解除分配。注意，不能从表中删除单个元素。
#include <search.h>
#include <stdio.h>
#include <stdlib.h>
static char *companies[] = {"Intel", "AMD", "ARM", "Apple",
"Marvell", "Qualcomm", "IBM", "Nvidia"};
static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
"ThunderX2", "Kryo", "z15", "Ampere"};
int main(void) {
ENTRY e;
ENTRY *ep;
const size_t capacity = sizeof companies / sizeof companies[0];
hcreate(capacity);
for (size_t i = 0; i < capacity - 2; i++) {
e.key = companies[i];
e.data = (void *)uarch[i];
ep = hsearch(e, ENTER);
if (ep == NULL) {
fprintf(stderr, "entry failed\n");
exit(EXIT_FAILURE);
}
}
for (size_t i = 0; i < capacity; i++) {
e.key = companies[i];
ep = hsearch(e, FIND);
ep ? printf("%s -> %s\n", e.key, (char *)ep->data)
: printf("%s -> %s\n", e.key, "Entry not found");
}
hdestroy();
exit(EXIT_SUCCESS);
}
输出：
Intel -> Willow Cove
AMD -> Zen 3
ARM -> A78
Apple -> A14
Marvell -> ThunderX2
Qualcomm -> Kryo
IBM -> Entry not found
Nvidia -> Entry not found
