快速的方式在C实现词典 [英] Quick Way to Implement Dictionary in C

问题描述

一，而用C写程序，我怀念的东西是一本字典的数据结构。什么是实现一个在C中最便捷的方式？我不是在寻找性能，但缓解从头开始对其进行编码的。我不希望它是通用的两种 - 像与字符串>内部会做。但我希望它能够存储物品任意数量。

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.

这是为了更多的练习。我知道有第三方库提供哪些人可以使用。但是，考虑了一会儿，他们不存在。在这种情况下什么是最快的方式，你可以实现一个字典满足上述要求。

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.

推荐答案

C程序设计语言 presents一个简单的字典（哈希表）的数据结构。我不认为一个有用的字典实现可以得到任何比这更简单。为方便起见，我在这里重现code。

Section 6.6 of The C Programming Language presents 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.

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 的价值减少冲突的可能性。对于数据结构的完整论述，请参阅本书。

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.

这篇关于快速的方式在C实现词典的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！