在哈希表中插入一个节点
Inserting a node in a hashtable
下面的代码是正确的,但我不明白为什么有两行代码可以工作。我指的是最后一个 else 块。具体来说,我指的是这两行:
newWord->next = hashtable[index];
散列table[索引] = newWord;
如果目标是将节点附加到 linked 列表的散列索引 table,为什么 newWord->next 指向散列索引[=21] =] 当该索引处可能已经有节点时。我认为它应该是 newWord->next = NULL,因为该节点将是 linked 列表中的最后一个 link,因此应该指向 NULL。从代码来看,结构的 "next" 字段似乎引用了索引。我希望我说得有道理。
/**
* 将字典加载到内存中。 Returns 如果成功则为真,否则为假。
*/
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;
}
}
你假设新节点追加到末尾是错误的。代码将新节点插入链表的前面,有效地使其成为新的头。 "tail" 是旧列表,它的头部现在是新头部之后的节点。
这种插入速度更快,因为您不必遍历列表来找到结尾。节点的顺序在这里无关紧要。
你甚至不需要if (hashtable[index] == NULL)
中的区别;您可以将这两种情况合并为一种情况,即 else
子句中的代码。
下面的代码是正确的,但我不明白为什么有两行代码可以工作。我指的是最后一个 else 块。具体来说,我指的是这两行:
newWord->next = hashtable[index];
散列table[索引] = newWord;
如果目标是将节点附加到 linked 列表的散列索引 table,为什么 newWord->next 指向散列索引[=21] =] 当该索引处可能已经有节点时。我认为它应该是 newWord->next = NULL,因为该节点将是 linked 列表中的最后一个 link,因此应该指向 NULL。从代码来看,结构的 "next" 字段似乎引用了索引。我希望我说得有道理。 /** * 将字典加载到内存中。 Returns 如果成功则为真,否则为假。 */
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;
}
}
你假设新节点追加到末尾是错误的。代码将新节点插入链表的前面,有效地使其成为新的头。 "tail" 是旧列表,它的头部现在是新头部之后的节点。
这种插入速度更快,因为您不必遍历列表来找到结尾。节点的顺序在这里无关紧要。
你甚至不需要if (hashtable[index] == NULL)
中的区别;您可以将这两种情况合并为一种情况,即 else
子句中的代码。