fork(2) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef int trieValueT;
  5.  
  6. typedef struct trieNodeTag {
  7.     char key;
  8.     int words;
  9.     int prefix;
  10.     trieValueT value;
  11.     struct trieNodeTag *next, *children;
  12. } trieNodeT;
  13.  
  14. typedef struct trieCDT {
  15.     trieNodeT *root;
  16. } trieCDT;
  17.  
  18. typedef struct trieCDT *trieADT;
  19.  
  20. // Functions
  21. void trieCreate(trieCDT *trie);
  22. void trieAdd(trieNodeT *trie, char *key, int value);
  23. trieNodeT* addChild(char key);
  24. int trieIsMember(trieCDT trie, char keys[]);
  25. int totalStringsWithPrefix(trieCDT trie, char keys[]);
  26. void trieDestroy(trieNodeT *root);
  27. void test1();
  28. void startTesting();
  29. void startTestingFromFile(char** stdip_v);
  30.  
  31. // To enable debug messages uncomment #define
  32. #define TEST 1
  33. // To test trie by providing input from file, uncomment 'TESTFROMFILE'
  34. // Compile code and while executing provide file name at command line
  35. // For e.g. > ./a.out ipFile.txt
  36. //
  37. //#define TESTFROMFILE 1
  38. //
  39. // To enable debug messages uncomment 'DEBUG'
  40. //#define DEBUG 1
  41.  
  42. #ifdef DEBUG
  43. #  define D(x) x
  44. #else
  45. #  define D(x)
  46. #endif
  47.  
  48. int main(int argc, char* argv[])
  49. {
  50.     #ifdef TEST
  51.         startTesting();
  52.     #endif
  53.  
  54.     #ifdef TESTFROMFILE
  55.         startTestingFromFile(argv);
  56.     #endif
  57.  
  58.     return 0;
  59. }
  60.  
  61. // Create root node of trie
  62. void trieCreate(trieCDT *trie)
  63. {
  64.     trie->root = (trieNodeT*)calloc(1,sizeof(trieNodeT));
  65.  
  66.     if (trie->root == NULL) {
  67.     printf("Can not alloc memory\n");
  68.     return;
  69.     }
  70.  
  71.     trie->root->key = '\0';
  72.     trie->root->value = -1;
  73.     trie->root->next = NULL;
  74.     trie->root->children = NULL;
  75. }
  76.  
  77. // This is recursive function for adding node in trie
  78. // It covers 3 cases
  79. // Case 1: When only root node is present in a trie. In this
  80. //         case keep on adding node one level after another.
  81. //
  82. //         If input given is "Good" and if 'G' is not found then
  83. //         insert 'G' and return 'G' node from where next insertion
  84. //         has to be done as we have already found there is no
  85. //         other 'G' exist.
  86. //
  87. // Case 2: When matching key node is already found return the matching
  88. //         node and increment key
  89. //
  90. // Case 3: When key does not match to existing children i.e. for
  91. //         "abcd", "abef" and "abgh"
  92. //         .  ----> root
  93. //         |
  94. //         a
  95. //         |
  96. //         b
  97. //         |
  98. //         c ===> e ===> g        (LL, children of b)
  99. //         |      |      |
  100. //         d      f      h
  101.  
  102.  
  103. void trieAdd(trieNodeT* trie, char *key, int value) {
  104.  
  105.     // Get root of children
  106.     if (key == NULL) {
  107.     return;
  108.     } else if (trie->children == NULL && trie->next == NULL) {
  109.  
  110.         // Case 1
  111.     trieNodeT* child = addChild(*key);
  112.     trie->children = child;
  113.  
  114.     if (*key == '\0') {
  115.         child->value = value;
  116.         child->words++;
  117.         return;
  118.     }
  119.  
  120.     return trieAdd(child, ++key, value);
  121.     }
  122.  
  123.     trieNodeT* level = trie->children;
  124.     trieNodeT* current;
  125.     for (current = level; current != NULL; current = current->next) {
  126.  
  127.     // Case 2
  128.     if (current->key == *key) {
  129.         current->prefix++;
  130.  
  131.         if (*key == '\0') {
  132.         current->words++;
  133.         return;
  134.         }
  135.         return trieAdd(current, ++key, value);
  136.     }
  137.  
  138.     // This is last element in LL and key is not found
  139.     // For e.g. for "abc" and "abd", c and d should be
  140.     // child of b.
  141.     // Since, c != d, Append d to c in LL signifying they
  142.     // are both child of 'b' and are on same level
  143.     //
  144.     // Case 3
  145.     if (current->next == NULL) {
  146.         //Add key
  147.         trieNodeT* child = addChild(*key);
  148.         current->next = child;
  149.  
  150.         if (*key == '\0') {
  151.             child->words++;
  152.         child->value = value;
  153.         return;
  154.         }
  155.  
  156.         return trieAdd(child, ++key, value);
  157.     }
  158.     }
  159. }
  160.  
  161. trieNodeT* addChild(char key)
  162. {
  163.     trieNodeT* child = (trieNodeT*)calloc(1,sizeof(trieNodeT));
  164.  
  165.     if (child == NULL) {
  166.     printf("Can not alloc memory\n");
  167.     return NULL;
  168.     }
  169.     child->key = key;
  170.     child->value = -1;
  171.     child->next = NULL;
  172.     child->children = NULL;
  173.     child->prefix = 1;
  174.     child->words = 0;
  175.  
  176.     return child;
  177. }
  178.  
  179. int totalStringsWithPrefix(trieCDT trie, char keys[])
  180. {
  181.     trieNodeT *level = trie.root->children;
  182.  
  183.     while (keys != NULL) {
  184.     trieNodeT *found = NULL;
  185.     trieNodeT *current;
  186.  
  187.     for (current = level; current != NULL; current = current->next) {
  188.         if (current->key == *keys) {
  189.         found = current;
  190.         break;
  191.         }
  192.     }
  193.  
  194.     if (found == NULL) {
  195.         return 0;
  196.     } else if (*(keys + 1)  == '\0') {
  197.         return found->prefix;
  198.     }
  199.     level = found -> children;
  200.     keys++;
  201.     }
  202.  
  203.     return 0;
  204. }
  205.  
  206. int trieIsMember(trieCDT trie, char keys[])
  207. {
  208.     trieNodeT *level = trie.root->children;
  209.  
  210.     while (keys != NULL) {
  211.     trieNodeT *found = NULL;
  212.     trieNodeT *current;
  213.  
  214.     for (current = level; current != NULL; current = current->next) {
  215.         if (current->key == *keys) {
  216.         found = current;
  217.         break;
  218.         }
  219.     }
  220.  
  221.     if (found == NULL) {
  222.         return 0;
  223.     } else if (*keys == '\0') {
  224.         return 1;
  225.     }
  226.     level = found -> children;
  227.     keys++;
  228.     }
  229.  
  230.     return 0;
  231. }
  232.  
  233. void trieDestroy(trieNodeT * root)
  234. {
  235.     if (root->children == NULL && root->next == NULL) {
  236.         D(printf("Destroying %d\n", root->value));
  237.     free (root);
  238.     return;
  239.     }
  240.  
  241.     // If root have next and children free them first
  242.     if (root->next != NULL) {
  243.     trieDestroy(root->next);
  244.     }
  245.  
  246.     if (root->children != NULL) {
  247.     trieDestroy(root->children);
  248.     }
  249.  
  250. #ifdef DEBUG
  251.     if (root->key != '\0') {
  252.     printf("Destroying %c\n", root->key);
  253.     } else {
  254.     printf("Destroying Root %d\n", root->value);
  255.     }
  256. #endif
  257.  
  258.     free (root);
  259. }
  260.  
  261. void test1()
  262. {
  263.     char s[] = "ABCD";
  264.     char s1[] = "ABCDE";
  265.     int i = 0;
  266.     trieCDT trie;
  267.     trieCreate(&trie);
  268.     trieAdd(trie.root, "ABCD", 20);
  269.     trieAdd(trie.root, "ABCDE", 30);
  270.  
  271.     if (trieIsMember(trie, s)) {
  272.     printf("Found member 'ABCD'\n");
  273.     }
  274.  
  275.     i = totalStringsWithPrefix(trie, "ABC");
  276.     printf("Total words with prefix 'ABC' %d\n", i);
  277.  
  278.     trieDestroy(trie.root);
  279. }
  280.  
  281. void startTesting()
  282. {
  283.     test1();
  284. }
  285.  
  286. void startTestingFromFile(char** stdip_v)
  287. {
  288.     FILE *fp = NULL;
  289.     char key[50];
  290.     trieCDT trie;
  291.     int i = 0;
  292.  
  293.     fp = fopen(stdip_v[1], "r");
  294.     if(fp == NULL) {
  295.     fprintf(stderr, "Can not read file!!\n");
  296.     return;
  297.     }
  298.  
  299.     trieCreate(&trie);
  300.  
  301.     while(fscanf(fp, "%s", key) != EOF) {
  302.     trieAdd(trie.root, key, i);
  303.     i++;
  304.  
  305.     if(!trieIsMember(trie, key)) {
  306.         printf("Key '%s' NOT found in trie\n", key);
  307.     }
  308.     }
  309.  
  310.     printf("Total words inserted in trie %d\n", i);
  311.  
  312.     i = totalStringsWithPrefix(trie, "Abe");
  313.  
  314.     printf("Total prefixs with 'Abe' %d\n", i);
  315.  
  316.     trieDestroy(trie.root);
  317. }
Success #stdin #stdout 0s 2380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Found member 'ABCD'
Total words with prefix 'ABC' 2
https://ideone.com/AV5jKS
Trie
language:
C (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!