c - 我要覆盖我的链表吗？

Question

免责声明:这是一个家庭作业问题。显而易见的是，我正试图自己解决它。我似乎遇到了一个我无法弄清楚的问题，因此不胜感激。

我需要散列一组单词，并将其插入到一个链表数组中。因此，如果 3 个不同的单词在数组 [38] 处的哈希值为 38，我需要一个包含这 3 个单词的链表。

我正在使用这个结构

struct Word {
    char* word;
    struct Word* next;
};

散列后，我将它插入到数组中，如下所示:

struct Word* table[1000];   // array of linked-lists

char word[128];
while(fgets(word, sizeof(word), dict) != NULL) {
    hashValue = hashWord(word, strlen(word));        

    struct Word *newWord = malloc(sizeof(struct Word));
    newWord->word = word;           

    if (table[hashValue] == NULL) {
        table[hashValue] = newWord;             
    } else {   // at index hashValue, table already contains at least one element
        // insert new word as first element of linked-list
        newWord->next = table[hashValue];
        table[hashValue] = newWord;         
    }

}

我知道大约有 5 个单词的哈希值为 38，但是当我打印它们时，我得到了相同的单词 5 次:

struct Word* foo = table[38];

while (foo->next != NULL) {
    printf("%s", foo->word); // prints the same word every time
    foo = foo->next;
}

似乎我在某个时候覆盖了我的链表，但我不知道在哪里。

Answer 1

while(fgets(word, sizeof(word), dict) != NULL) {
    ...
    newWord->word = word;           

问题是您正在替换 word 的内容，这是存储在每个 newWord 中的相同指针。

您每次使用此行在堆上分配一个新的 Word 结构:

struct Word *newWord = malloc(sizeof(struct Word));

但这只是为Word 结构本身分配内存； Word 结构包含一个 char *word——即指向字符(或以 NUL 结尾的字符串，在本例中)的指针，但它实际上不包含字符串本身的任何空间。

现在您需要显式地为字符串分配内存。试试这个:

newWord->word = strdup(word);

这会将word 的副本 放入每个Word 结构中。当 fgets() 下一次在您的 while 循环中被调用时，该副本不会被覆盖。请记住，堆栈分配的字符数组:

char word[128];

仅在该函数执行时有效；你必须在堆上分配一些东西(使用 malloc()，或者使用它的东西，比如 strdup())如果你想让它在函数调用之后继续存在。

完成后，不要忘记在释放每个 Word* 之前 free() char *word。