USA: +1 (725) 712-1730 
Sign in
Use the coding skeleton provided to create a spellchecker.
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
#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
hashMap.c – for reference
/*
* CS 261 Data Structures
* Assignment 6
* Name: Tim Kelly
* Date: 8/8/17
*/
#include “hashMap.h”
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
int hashFunction1(const char* key)
{
int r = 0;
for (int i = 0; key[i] != ‘ ’; i++)
{
r += key[i];
}
return r;
}
int hashFunction2(const char* key)
{
int r = 0;
for (int i = 0; key[i] != ‘ ’; i++)
{
r += (i + 1) * key[i];
}
return r;
}
/**
* Creates a new hash table link with a copy of the key string.
* @param key Key string to copy in the link.
* @param value Value to set in the link.
* @param next Pointer to set as the link’s next.
* @return Hash table link allocated on the heap.
*/
HashLink* hashLinkNew(const char* key, int value, HashLink* next)
{
HashLink* link = malloc(sizeof(HashLink));
link->key = malloc(sizeof(char) * (strlen(key) + 1));
strcpy(link->key, key);
link->value = value;
link->next = next;
return link;
}
/**
* Free the allocated memory for a hash table link created with hashLinkNew.
* @param link
*/
static void hashLinkDelete(HashLink* link)
{
free(link->key);
free(link);
}
/**
* Initializes a hash table map, allocating memory for a link pointer table with
* the given number of buckets.
* @param map
* @param capacity The number of table buckets.
*/
void hashMapInit(HashMap* map, int capacity)
{
map->capacity = capacity;
map->size = 0;
map->table = malloc(sizeof(HashLink*) * capacity);
for (int i = 0; i < capacity; i++)
{
map->table[i] = NULL;
}
}
/**
* Removes all links in the map and frees all allocated memory. You can use
* hashLinkDelete to free the links.
* @param map
*/
void hashMapCleanUp(HashMap* map)
{
// FIXME: implement
struct HashLink *link;
struct HashLink *next;
for (int i = 0; i < map->capacity; i++) {
link = map->table[i];
//iterate through the buckets
if (link != 0) {
do {
next = link->next;
hashLinkDelete(link);
link = next;
} while (next != 0);
}
}
free(map->table);
map->table = 0;
}
/**
* Creates a hash table map, allocating memory for a link pointer table with
* the given number of buckets.
* @param capacity The number of buckets.
* @return The allocated map.
*/
HashMap* hashMapNew(int capacity)
{
HashMap* map = malloc(sizeof(HashMap));
hashMapInit(map, capacity);
return map;
}
/**
* Removes all links in the map and frees all allocated memory, including the
* map itself.
* @param map
*/
void hashMapDelete(HashMap* map)
{
hashMapCleanUp(map);
free(map);
}
/**
* Returns a pointer to the value of the link with the given key. Returns NULL
* if no link with that key is in the table.
*
* Use HASH_FUNCTION(key) and the map’s capacity to find the index of the
* correct linked list bucket. Also make sure to search the entire list.
*
* @param map
* @param key
* @return Link value or NULL if no matching link.
*/
int* hashMapGet(HashMap* map, const char* key)
{
// FIXME: implement
int hashIndex = HASH_FUNCTION(key) % map->capacity;
if (hashIndex < 0)
hashIndex = hashIndex + map->capacity;
struct HashLink *link = map->table[hashIndex];
while (link != 0) {
if (strcmp(link->key, key) == 0)
return &(link->value);
else
link = link->next;
}
return 0;
}
/**
* Resizes the hash table to have a number of buckets equal to the given
* capacity. After allocating the new table, all of the links need to be
* rehashed into it because the capacity has changed.
*
* Remember to free the old table and any old links if you use hashMapPut to
* rehash them.
*
* @param map
* @param capacity The new number of buckets.
*/
void resizeTable(HashMap* map, int capacity)
{
// FIXME: implement
struct HashMap *newMap = hashMapNew(capacity);
struct HashLink *link;
for (int i = 0; i < map->capacity; i++) {
link = map->table[i];
//add links
while (link != 0) {
hashMapPut(newMap, link->key, link->value);
link = link->next;
}
}
//Swap the capacities of the tables
hashMapCleanUp(map);
map->table = newMap->table;
map->size = newMap->size;
map->capacity = newMap->capacity;
free(newMap); //free temporary map
}
/**
* Updates the given key-value pair in the hash table. If a link with the given
* key already exists, this will just update the value. Otherwise, it will
* create a new link with the given key and value and add it to the table
* bucket’s linked list. You can use hashLinkNew to create the link.
*
* Use HASH_FUNCTION(key) and the map’s capacity to find the index of the
* correct linked list bucket. Also make sure to search the entire list.
*
* @param map
* @param key
* @param value
*/
void hashMapPut(HashMap* map, const char* key, int value)
{
// FIXME: implement
int hashIndex = HASH_FUNCTION(key) % map->capacity;
if (hashIndex < 0)
hashIndex = hashIndex + map->capacity;
struct HashLink *link = map->table[hashIndex];
while (link != 0) {
if (strcmp(link->key, key) == 0) {
link->value = value; //set new value
return;
}
link = link->next; //move to next
}
//No value found to match, add to front
link = hashLinkNew(key, value, map->table[hashIndex]);
map->table[hashIndex] = link;
map->size++;
if (hashMapTableLoad(map) > MAX_TABLE_LOAD) {
resizeTable(map, 2 * hashMapCapacity(map)); //resize if load factor’s higher than max
}
}
/**
* Removes and frees the link with the given key from the table. If no such link
* exists, this does nothing. Remember to search the entire linked list at the
* bucket. You can use hashLinkDelete to free the link.
* @param map
* @param key
*/
void hashMapRemove(HashMap* map, const char* key)
{
// FIXME: implement
assert(map != 0);
int hashIndex = HASH_FUNCTION(key) % map->capacity;
if (hashIndex < 0)
hashIndex = hashIndex + map->table[hashIndex]->next;
struct HashLink *link = map->table[hashIndex];
struct HashLink *next = map->table[hashIndex]->next;
if (link == 0) {
return;
}
if (strcmp(link->key, key) == 0) {
hashLinkDelete(link);
map->table[hashIndex] = next;
map->size–;
return;
}
while (next != 0) {
if (strcmp(next->key, key) == 0) {
link->next = next->next;
hashLinkDelete(next);
map->size–;
return;
}
else {
link = link->next;
next = next->next;
}
}
}
/**
* Returns 1 if a link with the given key is in the table and 0 otherwise.
*
* Use HASH_FUNCTION(key) and the map’s capacity to find the index of the
* correct linked list bucket. Also make sure to search the entire list.
*
* @param map
* @param key
* @return 1 if the key is found, 0 otherwise.
*/
int hashMapContainsKey(HashMap* map, const char* key)
{
// FIXME: implement
int hashIndex = HASH_FUNCTION(key) % map->capacity;
if (hashIndex < 0)
hashIndex = hashIndex + map->capacity;
struct HashLink *link = map->table[hashIndex];
while (link != 0) {
if (strcmp(link->key, key) == 0) {
return 1;
}
else
link = link->next;
}
return 0;
}
/**
* Returns the number of links in the table.
* @param map
* @return Number of links in the table.
*/
int hashMapSize(HashMap* map)
{
// FIXME: implement
return map->size; //return num of links
}
/**
* Returns the number of buckets in the table.
* @param map
* @return Number of buckets in the table.
*/
int hashMapCapacity(HashMap* map)
{
// FIXME: implement
return map->capacity; //return num of buckets
}
/**
* Returns the number of table buckets without any links.
* @param map
* @return Number of empty buckets.
*/
int hashMapEmptyBuckets(HashMap* map)
{
// FIXME: implement
int count = 0;
for (int i = 0; i < map->capacity; i++) {
if (map->table[i] == 0) { //if bucket is empty, increment count
count++;
}
}
return count;
}
/**
* Returns the ratio of (number of links) / (number of buckets) in the table.
* Remember that the buckets are linked lists, so this ratio tells you nothing
* about the number of empty buckets. Remember also that the load is a floating
* point number, so don’t do integer division.
* @param map
* @return Table load.
*/
float hashMapTableLoad(HashMap* map)
{
// FIXME: implement
return (double)map->size / (map->capacity); //calculate table load = num of links / num of buckets
}
/**
* Prints all the links in each of the buckets in the table.
* @param map
*/
void hashMapPrint(HashMap* map)
{
for (int i = 0; i < map->capacity; i++)
{
HashLink* link = map->table[i];
if (link != NULL)
{
printf(“nBucket %i ->”, i);
while (link != NULL)
{
printf(” (%s, %d) ->”, link->key, link->value);
link = link->next;
}
}
}
printf(“n”);
}
Expert Answer
Code:
hashMap.h
//Include libraries
#ifndef HASH_MAP_H
#define HASH_MAP_H
#define HASH_FUNCTION hashFunction1
#define MAX_TABLE_LOAD .75
//Define structure
typedef struct HashMap HashMap;
//Define structure
typedef struct HashLink HashLink;
//Define structure
struct HashLink
{
//Declare variable
char* key;
//Declare variable
int value;
//Declare variable
HashLink* next;
};
//Define structure
struct HashMap
{
//Declare variable
HashLink** table;
//Declare variable
int size;
//Declare variable
int capacity;
};
//Define a method
HashMap* hashMapNew(int capacity);
//Define a method
void hashMapDelete(HashMap* map);
//Define a method
int* hashMapGet(HashMap* map, const char* key);
//Define a method
void hashMapPut(HashMap* map, const char* key, int value);
//Define a method
void hashMapRemove(HashMap* map, const char* key);
//Define a method
int hashMapContainsKey(HashMap* map, const char* key);
//Define a method
int hashMapSize(HashMap* map);
//Define a method
int hashMapCapacity(HashMap* map);
//Define a method
int hashMapEmptyBuckets(HashMap* map);
//Define a method
float hashMapTableLoad(HashMap* map);
//Define a method
void hashMapPrint(HashMap* map);
//End
#endif
hashMap.c
//Include libraries
#include “hashMap.h”
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
//Define a method
int hashFunction1(const char* key)
{
int r = 0;
for (int i = 0; key[i] != ‘ ’; i++)
{
r += key[i];
}
return r;
}
//Define a method
int hashFunction2(const char* key)
{
int r = 0;
for (int i = 0; key[i] != ‘ ’; i++)
{
r += (i + 1) * key[i];
}
return r;
}
//Define a method
HashLink* hashLinkNew(const char* key, int value, HashLink* next)
{
HashLink* link = (HashLink*)malloc(sizeof(HashLink));
link->key = (char*)malloc(sizeof(char) * (strlen(key) + 1));
strcpy(link->key, key);
link->value = value;
link->next = next;
return link;
}
//Define a method
static void hashLinkDelete(HashLink* link)
{
free(link->key);
free(link);
}
//Define a method
void hashMapInit(HashMap* map, int capacity)
{
map->capacity = capacity;
map->size = 0;
map->table = (HashLink**)malloc(sizeof(HashLink*) * capacity);
for (int i = 0; i < capacity; i++)
{
map->table[i] = NULL;
}
}
//Define a method
void hashMapCleanUp(HashMap* map)
{
for (int i = 0; i < map->capacity; i++)
{
HashLink* link = map->table[i];
map->table[i] = NULL;
while (link != NULL)
{
HashLink* temp = link;
link = link->next;
hashLinkDelete(temp);
}
free(map->table[i]);
}
free(map->table);
}
//Define a method
HashMap* hashMapNew(int capacity)
{
HashMap* map = (HashMap*)malloc(sizeof(HashMap));
hashMapInit(map, capacity);
return map;
}
//Define a method
void hashMapDelete(HashMap* map)
{
hashMapCleanUp(map);
free(map);
}
//Define a method
int* hashMapGet(HashMap* map, const char* key)
{
int idx = HASH_FUNCTION(key) % (map->capacity);
HashLink* link = map->table[idx];
while (link != NULL)
{
if (strcmp(link->key, key) == 0)
{
return &(link->value);
}
link = link->next;
}
return NULL;
}
//Define a method
void resizeTable(HashMap* map, int capacity)
{
int oldCap = map->capacity;
HashLink ** oldTable = map->table;
hashMapInit(map, capacity);
for (int i = 0; i < oldCap; i++)
{
HashLink * link = oldTable[i];
while (link != NULL)
{
hashMapPut(map, link->key, link->value);
link = link->next;
}
}
for (int i = 0; i < oldCap; i++)
{
HashLink* link = oldTable[i];
oldTable[i] = NULL;
while (link != NULL)
{
HashLink* temp = link;
link = link->next;
hashLinkDelete(temp);
}
free(oldTable[i]);
}
free(oldTable);
}
//Define a method
void hashMapPut(HashMap* map, const char* key, int value)
{
if (hashMapTableLoad(map) >= MAX_TABLE_LOAD)
{
resizeTable(map, 2 * map->capacity);
}
// Compute index
int idx = HASH_FUNCTION(key) % (map->capacity);
if (idx < 0)
{
idx += map->capacity;
}
// Add to bucket
HashLink* link = map->table[idx];
HashLink* newLink = NULL;
if (link == NULL)
{
// Bucket is currently empty
newLink= hashLinkNew(key, value, NULL);
map->table[idx] = newLink;
map->size++;
return;
}
else
{
// Bucket contains at least one link
while (link != NULL)
{
if (strcmp(link->key, key) == 0)
{
// Link with given key already exists
link->value = value;
return;
}
link = link->next;
}
// Link with given key does not already exist, create new Link
newLink = hashLinkNew(key, value, map->table[idx]);
map->table[idx] = newLink;
map->size++;
return;
}
}
//Define a method
void hashMapRemove(HashMap* map, const char* key)
{
if (!hashMapContainsKey(map, key))
{
//printf(“Not in mapn”);
return;
}
int idx = HASH_FUNCTION(key) % (map->capacity);
HashLink* cur = map->table[idx];
HashLink* last = map->table[idx];
if (cur == NULL)
{
printf(“No links in bucket to removen”);
}
while (cur != NULL)
{
if (strcmp(cur->key, key) == 0)
{
printf(“Found key/link to removen”);
if (cur == map->table[idx])
{
printf(“Link to remove is first linkn”);
map->table[idx] = cur->next;
hashLinkDelete(cur);
map->size–;
cur = 0;
}
else
{
last->next = cur->next;
hashLinkDelete(cur);
map->size–;
cur = 0;
}
}
else
{
last = cur;
cur = cur->next;
}
}
}
//Define a method
int hashMapContainsKey(HashMap* map, const char* key)
{
int idx = HASH_FUNCTION(key) % (map->capacity);
HashLink* link = map->table[idx];
while (link != NULL)
{
if (strcmp(link->key, key) == 0)
{
return 1;
}
link = link->next;
}
return 0;
}
//Define a method
int hashMapSize(HashMap* map)
{
return map->size;
}
//Define a method
int hashMapCapacity(HashMap* map)
{
return map->capacity;
}
//Define a method
int hashMapEmptyBuckets(HashMap* map)
{
int emptyBuckets = 0;
for (int i = 0; i < map->capacity; i++)
{
HashLink* link = map->table[i];
if (link == NULL)
{
emptyBuckets++;
}
}
return emptyBuckets;
}
//Define a method
float hashMapTableLoad(HashMap* map)
{
float links = (float)map->size;
float buckets = (float)map->capacity;
return (links/buckets);
}
//Define a method
void hashMapPrint(HashMap* map)
{
for (int i = 0; i < map->capacity; i++)
{
HashLink* link = map->table[i];
if (link != NULL)
{
printf(“nBucket %i ->”, i);
while (link != NULL)
{
printf(” (%s, %d) ->”, link->key, link->value);
link = link->next;
}
}
}
printf(“n”);
}
Main.c
//Inlcude libraries
#include “hashMap.h”
#include <assert.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Define a method
char* nextWord(FILE* file)
{
//Declare variable
int maxLength = 16;
//Declare variable
int length = 0;
//Allocate memory
char* word = (char*)malloc(sizeof(char) * maxLength);
//Loop
while (1)
{
//Get
char c = fgetc(file);
//Check condition
if ((c >= ‘0’ && c <= ‘9’) ||
(c >= ‘A’ && c <= ‘Z’) ||
(c >= ‘a’ && c <= ‘z’) ||
c == ”’)
{
//Check condition
if (length + 1 >= maxLength)
{
//Assign length
maxLength *= 2;
//Assign value
word = (char*)realloc(word, maxLength);
}
//Assign value
word[length] = c;
//Increment
length++;
}
//If condition matches
else if (length > 0 || c == EOF)
{
//Break
break;
}
}
//If length is 0
if (length == 0)
{
//Free
free(word);
//Return
return NULL;
}
//Assign value
word[length] = ‘ ’;
//Return
return word;
}
//Define a method
unsigned long hashstring(unsigned char *str)
{
//Declare variable
unsigned long hash = 5381;
//Declare variable
int c;
//Loop
while (c = *str++)
{
//Compute hash
hash = ((hash << 5) + hash) + c;
}
//Return
return hash;
}
//Define a method
void loadDictionary(FILE* file, HashMap* map)
{
//Call method
char * word = nextWord(file);
//Loop
while (word != NULL)
{
// Compute hash value
unsigned long hash = hashstring((unsigned char*)word);
//If condition matches
if (hashMapContainsKey(map, word))
{
}
else
{
// Add word
hashMapPut(map, word, hash);
}
//Free
free(word);
//Call method
word = nextWord(file);
}
}
//Define main
int main(int argc, const char** argv)
{
// Declare value
HashMap* map = hashMapNew(1000);
//Define file
FILE* file = fopen(“dictionary.txt”, “r”);
// If file not present
if (file == NULL)
{
//Display error
perror(“Error”);
}
//Define timer
clock_t timer = clock();
//Load file
loadDictionary(file, map);
//Check time
timer = clock() – timer;
//Display
printf(“Dictionary loaded in %f secondsn”, (float)timer / (float)CLOCKS_PER_SEC);
//Close file
fclose(file);
//Declare array
char inputBuffer[256];
//Declare variable
int quit = 0;
//Loop
while (!quit)
{
//Display
printf(“Enter a word or “quit” to quit: “);
//Store value
scanf(“%s”, inputBuffer);
//If condition matches
if (hashMapContainsKey(map, inputBuffer))
{
//Display message
printf(“That word is spelled correctly!n”);
}
//Otherwise
else
{
//Display message
printf(“That word is mispelled!n”);
}
//If value is 0
if (strcmp(inputBuffer, “quit”) == 0)
{
//Set value
quit = 1;
}
}
//Call method
hashMapDelete(map);
//Get
getchar();
//Return
return 0;
}
