Logistics
This program is worth 8 points, or 8% of your final grade. The
pertinent time coordinates:
- Assigned: Tues May 24, 2005
- Program due: Fri Jun 3, 2005 at 10:00 am
Some of the fun, new C++ stuff we'll cover includes:
- Doubly linked lists
- Recursion
- Polymorphism... ok, this isn't exactly new, but it is fun
|
Description
Write a little program to manage a doubly-linked list of wombats...
actually, whatever class of object that you decide. If you're listing
wombats, then your menu should have the following options:
1. Append wombat |
2. Remove wombat |
3. Remove all wombats |
4. Insert wombat in
order |
5. Show number of
wombats |
6. Print list |
7. Reverse print list |
8. Exit |
Of course, when you create a new wombat (during append or insert),
then you must prompt the user for the wombat's name and any other vital
information regarding wombats.
Note that for "insert wombat" to work correctly, then all wombats
must be "inserted", so that the order is always maintained. You don't
have to check for this bad case in your code.
|
Design Requirements
You should:
- Implement a doubly-linked list. I think the text's
FloatList example in
section 17.2 is an excellent starting point. Each node should have
and maintain a previous node and next node pointer.
- You list should always maintain a head pointer to the
first node in the list, and a tail pointer to the last node
in the list.
- In the size() function for your list, please count the nodes
recursively.
- You list nodes should store pointers to
Listable objects. (Why do
we want to stick with pointers? Remember?)
Listable should be an
abstract base class with the following pure virtual functions:
// Returns (this -
right), ala strcmp |
// If two Listable are
equal, returns 0. |
int compare( Listable
*right); |
|
// prints a Listable
object |
void print( ostream
&out = cout); |
|
- With your Listable
class in order, then you need to create a subclass of
Listable that you want to
be able to, well, list. I can be anything (wombats?) as long as you
can create, compare, and print them.
- Please use your TextMenu
class for all menu action.
A note on this Listable
nonsense. If we covered C++ templates in this course, then we'd be
implementing this list as a template. You can see one in section 17.3 if
you'd like to compare and contrast.
Also, if you would like to overload operators rather than use
the compare() and
print() functions, you're free
to do so.
Special design requirement
You must complete and hand in "before and after" node diagrams of
each operation your list performs. These should look like mine on the
board, or those in our book on page 1019 and other pages. Some things
you'll want to show:
- Append to an empty list
- Append to a full list
- Insert to an empty list
- Insert to first node, effecting head
- Insert to last node, effecting tail
- Insert in middle of list
- Remove last node in list
- Remove head node
- Remove tail node
- Remove node in middle of list
- and whatever other ones that I've forgotten...
|
Grading
Short program this time:
- Quality, 50%
- Function, 50%
Each of these areas is discussed in the handout: CSC 161 Program
Design, Style and Testing. Please leave a README file in your folder describing
your testing and the state of your program... problems, questions, etc.
thanks... yow, bill
|
Notes
May 24, 2005
I will not help individuals with coding problems that do not have
their list diagrams completed and with them.
zealous, not cranky... yow, bill
May 26, 2005
OK, for our last program, let's mix up our commenting and naming
tactics. For Program #5, please:
- Use underscore as the first character of member variable names,
like _head. This will make member
variable easier to identify in your code.
- Comment your member functions in the header file. For example,
my List::print_reverse function in
list.h looks like this:
//-------------------------------------------------------------- |
// print_reverse( out) |
// Prints the objects
in a list to an output stream in reverse |
// order, last to
first. |
// pre: "out" param is
an open output stream |
// post: none |
void print_reverse(
ostream &out = cout) const; |
- In your implementation, C++ file, document any implementation
specifics for the function. Example:
//-------------------------------------------------------------- |
// List::print_reverse |
// Starts traversing
the List from the _tail and uses |
// _prev pointers to
print objects in reverse order |
void
List::print_reverse( ostream &out = cout) const { |
// your
code here... |
} |
- In each function description, document the pre-conditions
(parameters and any other conditions needed for the function to
work, and post-conditions (return value and any other side effects).
I have also shown this in my example above.
- Use underscores to separate words in a name, rather than
the Java-style capitalization that we've used so far. For example,
use print_reverse(), rather than
printReverse().
Extra credit! If your list can handle 2 flavors of
Listable objects correctly, then you
will get one point of extra credit. This entails:
- Creating another subclass of Listable,
like Wallaby or something.
- The append and insert choices in your menu must ask if you want
to create a new Wombat or
Wallaby.
- Change the compare() function in
each Listable subclass so that it
throws an exception if you try and compare two objects of different
classes.
- You can use dynamic_cast to
convert from a Listable * to, for
example, a Wombat *. The cast will
return 0 if the object pointer is not actually a
Wombat (must then be a
Wallaby, eh). You can google this
for more information... I don't think it's in our book.
- Finally, you'll have to modify your
List functions that use compare(),
so they catch the exception.
- Given the magic of polymorphism, your
print() functions should be OK.
get it, got, good... yow, bill
|