Lab 3 - University of Washington

University of Washington, Bothell
CSS 342: Data Structures, Algorithms, and Discrete Mathematics
Winter 2015
Program 3: Linked Lists
Assigned: Thursday, January 29, 2015
Due: Wednesday, February 11, 2015, 10pm PST
This programming assignment will require the usage of dynamic memory, pointers and linked
lists. It will also require the usage of File IO and templates. Also, required is a good
understanding of overloading assignment and copy constructors. Learnings from previous
assignments, especially operator overloading will also be required.
Problem: The List.
You will build a class for a fully ordered list. The list class, called List342, will be templatized so
that different types of objects can be stored in it.
List342<string> aListofStrings;
List342<int> aListofInts;
List342<Child> children;
List342<MyRandomObj> myRO;
The following member functions should be created for the List342 class. Please make sure the
signatures are exact or points will be deducted as the test programs will not compile. Also
make sure that the proper constructors/destructors are created for the class.
bool BuildList(string FileName) : Given a string which represents a file, open the file,
read the objects from file, and build an ordered list. Note that BuildList puts the responsibility
on the Object class to know how to read from a file. That is, do not have object specific logic in
the implementation. Use an Insertion Sort to order the list.
Assume that the list passed in is well-formed for the object being read into.
bool Insert( ItemType *obj ) : Insert an object in the list in the correct place. Return
true or false depending on whether the insert was successful. Duplicates of an object are not
allowed. If there is a duplicate the function should return false. Note that a pointer to the
object is passed in but the Insert should create a copy of the object to keep in the list.
bool Remove(ItemType target, ItemType &result): Remove the target item from the
list. Return the item using a second parameter that is passed in by reference. If the item was
found and removed return true, else return false.
bool Peek(ItemType target, ItemType &result): The same as Remove except the item
is not removed from the list. Again, the second item is returned by reference.
bool isEmpty(): Is the list empty?
void DeleteList(): Remove all items from the list. Deallocate all memory appropriately.
This includes not only the nodes in the list but the items being pointed to by the nodes.
bool Merge(List342 &list1): Takes a sorted list and merges into the calling sorted list
(no new memory should be allocated). At termination of function, the list passed in (list1)
should be empty (unless it is the calling list). No duplicates are allowed.
The following operators should be overloaded for the List342<>. Please make sure signatures
are correct on overloads.
+, += : This should add two lists together. The lists are assumed to be sorted and the
returned list must also be sorted. Use an efficient sort algorithm and avoid unnecessary data
allocations. Duplicates are not allowed and expected.
<< : Display the list and only the List object, no extra blanks, no tabs, no endl. Display
the items on the list in increasing order. See examples below.
== and != : check for equality or inequality.
= : Assignment. Make a deep copy of all new memory.
Details on testing:
We will need specific objects to test the list. We will use some of the built in types like ints. As
List342<> is templatized we will also test with a set of objects we create. We will also use a
Child and Bird class for the examples and testing. Please create a Child and Bird class as well.
Details are below.
The child class should contain a first name (string), last name (string), and age (int). Input will
be of the form “firstname lastname age” in the file. Assume it is well formed w/o errors. For
instance, a file could have the following.
George Washington 12
Lyndon Johnson
Joseph Smith
Thomas Paine
Thomas Paine
Please sort Child alphabetically by last name first. Please provide a getter function for
the first name:
string getLastName() const
A Bird class will have the name of the Bird (string) and a unique ID (int). An input file for Birds
can look like this:
Please sort the birds by ID number. Please provide a getter function for name:
string getName() const;
Other Rules and Hints
1) Implement the List342<> class using Nodes defined as below. It can be internal or
external to the List342<> class. Keeping the struct definition external to the List342
class may be the easiest solution. However, templatizing the struct may encounter
issues in this way. Therefore, keeping Node in the private area of List342<> is probably
struct Node {
ItemType *data;
Node *next;
2) Due to vicissitudes of different IDEs and templating we will be factoring the code into
files a little sub-optimally. Put all code into the List342.h file—this includes the
implementation (.cpp) as well as the .h.
TURN IN (in a .zip file):
o List342.h and List342.cpp
o Bird.h, Bird.cpp, Child.h, Child.cpp
o The .exe if built/tested on windows, the a.out if built/tested on Linux
Sample input/output will soon be provided.