有人可以检查我实现哈希 table 的代码的逻辑吗？

Question

我正在尝试实现一个程序，该程序接受一个 .txt 文件，该文件中充满了字典中的单词，加载函数的目标是打开文件，然后通读它，并存储所有单词在哈希 table 中。我对数据结构很陌生，所以我不确定我在哈希 table.

中加载单词的逻辑

// Represents a node in a hash table
typedef struct node {
    char word[LENGTH + 1];
    struct node *next;
} node;

// Number of buckets in hash table
//                  N = 2 ^ 13
const unsigned int N = 8192;

// Hash table
node *table[N];

这是加载函数，负责从字典文件中读取所有单词，然后将它们全部加载到散列中table，其中它们的索引将在传递给散列函数 djb2 时确定来自互联网。

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary) {
    // TODO
    const int max_len = LENGTH + 1;
    char words[max_len];
    int index;

    // Initialize the array to NULL
    for (int i = 0; i < N; i++) {
        table[i] = NULL;
    }

    // Open the dictionary file
    FILE indata = fopen(dictionary, "r")
    if (indata == NULL) {
        return false;
    }

    // loop to get the words from the file
    while (fgets(words, max_len, indata) != NULL) {
        // get the index of the word using the hash function
        index = hash(words);

        // create a new node and check if the computer has memory
        node *newNode = malloc(sizeof(node));
        if (newNode == NULL) {
            return false;
        }

        if (table[index] == NULL) {
            newNode->word = words;
            newNode->next = NULL;
            table[index] = newNode;
        } else {
            newNode->word = words;
            newNode->next = table[index];
            table[index] = newNode;
        }
    }
    return true;
}

Answer 1

您的代码中存在多个问题：

load()中的数组定义使用了 C99 可变长度数组语法。有些编译器不接受这种语法。只需编写 char words[LENGTH + 1]; 并将 sizeof words 作为大小参数传递给 fgets();
数组 word[] 的定义大小为 MAXLENGTH+1。这会给文件中 MAXLENGTH 或更多字节的单词带来问题，因为 fgets() 不会读取整行。您可能应该扩大数组并测试输入行是否被截断。
您没有删除 fgets() 留在数组中的尾随换行符，因此您在散列 table 中的条目将有一个尾随换行符，这可能不是您想要的。
您不能将一个数组分配给一个数组：要么让节点持有指向字符串的指针，要么使用 strcpy() 复制单词。

哈希索引的bucket中是否已经有节点就不用测试了：直接写：

      strcpy(newNode->word, words);
      newNode->next = table[index];
      table[index] = newNode;

您在从 load() 返回前忘记关闭 indata。

有人可以检查我实现哈希 table 的代码的逻辑吗？

Can someone check the logic of my code that implements a hash table?

c

hashtable

linked-list

cs50