CMSC 341 Fall 1999 Project 2
Project 2
| Assigned |
Monday, 20 September 1999 |
| Due |
Monday, 04 October 1999 |
Background
The List ADT is a fundamental building block for other ADTs such as the
Stack and Queue. 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 two iterators 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.
Description
Basically you will doing Exercise 3.15, part a (page 117) of the Weiss text as
modified below.
You are required to implement your list as a circular doubly-linked list (See sections 3.2.5 and 3.2.6 for descriptions of doubly-linked list and
circular lists).
The solution will require that you implement two iterators for the list.
One iterator (ListItr) runs from "beginning" to "end", referencing each data
element of the list just once. The second iterator (CircListItr) runs around
the circular list forever and never stops visiting data nodes
(unless the list is empty).
Please remember that you must provide
good documentation as described in the
"Project Organization" handout.
Here are your tasks:
- Read and understand the material on Lists in chapter 3.
- Understand the concept of the header node in the implementation of the List.
- Implement the List class as circular doubly-linked list. You may
use any code found in the text.
Source code from the text
is available, but will most likely need to be modified.
Dr. Anastasio has provided slightly modified code from the text in
his public directory
/afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341
- Implement the ListItr class that iterates through the list just once.
This iterator should support the common idiom:
<![CDATA[
ListItr itr = theList.first ();
for (; !itr.isPastEnd (); itr.advance () )
{
Object x = itr.retrieve();
// process x
}
]]>
- Implement the CircListItr class that continually iterates through
the data elements in the list (unless the list is empty).
This iterator should support the same idiom as above:
<![CDATA[
CircListItr itr = theList.circFirst ();
for (; !itr.isPastEnd(); itr.advance()
{
Object x = itr.retrieve ();
// process x
}
]]>
- Provide a main program to solve the Josephus problem described in
Exercise 3.15 of the Weiss text. The main program takes two arguments
- N -- the number of people in the circle
- M -- the number of passes to determine which person is eliminated from the game.
Any errors on the command line (no argument, more than two arguments,
argument not an integer, argument is an integer but value is inappropriate
are to be reported to
cerr and the program is to exit with a
failure indication.
-
Write a makefile. You can start with your makefile from Proj1
and modify it as needed.
- As with project 1, your code will need to handle exceptions. The text
code throws BadIterator(). You should handle this situation and add any others
you feel are appropriate.
-
Answer the questions posed in 341-Fall99-proj2_questions.txt. Copy the file
/afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341/Proj2/341-Fall99-proj2_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 counts
10% toward this project's grade.
Grading and Academic Integrity
Project grading is described in the
Project Policy handout.
Your answers to
341-Fall99-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.
Definition of the ADTs
List:
A List is a homogeneous sequence
of Objects.
Duplicates are allowed. Every List
has infinite capacity, the number of elements it is capable of holding.
The operations listed below constitute a minimal ADT directed towards
solving the Josephus problem in the text. You are free to
add operations as you feel necessary, but all operations listed
below must be implemented.
The operations allowed on a List are:
Take a look at the
sample output below. Note that a List
is printed as a comma-separated list of the elements enclosed by
angle brackets. Observe carefully that there is no comma after the
last element. An empty List is presented simply as a pair of
angle brackets.
ListItr:
A list iterator is an abstraction of the concept of position of an
Objectwithin the List.
It provides methods that can be used to iterate (move one element at a time)
through the list and to retrieve the Object
associated with the position the iterator represents.
The operations allowed on a ListItr are:
- construction of a ListItr that represents no position (default constructor)
- construction of a ListItr from another ListItr (copy constructor)
- destruction of a ListItr (destructor)
- assignment operator (operator=)
- bool isPastEnd () const that returns
true if the iterator is beyond the end of the list, false otherwise.
- void advance () that moves the
iterator to the next element in the list. An iterator that is past the
end of the list is unchanged by advance().
- const Object & retrieve () const
that returns a reference to the Object
stored in the current position. It is an error to retrieve an
Object from a ListItr that is past the
end of the list.
- Write a private constructor for use by the
List class, similar to that described in class and in the text.
CircListItr:
Like a ListItr, the CircListItr provides methods that move through the
list one element at a time. Unlike the ListItr which advances through
the list only once, the CircListItr continually advances around the
data elements in the circular list.
The operations allowed on a CircListItr are:
- construction of a CircListItr that represents no position (default constructor)
- construction of a CircListItr from another CircListItr (copy constructor)
- destruction of a CircListItr (destructor)
- assignment operator (operator=)
- void advance (void) that moves the
iterator to the next element in the list.
advance() continually advances around the
circular list as long as there is at least one element in the list.
- const Object & retrieve (void) const
that returns a reference to the Object
stored in the current position.
- bool isPastEnd () const that returns
true if the list is empty, false otherwise.
- Write a private constructor for use by the
List class, similar to that described in class and in the text.
Notes about Iterators and isPastEnd()
The concept of isPastEnd() plays an important role with iterators,
particularly in this project. Pay particular attention to situations involving
an empty list. Some facts about iterators that may help
with this project
- a newly constructed zeroth() iterator is not "past end"
- a newly constructed iterator that expects to point to a data node
is "past end" if the data node does not exist.
- any iterator may become "past end" when it advances.
Files To Be Submitted
You should submit only the files you have written, a makefile, and the
file containing your answers to the questions. The files to be
submitted are:
- the List class files
- the ListItr class files.
- the CircListItr class files.
- your main program file
- your makefile
- any auxiliary files you may have written for the project
- 341-Fall99-proj2_questions.txt -
containing your answers to the questions.
Submit the files using the procedure given to you for your section
of the course.
Sample Output
Sample output is available for your study at
/afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341/Proj2/341-Fall99-p2-sample_output.txt
It was obtained by executing
to be provided
A copy of the executable is available for you to try out. It is
/afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341/Proj2/Proj2