CSCI 2720 -- Data Structures
Spring 2007
Project 1 : templated DLL classes: regular and XOR
Assigned: Wednesday, Feb. 7
Due: Thursday, Mar. 1
Extended to: Sunday, Mar. 4th
This project has two parts. In both parts you will implement a templated
list class in which the nodes are dynamically allocated linked structures.
For both of these classes, it should be possible to traverse the list in
O(n) time, in either the forward or backward direction. That is, the
"next" operation should take O(1) time, as should the "prev" operation.
- In version one of the DLL class, each node should contains three fields:
a "next" field, a "value" field of the templated type, and a "prev" field.
- In version two of the DLL class, each node should contain only two
fields, a "value" field of the templated type, and an "xor_ptr" field that
contains the the result of XORing together the addresses of the previous
node in the list and the next node in the list.
The public methods (member functions declared to have public access)
that your list class needs to provide are:
- a default constructor (creating an empty list);
- a member function int IsEmpty( ) const, returning 1 if the list is
empty and 0 if not;
- a member function int Length( ) const, returning the number of elements
in the list;
- member functions void Push_front(const Dtype & X) which adds X at the
front of the list, and void Push_back(const Dtype & X) which adds
X at the back of the list;
- member function void Pop_front( ) which removes the front element of
the list; and void Pop_back( ) which removes the back element of the list;
- member functions Dtype & Front( ) const which returns the front element
of the list, and Dtype & Back( ) const which returns the back element
of the list;
- member function void Print( ) const which writes the elements of the
list from front to back, to cout, without altering the list.
- member function void PrintBack( ) const which writes the elements of the
list from back to front, to cout, without altering the list.
- member function void Iterate(void vist(T& item)) which visits each element
of the list and invokes the function pointed to by visit on the "value"
field of the node. The contents of the list may be altered as a result
of invoking this method.
- member function void Reverse( ) which reverses the entire list without
copying any data (use the "link inversion" method)
- default destructor (deallocates all nodes using delete)
Your specification for the first list version should be in a file called
list1.h and your implementation code should be in a file called list1.cc.
Your specification for the second list version should be in a file called
list2.h and your implementation code should be in a file called list2.cc
Other useful links
Submission Procedure
In your home directory on atlas make a subdirectory named "cs2720p1" and
put copies of your source files in it, as well as the header files and the
Makefile. Include a README file with any information you'd like the grader to
see, as well as a declaration that the files you are submitting represent your
own work. DON'T include executables.
LOGGED ONTO ATLAS and in your home directory execute the command line
"submit cs2720p2 cs2720a".