在用C语言编写程序时，我错过了一件事，那就是字典数据 struct .用C语言实现的最方便的方式是什么？我不是在寻找性能，而是从头开始编码的简便性.我也不希望它是通用的--大约char*→int就可以了.但我确实希望它能够存储任意数量的物品.
这更像是一种练习.我知道有第三方图书馆可以使用.但是考虑一下，它们不存在.在这种情况下，实现满足上述要求的词典的最快方法是什么.
在用C语言编写程序时，我错过了一件事，那就是字典数据 struct .用C语言实现的最方便的方式是什么？我不是在寻找性能，而是从头开始编码的简便性.我也不希望它是通用的--大约char*→int就可以了.但我确实希望它能够存储任意数量的物品.
这更像是一种练习.我知道有第三方图书馆可以使用.但是考虑一下，它们不存在.在这种情况下，实现满足上述要求的词典的最快方法是什么.
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来降低碰撞的可能性.有关数据 struct 的完整讨论，请参阅本书.