在C语言中实现字典的捷径

在C中编写程序时我想念的一件事是字典数据结构。 用C实现一个最方便的方法是什么？ 我不是在寻找性能，而是从头开始编码。 我不希望它是通用的 – 就像string-> int会做。 但我确实希望能够存储任意数量的项目。

这更像是一个练习。 我知道有第三方库可供使用。 但是考虑一下，他们不存在。 在这种情况下，可以用最快的方法来实现满足上述要求的字典。

Answer 1

C语言的 6.6节提供了一个简单的字典（散列表）数据结构。 我不认为一个有用的字典实现可以得到比这更简单的。 为了您的方便，我在这里重现了代码。

struct nlist { /* table entry: */ struct nlist *next; /* next entry in chain */ char *name; /* defined name */ char *defn; /* replacement text */ }; #define HASHSIZE 101 static struct nlist *hashtab[HASHSIZE]; /* pointer table */ /* hash: form hash value for string s */ unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31 * hashval; return hashval % HASHSIZE; } /* lookup: look for s in hashtab */ struct nlist *lookup(char *s) { struct nlist *np; for (np = hashtab[hash(s)]; np != NULL; np = np->next) if (strcmp(s, np->name) == 0) return np; /* found */ return NULL; /* not found */ } char *strdup(char *); /* install: put (name, defn) in hashtab */ struct nlist *install(char *name, char *defn) { struct nlist *np; unsigned hashval; if ((np = lookup(name)) == NULL) { /* not found */ np = (struct nlist *) malloc(sizeof(*np)); if (np == NULL || (np->name = strdup(name)) == NULL) return NULL; hashval = hash(name); np->next = hashtab[hashval]; hashtab[hashval] = np; } else /* already there */ free((void *) np->defn); /*free previous defn */ if ((np->defn = strdup(defn)) == NULL) return NULL; return np; } char *strdup(char *s) /* make a duplicate of s */ { char *p; p = (char *) malloc(strlen(s)+1); /* +1 for '\0' */ if (p != NULL) strcpy(p, s); return p; } 

请注意，如果两个string的散列相冲突，则可能导致O(n)查找时间。 您可以通过增加HASHSIZE的值来降低碰撞的可能性。 有关数据结构的完整讨论，请参阅本书。

Answer 2

最快的方法是使用已有的实现，如uthash 。

而且，如果您真的想自己编写代码，则可以检查并重新使用uthash的algorithm。 这是BSD的许可证，除了要求传达版权声明之外，你可以用它做的事情是无限的。

Answer 3

为了便于实现，很难打败数组。 除了一些错误检查，这是一个完整的实现（未经testing）。

 typedef struct dict_entry_s { const char *key; int value; } dict_entry_s; typedef struct dict_s { int len; int cap; dict_entry_s *entry; } dict_s, *dict_t; int dict_find_index(dict_t dict, const char *key) { for (int i = 0; i < dict->len; i++) { if (!strcmp(dict->entry[i], key)) { return i; } } return -1; } int dict_find(dict_t dict, const char *key, int def) { int idx = dict_find_index(dict, key); return idx == -1 ? def : dict->entry[idx].value; } void dict_add(dict_t dict, const char *key, int value) { int idx = dict_find_index(dict, key); if (idx != -1) { dict->entry[idx].value = value; return; } if (dict->len == dict->cap) { dict->cap *= 2; dict->entry = realloc(dict->entry, dict->cap * sizeof(dict_entry_s)); } dict->entry[dict->len].key = strdup(key); dict->entry[dict->len].value = value; dict->len++; } dict_t dict_new(void) { dict_s proto = {0, 10, malloc(10 * sizeof(dict_entry_s))}; dict_t d = malloc(sizeof(dict_s)); *d = proto; return d; } void dict_free(dict_t dict) { for (int i = 0; i < dict->len; i++) { free(dict->entry[i].key); } free(dict->entry); free(dict); } 

Answer 4

创build一个简单的哈希函数和一些链接的结构列表（取决于哈希），分配哪个链接列表来插入值。 使用散列来检索它。

我回头做了一个简单的实现：

 ...
 #define K 16 //链接系数

结构字典
 {
     char *名字;  / *密钥的名称* /
     int val;  / *值* /
     struct dict * next;  / *链接字段* /
 };

 typedef struct dict dict;
字典*表[K];
 int initialized = 0;


 void putval（char *，int）;

 void init_dict（）
 {   
    初始化= 1;
     int i;  
     for（i = 0; iname =（char *）malloc（strlen（key_name）+1）;
     ptr-> val = sval;
     strcpy（ptr-> name，key_name）;


     ptr-> next =（struct dict *）table [hsh];
     table [hsh] = ptr;

 }


 int getval（char * key_name）
 {   
     int hsh = hash（key_name）;   
     dict * ptr;
     for（ptr = table [hsh]; ptr！=（dict *）0;
         ptr =（dict *）ptr-> next）
     if（strcmp（ptr-> name，key_name）== 0）
        返回ptr-> val;
    返回-1;
 }

Answer 5

这里是一个快速的实现，我用它来从string中获得“matrix”（sruct）。 你可以有一个更大的数组，并在运行中更改其值：

 typedef struct { int** lines; int isDefined; }mat; mat matA, matB, matC, matD, matE, matF; /* an auxilary struct to be used in a dictionary */ typedef struct { char* str; mat *matrix; }stringToMat; /* creating a 'dictionary' for a mat name to its mat. lower case only! */ stringToMat matCases [] = { { "mat_a", &matA }, { "mat_b", &matB }, { "mat_c", &matC }, { "mat_d", &matD }, { "mat_e", &matE }, { "mat_f", &matF }, }; mat* getMat(char * str) { stringToMat* pCase; mat * selected = NULL; if (str != NULL) { /* runing on the dictionary to get the mat selected */ for(pCase = matCases; pCase != matCases + sizeof(matCases) / sizeof(matCases[0]); pCase++ ) { if(!strcmp( pCase->str, str)) selected = (pCase->matrix); } if (selected == NULL) printf("%s is not a valid matrix name\n", str); } else printf("expected matrix name, got NULL\n"); return selected; } 

Answer 6

散列表是一个简单的“字典”的传统实现。 如果你不关心速度或大小，只是谷歌 。 有许多免费的实现。

这是我看到的第一个 – 一眼看上去对我来说很好。 （这是非常基本的，如果你真的想要它保存无限量的数据，那么你需要添加一些逻辑来“重新分配”表内存。

祝你好运！

Answer 7

GLib和gnulib

如果您没有更具体的要求，这些是您可能的最佳投注，因为它们广泛可用，便携且可能高效。

• GLib：GNOME项目的https://developer.gnome.org/glib/ 。 在https://developer.gnome.org/glib/stable/glib-data-types.html上logging了几个容器，包括“哈希表”和“平衡二叉树”。; 许可证：LGPL

• gnulib：GNU工程https://www.gnu.org/software/gnulib/ 。 您的意思是将源代码复制粘贴到您的代码中。 有几个容器logging在： https ://www.gnu.org/software/gnulib/MODULES.html#ansic_ext_container，包括“rbtree-list”，“linkedhash-list”和“rbtreehash-list”。 GPL许可证。

另请参阅： 是否有任何开放源码的C库具有通用的数据结构？

Answer 8

散列是关键。 我认为使用查找表和哈希键为此。 你可以在网上find很多散列函数。

Answer 9

最快的方法是使用二叉树。 最坏的情况也只有O（logn）。

Answer 10

我很惊讶没有人提到hsearch / hcreate的一套库，虽然没有在Windows上可用，但标准与Linux / GNU

它甚至具有线程安全变体，易于使用和性能高。