Project #3: List Structure Exercises proj3.zip Solution

This programming assignment gives you practice with using pointers�particularly the this pointer�and building and using linked lists and trees. In addition, it provides you with experience in using recursion and designing constructors, and introduces you to destructors.

Readings
A Computer Science Tapestry Sections 12.1 - 12.2
Starter Code
Please download the starter code from above.

Your Task
Do all three of the programming exercises described below.

Miscellaneous Information
The null pointer is variously referred to in this document and the textbooks as NULL (an identifier defined in <cstdlib) or 0. Bjarne Stroustrup (inventor of C++) recommends using 0, since NULL is not necessarily type-compatible with all pointers.

Incidentally, the C++ standard library provides implementations for most of the data structures one would ever want to use, including those designed from scratch for this assignment. A good online reference for the standard library, should you go on to do more C++ programming, ishttp://www.sgi.com/Technology/STL.


Exercise 1: List Destructor
The files lists.h and lists.cpp implement a list data type that represents a list as a pointer to a ListNode, similar to what's described in A Computer Science Tapestry Section 12.2.

The ListNode class has a disadvantage that you deal with in this exercise. Its destructor function, called when a ListNode is deleted, results in an infinite loop. You are to discover why, and fix it, changing as little code as possible. (In particular, you're not allowed to change lists.h.) The corrected destructor should result not only in the node itself being deleted, but in deletion of all nodes linked to that node.

Here's an example. The version of ~ListNode that produced the output below included an output statement to show what was going on, and your version should also.

Test your program using destr.test.cpp. First create a test file with content:

3 4 5
Result of executing the program:

$ g++ -g -Wall -o destr.test destr.test.cpp lists.cpp $ destr.test < testfile 5 4 3 Deleting node with value 5 Deleting node with value 4 Deleting node with value 3
Checklist
Explanation of the problem with the existing code.
Corrected code, with as few changes as possible, tested as specified.
Adherence to CS 9F style standards:

appropriate use of indenting and white space;
avoidance of "forbidden C++";
variable and function names that reflect their use;
informative comments at the head of each function;
no routine more than twenty-four lines of code.

Exercise 2: Circularly Linked Lists
Background
The file selection.cpp contains most of a program that implements the following method of selecting a person from a group of n people:

All the people stand in a circle. Someone is designated as the starting person, and that person is given a marble.
The starting person thinks of a positive number k less than n.
The marble is passed from one person to the next on the circle, k times.
The person now holding the marble is "out", and his or her successor on the circle takes the marble.
Steps c and d are repeated until only one person remains in the circle. That's the selected person.
Here's an example. Suppose there are 8 people, k = 2, and person #1 is the starting person. The diagram below illustrates the seven repetitions of steps c and d. Arrows represent passes of the marble, and the shaded box indicates the person who goes out at each step.















 
Exercise
The program in selection.cpp uses a circularly linked list structure, partially implemented in the files CLLNode.h and CLLNode.cpp, to represent the candidates for selection. Two member functions for the CLLNode class, insert and remove, have not been supplied. You are to provide definitions for these functions that agree with the comments in the supplied code, and complete selection.cpp by supplying the appropriate calls to insert and remove.

The constant definitions in selection.cpp are set up to test your code on the example above. Bring the output of the program to a tutor for grading.

Checklist
Correct implementations of insert and remove, tested as specified.
Listings of program text, tests, and test results.
Adherence to CS 9F style standards:

appropriate use of indenting and white space;
avoidance of "forbidden C++";
variable and function names that reflect their use;
informative comments at the head of each function;
no routine more than twenty-four lines of code.

Exercise 3: Amoeba Family Trees
Background
An amoeba family tree is simpler than a normal family tree because amoebas do not get married. An amoeba has one parent, perhaps a million siblings (brothers and sisters), and billions and billions of children. An amoeba also has a name.

Amoebas (or amoebae) live dull lives. All they do is reproduce. So all we need to keep track of them are the following declarations:

class Amoeba { public: Amoeba(_____string); // birth of an amoeba _____string Name(); // returns your name Amoeba* Parent(); // returns your parent void AddChild(Amoeba*); // add a baby amoeba to the family private: _____string myName; // this amoeba's name Amoeba* myParent; // good old mom (or is it dad?) Amoeba* myOlderSibling; // the next older brother/sister Amoeba* myYoungestChild; // the youngest kid Amoeba* myOldestChild; // the oldest kid };
The above code is the content of amoebas.h; the member functions are in amoebas.cpp. A program that uses these functions is in the fileamoebamain.cpp.

NOTE: The header as it shown normally won't compile using a modern C++ compiler. Can you figure out why? (Hint: it has something to do with the _____ lines above. Hint#2: Check out this article if you are still stuck.)

Exercise
This exercise has five parts.

Draw a diagram of the "family" constructed by the program in amoebamain.cpp. Use arrows in the diagram to show all the family relationships. Make sure that your drawing shows the tree exactly as the program builds it (a misleading drawing is worse than none at all).
Suppose you were the amoeba represented by the pointer me. Add a statement to amoebamain.cpp to print the name of your grandparent, who should be Amos McCoy. Try it out, and be prepared to explain to a tutor what happens and what's necessary to make the statement work properly. (Hint: look at your drawing.)
Add a member function called PrintChildren to amoebas.cpp that prints the names of the amoeba's children, one per line. (Also add its prototype to amoebas.h.) Test your function by adding a call or two to the end of amoebamain.cpp, and show the results of your tests to a tutor for grading.
Add a member function called PrintGrandchildren to amoebas.cpp that prints the names of the amoeba's grandchildren, one per line. (Also add its prototype to amoebas.h.) Your function should use the PrintChildren function described above. Test your function by adding a call or two to the end of amoebamain.cpp-you may also need to add some amoebas to the tree-and show the results of your tests to a tutor for grading.
Add a member function called PrintDescendants to amoebas.cpp that prints the names of all the amoeba's descendants. (Also add its prototype to amoebas.h.)
One name should be printed per line. The names of the children of each descendant amoeba should be printed on the lines immediately following; they should be indented four spaces more than the name of their parent. Thus the output should appear in the form
child-name grandchild-name great-grandchild-name great-great-grandchild-name grandchild-name child-name grandchild-name child-name child-name grandchild-name
Test your function by adding a call or two to the end of amoebamain.cpp, and show the results of your tests to a tutor for grading. You may add private helper functions to the Amoeba class if you want.

Your PrintChildren, PrintGrandchildren, and PrintDescendants member functions should all work no matter which amoeba they are called with.

Checklist
Correct diagram.
Correct additions to amoebas.h and amoebas.cpp (statement to print the name of me's grandparent, plus member functions PrintChildren, PrintGrandchildren, and PrintDescendants), tested as specified.
Listings of program text, tests, and test results.
Adherence to CS 9F style standards:

appropriate use of indenting and white space;
avoidance of "forbidden C++";
variable and function names that reflect their use;
informative comments at the head of each function;
no routine more than twenty-four lines of code.