Patricia/Radix树单词插入功能异常程序崩溃求助

项目背景与预期效果 #

正在完成大学课程项目，用C语言实现Patricia/Radix树，功能为读取文本文件中每行的单词并插入树中。例如读取包含"roman"、"romance"、"romantic"的文件时，预期树结构如下：

(root)
      |
    roman$
   /     \
 ce$      tic$

当前运行异常情况 #

已添加检查点跟踪程序执行进度，崩溃前输出如下：

checkpoint 1
checkpoint 2
checkpoint 3 roman
checkpoint 4 roman
checkpoint 5
checkpoint 5

检查点1-4对应文件读取和单词验证逻辑，运行正常，之后程序崩溃。

相关代码 #

结构体定义 #

typedef struct no no; // 结构体声明

typedef struct no {
    char *str; // 存储字符串的指针
    struct no *child[26]; // 指向所有可能子节点的指针数组
    int isword; // 标记是否为完整单词
    int isroot; // 标记是否为树根节点
} tree;

插入函数 #

no* InsertWord(no *r, char *str){
    printf("checkpoint 5 %s\n", str);
    // 情况1：当前节点是根节点
    if(r->isroot){
        r->child[r->str[0] - 'a'] = InsertWord(r->str[r->str[0] - 'a'], str);
        return r;
    }
    // 情况2：找到空节点
    if(r->str == NULL){
        strcpy(r->str, str);
        r->isword = 1;
        printf("word %s inserted\n", str);
        return r;
    }
    // 情况3：单词与前缀完全匹配
    if(strcmp(r->str, str)){
        r->isword = 1;
        printf("word %s inserted\n", str);
        return r;
    }
    int i;
    for(i = 0; str[i] == r->str[i]; i++);
    // 情况4：前缀匹配单词的前半部分，单词还有剩余部分需要插入
    if(i == strlen(r->str)){
        r->child[str[i] - 'a'] = InsertWord(r->child[str[i] - 'a'], str + i);
        return r;
    }
    // 情况5：单词匹配前缀的前半部分，前缀还有剩余部分
    if(i == strlen(str)){
        char *aux1;
        char *aux2;
        strncpy(aux1, r->str, i);
        strcpy(aux2, r->str + i);
        no *aux = r;
        for(int j = 0; j < 26; j++){
            free(r->filhos[j]);
        }
        r->child[aux2[0] - 'a'] = aux;
        strcpy(r->str, aux1);
        strcpy(r->child[aux2[0] - 'a'], aux2);
        return r;
    }
    // 情况6：单词和前缀的前半部分匹配，但后续内容不同
    if(i < strlen(str) && i < strlen(r->str)){
        char *aux1;
        char *aux2;
        strncpy(aux1, r->str, i);
        strcpy(aux2, r->str + i);
        no *aux = r;
        for(int j = 0; j < 26; j++){
            free(r->child[j]);
        }
        r->child[aux2[0] - 'a'] = aux;
        strcpy(r->str, aux1);
        strcpy(r->child[aux2[0] - 'a'], aux2);
        r->child[str[i] - 'a'] = InsertWord(r->child[str[i] - 'a'], str + i);
        return r;
    }
}

文件读取与验证函数 #

no *ValidateWord(no *r, char *str) {
    int i;
    printf("checkpoint 3 %s\n", str);
    for (i = 0; str[i] != '\0'; i++) {
        if (str[i] < 'A' || (str[i] > 'Z' && str[i] < 'a') || str[i] > 'z') {
            return r;
        } else if (str[i] >= 'A' && str[i] <= 'Z') {
            str[i] = str[i] + 32;
        }
    }
    printf("checkpoint 4 %s\n", str);
    return InsertWord(r, str);
}

no *LoadFile(no *r) {
    printf("checkpoint 1");
    printf("Insert the name of the chosen file: ");
    char namefile[100];
    scanf("%s", namefile);
    FILE *fp1;
    fp1 = fopen(namefile, "r");
    if (fp1 == NULL) {
        printf("couldnt open the file.\n");
        return r;
    }
    char str[100];
    while (fgets(str, sizeof(str), fp1)) {
        printf("checkpoint 2 %s\n", str);
        str[strcspn(str, "\n")] = '\0';
        r = ValidateWord(r, str);
    }
    fclose(fp1);
    return r;
}

主函数与菜单 #

void menu(no* r) {
    int c = 0;
    printf("choose an operation:\n");
    printf("Load File - 1\nCheck Words - 2\nPrint Dictionary - 3\nLoad Stopwords File - 4\nExit - 0\n\n");
    scanf("%d", &c);
    while (c != 0) {
        if (c == 1)
            r = LoadFile(r); // 调用LoadFile函数
        else if (c == 2)
            CheckWords(r); // 调用CheckWords函数
        else if (c == 3)
            PrintDictionary(r); // 调用PrintDictionary函数
        else if (c == 4)
            r = LoadStopwordsFile(r); // 调用LoadStopwordsFile函数
        printf("choose an operation:\n");
        printf("Load File - 1\nCheck Words - 2\nPrint Dictionary - 3\nLoad Stopwords File - 4\nExit - 0\n\n");
        scanf("%d", &c);
    }
}

int main() {
    no* r = (no*) malloc(sizeof(no)); // 为根节点分配内存
    if (r == NULL) {
        printf("Error alocating memory.\n");
        return 1; // 退出程序
    }
    r->isroot = 1; // 设置根节点标记为真
    menu(&r); // 调用菜单函数
    free(r); // 释放根节点内存
    return 0;
}

问题排查请求 #

已尝试添加动态内存分配但未解决问题，无法确定崩溃原因，请求帮助排查。

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