tree

gistfile1.c

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

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

// Alphabet size (# of symbols)
#define ALPHABET_SIZE (26)
// Converts key current character into index
// use only 'a' through 'z' and lower case
#define CHAR_TO_INDEX(C) ((int)C - (int)'A')


char words[]={0};
int counters[1000]={0};

// trie node
typedef struct trie_node trie_node_t;
struct trie_node
{
    int counter;
    char letter;
    trie_node_t *children[ALPHABET_SIZE];
};

// trie ADT
typedef struct trie trie_t;
struct trie
{
    trie_node_t *root;
    int count;
};

// Returns new trie node (initialized to NULLs)
trie_node_t *getNode(void)
{
    trie_node_t *pNode = NULL;

    pNode = (trie_node_t *)malloc(sizeof(trie_node_t));

    if( pNode )
    {
        int i;

        pNode->counter = 0;

        for(i = 0; i < ALPHABET_SIZE; i++)
        {
            pNode->children[i] = NULL;
        }
    }

    return pNode;
}

// Initializes trie (root is dummy node)
void initialize(trie_t *pTrie)
{
    pTrie->root = getNode();
    pTrie->count = 0;
}

int wordnr=0;

void setorder(trie_node_t *pTrie, char word[])
{
    int length = strlen(word);
    char tempword[1000] = {0};


    for(int i=0; i<length; i++)
    {
        tempword[i]=word[i];
    }

    trie_node_t *pCrawl;
    pCrawl = pTrie->root;


    for(int i=0 ; i<26; i++ )
    {
        tempword[length]=pCrawl->letter;
        tempword[length+1]='\0';

        if(pCrawl->counter!=0)
        {
            for(int i=0; i<=length; i++)
                words[wordnr+i]=tempword[i];

            counters[wordnr]=pCrawl->counter;
        }

        else
        {
            pCrawl = pCrawl->children[i];
            setorder(pCrawl, tempword);
        }
    }
}

// If not present, inserts key into trie
// If the key is prefix of trie node, just marks leaf node
void insert(trie_t *pTrie, char key[])
{
    int level;
    int length = strlen(key);
    int index;
    trie_node_t *pCrawl;


    pTrie->count++;
    pCrawl = pTrie->root;

    for( level = 0; level < length; level++ )
    {
        index = CHAR_TO_INDEX(key[level]);
        if( !pCrawl->children[index] )
        {
            pCrawl->children[index] = getNode();
        }
        pCrawl->letter=key[level];
        pCrawl = pCrawl->children[index];
    }

    if(pCrawl->counter!=0)
        pCrawl->counter++;
    else
        pCrawl->counter=1;

    printf("counter slow 3= %d\n", pCrawl->counter);
}

// Returns non zero, if key presents in trie
int search(trie_t *pTrie, char key[])
{
    int level;
    int length = strlen(key);
    int index;
    trie_node_t *pCrawl;

    pCrawl = pTrie->root;

    for( level = 0; level < length; level++ )
    {
        index = CHAR_TO_INDEX(key[level]);

        if( !pCrawl->children[index] )
        {
            return 0;
        }

        pCrawl = pCrawl->children[index];
    }

    return (0 != pCrawl && pCrawl->counter);
}

// Driver
int main()
{
    // Input keys (use only 'a' through 'z' and lower case)
    char keys[][15] = {"THE", "THE", "BYE", "A", "THERE", "ANSWER", "ANSWER", "BBUWNTSMFK", "THE", "THEIR", "ANSWER", "THE", "LOL", "OMG", "WTF"};
    trie_t trie;

    char output[][20] = {"Not present in trie", "Present in trie"};

    initialize(&trie);

    // Construct trie
    for(int i = 0; i < ARRAY_SIZE(keys); i++)
    {
        insert(&trie, keys[i]);
    }

    char word[1000] = {0};
    setorder(&trie, word);

    // Search for different keys
    printf("%s --- %s\n", "THE", output[search(&trie, "THE")] );
    printf("%s --- %s\n", "THESE", output[search(&trie, "THESE")] );
    printf("%s --- %s\n", "THEIR", output[search(&trie, "THEIR")] );
    printf("%s --- %s\n", "THAW", output[search(&trie, "THAW")] );

    return 0;
}