fork download 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5.  
  6.  
  7. typedef struct Trie Trie;
  8.  
  9. struct Trie {
  10.     char key[16];
  11.     int end;
  12.     Trie *next;
  13.     Trie *child;
  14. };
  15.  
  16. static Trie *trie_create(const char *str)
  17. {
  18.     Trie *trie = malloc(sizeof(*trie));
  19.  
  20.     trie->next = NULL;
  21.     trie->child = NULL;
  22.     trie->end = 0;
  23.     strcpy(trie->key, str);
  24.  
  25.     return trie;
  26. }
  27.  
  28. void trie_add(Trie **trie, const char *str) 
  29. {
  30.     char buf[strlen(str) + 1];
  31.     char *tok;
  32.     int *p = NULL;
  33.  
  34.     strcpy(buf, str);
  35.  
  36.     tok = strtok(buf, ".");
  37.  
  38.     while (tok) {
  39.         while (*trie) {
  40.             if (strcmp((*trie)->key, tok) == 0) break;
  41.  
  42.             trie = &(*trie)->next;
  43.         }
  44.  
  45.         if (*trie == NULL) {
  46.             *trie = malloc(sizeof(**trie));
  47.  
  48.             (*trie)->next = NULL;
  49.             (*trie)->child = NULL;
  50.             (*trie)->end = 0;
  51.             strcpy((*trie)->key, tok);
  52.         }
  53.  
  54.         p = &(*trie)->end;
  55.         trie = &(*trie)->child;
  56.  
  57.         tok = strtok(NULL, ".");
  58.     }
  59.  
  60.     if (p) (*p)++;
  61. }
  62.  
  63. void trie_delete(Trie *trie)
  64. {
  65.     while (trie) {
  66.         Trie *t = trie;   
  67.  
  68.         trie_delete(trie->child);
  69.         trie = trie->next;
  70.         free(t);
  71.     }
  72. }
  73.  
  74. void trie_print(Trie *trie, int level)
  75. {
  76.     while (trie) {
  77.         printf("%*s%s", level * 4, "", trie->key);
  78.         if (trie->end) printf(" [%d]", trie->end);
  79.         puts("");
  80.  
  81.         trie_print(trie->child, level + 1);
  82.         trie = trie->next;
  83.     }
  84. }
  85.  
  86. int main()
  87. {
  88.     Trie *trie = NULL;
  89.  
  90.     trie_add(&trie, "foo.foo");
  91.     trie_add(&trie, "foo.foo");
  92.     trie_add(&trie, "foo.bar.foo.*");
  93.     trie_add(&trie, "foo.baz.*");
  94.     trie_add(&trie, "foo.*.bar");
  95.     trie_add(&trie, "bar.foo.*.one");
  96.     trie_add(&trie, "bar.foo.*.two");
  97.     trie_add(&trie, "foo.foo");
  98.     trie_add(&trie, "foo.foo");
  99.     trie_add(&trie, "bar");
  100.  
  101.     trie_print(trie, 0);
  102.  
  103.     trie_delete(trie);
  104.  
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0s 9424KB
comments (?)
stdin 
Standard input is empty
stdout 
foo
    foo [4]
    bar
        foo
            * [1]
    baz
        * [1]
    *
        bar [1]
bar [1]
    foo
        *
            one [1]
            two [1]
https://ideone.com/QibcV3
language:
C (gcc 8.3)
created:
7 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!