K&R表查询代码

Question

尝试理解以下代码,以获得K&R中讨论的简单哈希查找算法的链表/结构实现:

struct nlist *lookup(char *);
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;

我不明白的一些事情.这一行:

np = (struct nlist *) malloc(sizeof(*np));

在if语句将值赋给lookup(name)np之后发生.那么malloc任务有什么作用呢？它是否重新初始化了价值？如果是这样,以下几行怎么办？

if ((np = lookup(name)) == NULL)

如果malloc重新初始化它,它不会总是为空吗？或者malloc是否只是简单地分配内存而不会弄乱先前分配给np的值？如果是这种情况,那么为什么如果np为NULL,如果它已经在初始if语句中执行了那么它为什么再次检查？

说到np->next代码,我完全迷失了.为什么np-> next似乎是指自己？

这是lookup()函数的代码:

/* 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 */
}

这是nlist结构:

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

Answer 1

if ((np = lookup(name)) == NULL)

做两件事.首先,它分配的结果lookup(name)来np.其次,它测试该分配的结果,看它是否是NULL.

如果该if说法属实,这意味着np是NULL,让他们去到malloc它的值.

现在,如果malloc无法分配内存,它将返回NULL.strdup内部调用malloc,这就是下一行的原因

if (np == NULL || (np->name = strdup(name)) == NULL)

确保刚刚发生的两次分配都成功.

你是对的,因为新分配的入口np->next指向它自己.这就是他们如何表明清单的结尾.其他实现用于NULL指示列表末尾.

编辑:我是个傻瓜,你让我说服你错了!

首先,哈希表如下所示:它是一个指向链表的指针表.数组中的索引是哈希值:

现在,当我们添加一个新条目时:

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

hashtab[hashval]已经是具有相同哈希的条目列表的开头.它可能是NULL.此代码将新条目添加到列表的前面!因此,我们将新条目的next指针指向现有列表,并将哈希表设置为指向新条目,因此它现在是第一个.

他们将节点添加到列表的前面,以便插入是O(1)操作.