Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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')
- // trie node
- typedef struct trie_node trie_node_t;
- struct trie_node
- {
- int value;
- 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->value = 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;
- }
- // 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 = pCrawl->children[index];
- }
- printf("count%d\n", pTrie->count);
- // mark last node as leaf
- pCrawl->value = pTrie->count;
- }
- // 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->value);
- }
- // Driver
- int main()
- {
- // Input keys (use only 'a' through 'z' and lower case)
- char keys[][10] = {"THE", "THE", "THE", "A", "THERE", "ANSWER", "ANY", "BY", "BYE", "THEIR"};
- 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]);
- }
- // 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement