在 C 语言中实现字典

本文将演示关于如何在 C 语言中实现字典的多种方法。

使用 hcreatehsearchhdestroy 在 C 语言中实现字典功能

一般来说,C 标准库不包含内置的字典数据结构,但 POSIX 标准规定了哈希表管理例程,可以利用这些例程来实现字典功能。即:hcreatehsearchhdestroy 提供了创建哈希表、在表中插入项、在表中搜索项以及对整个数据结构进行重新分配等功能。尽管实现的功能是最基本的,但它可以解决很多问题场景。

首先,需要调用 hcreate 函数来创建一个给定最大元素数的哈希表,该表作为唯一的参数传递。需要注意的是,在 hcreate 调用后,容量是不能修改的,因此,用户需要在代码结构中考虑这个问题。一旦创建了表,就可以调用 hsearch 函数向其中添加元素。它需要 2 个参数;第一个参数的类型是 ENTRY,定义为 struct,其中 char*为键,void*为对应的数据。第二个参数的类型是 ACTION,本质上是一个 enum,由 FINDENTER 两个元素组成。后面的值用来指示对表进行什么操作。

#include <stdio.h>#include <stdlib.h>#include <search.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 <stdio.h>#include <stdlib.h>#include <search.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