Program Crashing due to string in structure in Trie

Question

I am implementation a trie,which will also print the definition once the end of word is reached.I am using string for definition.But the code is crashing when I assigning the definition to the string.

#include <bits/stdc++.h>
#define ALPHABET_SIZE 26
#define CHAR_TO_INDEX(c) ((int)c - (int)'0')
using namespace std;
typedef struct trienode{

string definition;          //For Definition of the word
bool isLeaf; 
struct trienode *children[ALPHABET_SIZE]; 

}node;
node* getnode()
{
    int i;
    node *t=new node();
    t->isLeaf=false;
    for(i=0;i<26;i++)
    {
        t->children[i]=NULL;
    }
    return t;
}
void insert(node *root,string s)
{
    node *crawler=root;
    int level,index,length=s.length();
    for(level=0;level<length;level++)
    {
        index=  CHAR_TO_INDEX(s[level]);
        if(crawler->children[index]==NULL)
        {
            crawler->children[index]=getnode();
        }
        crawler=crawler->children[index];
    }
    crawler->definition= "Definition of" + s;  //Here is the code crashing,when I am assigning the definition
    crawler->isLeaf=true;
}

Answer 1

Your code has a lot of problems.

The bigger that I see, the problem that (I suppose) is causing the crash, is in following line

#define CHAR_TO_INDEX(c) ((int)c - (int)'0')

The CHAR_TO_INDEX() macro is intended to return an index value from 0 to 9 when c is a char that represent a number (from 0 to 9).

The problem is that you use it to obtain a number from 0 to 25 when c is between a and z or (I suppose) between A and Z.

An example: when c is r, (int)'r' - (int)'0') is 114 - 48 = 66. So you try to access in slot 66 of children that has only 26 slots.

To correct this problem you can rewrite CHAR_TO_INDEX() in this way

#define CHAR_TO_INDEX(c) (c - (int)'a')

and call it in this way

index = CHAR_TO_INDEX( std::tolower( s[level] ) );

But I think it's a bad idea to use macros, so I suggest you to define a simple function with some check; something like this

int charToIndec (int ch)
 {
   if ( (ch < int(`a`)) || (ch > int(`z`)) )
    ; // throw something

   return ch - int(`a`);
 }

Other suggestions, without particular order...

You're using C++, not C; so there is no need of that typedef for trienode; you can simply write

struct trienode {
   string definition; //For Definition of the word
   bool isLeaf; 
   trienode *children[ALPHABET_SIZE]; 
};

and simply use the struct as trienode

Again: you're using C++, not C; so I don't understand why you write a function getnode() that should be (IMHO) the constructor of trienode; something like

trienode () : definition(""), isLeaf(false)
 {
   for ( int i = 0 ; i < ALPHABET_SIZE ; ++i )
      children[i] = NULL;
 }

that should be used in this way

crawler->children[index]= new trienode;

In any case, you have defined ALPHABET_SIZE as 26; remember to use it everywhere instead of 26 (when 26 is the dimension of children); so substitute the 26 in getnode() with ALPHABET_SIZE

Include; what is bits/stdc++.h? In don't know it and I don't even know if it's a C++ standard include. Suggestion: use standard includes.

Last suggestion: you use new for nodes; remember to delete the allocated nodes; if you can use a C++11 compiler, consider the hypothesis to use std::unique_ptr to avoid this need.

p.s.: sorry for my bad English.