链表处理哈希表冲突时出现无限链表的问题求助

我正在实现一个用链表处理冲突的哈希表（数组结构）存储单词字典，填充哈希表时，同一哈希值对应多个条目会创建无限链表。

节点结构体定义：

typedef struct node
{
    char word[LENGTH + 1];
    int hash;
    struct node *next;
}
node;

问题根源分析 #

初始代码的核心问题 #

1. 自引用循环：处理已有哈希条目的逻辑中，list->next = &table[list->hash]; 后执行 table[list->hash] = *list;，这会让新覆盖的表项next指向自身，形成无限循环的链表。
2. 循环终止遗漏：while (list->next != NULL) 会跳过链表的最后一个节点，导致该节点无法加入哈希表。

优化后代码的核心问题 #

1. 无效内存引用：创建节点n后，将*n赋值给表项再free(n)，后续表项的next指向的是已释放的内存或自引用地址，属于非法访问。
2. 错误的链表逻辑：错误地用结构体赋值代替指针操作，既浪费内存又容易引发循环引用。

修复方案 #

核心思路：哈希表的每个桶（数组元素）作为链表的头指针，新节点直接通过指针挂载到对应桶的链表头部，采用标准头插法实现链表冲突处理，避免结构体赋值带来的自引用问题。

修复后的完整代码 #

#include <ctype.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define LENGTH 45
const unsigned int N = 4000;

typedef struct node
{
    char word[LENGTH + 1];
    int hash;
    struct node *next;
} node;

bool load(const char *dictionary);
unsigned int hash(const char *word);

// 哈希表每个元素是链表头指针，初始化为空
node *table[N] = {NULL};

int main(void)
{
    char *dict = "dictionaries/medium";
    bool loaded = load(dict);
    if (!loaded)
    {
        printf("could not load dictionary\n");
        return 1;
    }
    printf("worked\n");
    
    // 测试打印哈希值196对应的链表（单词Nina）
    node *current = table[196];
    while (current != NULL)
    {
        printf("%s\n", current->word);
        current = current->next;
    }
    
    return 0;
}

bool load(const char *dictionary)
{
    FILE *input = fopen(dictionary, "r");
    if (input == NULL)
    {
        return false;
    }

    char word[LENGTH + 1];
    while(fscanf(input, "%s", word) != EOF)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            fclose(input);
            return false;
        }
        strcpy(n->word, word);
        n->hash = hash(word);
        
        // 头插法挂载新节点到对应哈希桶
        n->next = table[n->hash];
        table[n->hash] = n;
    }

    fclose(input);
    return true;
}

unsigned int hash(const char *word)
{
    unsigned int hash = 0;
    int len = strlen(word);
    for (int i = 0; i < len; i++)
    {
        if (word[i] != '\'')
        {
            hash += ((toupper(word[i]) - 64));
        }
        if (i % 2 == 0)
        {
            hash = (hash * 3);
        }
    }
    return hash % N;
}

关键修复点 #

1. 哈希表类型调整：将node table[N]改为node *table[N] = {NULL}，每个桶是链表头指针，初始为空，避免结构体默认值引发的判断错误。
2. 标准头插法：新节点直接通过指针挂载到对应桶的链表头部，彻底避免自引用问题。
3. 修正资源释放：将fclose(input)移到return true之前，确保文件能正常关闭。
4. 安全测试逻辑：用循环遍历链表打印，避免固定次数打印导致的越界或无限循环。

内容的提问来源于stack exchange，提问作者maosi100