k&r的表查找安装功能

Question

K&R的6.6节讨论了使用链表的哈希表.

简而言之,哈希表是一个指针数组.指针指向链表.链表是一个结构,看起来像:

struct nlist {             /* table entry: */
    struct nlist *next;    /* next entry in chain */
    char *name;            /* defined name */
    char *defn;            /* replacement text */
};

名称经过哈希处理,此哈希值确定表中的索引.然后,本章将显示向表中添加名称/ 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;
}

除了以下两行之外,一切都有意义:

np->next = hashtab[hashval];
hashtab[hashval] = np;

当我试图理解这一点时,我不断得出结论,列表现在链接回自己,如果你试图遍历链表,它将像一条狗追逐自己的尾巴.我希望代码将np->设置为NULL.

我不明白的是什么？为什么这段代码有效？

Answer 1

它导致新值插入列表的开头.

所以它来自:

hashtab[hashval]   -->  original_list

至:

hashtab[hashval]   -->  original_list
np->next           -->  original_list

至:

hashtab[hashval]  -->  *np
        np->next  -->  original_list

黄金法则是,如果链表代码没有意义,总是绘制出一个图表!