C programming, HASH TABLES in file ListDeque.c functions you will need (but shou
ID: 666255 • Letter: C
Question
C programming, HASH TABLES
in file ListDeque.c functions you will need (but should not need to change)
initListDeque
freeListDeque
removeLinkListDeque
Functions you will NEED TO CHANGE:
containsListDeque - Rather than simply returning an integer, return a DLink* which points to either NULL, or the link where the value can be found. The function signature should be: DLink* containsListDeque(ListDeque* q, TYPE val);
printListDeque - Currently, this function is set up to print characters, Set it up so that it will print a character string, followed by a number (these are the two fields in a MapElement, refer to type.h).
Next, you will need to write the following functions to complete the assignment (in the order that they are found in the file, feel free to write them in whatever order you choose)
initHashMap
freeHashMap*
insertHashMap*
atHashMap
removeHashMap*
longestChain
emptyBuckets
numCollisions
The functions marked with a star will contain a line of code that frees the key associated with map elements. This is necessary because as we compute the "concordance" of the input text file, getWord will malloc space for each character string, which we must free.
files you need:
//ListDeque.h
#ifndef LIST_DEQUE_H_INCLUDED
#define LIST_DEQUE_H_INCLUDED
#include "type.h"
/* Link structure composing one element of the linked list. */
/* Note that it is doubly-linked (hence the D) */
struct DLink {
TYPE value; /* value of the link */
struct DLink* next; /* pointer to the next link */
struct DLink* prev; /* pointer to the previous link */
};
typedef struct DLink DLink;
/* Linked List datastructure, composed of DLink
* Note that we have a pointer to both head and tail,
* this means that add/remove to the front/back in O(1) time
*/
struct ListDeque {
int size; /* number of links in the deque */
DLink* head; /* pointer to the front */
DLink* tail; /* pointer to the back */
};
typedef struct ListDeque ListDeque;
/* Basic Operations */
void initListDeque(ListDeque* q);
void freeListDeque(ListDeque* q);
int isEmptyListDeque(ListDeque *q);
TYPE frontListDeque(ListDeque* q);
TYPE backListDeque(ListDeque* q);
void addLinkAfterListDeque(ListDeque* q, DLink* addAfter, DLink* newLink);
void addLinkBeforeListDeque(ListDeque* q, DLink* addBefore, DLink* newLink);
DLink* removeLinkListDeque(ListDeque* q, DLink* toRemove);
/* Deque interface */
void addBackListDeque(ListDeque* q, TYPE val);
void addFrontListDeque(ListDeque* q, TYPE val);
void removeFrontListDeque(ListDeque* q);
void removeBackListDeque(ListDeque* q);
/* Bag Interface */
int containsListDeque(ListDeque* q, TYPE val);
void removeListDeque(ListDeque* q, TYPE val);
/* Other functions */
void reverseListDeque(ListDeque* q);
void printListDeque(ListDeque* q);
#endif
//ListDeque.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "ListDeque.h"
/* Create a link for a value.
Use this function in your add operations to make it easier to allocate links
param: val the value to store in the newy created link
pre: none
post: a link is allocated on the heap, storing the argument value
ret: the newly allocated link
*/
DLink* _createLink(TYPE val)
{
DLink* lnk = (DLink*) malloc(sizeof(DLink));
assert(lnk != 0);
lnk->value = val;
return lnk;
}
/* ************************************************************************
Basic Operations
************************************************************************ */
/* Initializes a deque.
param: d pointer to the deque
pre: d is not null
post: size, head, and tail are initialized
*/
void initListDeque(ListDeque* d)
{
/*FIXME you will write this function */
d->head = malloc(sizeof(struct DLink));
d->tail = malloc(sizeof(struct DLink));
d->size = 0;
d->head = 0;
d->tail = 0;
}
/* De-allocate all links of the deque.
Write this function in terms of a remove function, such as removeBack.
param: d pointer to the deque
pre: d is not null
post: All links are de-allocated
*/
void freeListDeque(ListDeque* d)
{
/*FIXME you will write this function */
DLink *position = d->head;
while(position != 0)
position = removeLinkListDeque(d,position);
d->size = 0;
}
/* Check whether the deque is empty.
param: d pointer to the deque
pre: d is not null
ret: 1 if the deque is empty. Otherwise, 0.
*/
int isEmptyListDeque(ListDeque *d) {
/*FIXME you will write this function */
if(d->size == 0)
return 1;
else
return 0;
}
/* Get the value stored in the link at the front of the deque
param: d pointer to the deque
pre: d is not null
pre: d is not empty
post: none
ret: value of the front of the deque
*/
TYPE frontListDeque (ListDeque *d)
{
assert(!isEmptyListDeque(d));
return d->head->value;
}
/* Get the value stored in the link at the back of the deque
param: d pointer to the deque
pre: d is not null
pre: d is not empty
post: none
ret: value of the back of the deque
*/
TYPE backListDeque(ListDeque *d)
{
/*FIXME you will write this function */
TYPE var;
var = d->tail->value;
return var;
}
/* Adds a link AFTER another link.
Write your other add functions in terms of addAfter and addBefore when possible.
param: d pointer to the deque
param: addAfter pointer to the existing link in the deque
param: newLnk pointer to the new link to add after the existing link
pre: d is not null
pre: newLnk has been properly initialized
pre: addAfter is in the deque if it is not a NULL pointer
post: newLnk is added into the deque AFTER the existing link
*/
void addLinkAfterListDeque(ListDeque* d, DLink* addAfter, DLink* newLnk)
{
/*FIXME you will write this function */
ListDeque *t=d;
while(t->head!=addAfter)
t->head=t->head->next;
if(t->head==addAfter)
t->head->next=newLnk;
newLnk->prev=t->head;
}
/* Adds a link BEFORE another link.
Write your other add functions in terms of addAfter and addBefore when possible.
param: d pointer to the deque
param: addBefore pointer to the existing link in the deque
param: newLnk pointer to the new link to add before the existing link
pre: d is not null
pre: newLnk has been properly initialized
pre: addBefore is in the deque if it is not a NULL pointer
post: newLnk is added into the deque BEFORE the existing link
*/
void addLinkBeforeListDeque(ListDeque* d, DLink* addBefore, DLink* newLnk)
{
/*FIXME you will write this function */
addBefore->prev->next = newLnk;
newLnk->prev = addBefore->prev;
newLnk->next = addBefore;
addBefore->prev = newLnk;
d->size++;
}
/* Remove a link from the deque.
Write our other remove functions in terms of this function when possible.
Be careful not to use a pointer that you have already freed when returning.
param: d pointer to the deque
param: lnk pointer to the link to be removed
pre: d is not null
pre: d is not empty
pre: lnk is in the deque
post: lnk is removed from the deque
ret: The pointer which follows lnk
*/
DLink* removeLinkListDeque(ListDeque *d, DLink *lnk)
{
/*FIXME you will write this function */
if(lnk==d->head){
removeFrontListDeque(d);
return d->head;
}
else if(lnk==d->tail){
removeBackListDeque(d);
return d->tail;
}
else{
DLink *temp = lnk->next;
temp->prev = lnk->prev;
lnk->prev->next = temp;
d->size--;
return temp;
}
return 0;
}
/* ************************************************************************
Deque Interface
************************************************************************ */
/* Adds a link to the back of the deque.
Write this function in terms of addLinkAfter() when possible.
param: d pointer to the deque
param: val value for the link to be added
pre: d is not null
post: a link storing val is added to the back of the deque
*/
void addBackListDeque (ListDeque *d, TYPE val)
{
/*FIXME you will write this function */
/*struct DLink *hehehe= malloc(sizeof(DLink));
hehehe->value = val;
addLinkBeforeListDeque(d,d->tail,hehehe);*/
DLink *newLnk=_createLink(val);
if(isEmptyListDeque(d)==1){
d->head = newLnk;
d->tail = newLnk;
newLnk->next = 0;
newLnk->prev = 0;
}
else {
d->tail->next = newLnk;
newLnk->prev = d->tail;
d->tail = newLnk;
newLnk->next = 0;
}
d->size++;
}
/* Adds a link to the front of the deque.
Write this function in terms of addLinkBefore when possible.
param: d pointer to the deque
param: val value for the link to be added
pre: d is not null
post: a link storing val is added to the front of the deque
*/
void addFrontListDeque(ListDeque *d, TYPE val)
{
/*FIXME you will write this function */
DLink *newLnk=_createLink(val);
if(isEmptyListDeque(d)==1){
d->head = newLnk;
d->tail = newLnk;
newLnk->next = 0;
newLnk->prev = 0;
}
else {
d->head->prev = newLnk;
newLnk->next = d->head;
d->head = newLnk;
newLnk->prev = 0;
}
d->size++;
}
/* Remove the front of the deque.
Write this function in terms of removeLinkListDeque().
param: d pointer to the deque
pre: d is not null
pre: d is not empty
post: the front is removed from the deque
*/
void removeFrontListDeque (ListDeque *d)
{
/*FIXME you will write this function */
if(d->size==1){
d->head = 0;
d->tail = 0;
}
else {
d->head = d->head->next;
d->head->prev = 0;
}
d->size--;
}
/* Remove the back of the deque.
Write this function in terms of removeLinkListDeque().
param: d pointer to the deque
pre: d is not null and q is not empty
post: the back is removed from the deque
*/
void removeBackListDeque(ListDeque *d)
{
/*FIXME you will write this function */
if(d->size==1){
d->head = 0;
d->tail = 0;
}
else {
d->tail = d->tail->prev;
d->tail->next = 0;
}
d->size--;
}
/* ************************************************************************
Bag Interface
************************************************************************ */
/* Returns whether or not the given value is stored in the deque
param: d pointer to the deque
param: val value that we are looking for in the deque
ret: 1 if val is contained in d, 0 otherwise
*/
int containsListDeque(ListDeque* d, TYPE val)
{
/*FIXME you will write this function */
DLink *position = d->head;
while(position != NULL)
{
if(position->value==val)
return 1;
else
position = position->next;
}
return 0;
return 0;
}
/* Removes the first occurrence of the given value from the list.
param: d pointer to the deque
param: val value that we are looking for in the deque
post: first occurrence of val is removed from the list
*/
void removeListDeque(ListDeque* q, TYPE val)
{
/*FIXME you will write this function */
/*ListDeque *t=q;
while(t->head->value!=val)
t->head=t->head->next;
if(t->head->value==val)
{
t->head->next->prev=t->head->next;
t->head->prev=t->head->next;
free(t);
}*/
DLink *position = q->head;
while(position != NULL)
{
if(position->value==val)
position = removeLinkListDeque(q,position);
else
position = position->next;
}
}
/* Reverse the deque. Note that careful swapping of the pointers inside each link
(next and prev) will cause a reverse, provided head and tail are updated properly.
param: d pointer to the deque
pre: d is not null
post: the deque is reversed
*/
void reverseListDeque(ListDeque *q)
{
/*FIXME you will write this function */
DLink *position = q->head;
DLink *temp1, *temp2;
temp1 = q->head;
temp2 = q->tail;
q->head = temp2;
q->tail = temp1;
while(position != NULL)
{
temp1 = position->next;
temp2 = position->prev;
position->next = temp2;
position->prev = temp1;
position = temp1;
}
}
/* Print the links in the deque from front to back
param: d pointer to the deque
pre: d is not null
post: the links in the deque are printed from front to back
*/
void printListDeque(ListDeque *q)
{
DLink* lnk;
lnk = q->head;
printf("Size = %d [ ", q->size);
while(lnk != NULL)
{
printf("%c ", lnk->value);
lnk = lnk->next;
}
printf("] ");
}
//HashMap.h
//HashMap.c
//type.h
//main.c
//main2.c
//input1.txt
//input2.txt
//input3.txt
Explanation / Answer
initHashMap
freeHashMap*
insertHashMap*
atHashMap
removeHashMap*
longestChain
emptyBuckets
numCollisions
The functions marked with a star will contain a line of code that frees the key associated with map elements. This is necessary because as we compute the "concordance" of the input text file, getWord will malloc space for each character string, which we must free.
files you need:
//ListDeque.h
#ifndef LIST_DEQUE_H_INCLUDED
#define LIST_DEQUE_H_INCLUDED
#include "type.h"
/* Link structure composing one element of the linked list. */
/* Note that it is doubly-linked (hence the D) */
struct DLink {
TYPE value; /* value of the link */
struct DLink* next; /* pointer to the next link */
struct DLink* prev; /* pointer to the previous link */
};
typedef struct DLink DLink;
/* Linked List datastructure, composed of DLink
* Note that we have a pointer to both head and tail,
* this means that add/remove to the front/back in O(1) time
*/
struct ListDeque {
int size; /* number of links in the deque */
DLink* head; /* pointer to the front */
DLink* tail; /* pointer to the back */
};
typedef struct ListDeque ListDeque;
/* Basic Operations */
void initListDeque(ListDeque* q);
void freeListDeque(ListDeque* q);
int isEmptyListDeque(ListDeque *q);
TYPE frontListDeque(ListDeque* q);
TYPE backListDeque(ListDeque* q);
void addLinkAfterListDeque(ListDeque* q, DLink* addAfter, DLink* newLink);
void addLinkBeforeListDeque(ListDeque* q, DLink* addBefore, DLink* newLink);
DLink* removeLinkListDeque(ListDeque* q, DLink* toRemove);
/* Deque interface */
void addBackListDeque(ListDeque* q, TYPE val);
void addFrontListDeque(ListDeque* q, TYPE val);
void removeFrontListDeque(ListDeque* q);
void removeBackListDeque(ListDeque* q);
/* Bag Interface */
int containsListDeque(ListDeque* q, TYPE val);
void removeListDeque(ListDeque* q, TYPE val);
/* Other functions */
void reverseListDeque(ListDeque* q);
void printListDeque(ListDeque* q);
#endif
//ListDeque.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "ListDeque.h"
/* Create a link for a value.
Use this function in your add operations to make it easier to allocate links
param: val the value to store in the newy created link
pre: none
post: a link is allocated on the heap, storing the argument value
ret: the newly allocated link
*/
DLink* _createLink(TYPE val)
{
DLink* lnk = (DLink*) malloc(sizeof(DLink));
assert(lnk != 0);
lnk->value = val;
return lnk;
}
/* ************************************************************************
Basic Operations
************************************************************************ */
/* Initializes a deque.
param: d pointer to the deque
pre: d is not null
post: size, head, and tail are initialized
*/
void initListDeque(ListDeque* d)
{
/*FIXME you will write this function */
d->head = malloc(sizeof(struct DLink));
d->tail = malloc(sizeof(struct DLink));
d->size = 0;
d->head = 0;
d->tail = 0;
}
/* De-allocate all links of the deque.
Write this function in terms of a remove function, such as removeBack.
param: d pointer to the deque
pre: d is not null
post: All links are de-allocated
*/
void freeListDeque(ListDeque* d)
{
/*FIXME you will write this function */
DLink *position = d->head;
while(position != 0)
position = removeLinkListDeque(d,position);
d->size = 0;
}
/* Check whether the deque is empty.
param: d pointer to the deque
pre: d is not null
ret: 1 if the deque is empty. Otherwise, 0.
*/
int isEmptyListDeque(ListDeque *d) {
/*FIXME you will write this function */
if(d->size == 0)
return 1;
else
return 0;
}
/* Get the value stored in the link at the front of the deque
param: d pointer to the deque
pre: d is not null
pre: d is not empty
post: none
ret: value of the front of the deque
*/
TYPE frontListDeque (ListDeque *d)
{
assert(!isEmptyListDeque(d));
return d->head->value;
}
/* Get the value stored in the link at the back of the deque
param: d pointer to the deque
pre: d is not null
pre: d is not empty
post: none
ret: value of the back of the deque
*/
TYPE backListDeque(ListDeque *d)
{
/*FIXME you will write this function */
TYPE var;
var = d->tail->value;
return var;
}
/* Adds a link AFTER another link.
Write your other add functions in terms of addAfter and addBefore when possible.
param: d pointer to the deque
param: addAfter pointer to the existing link in the deque
param: newLnk pointer to the new link to add after the existing link
pre: d is not null
pre: newLnk has been properly initialized
pre: addAfter is in the deque if it is not a NULL pointer
post: newLnk is added into the deque AFTER the existing link
*/
void addLinkAfterListDeque(ListDeque* d, DLink* addAfter, DLink* newLnk)
{
/*FIXME you will write this function */
ListDeque *t=d;
while(t->head!=addAfter)
t->head=t->head->next;
if(t->head==addAfter)
t->head->next=newLnk;
newLnk->prev=t->head;
}
/* Adds a link BEFORE another link.
Write your other add functions in terms of addAfter and addBefore when possible.
param: d pointer to the deque
param: addBefore pointer to the existing link in the deque
param: newLnk pointer to the new link to add before the existing link
pre: d is not null
pre: newLnk has been properly initialized
pre: addBefore is in the deque if it is not a NULL pointer
post: newLnk is added into the deque BEFORE the existing link
*/
void addLinkBeforeListDeque(ListDeque* d, DLink* addBefore, DLink* newLnk)
{
/*FIXME you will write this function */
addBefore->prev->next = newLnk;
newLnk->prev = addBefore->prev;
newLnk->next = addBefore;
addBefore->prev = newLnk;
d->size++;
}
/* Remove a link from the deque.
Write our other remove functions in terms of this function when possible.
Be careful not to use a pointer that you have already freed when returning.
param: d pointer to the deque
param: lnk pointer to the link to be removed
pre: d is not null
pre: d is not empty
pre: lnk is in the deque
post: lnk is removed from the deque
ret: The pointer which follows lnk
*/
DLink* removeLinkListDeque(ListDeque *d, DLink *lnk)
{
/*FIXME you will write this function */
if(lnk==d->head){
removeFrontListDeque(d);
return d->head;
}
else if(lnk==d->tail){
removeBackListDeque(d);
return d->tail;
}
else{
DLink *temp = lnk->next;
temp->prev = lnk->prev;
lnk->prev->next = temp;
d->size--;
return temp;
}
return 0;
}
/* ************************************************************************
Deque Interface
************************************************************************ */
/* Adds a link to the back of the deque.
Write this function in terms of addLinkAfter() when possible.
param: d pointer to the deque
param: val value for the link to be added
pre: d is not null
post: a link storing val is added to the back of the deque
*/
void addBackListDeque (ListDeque *d, TYPE val)
{
/*FIXME you will write this function */
/*struct DLink *hehehe= malloc(sizeof(DLink));
hehehe->value = val;
addLinkBeforeListDeque(d,d->tail,hehehe);*/
DLink *newLnk=_createLink(val);
if(isEmptyListDeque(d)==1){
d->head = newLnk;
d->tail = newLnk;
newLnk->next = 0;
newLnk->prev = 0;
}
else {
d->tail->next = newLnk;
newLnk->prev = d->tail;
d->tail = newLnk;
newLnk->next = 0;
}
d->size++;
}
/* Adds a link to the front of the deque.
Write this function in terms of addLinkBefore when possible.
param: d pointer to the deque
param: val value for the link to be added
pre: d is not null
post: a link storing val is added to the front of the deque
*/
void addFrontListDeque(ListDeque *d, TYPE val)
{
/*FIXME you will write this function */
DLink *newLnk=_createLink(val);
if(isEmptyListDeque(d)==1){
d->head = newLnk;
d->tail = newLnk;
newLnk->next = 0;
newLnk->prev = 0;
}
else {
d->head->prev = newLnk;
newLnk->next = d->head;
d->head = newLnk;
newLnk->prev = 0;
}
d->size++;
}
/* Remove the front of the deque.
Write this function in terms of removeLinkListDeque().
param: d pointer to the deque
pre: d is not null
pre: d is not empty
post: the front is removed from the deque
*/
void removeFrontListDeque (ListDeque *d)
{
/*FIXME you will write this function */
if(d->size==1){
d->head = 0;
d->tail = 0;
}
else {
d->head = d->head->next;
d->head->prev = 0;
}
d->size--;
}
/* Remove the back of the deque.
Write this function in terms of removeLinkListDeque().
param: d pointer to the deque
pre: d is not null and q is not empty
post: the back is removed from the deque
*/
void removeBackListDeque(ListDeque *d)
{
/*FIXME you will write this function */
if(d->size==1){
d->head = 0;
d->tail = 0;
}
else {
d->tail = d->tail->prev;
d->tail->next = 0;
}
d->size--;
}
/* ************************************************************************
Bag Interface
************************************************************************ */
/* Returns whether or not the given value is stored in the deque
param: d pointer to the deque
param: val value that we are looking for in the deque
ret: 1 if val is contained in d, 0 otherwise
*/
int containsListDeque(ListDeque* d, TYPE val)
{
/*FIXME you will write this function */
DLink *position = d->head;
while(position != NULL)
{
if(position->value==val)
return 1;
else
position = position->next;
}
return 0;
return 0;
}
/* Removes the first occurrence of the given value from the list.
param: d pointer to the deque
param: val value that we are looking for in the deque
post: first occurrence of val is removed from the list
*/
void removeListDeque(ListDeque* q, TYPE val)
{
/*FIXME you will write this function */
/*ListDeque *t=q;
while(t->head->value!=val)
t->head=t->head->next;
if(t->head->value==val)
{
t->head->next->prev=t->head->next;
t->head->prev=t->head->next;
free(t);
}*/
DLink *position = q->head;
while(position != NULL)
{
if(position->value==val)
position = removeLinkListDeque(q,position);
else
position = position->next;
}
}
/* Reverse the deque. Note that careful swapping of the pointers inside each link
(next and prev) will cause a reverse, provided head and tail are updated properly.
param: d pointer to the deque
pre: d is not null
post: the deque is reversed
*/
void reverseListDeque(ListDeque *q)
{
/*FIXME you will write this function */
DLink *position = q->head;
DLink *temp1, *temp2;
temp1 = q->head;
temp2 = q->tail;
q->head = temp2;
q->tail = temp1;
while(position != NULL)
{
temp1 = position->next;
temp2 = position->prev;
position->next = temp2;
position->prev = temp1;
position = temp1;
}
}
/* Print the links in the deque from front to back
param: d pointer to the deque
pre: d is not null
post: the links in the deque are printed from front to back
*/
void printListDeque(ListDeque *q)
{
DLink* lnk;
lnk = q->head;
printf("Size = %d [ ", q->size);
while(lnk != NULL)
{
printf("%c ", lnk->value);
lnk = lnk->next;
}
printf("] ");
}
//HashMap.h
#ifndef HASHMAP_H_INCLUDED
#define HASHMAP_H_INCLUDED 1
#include "type.h"
#include "ListDeque.h"
struct HashMap {
/* array of linked lists used to represent a hash table with chaining. */
ListDeque* table;
/* The number of buckets in the hash table */
int tableSize;
/* The number of actual key, value pairs stored in the hash tables*/
int numItems;
/* An integer used in the _hash function to pick which hash funciton to use
This is not usually a parameter of a typical HashMap because they usually
only use 1 function, but we would like to test several functions in this assignment
*/
int hashChoice;
};
typedef struct HashMap HashMap;
void initHashMap(HashMap* hm, int tableSize, int hashChoice);
void freeHashMap(HashMap* hm);
void insertHashMap(HashMap* hm, TYPE toAdd);
MapElement* atHashMap(HashMap* hm, KeyType key);
void removeHashMap(HashMap* hm, KeyType key);
int longestChain(HashMap* hm);
int emptyBuckets(HashMap* hm);
int numCollisions(HashMap* hm);
void printHashMap(HashMap* hm, int showBuckets);
#endif
//HashMap.c
#include "HashMap.h"
#include <stdlib.h>
#include <stdio.h>
/* ************************************************************************
Various Hashing functions
************************************************************************ */
int _hashFunction1(char* str)
{
int i;
int result = 0;
for (i = 0; str[i] != ''; i++){
result += str[i];
}
return abs(result);
}
int _hashFunction2(char* str)
{
int i;
int result = 0;
for (i = 0; str[i] != ''; i++){
result += i * str[i];
}
return abs(result);
}
int _hashFunction3(char* str)
{
int i;
int result = 0;
int c = 33;
for (i = 0; str[i] != ''; i++){
result += c * str[i];
c *= c;
}
return abs(result);
}
int _hashFunction4(char* str)
{
int i;
int result = 5381;
for (i = 0; str[i] != ''; i++){
result = 33*result + str[i];
}
return abs(result);
}
int _hashFunction5(char* str)
{
int i;
int result = 0;
for (i = 0; str[i] != ''; i++){
result -= (result << 4)^(result >> 28)^str[i];
}
return abs(result);
}
/* Function which is responsible for choosing which hash function
gets executed, returns the result from that hash function.
param: str The string to be hashed
param: hashChoice The number of the hash function to be called
ret: result from hashing str given the appropriate hash function,
0 if hashChoice was not in the legal range [1-5] ([1-6] if
doing the extra credit)
*/
int _hash(char* str, int hashChoice)
{
switch(hashChoice)
{
case 1:
return _hashFunction1(str);
case 2:
return _hashFunction2(str);
case 3:
return _hashFunction3(str);
case 4:
return _hashFunction4(str);
case 5:
return _hashFunction5(str);
default:
printf("************************ INVALID HASH CHOSEN ************************ ");
return 0;
}
}
/* Responsible for setting up the hash map
param: hm The hash map to be initialized
param: tableSize Number of chains (linked lists) which should be stored
in the array representing the hash map.
param: hashChoice the number of the hash function that we would like
to use when performing operations on the hash map.
post: An array of linked lists has been dynamically allocated
post: Each linked list in the array has been initialized
post: tableSize, hashChoice, and numItems are initialized
*/
void initHashMap(HashMap* hm, int tableSize, int hashChoice)
{
/* FIXME you will write this part */
}
/* Responsible for freeing the memory associated with the hash map
param: hm The hash map to be released
post: the key stored within each link of the linked list is released
IMPORTANT!!!!!!!!!!!! This is due to the fact that getWord is mallocing
space for the strings representing keys for this assignment.
This code is not general, but should be placed here anyway.
post: each linked list in the array of linked lists is released
post: the array of linked lists itself is released
*/
void freeHashMap(HashMap* hm)
{
/* FIXME you will write this part */
}
/* This function will insert items into the hash map.
If duplicate keys are added, the old map element(key, value pair)
should be overwritten.
IMPORTANT!!!!!!!!! in the case of a duplicate add, be sure to free the key
associated with the element because it was dynamically allocated by getWord.
This code is not general, but should be placed here anyway.
param: hm hash map to perform the insert in
param: toAdd Element to add to the map. Note that this type
should conform to the type stored in the linked list
post: the element has been added to the collection and properly book-kept??
*/
void insertHashMap(HashMap* hm, TYPE toAdd)
{
/* FIXME you will write this part */
}
/* This function is responsible for returning the element(key, value pair)
associated with a particular key, if it exists
param: hm hasm map to perform the lookup in
param: key the key to look up in the hash map
ret: pointer to the map element where the argument key is found if it exists
NULL otherwise
post: none
*/
MapElement* atHashMap(HashMap* hm, KeyType key)
{
/* FIXME you will write this part */
return NULL;
}
/* This function is responsible for removing the argument key form the argument hash table
(if it exists)
param: hm The hash map to have a key (potentially) removed from
param: key the key of the element which we would like to remove
post: if the key was not found, one
otherwise, the map element (key, value pair) has been removed
from the hashMap, and the map is properly book-kept??
IMPORTANT!!!!!!!!!!!! Due to the fact that getWord is mallocing
space for the strings representing keys for this assignment, this function needs
to free the key stored in the map element.
This code is not general, but should be placed here anyway.
*/
void removeHashMap(HashMap* hm, KeyType key)
{
/* FIXME you will write this part */
}
/* Indicates the length of the longest chain in the argument hashmap
param: hm hash table to find the longest chain in
ret: the length of the longest chain in the hash table
*/
int longestChain(HashMap* hm)
{
/* FIXME you will write this part */
return 0;
}
/* Indicates the number of empty buckets contained in the argument hashmap
param: hm hash table to count the number of empty buckets in
ret: the number of buckets contained in the hash table which are empty.
*/
int emptyBuckets(HashMap* hm)
{
/* FIXME you will write this part */
return 0;
}
/* Indicates the number of collisions that have occured upon insertion into this
hash table
Note: You do not need to perform bookkeeping on this as inserts come, you can
calculate this based on the length of the chains.
Ex. A chain of length 2 has had 1 collision
param: hm hash table to count the number of collisions upon insert
ret: the number of collisions that have occured as a result of insertion
*/
int numCollisions(HashMap* hm)
{
/* FIXME you will write this part */
return 0;
}
/* Print useful information about the hash map
param: hm map for which we would like to print contents/statistics
param: showBuckets Indicates whether or not we should print the contents
post: statistics have been printed, perhaps contents of the hash map
*/
void printHashMap(HashMap* hm, int showBuckets)
{
int i;
if(showBuckets)
for(i = 0; i < hm->tableSize; ++i)
printListDeque(&hm->table[i]);
printf(" Hash Table Size: %d ", hm->tableSize);
printf("Number of items: %d ", hm->numItems);
printf("Hash Function Choice: %d ", hm->hashChoice);
printf("Load Factor: %f ", (float)hm->numItems/(float)hm->tableSize);
printf("Longest Chain: %d ", longestChain(hm));
printf("%% of Buckets Empty: %f ", (float)emptyBuckets(hm)/(float)hm->tableSize);
printf("%% of inserts resulting in a collision: %f ", (float)numCollisions(hm)/(float)hm->numItems);
}
//type.h
/* type.h
Defines the type to be stored in the data structure. These macros
are for convenience to avoid having to search and replace/dup code
when you want to build a structure of doubles as opposed to ints
for example.
*/
#ifndef __TYPE_H
#define __TYPE_H
#include <string.h>
#define KeyType char*
#define ValType int
struct MapElement {
KeyType key;
ValType value;
};
typedef struct MapElement MapElement;
# ifndef TYPE
# define TYPE MapElement
# define TYPE_SIZE sizeof(MapElement)
# endif
# ifndef EQ
# define EQ(A, B) (strcmp(A.key, B.key) == 0)
# endif
#endif
//main.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include "type.h"
#include "HashMap.h"
char* getWord(FILE *file);
int main (int argc, const char * argv[])
{
HashMap hm;
MapElement toAdd;
MapElement* retrieved;
clock_t start, finish;
FILE *theFile;
int hashChoice = 1;
/**************************************
When testing your code, change these values
***************************************/
const char* filename = "input1.txt";
int tableSize = 4;
int showBuckets = 1;
initHashMap(&hm, tableSize, hashChoice);
/* Open the file */
theFile = fopen(filename, "r");
if(!theFile) {
fprintf(stderr, "Cannot open %s ", filename);
return 1;
}
start = clock();
/* This is an infinite loop, but it is ok because eventually the file will run out */
while(1){
toAdd.key = getWord(theFile);
if(!toAdd.key)
break;
/* Assume we have not seen the word before */
toAdd.value = 1;
/* if the word has been seen before, increment its count */
retrieved = atHashMap(&hm, toAdd.key);
if(retrieved)
toAdd.value = retrieved->value + 1;
insertHashMap(&hm, toAdd);
}
finish = clock();
printHashMap(&hm, showBuckets);
printf("concordance ran in %f seconds ", (float)(finish-start) / (float)CLOCKS_PER_SEC);
fclose(theFile);
freeHashMap(&hm);
return 0;
}
/* This is a function which will return the next character string in a file
Note that it calls malloc/realloc, so the pointer returned MUST BE FREED!!!!
Also, this function is not totally robust against certain kinds of punctuation, so keep it simple.
*/
char* getWord(FILE *file)
{
int length = 0;
int maxLength = 16;
char character;
/*char * c =0;*/
char* word = (char*)malloc(sizeof(char) * maxLength);
assert(word != NULL);
while( (character = fgetc(file)) != EOF)
{
if((length+1) > maxLength)
{
maxLength *= 2;
word = (char*)realloc(word, maxLength);
}
if((character >= '0' && character <= '9') || /*is a number*/
(character >= 'A' && character <= 'Z') || /*or an uppercase letter*/
(character >= 'a' && character <= 'z') || /*or a lowercase letter*/
character == 39) /*or is an apostrophe*/
{
word[length] = character;
length++;
}
else if(length > 0)
break;
}
if(length == 0)
{
free(word);
return NULL;
}
word[length] = '';
return word;
}
//main2.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include "type.h"
#include "HashMap.h"
char* getWord(FILE *file);
int main (int argc, const char * argv[])
{
HashMap hm;
MapElement toAdd;
MapElement* retrieved;
FILE *theFile;
int tableSize;
const char* filename = "input3.txt";
/**************************************
For the written questions, change this value 1-5 (1-6 if doing the Extra Credit)
***************************************/
int hashChoice = 5;
printf(" ********Results for Hash Function %d ", hashChoice);
printf("LoadFactor EmptyBuckets%% Collision%% LongestChain ");
/* Create a number of hash maps of various sizes */
for(tableSize = 250; tableSize < 1050; tableSize += 50)
{
initHashMap(&hm, tableSize, hashChoice);
/* Open the file */
theFile = fopen(filename, "r");
if(!theFile) {
fprintf(stderr, "Cannot open %s ", filename);
return 1;
}
/* This is an infinite loop, but it is ok because eventually the file will run out */
while(1){
toAdd.key = getWord(theFile);
if(!toAdd.key)
break;
/* Assume we have not seen the word before */
toAdd.value = 1;
/* if the word has been seen before, increment its count */
retrieved = atHashMap(&hm, toAdd.key);
if(retrieved)
toAdd.value = retrieved->value + 1;
insertHashMap(&hm, toAdd);
}
/* Print out some stats about the hash table */
printf("%f %f %f %d ", (float)hm.numItems/(float)hm.tableSize,
(float)emptyBuckets(&hm)/(float)hm.tableSize,
(float)numCollisions(&hm)/(float)hm.numItems,
longestChain(&hm));
fclose(theFile);
freeHashMap(&hm);
}
return 0;
}
/* This is a function which will return the next character string in a file
Note that it calls malloc/realloc, so the pointer returned MUST BE FREED!!!!
Also, this function is not totally robust against certain kinds of punctuation, so keep it simple.
*/
char* getWord(FILE *file)
{
int length = 0;
int maxLength = 16;
char character;
/*char * c =0;*/
char* word = (char*)malloc(sizeof(char) * maxLength);
assert(word != NULL);
while( (character = fgetc(file)) != EOF)
{
if((length+1) > maxLength)
{
maxLength *= 2;
word = (char*)realloc(word, maxLength);
}
if((character >= '0' && character <= '9') || /*is a number*/
(character >= 'A' && character <= 'Z') || /*or an uppercase letter*/
(character >= 'a' && character <= 'z') || /*or a lowercase letter*/
character == 39) /*or is an apostrophe*/
{
word[length] = character;
length++;
}
else if(length > 0)
break;
}
if(length == 0)
{
free(word);
return NULL;
}
word[length] = '';
return word;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.