USA: +1 725-224-8795 
Sign in
There are a lot of uses for a hash map, and one of them is implementing a spell checker. All you need to get started is a dictionary, which is provided in dictionary.txt. In spellChecker.c you will find some code to get you started with the spell checker. It is fairly similar to the code in main.c. You can build the program with make spellChecker. FYI: The spellchecker program flow should as following – 1. The user types in a word 2. Potential matches are outputted Like “Did you mean…?” etc 3. Continue to prompt user for word until they type quit The best way to implement a dictionary that’s used for a spellchecker would probably be to design it with that purpose in mind from the beginning, i.e. associating a similarity for each word to some base word (maybe “abcdefghijklmnopqrstuvwyz”) and then incorporating that into the hash function. There are better ways ( https://en.wikipedia.org/wiki/Levenshtein_distance) to establish similarity than computing the cosine of the angle between two vectors (strings) to create a list of candidates and further winnowed that list according to substring comparisons. So, I would say calculating the Levenshtein distance between the misspelled word and all strings in the dictionary, create 5/6 best candidates and print them as suggestion.
spellchecker.c
#include “hashMap.h”
#include <assert.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
* Allocates a string for the next word in the file and returns it. This string
* is null terminated. Returns NULL after reaching the end of the file.
* @param file
* @return Allocated string or NULL.
*/
char* nextWord(FILE* file)
{
int maxLength = 16;
int length = 0;
char* word = malloc(sizeof(char) * maxLength);
while (1)
{
char c = fgetc(file);
if ((c >= ‘0’ && c <= ‘9’) ||
(c >= ‘A’ && c <= ‘Z’) ||
(c >= ‘a’ && c <= ‘z’) ||
c == ”’)
{
if (length + 1 >= maxLength)
{
maxLength *= 2;
word = realloc(word, maxLength);
}
word[length] = c;
length++;
}
else if (length > 0 || c == EOF)
{
break;
}
}
if (length == 0)
{
free(word);
return NULL;
}
word[length] = ‘ ’;
return word;
}
/**
* Loads the contents of the file into the hash map.
* @param file
* @param map
*/
void loadDictionary(FILE* file, HashMap* map)
{
// FIXME: implement
}
/**
* Prints the concordance of the given file and performance information. Uses
* the file input1.txt by default or a file name specified as a command line
* argument.
* @param argc
* @param argv
* @return
*/
int main(int argc, const char** argv)
{
// FIXME: implement
HashMap* map = hashMapNew(1000);
FILE* file = fopen(“dictionary.txt”, “r”);
clock_t timer = clock();
loadDictionary(file, map);
timer = clock() – timer;
printf(“Dictionary loaded in %f secondsn”, (float)timer / (float)CLOCKS_PER_SEC);
fclose(file);
char inputBuffer[256];
int quit = 0;
while (!quit)
{
printf(“Enter a word or “quit” to quit: “);
scanf(“%s”, inputBuffer);
// Implement the spell checker code here..
if (strcmp(inputBuffer, “quit”) == 0)
{
quit = 1;
}
}
hashMapDelete(map);
return 0;
}
hashMap.h
#ifndef HASH_MAP_H
#define HASH_MAP_H
/*
* CS 261 Data Structures
* Assignment 6
*/
#define HASH_FUNCTION hashFunction1
#define MAX_TABLE_LOAD .75
typedef struct HashMap HashMap;
typedef struct HashLink HashLink;
struct HashLink
{
char* key;
int value;
HashLink* next;
};
struct HashMap
{
HashLink** table;
// Number of links in the table.
int size;
// Number of buckets in the table.
int capacity;
};
HashMap* hashMapNew(int capacity);
void hashMapDelete(HashMap* map);
int* hashMapGet(HashMap* map, const char* key);
void hashMapPut(HashMap* map, const char* key, int value);
void hashMapRemove(HashMap* map, const char* key);
int hashMapContainsKey(HashMap* map, const char* key);
int hashMapSize(HashMap* map);
int hashMapCapacity(HashMap* map);
int hashMapEmptyBuckets(HashMap* map);
float hashMapTableLoad(HashMap* map);
void hashMapPrint(HashMap* map);
#endif
Expert Answer
Copyable code:
File Name: hashMap.h
//Define header
#ifndef HASH_MAP_H
#define HASH_MAP_H
//Define preprocessor
#define HASH_FUNCTION hashFunction1
//Define constant
#define MAX_TABLE_LOAD .75
//Rename structure
typedef struct HashMap HashMap;
//Rename structure
typedef struct HashLink HashLink;
//Deifne structure
struct HashLink
{
//Create variable
char* key;
//Create variable
int value;
//Create link
HashLink* next;
};
//Define structure
struct HashMap
{
//Create variable
HashLink** table;
//Create variable
int size;
//Create variable
int capacity;
};
//Declare function
HashMap* hashMapNew(int capacity);
//Declare function
void hashMapDelete(HashMap* map);
//Declare function
int* hashMapGet(HashMap* map, const char* key);
//Declare function
void hashMapPut(HashMap* map, const char* key, int value);
//Declare function
void hashMapRemove(HashMap* map, const char* key);
//Declare function
int hashMapContainsKey(HashMap* map, const char* key);
//Declare function
int hashMapSize(HashMap* map);
//Declare function
int hashMapCapacity(HashMap* map);
//Declare function
int hashMapEmptyBuckets(HashMap* map);
//Declare function
float hashMapTableLoad(HashMap* map);
//Declare function
void hashMapPrint(HashMap* map);
#endif
File Name: hashMap.c
//Include the files
#include “hashMap.h”
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
//Define function
HashLink* hashLinkNew(const char* key, int value, HashLink* next)
{
//Allocate space
HashLink* lnk = (HashLink*) malloc(sizeof(HashLink));
//Allocate space for key
lnk->key = (char*)malloc(sizeof(char) * (strlen(key) + 1));
//Copy key
strcpy(lnk->key, key);
//Copy value
lnk->value = value;
//Set link
lnk->next = next;
//Return
return lnk;
}
//Deifne function
static void hashLinkDelete(HashLink* lnk)
{
//Delete
free(lnk->key);
//Remove space
free(lnk);
}
//Define function
void hashMapInit(HashMap* hmap, int capacity)
{
//Declare variable
int cc;
//Set value
hmap->capacity = capacity;
//Set value
hmap->size = 0;
//Allocate space
hmap->table = (HashLink**) malloc(sizeof(HashLink*) * capacity);
//Loop
for (cc = 0; cc < capacity; cc++)
{
//Set value
hmap->table[cc] = NULL;
}
}
//Define function
void hashMapCleanUp(HashMap* hmap)
{
//Declare variable
int indxx;
//Create loop
for (indxx = 0; indxx < hmap->capacity; indxx++)
{
//Set value
HashLink *tp = hmap->table[indxx];
//Set value
hmap->table[indxx] = 0;
//Loop
while (tp != 0)
{
//Set value
HashLink *trailer = tp;
//Set value
tp = tp->next;
//Call function
hashLinkDelete(trailer);
}
//Delete
free(hmap->table[indxx]);
}
//Delete space
free(hmap->table);
}
//Define function
HashMap* hashMapNew(int capacity)
{
//Allocate space
HashMap* hmap = (HashMap *)malloc(sizeof(HashMap));
//Call function
hashMapInit(hmap, capacity);
//Return
return hmap;
}
//Deifne function
void hashMapDelete(HashMap* hmap)
{
//Call function
hashMapCleanUp(hmap);
//Delete space
free(hmap);
}
//Define function
int* hashMapGet(HashMap* hmap, const char* key)
{
//Set value
int indxx = HASH_FUNCTION(key) % hmap->capacity;
//Find value
HashLink *tp = hmap->table[indxx];
//Create loop
while (tp != 0)
{
//Check condition
if (strcmp(tp->key, key)==0)
{
//Return
return &(tp->value);
}
//Get next element
tp = tp->next;
}
//Return
return NULL;
}
//Define function
void resizeTable(HashMap* hmap, int capacity)
{
//Create variable
HashLink *tp;
//Create variable
HashLink *ldLink;
//Create variable
HashLink *trLink;
//Create and set value
int prevCap = hmap->capacity;
//Declare variable
int indxx;
//Create varaible
int delindx;
//Get value
HashLink **prevMap = hmap->table;
//Call function
hashMapInit(hmap, 2*capacity);
//Loop
for (indxx = 0; indxx < prevCap; indxx++)
{
//Get value
tp = prevMap[indxx];
//Loop
while (tp != 0)
{
//Call function
hashMapPut(hmap, tp->key, tp->value);
//Get next element
tp = tp->next;
}
}
//Loop
for (delindx = 0; delindx < prevCap; delindx++)
{
//Get value
ldLink = prevMap[delindx];
//Set value
prevMap[delindx] = 0;
//Loop
while (ldLink != 0)
{
//Get value
trLink = ldLink;
//Get next element
ldLink = ldLink->next;
//Call function
hashLinkDelete(trLink);
}
//Delete space
free(prevMap[delindx]);
}
//Free space
free(prevMap);
}
//Define function
void hashMapPut(HashMap* hmap, const char* key, int value)
{
//Declare variable
float tpLoad;
//Declare variable
HashLink *new1;
//Declare variable
HashLink *tp;
//Find value
int indxx = HASH_FUNCTION(key) % hmap->capacity;
//Check condition
if (indxx < 0)
{
//Add value
indxx += hmap->capacity;
}
//Get value
tp = hmap->table[indxx];
//Loop
while (tp != 0)
{
//Check condition
if (strcmp(tp->key, key)==0)
{
//Set value
tp->value = value;
//Return
return;
}
//Get next element
tp = tp->next;
}
//Check condition
if (hmap->table[indxx] == 0)
{
//Call function
new1 = hashLinkNew(key, value, 0);
}
//Else
else
{
//Call function
new1 = hashLinkNew(key, value, (hmap->table[indxx]) );
}
//Set value
hmap->table[indxx] = new1;
//Increment size by 1
hmap->size++;
//Call function
tpLoad = hashMapTableLoad(hmap);
//Check condition
if (tpLoad >= MAX_TABLE_LOAD)
{
//Call function
resizeTable(hmap, hmap->capacity);
}
}
//Define function
void hashMapRemove(HashMap* hmap, const char* key)
{
//Declare variable
HashLink *tpLead, *tpTrail;
//Delcare variable
int indxx;
//Check condition
if (hashMapContainsKey(hmap, key) == 0)
{
//return
return;
}
//Else
else
{
//Call function
indxx = HASH_FUNCTION(key) % hmap->capacity;
//Check condition
if (indxx < 0)
{
//Set value
indxx += hmap->capacity;
}
//Get value
tpLead = hmap->table[indxx];
//Get value
tpTrail = hmap->table[indxx];
//Loop
while (tpLead != 0)
{
//Check condition
if (strcmp((hmap->table[indxx])->key, key) == 0)
{
//Set value
hmap->table[indxx] = tpLead->next;
//Call function
hashLinkDelete(tpLead);
//Decrement value
hmap->size–;
//Return
return;
}
//Check condition
else if (strcmp(tpLead->key, key) == 0)
{
//Set value
tpTrail->next = tpLead->next;
//Call function
hashLinkDelete(tpLead);
//Decrement size by 1
hmap->size–;
//Return
return;
}
//Set value
tpTrail = tpLead;
//Get next element
tpLead = tpLead->next;
}
}
}
//Deifne function
int hashMapContainsKey(HashMap* hmap, const char* key)
{
//Call function
int indxx = HASH_FUNCTION(key) % hmap->capacity;
//Get value
HashLink *tp = hmap->table[indxx];
//Loop
while (tp != 0)
{
//Check condition
if (strcmp(tp->key, key)==0)
{
//Return
return 1;
}
//Get next value
tp = tp->next;
}
//Stop
return 0;
}
//Define function
int hashMapSize(HashMap* hmap)
{
//Return
return hmap->size;
}
//Define function
int hashMapCapacity(HashMap* hmap)
{
//Return
return hmap->capacity;
}
//Define function
int hashMapEmptyBuckets(HashMap* hmap)
{
//Declare variable
int indxx = 0;
//Declare variable
int nBts = 0;
//Loop
for (indxx = 0; indxx < hmap->capacity; indxx++)
{
//Check condition
if ( hmap->table[indxx] == 0)
{
//Increment value
nBts++;
}
}
//Return
return nBts;
}
//Define function
float hashMapTableLoad(HashMap* hmap)
{
//Get value
double nBts = (double)hmap->capacity;
//Get value
double nLinks = (double)hashMapSize(hmap);
//Find and return value
return nLinks/nBts;
}
//Define function
void hashMapPrint(HashMap* hmap)
{
//Declare variable
int cc;
//Loop
for (cc = 0; cc < hmap->capacity; cc++)
{
//Get value
HashLink* lnk = hmap->table[cc];
//Check condition
if (lnk != NULL)
{
//Print statement
printf(“nBucket %cc ->”, cc);
//Loop
while (lnk != NULL)
{
//Print statement
printf(” (%s, %d) ->”, lnk->key, lnk->value);
//Get next value
lnk = lnk->next;
}
}
}
//Print new line
printf(“n”);
}
//Define function
int hashFunction1(const char* key)
{
//Declare variable
int kr = 0;
//Declare variable
int cc;
//Loop
for (cc = 0; key[cc] != ‘ ’; cc++)
{
//Get value
kr += key[cc];
}
//Return
return kr;
}
//Define function
int hashFunction2(const char* key)
{
//Create variable
int kr = 0;
//Create variable
int cc;
//Loop
for (cc = 0; key[cc] != ‘ ’; cc++)
{
//Find value
kr += (cc + 1) * key[cc];
}
//Return
return kr;
}
File Name: spellchecker.c
//Include headers
#include “hashMap.h”
#include <assert.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Define function
char* nextWord(FILE* inpFile)
{
//Create variable
int maxLength = 16;
//Define variable
int length = 0;
//Allocate space
char* wrd = (char *)malloc(sizeof(char) * maxLength);
//Loop
while (1)
{
//Read character
char c = fgetc(inpFile);
//Check condition
if ((c >= ‘0’ && c <= ‘9’) ||
(c >= ‘A’ && c <= ‘Z’) ||
(c >= ‘a’ && c <= ‘z’) ||
c == ”’)
{
//Check condition
if (length + 1 >= maxLength)
{
//Multiply
maxLength *= 2;
//Allocate space
wrd = (char *)realloc(wrd, maxLength);
}
//Set value
wrd[length] = c;
//Increment value
length++;
}
//Check condition
else if (length > 0 || c == EOF)
{
//Break
break;
}
}
//Check condition
if (length == 0)
{
//Remove space
free(wrd);
//Return
return NULL;
}
//Terminate array
wrd[length] = ‘ ’;
//Return
return wrd;
}
//Define function
void loadDictionary(FILE* inpFile, HashMap* map)
{
//Call function
char* wrd = nextWord(inpFile);
//Loop
while (wrd)
{
//Call function
hashMapPut(map, wrd, 1);
//Delete space
free(wrd);
//Call function
wrd = nextWord(inpFile);
}
//Delet espace
free(wrd);
}
//Define function
int main(int argc, const char** argv)
{
//Declare variable
char inpBuf[256];
//Declare variable
char wrdAns[50];
//Declare variable
int quit = 0;
//Delcare variable
int wrdBool = 0;
//Delcare file pointer
FILE* inpFile;
//Create timer variable
clock_t timer;
//Call function
HashMap* map = hashMapNew(1000);
//Print message
printf(“Opening dictionary.txtn”);
//Open file
inpFile = fopen(“dictionary.txt”, “r”);
//Start timer
timer = clock();
//Call function
loadDictionary(inpFile, map);
//Call function
hashMapPrint(map);
//Stop timer
timer = clock() – timer;
//Print statement
printf(“Dictionary loaded in %f secondsn”, (float)timer / (float)CLOCKS_PER_SEC);
//Close file
fclose(inpFile);
//Loop
while (!quit)
{
//Print statement
printf(“Enter a word or “quit” to quit: “);
//Read input
scanf(“%s”, inpBuf);
//Check condition
if (hashMapContainsKey(map, inpBuf))
{
//Call function
int idx = hashFunction1(inpBuf) % hashMapCapacity(map);
//Get value
HashLink* cur = map->table[idx];
//Print statement
printf(“Possible matches:n”);
//Loop
while (cur) {
//Check condition
if (cur->key[0] == inpBuf[0]) {
//Print statement
printf(“%sn”, cur->key);
}
//Set value
cur = cur->next;
}
}
//Check condition
else if (strcmp(inpBuf, “quit”) == 0)
{
//Set value
quit = 1;
}
//Else
else {
//Print statement
printf(“Word not found in dictionary!n”);
//Set value
wrdBool = 1;
//Loop
while (wrdBool)
{
//Print statement
printf(“Would you like to add your word to the dictionary? y/n: “);
//Read value
scanf(“%s”, wrdAns);
//Set value
wrdBool = 0;
//Check condition
if (strcmp(wrdAns, “y”) == 0) {
//Call function
hashMapPut(map, inpBuf, 1);
//Print statement
printf(“Word added to dictionary!n”);
}
//Check condition
else if (strcmp(wrdAns, “n”) == 0)
{
//Print statement
printf(“Word ignored!n”);
}
//Else
else {
//Set value
wrdBool = 1;
}
}
}
}
//Call function
hashMapDelete(map);
//Stop
return 0;
}
