我的Trie联想提示算法触发段错误，请求排查问题

正在实现基于Trie数据结构的联想提示算法，预期输入前缀（如"he"）时返回所有以此开头的单词（例如["hello","help","held","hen"]等），但运行代码时出现段错误，初步定位问题出在construct_str函数。

运行输出 #

List of possible keys:
[construct_str]
Segmentation fault (core dumped)

相关代码 #

//NOTE: The expression sizeof(array)/sizeof(node) must always evaluate to 26. Not more; not less, for all the node arrays.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *chars="abcdefghijklmnopqrstuvwxyz";
struct node{
    char ch;
    struct node *next[26];
};
void init_w_null(struct node **n, int len){
    register int counter=0;
    while(counter<len){
       *(n+counter)=NULL;
       counter++;
    }
}
int index_of_char(char ch){
    register int counter=0;
    while(*(chars+counter)!='\0'){
        if(*(chars+counter)==ch){
            return counter;
        }
        counter++;
    }
    return -1;
}
void insert(struct node **root, char *key){
    if(*root==NULL){
        *root=(struct node*)malloc(sizeof(struct node));
        if(*root==NULL){
            perror("[malloc]");
            exit(EXIT_FAILURE);
        }
        init_w_null((**root).next,26);
        struct node *selected=*root;
        (**root).ch=key[0];
        register int counter=1;
        while(counter<strlen(key)){
            int ind=index_of_char(key[counter]);
            (*selected).next[ind]=(struct node *)malloc(sizeof(struct node));
            if(selected==NULL){
                perror("[malloc]");
                exit(EXIT_FAILURE);
            }
            (*(*selected).next[ind]).ch=key[counter];
            selected=(*selected).next[ind];
            counter++;
        }
        return;
    }
    register int counter=1;
    struct node *selected=*root;
    while(counter<=strlen(key)){
        int ind=index_of_char(key[counter]);
        if((*selected).next[ind]!=NULL){
            selected=(*selected).next[ind];
            counter++;
            continue;
        }
        (*selected).next[ind]=(struct node*)malloc(sizeof(struct node));
        if((*selected).next[ind]==NULL){
            perror("[malloc]");
            exit(EXIT_FAILURE);
        }
        (*(*selected).next[ind]).ch=key[counter];
        selected=(*selected).next[ind];
        init_w_null((*selected).next,26);
        counter++;
    }
}
void find(struct node *root, char *key){
    register int counter=1;
    struct node *selected=root;
    int ind=0;
    while(counter<=strlen(key)){
        //if key param ends, and tree doesn't
        if(key[counter]=='\0'){
            printf("List of possible keys:\n");
            construct_str(selected,key);
            return;
        }
        ind=index_of_char(key[counter]);
        //a character of key not found.
        if((*selected).next[ind]==NULL){
            puts("Similar keys not found.");
            return;
        }
        selected=(*selected).next[ind];
        counter++;
    }
    puts("Key found.");
}
void construct_str(struct node *n, char *str){
    puts("[construct_str]");
    //end of recursion
    if(all_children_null(n)&&n!=NULL){
        printf("%s\n",str);
        return;
    }
    register int counter=0;
    while(counter<26){
        if((*n).next[counter]!=NULL){
            char nstr[2];
            nstr[0]=(*(*n).next[counter]).ch;
            nstr[1]='\0';
            str=strcat(str,nstr);
            construct_str((*n).next[counter],str);
        }
        counter++;
    }
}
int all_children_null(struct node *n){
    register int counter=0;
    while(counter<26){
        if((*n).next[counter]!=NULL){
            return 0;
        }
        counter++;
    }
    return 1;
}
void insert_full(struct node **arr, char *key){
    int first=index_of_char(key[0]);
    insert(&arr[first],key);
}
//a debugging function to see whether insertion is successful.
/*void raw_print(struct node *n){
    //puts("[raw_print]");
    if(n!=NULL){
        putchar((*n).ch);
        register int counter=0;
        for(;counter<26;counter++){
            raw_print((*n).next[counter]);
        }
        if(all_children_null(n)){
            printf("\nAll children of %c are NULL.\n",(*n).ch);
        }
    }
}*/
int main(){
    struct node *nds[26];
    init_w_null(nds,26);
    insert_full(nds,"hello");
    insert_full(nds,"help");

    insert_full(nds,"bruh");
    insert_full(nds,"lmao");
    find(nds[index_of_char('l')],"lm");
    return 0;
}

Trie结构说明 #

Trie是存储共享前缀字符串的数据结构，每个节点包含一个字符和一个含26个元素的节点指针数组。例如存入"hello"和"help"后，两个单词的第四个字符节点为同级节点。

问题根源与修复 #

1. construct_str的字符串操作错误 #

原代码中str = strcat(str, nstr)存在致命问题：

• 传入的str是字符串字面量（如main中的"lm"），字面量存储在只读内存区，strcat尝试修改只读内存直接触发段错误。
• 即使是可写内存，递归中反复修改同一个字符串会导致内容被持续追加，后续分支会使用被污染的字符串，结果完全错误。

修复方案：递归时为每个分支创建独立的字符串副本，避免共享内存：

void construct_str(struct node *n, char *str) {
    if (n == NULL) return;

    if (all_children_null(n)) {
        printf("%s\n", str);
        return;
    }

    register int counter = 0;
    while (counter < 26) {
        if ((*n).next[counter] != NULL) {
            size_t new_len = strlen(str) + 2;
            char *new_str = malloc(new_len);
            if (new_str == NULL) {
                perror("[malloc]");
                exit(EXIT_FAILURE);
            }
            strcpy(new_str, str);
            new_str[strlen(str)] = (*(*n).next[counter]).ch;
            new_str[strlen(str)+1] = '\0';

            construct_str((*n).next[counter], new_str);
            free(new_str);
        }
        counter++;
    }
}

2. 空指针访问风险 #

原construct_str先判断all_children_null(n)再检查n!=NULL，若n为NULL，all_children_null(n)会访问空指针的next数组，直接触发段错误。需先判断n==NULL再执行后续逻辑。

3. 其他潜在问题 #

• insert函数中，分配节点后检查selected==NULL是错误的，应检查(*selected).next[ind]是否为NULL，因为selected是刚分配的*root，不可能为NULL。
• find函数中，循环条件counter<=strlen(key)会导致访问key[strlen(key)]（即'\0'），index_of_char返回-1，进而访问next[-1]触发段错误，需调整循环逻辑。

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