trie.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct trie {
	int isWord;
	struct trie* nextLetter[26];
};

const int MAX_WORD_LENGTH = 20;

// Main Dictionary Functions
struct trie* createSingleTrie();
void insertWord(struct trie* dictionary, char word[], int index, int wordLength);
int isInDictionary(struct trie* dictionary, char word[], int index, int length);

// Helper Fucntions
void printDictionary(struct trie* dictionary, char word[], int index, int length);
void printWord(char word[], int length);
void freeDictionary(struct trie* dictionary);

int main() {
	char word[MAX_WORD_LENGTH];

	// Create dictionary
	struct trie* dictionary = createSingleTrie();
	insertWord(dictionary, "dog", 0, 3);
	insertWord(dictionary, "monkey", 0, 6);
	insertWord(dictionary, "human", 0, 5);
	insertWord(dictionary, "dolphin", 0, 7);
	insertWord(dictionary, "elephant", 0, 8);
	insertWord(dictionary, "frog", 0, 4);

	// Check our dictionary first
	printf("Dictionary...\n");
	printDictionary(dictionary, word, 0, 0);

	// Let's do test
	strcpy(word, "dolphin");
	printf("%s is %sin dictionary.\n", word, isInDictionary(dictionary, word, 0, 7) ? "" : "not ");
	strcpy(word, "sample");
	printf("%s is %sin dictionary.\n", word, isInDictionary(dictionary, word, 0, 6) ? "" : "not ");
	strcpy(word, "tiger");
	printf("%s is %sin dictionary.\n", word, isInDictionary(dictionary, word, 0, 5) ? "" : "not ");
	strcpy(word, "kojote");
	printf("%s is %sin dictionary.\n", word, isInDictionary(dictionary, word, 0, 6) ? "" : "not ");
	strcpy(word, "elephant");
	printf("%s is %sin dictionary.\n", word, isInDictionary(dictionary, word, 0, 8) ? "" : "not ");

	// Free dictionary
	freeDictionary(dictionary);
}

// Main Dictionary Functions
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);
}

// Helper Functions
void printDictionary(struct trie* dictionary, char word[], int index, int length) {
	if (dictionary->isWord == 1) {
		printWord(word, length);
	}
	int i;
	for (i = 0; i < 26; i++) {
		if (dictionary->nextLetter[i] != NULL) {
			word[index] = (char) 97 + i;
			printDictionary(dictionary->nextLetter[i], word, index + 1, length + 1);
		}
	}
}

void printWord(char word[], int length) {
	int i;
	for (i = 0; i < length; i++) {
		printf("%c", word[i]);
	}
	printf("\n");
}


void freeDictionary(struct trie* dictionary) {
	if (dictionary == NULL) {
		free(dictionary);
		return;
	}
	int i;
	for (i = 0; i < 26; i++) {
		if (dictionary->nextLetter[i] != NULL) {
			freeDictionary(dictionary->nextLetter[i]);
			free(dictionary->nextLetter[i]);
		}
	}
}