Trie Implementation in C
Hello, I learned Trie in my CS1 class, and implemented it. So, let me share my code! My struct for trie looks like this
struct trie {
int isWord;
struct trie* nextLetter[26];
};
And, my code for creating single node, and inserting a word looks like this.
struct trie* createSingleTrie() {
struct trie* temp = malloc(sizeof(struct trie));
temp->isWord = 0;
int i;
for (i = 0; i < 26; i++) {
temp->nextLetter[i] = NULL;
}
return temp;
}
void insertWord(struct trie* dictionary, char word[], int index, int wordLength) {
if (index == wordLength) {
dictionary->isWord = 1;
return;
}
if (dictionary->nextLetter[word[index] - 'a'] == NULL) {
dictionary->nextLetter[word[index] - 'a'] = createSingleTrie();
}
insertWord(dictionary->nextLetter[word[index] - 'a'], word, index + 1, wordLength);
}
int isInDictionary(struct trie* dictionary, char word[], int index, int length) {
if (dictionary == NULL) {
return 0;
}
if (index == length) {
return dictionary->isWord;
}
return isInDictionary(dictionary->nextLetter[word[index] - 'a'], word, index + 1, length);
}
It is a bit long to put all codes here, so check out my Github Gist!