C语言 在哈希表中插入节点

Question

下面的代码是正确的，但我不明白为什么2行代码工作。我指的是最后一个else块。具体来说，我指的是这两行:

newWord->next = hashtable[index];
hashtable[index] = newWord;

如果目标是在哈希表的索引处将节点追加到链表，为什么newWord->next指向哈希表的索引，而可能已经有节点在该索引处。我认为它应该是newWord->next = NULL，因为该节点将是链表中的最后一个链接，因此应该指向NULL。从代码中，看起来结构体的"next"字段引用了索引。我希望我说得有道理。/* **载入字典到内存。如果成功返回true，否则返回false。*/

bool load(const char* dictionary)
{
    // TODO
    // opens dictionary
    FILE* file = fopen(dictionary, "r");
    if (file == NULL)
        return false;
// create an array for word to be stored in
char word[LENGTH+1];
// scan through the file, loading each word into the hash table
while (fscanf(file, "%sn", word)!= EOF)
{
    // increment dictionary size
    dictionarySize++;
    // allocate memory for new word 
    node* newWord = malloc(sizeof(node));
    // put word in the new node
    strcpy(newWord->word, word);
    // find what index of the array the word should go in
    int index = hash(word);
    // if hashtable is empty at index, insert
    if (hashtable[index] == NULL)
    {
        hashtable[index] = newWord;
        newWord->next = NULL;
    }
    // if hashtable is not empty at index, append
    else
    {
        newWord->next = hashtable[index];
        hashtable[index] = newWord;
    }      
}

Answer 1

您假定新节点被附加到末尾是错误的。代码将新节点插入到链表的前面，有效地使其成为新的头部。"尾"是旧的列表，它的头现在位于新头之后的节点。

这种插入更快，因为你不需要遍历列表来找到末尾。节点的顺序在这里不重要。

在if (hashtable[index] == NULL)中你甚至不需要区分;您可以将这两种情况合并为一个，即else子句中的代码。