Something is wrong with my check(). It over-calculates the number of misspelled words. It seems that my code misses some conditions. Here is my code:
#include <stdbool.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdio.h>
#include "dictionary.h"
// Define a struct node to store words
typedef struct node
{
bool is_word;
struct node* children[27];
}
node;
// Set the root of tries
node root = {false, {NULL}};
I've updated the check(). Now it works.
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char* word)
{
node* current_node = &root;
for (int i = 0; i < LENGTH; i++)
{
// Check if the letter is in the right order.
if (word[i] != '\0')
{
// Calculate the index of the pointer of the corresponding trie.
int index = (isalpha(word[i])) ? (tolower(word[i]) - 'a'): 26;
// If the letter is in the loaded dictionary
if (current_node -> children[index] != NULL)
{
current_node = current_node -> children[index];
}
// If the letter is not in the loaded dictionary
else
{
return false;
}
}
// If reach the end of the word, check if it is indeed a word.
else
{
if (current_node -> is_word == true)
{
return true;
}
else
{
return false;
}
}
}
return false;
}
/**
* Loads dictionary into memory. Returns true if successful else false.
*/
EDIT 1: a new question.
current_node -> children[index] = malloc(sizeof(node));
current_node -> children[index] = {false, {NULL}}
After allocating memory for a new node, I tried to set the node to NULL, but my code reported error. Why my previous code node root = {false, {NULL}}; will work, but the code above won't? I think I'm still confused about the details of the usage of pointers.
EDIT 2: one more question.
node root = {false, {NULL}}
current_node -> children[index] = calloc(1, sizeof(node));
The first line create a node type in memory. How about the second one? Does it also create a node type or merely allocate the memory of the size of a node and set the data to zeroes? If it merely allocates memory, what operators should I use to assign values as current_node -> children[index] = {false, {NULL}} or current_node -> is_word = truewon't work?
int word_counter = 0;
bool load(const char* dictionary)
{
// Read words from dictionary and store them in the tries
// Read the first letter
// Store it in the relevant children array (node -> children[x])
// Read the next letter
// Store it in the relevant children array (node -> children[x] -> children[x])
// If a space is read, set is_word true. And contine the loop.
// Open the dictionary
FILE* infile = fopen(dictionary, "r");
if (infile == NULL)
{
printf("Could not open %s.\n", dictionary);
return false;
}
node* current_node = &root;
for (int c = fgetc(infile); c != EOF; c = fgetc(infile))
{
if (c != '\n')
{
// Calculate the index of the children array if c is a letter or an apostrophe.
int index = (isalpha(c)) ? (c - 'a'): 26;
// If children[index] is NULL, add another node to it to suggest that the word hasn't ended yet.
if (current_node -> children[index] == NULL)
{
current_node -> children[index] = malloc(sizeof(node));
if (current_node -> children[index] == NULL)
{
printf("Memory allocation failed!");
return false;// Or return 1???
}
current_node = current_node -> children[index];
}
else
{
current_node = current_node -> children[index];
}
}
// If c is a '\n', mark the node as the end of the word. And reset the current_node to the root.
else
{
current_node -> is_word = true;
word_counter ++;
current_node = &root;
}
}
fclose(infile);
return true;
}
/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int size(void)
{
// TODO
return word_counter;
}
/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
void free_node(node* cursor);
bool unload(void)
{
// TODO
//node* current_node = root;
for (int i = 0; i < 27; i++)
{
if (root.children[i] != NULL)
{
free_node(root.children[i]);
}
}
return true;
}
void free_node(node* cursor)
{
for (int i = 0; i < 27; i++)
{
// If the child pointer do not point to Null,
// it suggests that the pointer points to another node.
// So dive into the child node.
if (cursor -> children[i] != NULL)
{
cursor = cursor -> children[i];
// and return the for loop
return free_node(cursor);
}
}
// Continue the for loop
// If reach the end of the loop, it suggests the pointer array all point to null.
// Now you can free the current node.
free(cursor);
}
