-
Notifications
You must be signed in to change notification settings - Fork 0
/
trie.c
96 lines (73 loc) · 2.05 KB
/
trie.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
#define NUM_ASCII_CHARS 256
struct trie_node {
int terminal;
trie_t children[NUM_ASCII_CHARS];
};
trie_t trie_new_node() {
trie_t node = malloc(sizeof(struct trie_node));
if (node) {
int i;
node->terminal = 0;
for(i = 0; i < NUM_ASCII_CHARS; i++)
node->children[i] = NULL;
}
return node;
}
void trie_delete_node(trie_t node) {
int i;
if (node == NULL)
return;
for (i = 0; i < NUM_ASCII_CHARS; i++)
trie_delete_node(node->children[i]);
free(node);
}
void trie_insert_word(trie_t root, char *word) {
for (int i = 0; i < strlen(word); ++i) {
if (root->children[word[i]] == NULL)
root->children[word[i]] = trie_new_node();
root = root->children[word[i]];
}
root->terminal = 1;
}
int trie_search_word(trie_t root, char *word) {
if(root == NULL)
return 0;
for (int i = 0; i < strlen(word); ++i) {
root = root->children[word[i]];
if (root == NULL)
return 0;
}
return root->terminal;
}
void trie_print_node(trie_t node, char* prefix) {
int ascii_index = 0;
if (node->terminal)
printf("%s\n", prefix);
for (ascii_index = 0; ascii_index < NUM_ASCII_CHARS; ++ascii_index) {
if (node->children[ascii_index]) {
size_t len = strlen(prefix);
char * word = malloc(len + 2);
strncpy(word, prefix, len);
word[len] = ascii_index;
word[len + 1] = '\0';
trie_print_node(node->children[ascii_index], word);
free(word);
}
}
}
void trie_print_prefixed_word(trie_t root, char *prefix) {
int i;
for (i = 0; i < strlen(prefix); ++i){
char ascii_index = prefix[i];
if (!root->children[ascii_index]) {
printf("Nema mogucih kandidata.\n");
return;
}
root = root->children[ascii_index];
}
trie_print_node(root, prefix);
}