Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

OVERVIEW In this assignment, you will implement a dictionary - like data structure called a hash table as a C abstract data type ( ADT

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,G1E7C2
Forest Grove,V0K1M0
Gloucester,K1B3L7
Saint-felicien,G8K1R8
North York,M3J2Z3
Montreal,H2Y3B6
Welland,L3C6T4
Montreal,H2Z1P3
Laval,H7A2E9
Oshawa,L1H1B8
Kinburn,K0A2H0
Montreal,H2G2G6
Winnipeg,R3L1K3
Williamswood,B3V1C5
Calgary,T3G3M9
Unionville,L3R3Y7
Leamington,N8H4W7
Markham,L3R0N8
Fort Erie,L2A3R4
Mississauga,L5T1E1
$
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:
T3G3M9,
Enter a city name: Montreal
Postal codes found:
H2Y3B6, H2Z1P3, H2G2G6,
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;
}
Please implement these 6 functions as per given skeletons above.
image text in transcribed

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Concepts of Database Management

Authors: Philip J. Pratt, Mary Z. Last

8th edition

1285427106, 978-1285427102

More Books

Students also viewed these Databases questions