For this assignment, you will implement the dictionary abstract type using a hash table imple- mentation. Remember that a dictionary can be thought of as a set of key-value pairs, where no two pairs...

1 answer below »

For this assignment, you will implement the dictionary abstract type using a hash table imple- mentation. Remember that a dictionary can be thought of as a set of key-value pairs, where no two pairs have the same key. This is equivalent to thinking of a dictionary as a function from keys to values. The dictionary type that you will implement maps string keys to integer values. The idea behind the implementation is discussed in the lecture materials. Roughly speaking, it is the same as using a hash table to implement a set: use an array T, where each T[i] is a singly-linked list, where each element in that list is one of the key-value pairs where the key has hash code i. The interface is specified in hw9.h, and I have provided starter code for you in hw9starter.c. Here are a few comments about this assignment:

  • Strings are represented by char arrays of length MAX_LEN, where MAX_LEN is defined in hw9.h.

  • The size of your table must be TBL_SIZE, which is defined for you in hw9.c. You must not change this definition. It is intentionally small so as to make it easy to create collisions.

  • The starter code includes a hash function; you must not change it.

  • You will need to design some sort of structure yourself for key-value pairs.

  • You must identify in documentation an appropriate invariant for your implementation, and

    you must use assertions appropriately to verify that it holds.

  • The function dict_add(d, k, v) adds the key-value pair (k, v) to the dictionary d if there is

    no pair with k already, and otherwise replaces the existing pair.

  • The function dict_size must run in constant time.

  • During usage, a dictionary will accumulate many nodes that have been allocated in the heap.

    For good memory management, those nodes must be released when no longer needed. That

    is the role of the dict_free() function.

  • The interface specifies two printing functions: dict_printkvs() and dict_print(). The

    former must print out the key-value pairs one per line, in the format key : value. It does not matter what order you print them out in. This is the function we will use to test your code. The latter is there for your use; you may have it do whatever you like, and we will not use it in testing.

  • I have provided a driver file that permits the client to enter words at the terminal, and which uses your dictionary implementation to count how many times each word has been entered. A sample trace of executing that program is shown in Figure 1.

    Code distribution and submission

    The code distribution contains the interface file hw9.h, driver dictdriver.c, and starter code hw9starter.c. You must rename the latter file to hw9.c for your submission.

    Submit only hw9.c. I will compile it using my own copy of hw9.h and my own driver program.

Answered Same DayMay 07, 2021

Solution

Arun Shankar S answered on May 08 2021
17 Votes

#include
#include
#include
#include
#include "hw9.h"
typedef struct entry
{
char* key;
int value;
struct entry*...

Submit New Assignment

Copy and Paste Your Assignment Here