作者：爱的甜蜜日记2010 | 来源：互联网 | 2023-05-18 02:04
Section 6.6 of K&R discusses a hash table using a linked list.
K&R的6.6节讨论了使用链表的哈希表。
In short, a hash table is an array of pointers. The pointers point to a linked list. The linked list is a struct that looks like:
简而言之,哈希表是一个指针数组。指针指向链表。链表是一个结构,看起来像:
struct nlist { /* table entry: */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};
The name is hashed, and this hash determines the index in the table. The chapter then shows code to add a name/defn pair to the table:
名称经过哈希处理,此哈希值确定表中的索引。然后,本章将显示向表中添加名称/ defn对的代码:
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;
}
Everything makes sense except for the following 2 lines:
除了以下两行之外,一切都有意义:
np->next = hashtab[hashval];
hashtab[hashval] = np;
When I try to understand this, I keep coming to the conclusion that the list now links back to itself and if you try to traverse the linked list it will be like a dog chasing its own tail. I would expect the code to set np->next to NULL.
当我试图理解这一点时,我不断得出结论,列表现在链接回自己,如果你试图遍历链表,它就像一条狗追逐自己的尾巴。我希望代码将np->设置为NULL。
What am I not understanding? How come this code works ?
我不明白的是什么?为什么这段代码有效?
4 个解决方案
京公网安备 11010802041100号