trie.c

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

#define STR_HELPER(x) #x
#define STR(x) STR_HELPER(x)

#define TRIE_INIT_SIZE 100
#define TRIE_ALPHABET_SIZE 26
#define FIRST_LETTER 'a'
#define MAX_WORD_LENGTH 100

typedef struct node{
	int is_word;
	struct node * next[TRIE_ALPHABET_SIZE];
}Trie;

void add_word(Trie * trie, char * word){
	Trie * root = trie;

	while(*word){
		if(!isalpha(*word)){
			word++;
			continue;
		}

		int letter_index = tolower((int)*word);
		int index = letter_index - FIRST_LETTER;

		Trie * next_root = root->next[index];
		if(next_root == NULL){
			next_root = root->next[index] = (Trie *)calloc(sizeof(Trie), 1);
		}

		root = next_root;
		word++;
	}

	root->is_word = 1;
}

int is_word(Trie * trie, char * word){
	Trie * root = trie;

	while(*word && root != NULL){
		if(!isalpha(*word)){
			word++;
			continue;
		}

		int letter_index = tolower((int)*word);
		int index = letter_index - FIRST_LETTER;

		root = root->next[index];
		word++;
	}

	return root != NULL && root->is_word;
}

void load_words_from_file(Trie * trie, char * word_file){
	FILE * file = fopen(word_file, "r");
	while(!feof(file)){
		char word_buffer[MAX_WORD_LENGTH + 1];
		fscanf(file, "%" STR(MAX_WORD_LENGTH) "s", word_buffer);

		add_word(trie, word_buffer);
	}
}

int main(int argc, char * argv[]){
	(void)argc;
	(void)argv;

	Trie * trie = (Trie *)calloc(sizeof(Trie), 1);
	load_words_from_file(trie, "/usr/share/dict/words");

	while(!feof(stdin)){
		char word_buffer[MAX_WORD_LENGTH + 1];

		printf("Enter a word: ");
		scanf("%" STR(MAX_WORD_LENGTH) "s", word_buffer);
		if(is_word(trie, word_buffer)){
			printf("%s is in the dictionary\n", word_buffer);
		}else{
			printf("%s is not in the dictionary\n", word_buffer);
		}
	}

}