CSE2305 - Object-Oriented Software
Engineering
Assessment
An associative array is an array that stores one data type (the value) indexed by another (the key). This is a generalisation of the standard array in C which only allows indexing by a number. For example:
postcode["Clayton South"] = 3068;
cout << "The postcode for " << cityName << " is " << postcodes[cityName] << endl;
Write a class¤ called Array
which
implements an associative array. The key for the array will be a std::string
. Elements
stored in the array will contain data, also of type std::string
.
Your Array
class should be able to store any number of
elements. The example above uses operator
overloading to overload operator[]
.
For this assignment, there is no need to overload operators, so member functions
will be used to get and set the data.
Your Array
class¤ should
provide the following methods:
Array
object.Array::Insert(string key,
string value)
,
which inserts the specified value into the array using index key.Array::Delete(string key)
,
which deletes the specified key and the value associated with it.Array::Exists(string key)
,
which searches for the specified key and returns true
if
the key was found and false
otherwise. Array::Find(string key)
,
which searches for the specified key and returns the data associated
with the key (if it exists), or a null string otherwise. Classes¤ such
as the List
and Array
classes¤ are
called Containers¤. Container
Classes¤ are
used to store any type of data. Consider for the future how
you could specify and store arbitrary data types for the key and value.
Using the Array
class¤ you
implemented in the previous question write a class¤ called PostCodeFinder
,
which can load a list of postcodes stored in a file,
and then be used to find the postcode for the supplied city name and state.
Your PostCodeFinder
class¤ should
provide the following methods:
Array
data
member¤¤
PostCodeFinder::Lookup(string cityName,
string state)
,
which returns the postcode for the city if it exists,
an empty string otherwise.
Use your PostCodeFinder
class¤ to
write a simple post code lookup program. The program should load a list of
cities, states and postcodes from a specified file into a PostCodeFinder
object,
then prompt for a city and state name, returning the corresponding postcode
if found, or the string "No postcode found for cityname" (where cityname is
the name of the city entered). This should repeat until
the user terminates the cycle. The program then quits.
Associative arrays are best implemented as a hash table. You will need to devise a suitable hash function to hash a string key to the appropriate position in the array.
Hash tables need to handle collisions (when two different
keys hash to the same location). To handle collisions, make sure your Array
class¤ stores
a List
of elements at each location in the array (see Assignment
1).
You should submit the following:
Makefile
, with 2 targets: the default target builds the
program(s), the clean target removes the executable and any intermediate
(e.g. .o files created during compilation).README
file briefly explaining what you have
done (including testing) and how to perform the tests on your submission.vi
).See the submit page for details on how to submit your assignment.
Last Modified: August 24, 2005