0

免责声明：这是一个家庭作业问题。应该很明显，我正在尝试自己解决它。我似乎遇到了一个我无法弄清楚的问题，因此我们将不胜感激。

我需要散列一组单词，并将其插入到链表数组中。因此，如果 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;
}

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

4

2 回答 2

5 
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()中调用 next时，不会覆盖此副本。while请记住堆栈分配的字符数组：

char word[128];

仅在此函数执行时有效；如果您希望它在函数调用之外存在，则必须在堆上分配一些东西（使用malloc()，或使用它的东西，例如）。strdup()

完成后，不要忘记释放每个 s 之前free()的s 。char *wordWord*

于 2012-07-19T04:06:20.637 回答
1

您正在覆盖单词数组。您只存储指向数组的指针，但数组会被每个新单词覆盖。您需要单独的内存来保存每个单词。

于 2012-07-19T04:06:11.803 回答