C programming, HASH TABLES in file ListDeque.c functions you will need (but shou
ID: 666341 • 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
This question has multiple subparts. Please post 3 more questions. I have answered the hash map creation and insertion part.
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
struct entry {
char *key;
char *value;
struct entry *next;
};
typedef struct entry entry_t;
struct hash {
int size;
struct entry **table;
};
typedef struct hash hash_t;
/* Create a new hashtable. */
hash_t *ht_create( int size ) {
hash_t *hashtable = NULL;
int i;
if( size < 1 ) return NULL;
/* Allocate the table itself. */
if( ( hashtable = malloc( sizeof( hash_t ) ) ) == NULL ) {
return NULL;
}
/* Allocate pointers to the head nodes. */
if( ( hashtable->table = malloc( sizeof( entry_t * ) * size ) ) == NULL ) {
return NULL;
}
for( i = 0; i < size; i++ ) {
hashtable->table[i] = NULL;
}
hashtable->size = size;
return hashtable;
}
/* Hash a string for a particular hash table. */
int ht_hash( hash_t *hashtable, char *key ) {
unsigned long int hashval;
int i = 0;
/* Convert our string to an integer */
while( hashval < ULONG_MAX && i < strlen( key ) ) {
hashval = hashval << 8;
hashval += key[ i ];
i++;
}
return hashval % hashtable->size;
}
/* Create a key-value pair. */
entry_t *ht_newpair( char *key, char *value ) {
entry_t *newpair;
if( ( newpair = malloc( sizeof( entry_t ) ) ) == NULL ) {
return NULL;
}
if( ( newpair->key = strdup( key ) ) == NULL ) {
return NULL;
}
if( ( newpair->value = strdup( value ) ) == NULL ) {
return NULL;
}
newpair->next = NULL;
return newpair;
}
/* Insert a key-value pair into a hash table. */
void ht_set( hash_t *hashtable, char *key, char *value ) {
int bin = 0;
entry_t *newpair = NULL;
entry_t *next = NULL;
entry_t *last = NULL;
bin = ht_hash( hashtable, key );
next = hashtable->table[ bin ];
while( next != NULL && next->key != NULL && strcmp( key, next->key ) > 0 ) {
last = next;
next = next->next;
}
/* There's already a pair. Let's replace that string. */
if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 ) {
free( next->value );
next->value = strdup( value );
/* Nope, could't find it. Time to grow a pair. */
} else {
newpair = ht_newpair( key, value );
/* We're at the start of the linked list in this bin. */
if( next == hashtable->table[ bin ] ) {
newpair->next = next;
hashtable->table[ bin ] = newpair;
/* We're at the end of the linked list in this bin. */
} else if ( next == NULL ) {
last->next = newpair;
/* We're in the middle of the list. */
} else {
newpair->next = next;
last->next = newpair;
}
}
}
/* Retrieve a key-value pair from a hash table. */
char *ht_get( hash_t *hashtable, char *key ) {
int bin = 0;
entry_t *pair;
bin = ht_hash( hashtable, key );
/* Step through the bin, looking for our value. */
pair = hashtable->table[ bin ];
while( pair != NULL && pair->key != NULL && strcmp( key, pair->key ) > 0 ) {
pair = pair->next;
}
/* Did we actually find anything? */
if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 ) {
return NULL;
} else {
return pair->value;
}
}
int main( int argc, char **argv ) {
hash_t *hashtable = ht_create( 65536 );
ht_set( hashtable, "key1", "inky" );
ht_set( hashtable, "key2", "pinky" );
ht_set( hashtable, "key3", "blinky" );
ht_set( hashtable, "key4", "floyd" );
printf( "%s ", ht_get( hashtable, "key1" ) );
printf( "%s ", ht_get( hashtable, "key2" ) );
printf( "%s ", ht_get( hashtable, "key3" ) );
printf( "%s ", ht_get( hashtable, "key4" ) );
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.