我是否覆盖了我的链表？

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循环中调用next 时,不会覆盖此副本.请记住堆栈分配的字符数组:

char word[128];

仅在执行此功能时有效; 如果你希望它超出函数调用malloc(),你必须在堆上分配一些东西(或者使用它,或者使用它的东西strdup()).

当你完成后,不要忘记在释放每个之前free()的char *words Word*.