CMSC-341 Fall 2001
Project 2
| Assigned |
17 Sept 2001 |
|
| Due |
03 Oct 2001 |
|
| Modification
| 24 Sept 2001
| Operator== and Operator!=
added to ListIterator class
|
Background
The List ADT is a fundamental building block for other ADTs such as the Stack and Queue.
The text describes a singly-linked list.
In this project you will get a chance to implement a doubly-linked circular list to solve a problem.
Iterators provide an abstraction of the concept of position within a data structure and a mechanism for walking through a data structure one element at a time. In this
project you will implement a bi-directional iterator for the circular linked list.
This project will require a well thought out design before you can begin coding. Identifying problems, issues and their solutions at design time will save you an
enormous amount of time compared to finding them at coding/testing/debugging time. You will be required to answer questions about the problems you discovered
and the design decisions you made to solve those problems. Make sure you understand the text's linked list and iterator before proceeding.
Description
This problem involves character based file I/O, building a linked list and traversing the list
using an iterator.
This project will read data from a file and build the linked list. The data in the file
consists of character/integer pairs (except the first entry which is a single integer).
The file format is described in detail below.
Your program will read the data from the file and store each character/data pair in the linked
list in the order it was found in the file.
The characters represent a scrambled message.
You are to print the message by moving from node to node in the list based on the integer found
in the node. Note that the integer may be positive
which means move towards the tail, or negative which means move towards the head, or zero which
means you have come to the end of the message.
The initial entry in the file is a single integer indicating the node that contains the first character of the message.
Here are your tasks:
- Read and understand the single-linked List and ListIter description from the text.
- Copy linked list files (LinkedList.C and LinkedList.H)
from Mr. Frey's public directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341
to your directory. Modify these files so that the Linked List is doubly-linked and circular
and so that the iterator is bi-directional (there is more than one way to do this).
- Design and implement a class which contains the character/integer pairs to be stored in the
linked list.
- Design and implement Proj2.C which contains main( ) and is the driver program for this project.
Note that the ListItr class may throw an exception. Recall from class that it is an error
to call retrieve() on an iterator that is "past end". Your code must handle this exception.
- Implement a makefile for this project. You can use the makefile
provided for project 1 as a model.
- Answer the questions posed in 341-Fall01-proj2_questions.txt. Copy the
file
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2/341-Fall01-p2_questions.txt
to your own directory and edit it to provide your answers to the questions.
Don't forget to submit the edited file; it is 10% of this project's grade.
Definition of the ADT
All classes must support the "Big-4"
- Default constructor
- Destructor
- Copy Constructor
- Assignment Opertor
If the linked list and iterator code do not provide these operations,
you must write them.
You must also provide them for any and all classes you design and implement, even if the
default behavior provided by the compiler would be acceptable.
As always, you are free to add whatever private data and methods you desire,
but you must provide only the public methods listed in this project description.
The List
The List supports only those public operations discussed in class
and which are defined in the code provided for you. You should not add any other public methods to the List class.
The Iterator
The iterator provided in the code supports only "forward" iteration and provides the following public methods
- advance ()
- isPastEnd ( )
- retrieve ()
One way to provide bi-directional functionality is to provide another
public method typically named "retreat" that moves the iterator "backwards".
In addition to retreat(), the equality operators (operator== and
operator!=) are also permitted, but not required.
A data class
You must provide a class which stores the character/integer pairs read
from the file. This class MUST support the "big 4" and may support the
following public operations:
- whatver constructor(s) you feel are necessary and sufficient
- accessors for the data elements. There is no need for public mutators.
- equality operators -- operator== and operator !=
The Command Line
Project 2 will be invoked with a command line that consists
of a single argument -- the name of the data file
to read.
As usual, you should check the validity of all command line arguments.
The Data File
The first line of the file contains a single integer. This is the "node number" (starting from 1) that contains the first character of the message.
The rest of the file consists of character/integer pairs.
There is one character/integer pair per line.
The first character on the line is the character
which is part of the message. The character and integer are separated by one or more spaces.
Any blank lines in the file should be ignored.
NOTE that all characters (including a space) are valid characters in the file.
Sample Output
Sample output is available for your study at
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2/341-Fall01-p2-sample_output.txt
The files used to create the sample output are also available.
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2/test1.dat
and
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2/test2.dat
Other files will be used for testing
your project. Students are encouraged to make up
their own files for testing.
Project Submission
DO submit these files
Since you submitting your own makefile, you are free to name your files
whatever you like, with the following restrictions
- All class definitions appear in .H files. Header files may NOT
contain any code.
- All class implementations appear in .C files.
- The name of your excutable MUST BE Proj2 (upper-case 'P').
The submitrun program and the scripts that we use to grade your files
assume that you follow this convention for naming your executable.
DO NOT submit these files
The file dsexceptions.h is provided by the author to provide some minimal exception classes
that are thrown by some of his code. In this project, it's #included in
List.H for the ListIterator class. DO NOT submit this file. This file
should be included in your project through your makefile.
Should you find the need to use either the string class or the vector
class, you are free to do so. However, as with project 1, DO NOT submit
string.H/C or vector.H/C.
Use the string.H/C and vector.H/C files in Mr. Frey's public
directory and include them in your project through your makefile.
Submit Tools
There are a number of tools available to you to check on your submittal.
It is your responsibility to ensure that the submittal is correct and will
result in a successful compilation of your project. Do not wait till the last minute to submit
your files. Give yourself enough time to check that your submittal is correct.
If you don't submit a project correctly, you will not get credit
for it. Why throw away all that hard work you did to write the project?
Check your submittals. Make sure they work. Do this before the due date.
Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/.
One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.
Additionally, there are two programs for use only by CMSC-341 students
(not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are
named submitmake and submitrun. You can
use these programs to make or run your submitted projects.
The syntax is similar to that for submit:
submitmake <class> <project>
Example: submitmake cs341 Proj2
This makes the project, and shows you the report from the make utility.
It cleans up the directory after making the project (removes .o files),
but leaves the executable in place.
submitrun <class> <project> [command-line args]
Example: submitrun cs341 Proj2 test.dat
This runs the project, assuming there is an executable (i.e. submitmake
was run successfully).
Grading and Academic Integrity
Your project will be tested using a variety of command lines, some of which
will be invalid.
Your project will also be tested using a variety of command files which
will test various conditions which your code should handle.
Project grading is described in the Project
Policy handout.
Your answers to 341-Fall01-proj2_questions.txt
are worth 10% of your project grade.
Cheating in any form will not be tolerated. Please re-read the Project
Policy handout for further details on honesty in doing projects for
this course.
Remember, the due date is firm. Submittals made after midnight of the
due date will not be accepted. Do not submit any files after that time.