C编程特里树插入
C programming trie tree insert
我刚开始编程,有一个初学者问题,我正在编写一个 trie 插入函数,将一个字符串插入到 trie 树中。但是当我添加一个包含两个以上字符的字符串时,我得到了堆缓冲区溢出。这是我的插入函数:
struct node* insert(struct node *root,char *c){
int i=0;
struct node *temp=root;
while(c[i]){
int index=c[i]-'a';
//New Node
struct node *n=malloc(sizeof(*n));
n=malloc(sizeof(struct node));
temp->child[index]=n;
i++;
temp=temp->child[index];
}
return root;
};
树节点的定义
struct node
{
int isword;
int prefix;
int occurrence;
int leaf;
struct node * child[26];
};
以及我如何称呼他们
char *c=malloc(3*sizeof(char));
c[0]='a';
c[1]='d';
c[2]='e';
struct node *root=malloc(sizeof(*root));
root=malloc(sizeof(struct node));
insert(root,c);
我认为这是我在插入函数中为新节点分配 space 的方式出错了,但我不确定避免堆缓冲区溢出的正确方法是什么,请提供任何建议?
c
不以 nul 结尾。所以 c[i] 是未定义的,如果 i>=3
(可能是核心转储,因为访问无效的内存地址)。 while(c[i])
可能 运行 3 次以上。这也许是重点。
char *c=malloc(3*sizeof(char));
c[0]='a';
c[1]='d';
c[2]='e';
顺便说一句,下面的代码会导致内存泄漏:
struct node *root=malloc(sizeof(*root));
root=malloc(sizeof(struct node));
我刚开始编程,有一个初学者问题,我正在编写一个 trie 插入函数,将一个字符串插入到 trie 树中。但是当我添加一个包含两个以上字符的字符串时,我得到了堆缓冲区溢出。这是我的插入函数:
struct node* insert(struct node *root,char *c){
int i=0;
struct node *temp=root;
while(c[i]){
int index=c[i]-'a';
//New Node
struct node *n=malloc(sizeof(*n));
n=malloc(sizeof(struct node));
temp->child[index]=n;
i++;
temp=temp->child[index];
}
return root;
};
树节点的定义
struct node
{
int isword;
int prefix;
int occurrence;
int leaf;
struct node * child[26];
};
以及我如何称呼他们
char *c=malloc(3*sizeof(char));
c[0]='a';
c[1]='d';
c[2]='e';
struct node *root=malloc(sizeof(*root));
root=malloc(sizeof(struct node));
insert(root,c);
我认为这是我在插入函数中为新节点分配 space 的方式出错了,但我不确定避免堆缓冲区溢出的正确方法是什么,请提供任何建议?
c
不以 nul 结尾。所以 c[i] 是未定义的,如果 i>=3
(可能是核心转储,因为访问无效的内存地址)。 while(c[i])
可能 运行 3 次以上。这也许是重点。
char *c=malloc(3*sizeof(char));
c[0]='a';
c[1]='d';
c[2]='e';
顺便说一句,下面的代码会导致内存泄漏:
struct node *root=malloc(sizeof(*root));
root=malloc(sizeof(struct node));