在 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
