用C语言实现字典的快速方法
用C语言实现字典的快速方法
提问于 2010-12-08 05:08:20
在用C编写程序时，我所怀念的事情之一就是字典数据结构。在C中实现一种最方便的方法是什么？我并不是在寻找性能，而是从零开始编写代码的容易程度。我也不希望它是通用的--比如char*→int就行了。但我确实希望它能够存储任意数量的物品。
这更多的是作为一种练习。我知道有第三方图书馆可以使用。但请考虑一下，它们并不存在。在这种情况下，实现满足上述要求的字典的最快方法是什么。
回答 11
Stack Overflow用户
回答已采纳
发布于 2010-12-08 05:26:28
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;
}请注意，如果两个字符串的散列发生冲突，则可能会导致O(n)查找时间。您可以通过增加HASHSIZE的值来减少碰撞的可能性。有关数据结构的完整讨论，请参阅本书。
Stack Overflow用户
发布于 2010-12-08 05:12:41
最快的方法是使用已经存在的实现，比如乌塔什。
而且，如果您真的想自己编写代码，可以检查和重用来自uthash的算法。这是BSD许可的，所以，除了传达版权通知的要求之外，你完全可以不受限制地使用它。
Stack Overflow用户
发布于 2013-04-21 08:08:57
为了便于实现，很难绕过对数组的天真搜索。除了一些错误检查之外，这是一个完整的实现(未经测试)。
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);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4384359
复制相关文章
相似问题
腾讯云开发者
