OVERVIEW

In this assignment, you will implement a dictionary$-$like data structure called a hash table as a C abstract data type $($ADT$).$ After validating its correctness, you will implement a program that makes use of your hash table.

GETTING STARTED

For this assignment, you are asked to implement a hash table ADT in two modules: the ht module with the public interface and the ht$\_$impl module with private declarations and definitions. You are given a header file, ht$.$h$,$ which describes the public interface for the hash table abstract data type. You will implement those function signatures in a file called ht$.$c and declare any additional private datatypes and functions in another header, called ht$\_$impl.h$.$ Skeleton versions of these additional files are provided. You will first test your hash table ADT with a separate program, before using it to implement a postal code collator. The public interface must be complete, and its header file must not be changed.

HASH TABLES IN ACTION: A POSTAL CODE COLLATOR

You are asked to write a program, named pcode.c$,$ which uses your hash table implementation for a postal code collator. A skeleton file is provided. We have also provided several files containing the name of a city, town, or hamlet in Canada followed by a postal code in that location. Larger communities have of course more than one postal code.

$ cat postalcodes$\_20.$in

Quebec,G$1$E$7$C$2$

Forest Grove,V$0$K$1$M$0$

Gloucester,K$1$B$3$L$7$

Saint$-$felicien,G$8$K$1$R$8$

North York,M$3$J$2$Z$3$

Montreal,H$2$Y$3$B$6$

Welland,L$3$C$6$T$4$

Montreal,H$2$Z$1$P$3$

Laval,H$7$A$2$E$9$

Oshawa,L$1$H$1$B$8$

Kinburn,K$0$A$2$H$0$

Montreal,H$2$G$2$G$6$

Winnipeg,R$3$L$1$K$3$

Williamswood,B$3$V$1$C$5$

Calgary,T$3$G$3$M$9$

Unionville,L$3$R$3$Y$7$

Leamington,N$8$H$4$W$7$

Markham,L$3$R$0$N$8$

Fort Erie,L$2$A$3$R$4$

Mississauga,L$5$T$1$E$1$

$

The path and name of the data file is passed as a command line argument to the program. The program reads the data from the file and inserts every postal code into the hash table, keyed by city. When a city$/$postal code pair is read, and the key $($city$)$ is already present in the table, the new postal code must be added to the existing value. For example, the file postalcodes$\_20.$in contains $3$ different postal codes for Montreal. When the program is finished processing each of the data lines,

the value for the key Montreal must contain all $3$ postal codes. It is your design decision how you want to store multiple postal codes in a single hash table value.

After the file has been processed and the hash table is created, the user can enter the name of a city $($on stdin$).$ The postal codes for that city are printed to standard output. If a city has more than one postal code, they should all be printed out, separated by commas, with a maximum of $10$ per line in the order that they appeared in the file. If the entered city does not exist, the program should print a message to the screen. The program should keep asking the user to enter a city until Ctrl$-$D is entered, and the program terminates. Example run $($the underlined text is the user input$)$:

$ $./$pcode postalcodes$\_20.$in

Enter a city name: Calgary

Postal codes found:

T$3$G$3$M$9,$

Enter a city name: Montreal

Postal codes found:

H$2$Y$3$B$6,$ H$2$Z$1$P$3,$ H$2$G$2$G$6,$

Enter a city name: Edmonton

No postal codes found

Enter a city name:

$

Skeleton Files:

$1)$ ht$.$h: Picture attached

$2)$ ht$.$c:

#include $"$ht$.$h$"/*$ Import the public hashtable header. $*/$

#include $"$ht$\_$impl.h$"/*$ Also import the private header. $*/$

struct hasht

$3)$ ht$\_$impl.h:

#ifndef HT$\_$IMPL$\_$H

#define HT$\_$IMPL$\_$H

#include $"$ht$.$h$"/*$ Import the public hashtable header. $*/$

$4)$ ht$\_$impl.c:

#include $"$ht$\_$impl.h$"/*$ Import the private header. $*/$

$5)$ htTest.c:

#include $"$ht$.$h$"/*$ Only import the public hashtable header. $*/$

$/*$ htTest.c is not allowed access to the ht$\_$impl.h private header $*/$

int main$($void$)\{$

return $0$;

$\}$

$6)$ pcode.c:

#include $"$ht$.$h$"/*$ Only import the public hashtable header. $*/$

$/*$ pcode.c is not allowed access to the ht$\_$impl.h private header $*/$

int main$($int argc, char $*$argv$[])\{$

return $0$;

$\}$