4

尝试理解以下代码，用于实现 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 重新初始化它，它不会总是 NULL 吗？还是 malloc 只是简单地分配内存而不会弄乱之前分配给 np 的值？如果是这种情况，那么如果 np 在初始 if 语句中已经这样做了，为什么还要再次检查 np 是否为 NULL 呢？

说到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 */
};
4

1 回答 1

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

做两件事。首先，它将结果分配给lookup(name)to np。其次，它测试那个赋值的结果，看它是否是NULL.

如果该if陈述为真，则意味着npis NULL，因此他们继续为其malloc赋值。

现在，如果malloc分配内存失败，则返回NULL. strdup内部调用malloc，所以这就是为什么下一行

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

确保刚刚发生的两个分配都成功了。

首先，哈希表看起来像这样：它是一个指向链表的指针表。数组中的索引是哈希值：

在此处输入图像描述

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

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

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

在此处输入图像描述

他们将节点添加到列表的前面，因此插入是一个 O(1) 操作。

于 2013-03-10T05:10:42.180 回答