C语言 在 C 中实现字典的快速方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4384359/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Quick Way to Implement Dictionary in C
提问by Rohit
One of the things which I miss while writing programs in C is a dictionary data structure. What's the most convenient way to implement one in C? I am not looking for performance, but ease of coding it from scratch. I don't want it to be generic either -- something like string->int will do. But I do want it to be able to store an arbitrary number of items.
我在用 C 编写程序时错过的一件事是字典数据结构。在 C 中实现一个最方便的方法是什么？我不是在寻找性能，而是从头开始编写代码的难易程度。我也不希望它是通用的——像 string->int 这样的东西就可以了。但我确实希望它能够存储任意数量的项目。
This is intended more as an exercise. I know that there are 3rd party libraries available which one can use. But consider for a moment, that they don't exist. In such a situation what's the quickest way you can implement a dictionary satisfying the above requirements.
这更像是一种练习。我知道有 3rd 方库可供使用。但是请考虑一下，它们不存在。在这种情况下，实现满足上述要求的字典的最快方法是什么。
采纳答案by Vijay Mathew
Section 6.6 of The C Programming Languagepresents a simple dictionary (hashtable) data structure. I don't think a useful dictionary implementation could get any simpler than this. For your convenience, I reproduce the code here.
The C Programming Language 的第 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 != '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);
}
'; 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 '...
#define K 16 // chaining coefficient
struct dict
{
char *name; /* name of key */
int val; /* value */
struct dict *next; /* link field */
};
typedef struct dict dict;
dict *table[K];
int initialized = 0;
void putval ( char *,int);
void init_dict()
{
initialized = 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)
return ptr->val;
return -1;
}
' */
if (p != NULL)
strcpy(p, s);
return p;
}
Note that if the hashes of two strings collide, it may lead to an O(n)lookup time. You can reduce the likelihood of collisions by increasing the value of HASHSIZE. For a complete discussion of the data structure, please consult the book.
请注意，如果两个字符串的哈希冲突，则可能会导致O(n)查找时间。您可以通过增加 的值来降低发生冲突的可能性HASHSIZE。有关数据结构的完整讨论，请参阅本书。
回答by paxdiablo
The quickestway would be to use an already-existing implementation, like uthash.
该最快的方法是使用一个已经存在的实现，像uthash。
And, if you reallywant to code it yourself, the algorithms from uthashcan be examined and re-used. It's BSD-licensed so, other than the requirement to convey the copyright notice, you're pretty well unlimited in what you can do with it.
而且，如果你真的想自己编码，uthash可以检查和重用来自的算法。它是 BSD 许可的，所以除了传达版权声明的要求之外，你可以用它做什么是无限的。
回答by Paul Hankin
For ease of implementation, it's hard to beat naively searching through an array. Aside from some error checking, this is a complete implementation (untested).
为了便于实现，很难在数组中进行天真搜索。除了一些错误检查，这是一个完整的实现（未经测试）。
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;
}
回答by abc def foo bar
Create a simple hash function and some linked lists of structures , depending on the hash , assign which linked list to insert the value in . Use the hash for retrieving it as well .
创建一个简单的散列函数和一些结构的链表，根据散列，指定要将值插入到哪个链表中。也可以使用散列来检索它。
I did a simple implementation some time back :
前段时间我做了一个简单的实现：
##代码##回答by fkl
I am surprised no one mentioned hsearch/hcreateset of libraries which although is not available on windows, but is mandated by POSIX, and therefore available in Linux / GNU systems.
我很惊讶没有人提到hsearch/hcreate 一组库，它们虽然在 Windows 上不可用，但由 POSIX 强制要求，因此在 Linux/GNU 系统中可用。
The link has a simple and complete basic example that very well explains its usage.
该链接有一个简单而完整的基本示例，很好地解释了它的用法。
It even has thread safe variant, is easy to use and very performant.
它甚至具有线程安全的变体，易于使用且非常高效。
回答by dagoltz
here is a quick implement, i used it to get a 'Matrix'(sruct) from a string. you can have a bigger array and change its values on the run also:
这是一个快速实现，我用它从字符串中获取“矩阵”（结构）。您可以拥有更大的数组并在运行时更改其值：
##代码##回答by Lee
A hashtable is the traditional implementation of a simple "Dictionary". If you don't care about speed or size, just google for it. There are many freely available implementations.
哈希表是简单“字典”的传统实现。如果您不在乎速度或大小，只需google 即可。有许多免费可用的实现。
here's the first one I saw-- at a glance, it looks ok to me. (it's pretty basic. If you really want it to hold an unlimited amount of data, then you'll need to add some logic to "realloc" the table memory as it grows.)
这是我看到的第一个——乍一看，我觉得还可以。（这是非常基本的。如果你真的希望它保存无限量的数据，那么你需要添加一些逻辑来“重新分配”表内存随着它的增长。）
good luck!
祝你好运！
回答by ashmish2
Hashing is the key. I think use lookup table and hashing key for this. You can find many hashing function online.
哈希是关键。我认为为此使用查找表和散列键。你可以在网上找到很多散列函数。
回答by cprogrammer
The quickest method would be using binary tree. Its worst case is also only O(logn).
最快的方法是使用二叉树。它的最坏情况也只有 O(logn)。
