迹忆客 专注技术分享

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

使用 hcreate、hsearch 和 hdestroy 在 C 语言中实现字典功能

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

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

#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