在哈希表中插入一個節點

下面的代碼是正確的，但我不明白爲什麼有兩行代碼工作。我指的是最後一個塊。具體來說，我指的是這兩行：在哈希表中插入一個節點

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

如果目標是在散列表的索引處追加節點到鏈表，爲什麼newWord-> next在假定節點已經在該索引處時指向散列表的索引。我認爲它應該是newWord-> next = NULL，因爲該節點將是鏈接列表中的最後一個鏈接，因此應該指向NULL。從代碼看來，結構的「下一個」字段引用索引。我希望我有道理。 /** *將字典載入內存。如果成功則返回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, "%s\n", 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; 
    }  
}

來源

2015-08-15 Jón Árnason

你的假設，即新節點追加到結尾是錯誤的。該代碼將新節點插入鏈表的前端，使其成爲新的頭部。「尾巴」是舊名單，其頭部現在是新頭後的節點。

這種插入速度更快，因爲您不必走列表來找到結尾。這裏節點的順序並不重要。

你甚至不需要區別if (hashtable[index] == NULL);您可以將兩個案例合併成一個案例，即else條款中的代碼。

來源

2015-08-15 09:29:26

在哈希表中插入一個節點

回答

相關問題