我正在编写一个使用trie数据结构的算法。基本上，如果输入是"0"；他"；，它将返回["hello"、"help"、"holded"、"hen"、other_word_starting_with_he]。代码：
//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)!=' '){
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]==' '){
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("%sn",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]=' ';
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;
}
输出：
List of possible keys:
[construct_str]
Segmentation fault (core dumped)
我已经把问题缩小到construct_str。如果我错了，请告诉我。对于那些不知道TRIE是什么的人：
它是一种可以存储具有相同前缀的字符串的结构，因此如果我们添加"；你好"；以及"；"帮助"；，两个字符串中的第四个字符将是兄弟姐妹。trie的节点包含一个字符和一个具有26个成员的节点数组。
我看到我的水晶球今天调得很好。
从开始。。。
find(nds[index_of_char('l')],"lm");
。。。将字符串文本作为第二个参数传递给find()。在该函数中，指向其第一个字符的指针与参数key相关联。
在find()中，您将该指针转发到construct_str():
construct_str(selected,key);
，其中它与参数str相关联。
在construct_str()中，将该指针作为第一个参数传递给strcat():
str=strcat(str,nstr);
strcat将第二个字符串的内容附加到包含第一个字符串的数组中。它不会为连接的结果创建新的数组。因此，左指针必须指向
- 是可修改的，并且
- 在字符串末尾后包含足够的空间以容纳额外的内容
字符串文字不满足这两个条件。哎呀。未定义的行为结果。
在行
str=strcat(str,nstr);
str是指向字符串文字的指针。您不允许修改它们。尝试使用函数strcat修改字符串文字将调用未定义的行为。
调用strcat时，必须确保第一个参数指向
- 您可以写信给，并且
- 有足够的空间将字符添加到字符串中