-
-
Save choaimeloo/ffb96f7e43d67e81f0d44c08837f5944 to your computer and use it in GitHub Desktop.
// Implements a dictionary's functionality | |
#include <ctype.h> | |
#include <stdbool.h> | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include <strings.h> | |
#include "dictionary.h" | |
#define HASHTABLE_SIZE 10000 | |
// Defines struct for a node | |
typedef struct node | |
{ | |
char word[LENGTH + 1]; | |
struct node *next; | |
} | |
node; | |
node *hashtable[HASHTABLE_SIZE]; | |
// Hashes the word (hash function posted on reddit by delipity) | |
// The word you want to hash is contained within new node, arrow, word. | |
// Hashing that will give you the index. Then you insert word into linked list. | |
int hash_index(char *hash_this) | |
{ | |
unsigned int hash = 0; | |
for (int i = 0, n = strlen(hash_this); i < n; i++) | |
{ | |
hash = (hash << 2) ^ hash_this[i]; | |
} | |
return hash % HASHTABLE_SIZE; | |
} | |
// Initializes counter for words in dictionary | |
int word_count = 0; | |
// Loads dictionary into memory, returning true if successful else false | |
bool load(const char *dictionary) | |
{ | |
// Opens dictionary | |
FILE *file = fopen(dictionary, "r"); | |
if (file == NULL) | |
{ | |
return false; | |
} | |
// Scans dictionary word by word (populating hash table with nodes containing words found in dictionary) | |
char word[LENGTH + 1]; | |
while (fscanf(file, "%s", word) != EOF) | |
{ | |
// Mallocs a node for each new word (i.e., creates node pointers) | |
node *new_node = malloc(sizeof(node)); | |
// Checks if malloc succeeded, returns false if not | |
if (new_node == NULL) | |
{ | |
unload(); | |
return false; | |
} | |
// Copies word into node if malloc succeeds | |
strcpy(new_node->word, word); | |
// Initializes & calculates index of word for insertion into hashtable | |
int h = hash_index(new_node->word); | |
// Initializes head to point to hashtable index/bucket | |
node *head = hashtable[h]; | |
// Inserts new nodes at beginning of lists | |
if (head == NULL) | |
{ | |
hashtable[h] = new_node; | |
word_count++; | |
} | |
else | |
{ | |
new_node->next = hashtable[h]; | |
hashtable[h] = new_node; | |
word_count++; | |
} | |
} | |
fclose(file); | |
return true; | |
} | |
// Returns true if word is in dictionary else false | |
bool check(const char *word) | |
{ | |
// Creates copy of word on which hash function can be performed | |
int n = strlen(word); | |
char word_copy[LENGTH + 1]; | |
for (int i = 0; i < n; i++) | |
{ | |
word_copy[i] = tolower(word[i]); | |
} | |
// Adds null terminator to end string | |
word_copy[n] = '\0'; | |
// Initializes index for hashed word | |
int h = hash_index(word_copy); | |
// Sets cursor to point to same address as hashtable index/bucket | |
node *cursor = hashtable[h]; | |
// Sets cursor to point to same location as head | |
// If the word exists, you should be able to find in dictionary data structure. | |
// Check for word by asking, which bucket would word be in? hashtable[hash(word)] | |
// While cursor does not point to NULL, search dictionary for word. | |
while (cursor != NULL) | |
{ | |
// If strcasecmp returns true, then word has been found | |
if (strcasecmp(cursor->word, word_copy) == 0) | |
{ | |
return true; | |
} | |
// Else word has not yet been found, advance cursor | |
else | |
{ | |
cursor = cursor->next; | |
} | |
} | |
// Cursor has reached end of list and word has not been found in dictionary so it must be misspelled | |
return false; | |
} | |
// Returns number of words in dictionary if loaded else 0 if not yet loaded | |
unsigned int size(void) | |
{ | |
return word_count; | |
} | |
// Unloads dictionary from memory, returning true if successful else false | |
bool unload(void) | |
{ | |
node *head = NULL; | |
node *cursor = head; | |
// freeing linked lists | |
while (cursor != NULL) | |
{ | |
node *temp = cursor; | |
cursor = cursor->next; | |
free(temp); | |
} | |
return true; | |
} |
Sir, my code is a question
:( program is free of memory errors
expected "MISSPELLED WOR...", not "### unhandled ..."
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define N 26
#define LENGTH 45
#define TABLE_SIZE 1000
typedef struct node
{
char word[LENGTH + 1];
struct node *left;
struct node *right;
}
node;
// Hash table declaration
node *hash_table[TABLE_SIZE];
// Define a function to compute the hash index of a word
unsigned int hash_index(const char *str)
{
unsigned int hash = 0;
int c;
while ((c = *str++) != '\0')
{
hash = hash << 1;
hash = hash + c;
}
return hash % TABLE_SIZE;
}
// Define a function to compare two strings in a case-insensitive manner
int strcasecmp(const char *s1, const char *s2)
{
char c1, c2;
while (*s1 && *s2)
{
c1 = toupper(*s1);
c2 = toupper(*s2);
if (c1 != c2)
{
return c1 - c2;
}
s1++;
s2++;
}
return *s1 - *s2;
}
node *insert(node *root, const char *word)
{
// Base case: empty tree
if (root == NULL)
{
// Allocate memory for new node
node *new_node = malloc(sizeof(node));
if (new_node == NULL)
{
return NULL;
}
// Copy word into node
strcpy(new_node->word, word);
// Set left and right children to NULL
new_node->left = new_node->right = NULL;
// Return the new node
return new_node;
}
// Compare word with node word
int cmp = strcasecmp(word, root->word);
// Insert node in left subtree if word is smaller than node word
if (cmp < 0)
{
root->left = insert(root->left, word);
}
// Insert node in right subtree if word is greater than node word
else if (cmp > 0)
{
root->right = insert(root->right, word);
}
// Return the root of the tree
return root;
}
// Calculate the hash index of the word
bool check(const char *word, node *hash_table_arr[])
{
// Calculate the hash index of the word
int h = hash_index(word);
// Find the correct entry in the hash table
for (node *entry = hash_table[h]; entry != NULL; entry = entry->right)
{
// If the word is found, return true
if (strcasecmp(word, entry->word) == 0)
{
return true;
}
}
// Return false if the word is not found
return false;
}
int main()
{
// ... (rest of the code remains the same)
}
Thank you so much! This code was very useful, but I just have one question. Why do you need to make a copy of the word in the check function? I just want to know how it works. Thank you.
still dont get it no error but fails valgrind how can i free up that remaining memory