c - K&R 在这里用这个链表做什么？

Question

我在用 C 语言的字典做一个 hackerRank 挑战，我从 K&R 书中撕下了一些代码。我不明白他们是如何在哈希表中建立一个链表桶的？在我看来，他们正在将 next 指针链接到链表的头部。他们是否以某种我没有捕捉到的方式创造了一个水桶？ np 是一个三成员结构体，包含一个字符串(name,defn) 和指向下一个的指针，查找 np 是否存在于字典中。

if ((np = lookup(name)) == NULL){ // file not found
    np = (struct nlist *) malloc(sizeof(*np));
    if (NULL == np || (np->name = strdup(name)) == NULL){
        return NULL;
    }
    hashval = hash(name);
    np->next = hashtab[hashval]; // WHAT THE HECK ARE THEY DOING HERE?!?!
    hashtab[hashval] = np;
}else{ // already there
    free((void *)np->defn);
}
if((np->defn = strdup(defn)) == NULL){
    return NULL;
}
return np;

我按如下方式修改了代码以使其正常工作，但我有一种挥之不去的感觉，他们错过了他们试图表达的观点。

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);
    phE->next = NULL; //if first entry set next to NULL, MOD HERE
    tmpNode = hashtab[hashval]; 
    if (tmpNode == NULL){ // EMPTY SPOT IN HASHTABLE
        hashtab[hashval] = np;
    }else{                         //HASH COLLISION, ADD NODE TO LIST END
        while (tmpNode->next != NULL){
            tmpNode = tmpNode->next;
        }
        tmpNode->next = np;
    }
}else{
    free((void *) np->defn);
}
if ((np->defn = strdup(defn)) == NULL){
    return NULL;
}
return np;

Answer 1

让我们跟踪这段代码，看看它做了什么:

np->next = hashtab[hashval]; // WHAT THE HECK ARE THEY DOING HERE?!?!
hashtab[hashval] = np;

最初，我们的哈希表看起来像这样:

    +---+---+---+---   ---+---------+---+---+---+
    |   |   |   |   ...   | hashval |   |   |   |
    +---+---+---+---   ---+---------+---+---+---+
                              |
                              |
                              |      +------+    +-----+
                              +----> | head | -> | ... |
                                     +------+    +-----+

这是np:

    +---+---+---+---   ---+---------+---+---+---+
    |   |   |   |   ...   | hashval |   |   |   |
    +---+---+---+---   ---+---------+---+---+---+
                              |
                              |
                 +-----+      |      +------+    +-----+
           np -> |     |      +----> | head | -> | ... |
                 +-----+             +------+    +-----+

现在，我们设置 np->next = hashtab[hashval]。现在事情看起来像这样:

    +---+---+---+---   ---+---------+---+---+---+
    |   |   |   |   ...   | hashval |   |   |   |
    +---+---+---+---   ---+---------+---+---+---+
                              |
                              |
                 +-----+      |      +------+    +-----+
           np -> |     |------+----> | head | -> | ... |
                 +-----+             +------+    +-----+

现在，新创建的单元格的 next 指针和 hashtab[hashval] 都指向同一事物。从 np 的角度来看，它现在指向通过预先添加新单元格然后使用所有现有单元格形成的列表。

最后，我们执行 hashtab[hashval] = np，如下所示:

    +---+---+---+---   ---+---------+---+---+---+
    |   |   |   |   ...   | hashval |   |   |   |
    +---+---+---+---   ---+---------+---+---+---+
                              |
                    +---------+
                    |
                    v         
                 +-----+             +------+    +-----+
           np -> |     |-----------> | head | -> | ... |
                 +-----+             +------+    +-----+

这会将新元素拼接到链表的前面。

换句话说，这是一个非常典型的列表前缀，通过使用链表指针数组变得有点棘手。