构建含全部英文单词的字典树仅显示最后一个单词的问题求助

问题描述 #

我尝试构建一棵包含所有英文单词的字典树，但最终树中仅存在词库的最后一个单词。search函数采用深度优先搜索（DFS）遍历树时，显示部分connections为空指针，但我在main函数的树构建循环中确认过这些指针并非空值。怀疑问题可能出在内存覆盖或已使用内存的重复分配上，求解决办法，同时欢迎任何批评或建议。

相关代码 #

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

#define ALPHSIZE 26
#define WORDBANKNAME "testwordbank.txt"

int hashy(int c){
    return (int) c-97;
};

struct Node{
    bool end;   
    char c;
    struct Node** connections;
};

void search(struct Node* head,int depth){
    depth++;
    for(int i = 0; i < ALPHSIZE; i++){
        printf("depth %i checking %c = %p\n",depth,i+97,head->connections[i]);
        if (head->connections[i]){
            if(head->connections[i]->end) printf("end!!: ");
            printf("%c\n",head->connections[i]->c);
            search(head->connections[i],depth);
        }
    }
};

struct Node* createNode(char c) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->end = false;
    newNode->c = c;
    newNode->connections = malloc(ALPHSIZE*sizeof(struct Node*));
    for (int i = 0; i < ALPHSIZE; i++) {
        newNode->connections[i] = NULL;
    }
    return newNode;
}


int main(){
    FILE* wordbank = fopen(WORDBANKNAME,"r");
    struct Node*root = createNode((char)1);
    
    struct Node* head = root;
    int nextchar = getc(wordbank);
    
  
    while(nextchar != EOF){
        if (nextchar == '\n'){
            head->end = true; 
            head = root;
            nextchar = getc(wordbank);
            continue;
        }
        int cindex = hashy(nextchar);
        head->connections[cindex] = createNode(nextchar);
        head = head->connections[cindex];
        nextchar = getc(wordbank);
    }
    printf("-----------\n");
    search(root,0);

    fclose(wordbank);
    return 0;
};

问题根源 #

核心问题出在字典树的构建逻辑：每次处理字符时，不管当前节点的对应连接是否已经存在，都直接创建新节点并覆盖原有指针。

举个例子：如果词库包含"apple"和"ant"两个单词：

1. 处理"apple"时，root的a连接会被创建为a节点，接着依次创建p、p、l、e节点，最后标记e为单词结束。
2. 处理"ant"时，root的a连接会被重新创建新的a节点，直接覆盖了之前"apple"对应的a节点，后续再创建n、t节点。最终树中只剩下"ant"的路径，"apple"的路径完全丢失。

修复方案 #

修改main函数中的构建逻辑，先检查当前节点的对应连接是否存在，仅当不存在时才创建新节点：

// 替换原main函数中对应代码块：
while(nextchar != EOF){
    if (nextchar == '\n'){
        head->end = true; 
        head = root;
        nextchar = getc(wordbank);
        continue;
    }
    int cindex = hashy(nextchar);
    // 新增判断：仅当连接为空时才创建节点
    if (!head->connections[cindex]) {
        head->connections[cindex] = createNode(nextchar);
    }
    head = head->connections[cindex];
    nextchar = getc(wordbank);
}

额外优化建议 #

• 内存泄漏处理：当前代码没有释放字典树内存的逻辑，使用完后需递归销毁所有节点：

void destroyTrie(struct Node* node) {
    if (!node) return;
    for (int i = 0; i < ALPHSIZE; i++) {
        destroyTrie(node->connections[i]);
    }
    free(node->connections);
    free(node);
}
// 在main函数return前调用：destroyTrie(root);

• 哈希函数健壮性：原hashy函数未处理非小写字母的情况，容易导致数组越界，可添加校验（需包含<ctype.h>）：

int hashy(int c){
    // 先转小写
    c = tolower(c);
    if (c < 'a' || c > 'z') {
        fprintf(stderr, "无效字符: %c\n", c);
        exit(EXIT_FAILURE);
    }
    return c - 'a'; // 用'a'代替97，代码可读性更高
};

• 文件打开校验：原代码未检查fopen是否成功，若文件不存在会直接崩溃，添加检查：

FILE* wordbank = fopen(WORDBANKNAME,"r");
if (!wordbank) {
    perror("打开词库文件失败");
    exit(EXIT_FAILURE);
}

• 根节点优化：根节点不需要存储有效字符，可将其c字段设为'\0'，避免无意义的赋值。

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