CS50 PSet 5: Speller

// Implements a dictionary's functionality#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <strings.h>
#include <ctype.h>
#include "dictionary.h"
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// Number of buckets in hash table
const unsigned int N = 100000;
// Hash table
node *table[N];
int dict_size = 0;

load()

  1. The file to be read from.
  2. The format of each item to be read. Here %s is used to tell it to read one string at a time.
  3. Where each item read is to be stored, the next_word array in this case.
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
// Open dictionary file
FILE *dict_pointer = fopen(dictionary, "r");
// Check if null
if (dictionary == NULL)
{
printf("Unable to open %s\n", dictionary);
return false;
}
// Initialise word array
char next_word[LENGTH + 1];
// Read strings from file one at a time
while (fscanf(dict_pointer, "%s", next_word) != EOF)
{
// Create new node for each word
node *n = malloc(sizeof(node));
if (n == NULL)
{
return false;
}
// copy word into node using strcopy
strcpy(n->word, next_word);
// Hash word to obtain hash value
int hash_value = hash(next_word);
// Insert node into hash table at that location
n->next = table[hash_value];
table[hash_value] = n;
dict_size++;
}
// Close file
fclose(dict_pointer);
return true;
}

hash()

// Hashes word to a number
unsigned int hash(const char *word)
{
// Function should take a string and return an index
// This hash function adds the ASCII values of all characters in the word together
long sum = 0;
for (int i = 0; i < strlen(word); i++)
{
sum += tolower(word[i]);
}
return sum % N;
}

size()

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
return dict_size;
}

check()

// Returns true if word is in dictionary else false
bool check(const char *word)
{
// Hash word to obtain hash value
int hash_value = hash(word);
// Access linked list at that index in hash table
node *n = table[hash_value];
// Traverse linked list, looking for word (strcasecomp)
while (n != NULL)
{
if (strcasecmp(word, n->word) == 0)
{
return true;
}
n = n->next;
}
return false;
}

unload()

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
// Iterate over hash table and free nodes in each linked list
for (int i = 0; i < N; i++)
{
// Assign cursor
node *n = table[i];
// Loop through linked list
while (n != NULL)
{
// Make temp equal cursor;
node *tmp = n;
// Point cursor to next element
n = n->next;
// free temp
free(tmp);
}
if (n == NULL && i == N - 1)
{
return true;
}
}return false;
}

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

On Architectural Testability

SKip — Attendance Cum Bunk Manager Application

Anatomy of a GUID

Computer Science (My first week was hell in heaven)

API first approach with OpenAPI contracts, Maven & Spring Boot

Introducing the Joget Operator for Red Hat OpenShift: Low Code App Deployment Made Easy

Significance of Agile Methodology:

Milestones Are About Deliverables — Tentamen Software Testing Blog

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
JR

JR

More from Medium

Which Programming Language Should You Learn First?

Programming a Button | Embedded Systems

What is the Big O all about?

History of the Programming Languages