CODEWITHSUNDEEP
ctreeinserttrie
woshidashen
woshidashen

Reputation: 351

C programming trie tree insert

I just started programming and have a beginner question,I am writing a trie insert function that insert a string into the trie tree. But when I add a string with more than two characters I'm getting heap buffer overflow. Here is my insert function:

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;
};

The definition of the tree node

struct node
{   
int isword;
int prefix;
int occurrence;
int leaf;
struct node * child[26];
};

and How I called them

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);

I think it's how I allocate space in the insert function for new node that went wrong, but I'm not sure what's the proper way to avoid heap buffer overflow, any advice please?

Upvotes: 0

Views: 216

Answers (1)

zzn
zzn

Reputation: 2465

c is not ending with nul. So c[i] is undefined if i>=3(maybe coredump because access invalid memory address). while(c[i]) may run more than 3 times. This maybe the point. 

char *c=malloc(3*sizeof(char));
c[0]='a';
c[1]='d';
c[2]='e';

btw, code below will cause memory leak:

struct node *root=malloc(sizeof(*root));
root=malloc(sizeof(struct node));

Upvotes: 1

Related Questions