fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #include <stdlib.h>
  4.  
  5. #include <stdbool.h>
  6.  
  7. #include <assert.h>
  8.  
  9. #include <string.h>
  10.  
  11. #define MAX_LINE 100
  12. #define maxChar 8
  13.  
  14. typedef struct Node {
  15.   char * data[25];
  16.   //struct Node *similar;
  17.   struct Node * children[8];
  18.   struct Node * parent;
  19.   bool isWord;
  20. }
  21. Node;
  22.  
  23. typedef struct Trie {
  24.   Node * root;
  25. }
  26. Trie;
  27.  
  28. //will convert the letter to a key for my tree, we only use
  29. //the numbers 2-9 for t9 word so I will convert each char to it's 
  30. //t9 value and subtract 2 so that I do not leave the first two 
  31. //spots of my array empty.
  32.  
  33. int charToInt(char s) {
  34.   switch (s) {
  35.   case 'a':
  36.   case 'b':
  37.   case 'c':
  38.     return 0;
  39.   case 'd':
  40.   case 'e':
  41.   case 'f':
  42.     return 1;
  43.   case 'g':
  44.   case 'h':
  45.   case 'i':
  46.     return 2;
  47.   case 'j':
  48.   case 'k':
  49.   case 'l':
  50.     return 3;
  51.   case 'm':
  52.   case 'n':
  53.   case 'o':
  54.     return 4;
  55.   case 'p':
  56.   case 'q':
  57.   case 'r':
  58.   case 's':
  59.     return 5;
  60.   case 't':
  61.   case 'u':
  62.   case 'v':
  63.     return 6;
  64.   case 'w':
  65.   case 'x':
  66.   case 'y':
  67.   case 'z':
  68.     return 7;
  69.   default:
  70.     return -1;
  71.   }
  72. }
  73.  
  74. //allocates the space for and creates new node
  75. Node * newNode(Node * parent) {
  76.   Node * n = (Node * ) malloc(1 * sizeof(struct Node));
  77.   n -> isWord = false;
  78.   for (int i = 0; i < 25; i++) {
  79.     n -> data[i] = NULL;
  80.   }
  81.   for (int i = 0; i < maxChar; i++) {
  82.     n -> children[i] = NULL;
  83.   }
  84.   n -> parent = parent;
  85.   return n;
  86. }
  87.  
  88. Node * setRoot() {
  89.   Node * n = (Node * ) malloc(1 * sizeof(struct Node));
  90.   //n->similar = NULL;
  91.   n -> isWord = false;
  92.   for (int i = 0; i < 25; i++) {
  93.     n -> data[i] = NULL;
  94.   }
  95.   for (int i = 0; i < maxChar; i++) {
  96.     n -> children[i] = NULL;
  97.   }
  98.   n -> parent = NULL;
  99.   return n;
  100. }
  101.  
  102. //checks if it is a word
  103. bool isItAWord(Node * n) {
  104.   return n -> isWord;
  105. }
  106.  
  107. //insert function. Starts at root and will traverse down tree creating 
  108. //additional nodes as needed until reaches the end of the word 
  109. void insert(Node * root, char * key) {
  110.   Node * trieExplorer = root;
  111.  
  112.   //Node *trieExplorer = malloc(1* sizeof(Node));
  113.   int depth;
  114.   int length = strlen(key);
  115.   int index;
  116.   char word[25] = {
  117.     0
  118.   };
  119.  
  120.   for (depth = 0; depth < length; depth++) {
  121.     index = charToInt(key[depth]);
  122.     word[depth] = key[depth];
  123.     if (!trieExplorer -> children[index]) {
  124.       trieExplorer -> children[index] = newNode(trieExplorer);
  125.     }
  126.     trieExplorer = trieExplorer -> children[index];
  127.   }
  128.  
  129.   trieExplorer -> isWord = true;
  130.   for (int i = 0; i < 25; i++) {
  131.     trieExplorer -> data[i] = & word[i];
  132.   }
  133.   printf(word);
  134.   printf(" %d ", trieExplorer -> isWord);
  135. }
  136.  
  137. //starting at the root of the trie this will crawl down the tree using the key
  138. //until it either reaches a dead end or the end of the input 
  139. bool search(Node * root, char * key) {
  140.  
  141.   Node * searchNode = root;
  142.   int depth;
  143.   int length = strlen(key);
  144.   int index;
  145.   char word[25] = {
  146.     0
  147.   };
  148.   for (depth = 0; depth < length; depth++) {
  149.     index = charToInt(key[depth]);
  150.     word[depth] = key[depth];
  151.     if (searchNode -> children[index] != NULL) {
  152.       searchNode = searchNode -> children[index];
  153.  
  154.     }
  155.   }
  156.   printf(word);
  157.   return isItAWord(searchNode);
  158.   free(searchNode);
  159. }
  160.  
  161. void freeNode(Node * n) {
  162.   if (n -> data != NULL) free((n -> data));
  163.   for (int i = 0; i < 8; i++) {
  164.     if (n -> children[i] != NULL) {
  165.       free(n -> children[i]);
  166.     }
  167.   }
  168.   free(n);
  169. }
  170.  
  171. void freeTrie(Node * n) {
  172.   if (n != NULL) {
  173.     for (int i = 0; i < 8; i++) {
  174.       if (n -> children[i] != NULL) {
  175.         freeTrie(n -> children[i]);
  176.       }
  177.     }
  178.     freeNode(n);
  179.   }
  180. }
  181.  
  182. int main(int argc, char ** argv) {
  183.   char word[MAX_LINE];
  184.  
  185.   //Node *start = malloc(1* sizeof(Node));
  186.   Node * start = setRoot();
  187.   while (fgets(word, MAX_LINE, stdin)) {
  188.     insert(start, word);
  189.     printf("%s\n", word);
  190.   }
  191.   printf("%d\n", search(start, "rocks"));
  192.   printf("%d\n", search(start, "up"));
  193.   printf("%d\n", search(start, "tuple"));
  194.   printf("%d\n", search(start, "things"));
  195.   printf("%d\n", search(start, "zebra"));
  196.   //fclose(file);
  197.   //freeTrie(start);
  198.   //free(start);
  199.  
  200. }
Success #stdin #stdout 0s 4952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
rocks0
up0
tuple0
things0
zebra0
https://ideone.com/J2khfy
language:
C (gcc 8.3)
created:
3 years ago
visibility:
public

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!