Wednesday, December 2, 2009

Trie datastructure C example

This post is about the trie datastructure. Here we are trying to do a lexicographic trie. It can store all the words of a dictionary in an efficient manner. In the lexicographic trie datastructure each node has 26 pointers. Each pointers represent a letter. So to store "lay" , the system will first create a path from pointer for letter l to a new node(call it ptr). Then it makes a new node and makes the ptr's pointer for letter a point to this new node and so on. The advantage is that many words start with the same substring (eg new and neo). So here the common part "n" & "e" is stored only once. Hence lesser storage space and efficiency. In terms of computational speed searching is much faster as each time we can eliminate 25 links and hence it must be log n to the base 26. This is used commonly to implement dictionaries etc.
See the code now.

CODE

#include < stdio.h >
#include < stdlib.h >
#include < string.h >

struct diction
{
struct diction *alpha[26];
int flag;
};
typedef struct diction dic;

dic *root;
int maptoptr(char a)
{
char j='a';
int i;
for(i=0; i<26 a="'a';" root="(dic" i="0;i<26;i++,a++)" t="maptoptr(a);">alpha[t]=NULL;
}
}


void insert(char ip[])
{
dic *ptr=root;
int t;
int f=0;//false
int i=0;

t=maptoptr(ip[i]);
while(ptr->alpha[t]!=NULL && f==0) //not finished searchin and if there is a path with current letter
{
if(ip[i]=='\0' && ptr->flag==1)
{
f=1;//true
}
else
{
ptr=ptr->alpha[t];
i++;
}
t=maptoptr(ip[i]);
}
if(f==1)
{
printf("Already exists\n");
}
else
{
dic *ptr1=NULL;
char temp='a';
int j;
while(ip[i]!='\0')
{
temp='a';
ptr1=(dic *)malloc(sizeof(dic));
for(j=0;j<26;j++,temp++) t="maptoptr(temp);">alpha[t]=NULL;
}
ptr1->flag=0;
t=maptoptr(ip[i]);
ptr->alpha[t]=ptr1;
ptr=ptr1;
i++;
}
ptr->flag=1;
}
}
void search(char ip[])
{
int i=0,f=1;
int t;
dic *ptr=root;
while(ip[i]!='\0'&& f==1)
{
t=maptoptr(ip[i]);
if(ptr->alpha[t]==NULL)
{
f=0;
i++;
break;
}
ptr=ptr->alpha[t];
i++;
}
if(f==1 && ip[i]=='\0' && ptr->flag==1)
printf("\nFound\n");
else
printf("\nNot found\n");
}

void bt_free(dic *ptr)
{
int i=0,t;
char a='a';
if(ptr==NULL)
return;
for(i=0;i<26;i++,a++) t="maptoptr(a);">alpha[t]!=NULL)
{
bt_free((ptr->alpha[t]));
}
}
free(ptr);
}
main()
{
char a[25];
printf("Enter the word to insert : ");
gets(a);
createroot();
insert(a);
printf("Enter another word to insert : ");
gets(a);
insert(a);
printf("Enter the word to be searched : ");
gets(a);
search(a);
bt_free(root);
}




OUTPUT

$ ./a.exe
Enter the word to insert : layman
Enter another word to insert : laymansviews
Enter the word to be searched : layman

Found

4 comments:

  1. What kind of for loop is that????? KISS principle is clearly avoided

    ReplyDelete
  2. int maptoptr(char a)
    {
    char j='a';
    int i;
    for(i=0; i<26 a="'a';" root="(dic" i="0;i<26;i++,a++)" t="maptoptr(a);">alpha[t]=NULL;
    }
    }

    what does this mean?? how does it work?

    ReplyDelete
  3. plese do compilation before posting...

    trie.c: In function ‘maptoptr’:
    trie.c:17:16: error: expected ‘;’ before ‘a’
    trie.c:18:4: error: expected expression before ‘}’ token
    trie.c:18:4: error: expected expression before ‘}’ token
    trie.c: At top level:
    trie.c:19:4: error: expected identifier or ‘(’ before ‘}’ token
    trie.c: In function ‘insert’:
    trie.c:56:49: error: ‘alpha’ undeclared (first use in this function)
    trie.c:56:49: note: each undeclared identifier is reported only once for each function it appears in
    trie.c: At top level:
    trie.c:66:1: error: expected identifier or ‘(’ before ‘}’ token
    trie.c: In function ‘bt_free’:
    trie.c:96:41: error: ‘alpha’ undeclared (first use in this function)
    trie.c:96:55: error: expected ‘;’ before ‘)’ token
    trie.c:96:55: error: expected statement before ‘)’ token
    trie.c: At top level:
    trie.c:101:1: warning: data definition has no type or storage class [enabled by default]
    trie.c:101:1: warning: parameter names (without types) in function declaration [enabled by default]
    trie.c:101:1: error: conflicting types for ‘free’
    trie.c:102:1: error: expected identifier or ‘(’ before ‘}’ token

    ReplyDelete