TOC PREV NEXT

Program — List structure exercises

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 and 12.2.

C++ Program Design, sections 9.5 (destructors), 12.1 through 12.3 (pointers, covered in a C context), and 12.8 (pointers, covered in a C++ context). Chapter 12 unfortunately relies heavily on C-style examples. Moreover, linked lists aren't covered until after templates; an example appears in section 14.5.

Computing Fundamentals with C++, chapters 14, 15, and 20. Ignore use of C-style arrays in sections 15.1 and 15.2.

Material on templates and operator overloading will be covered in the "Class design" segment.

Related quizzes

Dynamically allocated data

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, is http://www.sgi.com/Technology/STL.

Programming assignment

Do all three of the programming exercises described below.

List structure exercise 1 — list destructor

The files ~cs9f/lib/lists.h and ~cs9f/lib/lists.cpp implement a list data type that represents a list as a pointer to a ListNode, similar to what Astrachan describes in section 12.2 but simpler than Mercer's LinkedList class in chapter 15.

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 program: 

	#include <iostream>
	#include "lists.h"
	
	ListNode* FromInput (istream &is) {
		int k;
		ListNode* head = 0;
		while (is >> k) {
			head = new ListNode (k, head);
		}
		return head;
	}
	
	int main () {
		ListNode* list = FromInput (cin);
		list->Print ();
		if (list) {
			delete list;
		}
		return 0;
	}

Test file: 

	3 4 5

Result of executing the program: 

	% a.out < testfile
	5 4 3
	Deleting node with value 5
	Deleting node with value 4
	Deleting node with value 3

Use the program above to test your destructor. It's in ~cs9f/lib/destr.test.cpp.

Checklist

Explanation of the problem with the existing code.
Corrected code, with as few changes as possible, tested as specified.
Printed 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.

lists.h 

#ifndef LIST_H
#define LIST_H

class ListNode {
public:
	ListNode (int k);
	ListNode (int k, ListNode* ptr);
	~ListNode ();		// delete the node and all nodes
				// accessible through it;
				// precondition: this != 0.
	int First ();		// return the value stored in the list node
	ListNode *Rest ();	// return the list consisting of
				// the remaining elements
	void Print ();		// print the list
	
private:
	int myValue;
	ListNode* myNext;
};
#endif

lists.cpp 

#include <iostream>
#include <cassert>
using namespace std;

#include "lists.h"

ListNode::ListNode (int k) {
	myValue = k;
	myNext = 0;
}

ListNode::ListNode (int k, ListNode* ptr) {
	myValue = k;
	myNext = ptr;
}

// Delete the node and all nodes accessible through it.
// Precondition: this != 0.
ListNode::~ListNode () {
	// this version is buggy
	cout << "Deleting node with value " << myValue << endl;
	for (ListNode* p=this; p!=0; p=p->myNext) {
		delete p;
	}
}
// Print the list.
void ListNode::Print () {
	ListNode* list = this;
	for (; list; list = list->Rest()) {
		cout << list->First() << " ";
	}
	cout << endl;
}

// Return the value stored in the node.
int ListNode::First () {
	return myValue;
}

// Return the list of the remaining elements.
ListNode* ListNode::Rest () {
	return myNext;
}

List structure exercise 2 — doubly linked lists

Background

The file ~cs9f/lib/selection.cpp contains most of a program that implements the following method of selecting a person from a group of n people:

a. All the people stand in a circle. Someone is designated as the starting person, and that person is given a marble.

b. The starting person thinks of a positive number k less than n.

c. The marble is passed from one person to the next on the circle, k times.

d. The person now holding the marble is "out", and his or her successor on the circle takes the marble.

e. 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.



step 1: #1 starts, #3 is eliminated



step 2: #4 takes the marble, #6 is eliminated



step 3: #7 takes the marble, #1 is eliminated



step 4: #2 takes the marble, #5 is eliminated



step 5: #7 takes the marble, #2 is eliminated



step 6: #4 takes the marble, #8 is eliminated



step 7: #4 takes the marble and passes it to #7, who passes it back; #4 is thus eliminated

Exercise

The program in ~cs9f/lib/selection.cpp uses a doubly linked list structure, partially implemented in the files ~cs9f/lib/dll.h and ~cs9f/lib/dll.cpp, to represent the candidates for selection. Two member functions for the DLLnode class, Insert and Delete, have not been supplied. You are to provide definitions for these functions that agree with the comments in the supplied code, and complete ~cs9f/lib/selection.cpp by supplying the appropriate calls to Insert and Delete. As in exercise 1, your Delete function should print a message saying what is being deleted. (Unlike in exercise 1, it should only delete a single node.)

The constant definitions in ~cs9f/lib/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 Delete, tested as specified.
Printed 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.

dll.h 

#ifndef DLL_H
#define DLL_H

#include <iostream>
#include <cassert>

class DLLnode {
public:
	DLLnode (int k);
	DLLnode *Previous ();  // Return a ptr to the predecessor
	                       // of the given node.
	DLLnode *Next ();      // Return a ptr to the successor
	                       // of the given node.
	DLLnode *Insert (DLLnode *ptr);  // Insert ptr node at head 
	                                 // of list and return pointer 
	                                 // to new element.
	DLLnode *Delete ();    // Delete first node from the list;
	                       // return pointer to its successor, or 0.
	                       // Precondition: there is a node to delete.
	void Print ();
	bool LengthIs1 ();  // Return true if the list contains exactly 1 element.
private:
	int myValue;
	DLLnode* myPrevious;
	DLLnode* myNext;
};

#endif

dll.cpp 

#include <iostream>
#include <cassert>
using namespace std;
#include "dll.h"

// Implementation of a circular doubly linked list.

DLLnode::DLLnode (int k) {
	myValue = k;
	myPrevious = myNext = this;	// start off with null links
					// that eventually will be replaced
}

// Return the successor of the given node.
// Precondition: this != 0.
DLLnode *DLLnode::Next () {
	assert (this != 0);
	assert (myPrevious != 0);  // consistency checks on circular list
	assert (myNext != 0);
	return myNext;
}

// Return the predecessor of the given node.
// Precondition: this != 0.
DLLnode *DLLnode::Previous () {
	assert (this != 0);
	assert (myPrevious != 0);     // consistency checks on circular list
	assert (myNext != 0);
	return myPrevious;
}

// Insert the node pointed to by ptr at the head of list
// and return a pointer to new element.
DLLnode *DLLnode::Insert (DLLnode *ptr) {
	// you fill this in
}

// Delete the first node from the list and return pointer to its
// successor, or 0 if there was only one element in the list to
// start with. Precondition: this != 0.
DLLnode *DLLnode::Delete () {
	// you fill this in
}

// Print the list.
void DLLnode::Print () {
	if (this != 0) {
	    DLLnode *temp = this;
	    do {
	        cout << temp->myValue << " ";
	        temp = temp->myNext;
	    } while (temp != this);
	}
	cout << endl;
}

// Return true if the list contains exactly 1 element.
bool DLLnode::LengthIs1 () {
	if (this == 0) {
	    return false;
	} else if (this == myPrevious) {
	    assert (myNext == myPrevious);    // consistency check on 1-elem list
	    return true;
	} else if (this == myNext) {
	    assert (false);               // failed consistency check!
	} else {
	    return false;
	}
}

List structure exercise 3 — amoeba family trees

Background

An amoeba family tree1 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
};

This definition is in the file ~cs9f/lib/amoebas.h; the member functions are in ~cs9f/lib/amoebas.cpp. A program that uses these functions is in the file ~cs9f/lib/amoebamain.cpp. (A listing of all this code appears on the following pages.)

Exercise

This exercise has five parts.

  1. Draw a diagram of the "family" constructed by the program in ~cs9f/lib/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).
  2. 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.)
  3. 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.
  4. 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.
  5. 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.
Printed 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.

amoebas.cpp 

#include "amoebas.h"

using namespace std;

Amoeba::Amoeba (string s) {		// an amoeba is born, named s
	myName = s;
	myParent = 0;
	myOlderSibling = 0;
	myOldestChild = 0;
	myYoungestChild = 0;
}

// Access functions

string Amoeba::Name () {
	return myName;
}

Amoeba* Amoeba::Parent () {
	return myParent;
}

void Amoeba::AddChild (Amoeba* newChild) {
	// make child point to parent
	newChild->myParent = this;

	// check for parent having other children
	Amoeba* otherSibling = myYoungestChild;
	if (!otherSibling) {			// the new amoeba is an only child
		myYoungestChild = newChild;	// make the parent's child
		myOldestChild = newChild;	// ptrs point to the new one
		newChild->myOlderSibling = 0;	// no older sibling
	} else {				// there are other kids; make this one the youngest
		myYoungestChild = newChild;	// no younger siblings,
		newChild->myOlderSibling = otherSibling;	// but new kid now
	}		// has older siblings.
}

amoebamain.cpp 

#include <iostream>
#include "amoebas.h"

using namespace std;

int main () {
	Amoeba* me = new Amoeba (string ("me"));
	Amoeba* parent = new Amoeba (string ("mom/dad"));
	Amoeba* grandparent = new Amoeba (string ("Amos McCoy"));
	Amoeba* brother = new Amoeba (string ("Fred"));
	Amoeba* sister = new Amoeba (string ("Wilma"));
	Amoeba* child1 = new Amoeba (string ("Mike"));
	Amoeba* child2 = new Amoeba (string ("Homer"));
	Amoeba* child3 = new Amoeba (string ("Marge"));
	Amoeba* grandchild11 = new Amoeba (string ("Bart"));
	Amoeba* grandchild12 = new Amoeba (string ("Lisa"));
	Amoeba* grandchild31 = new Amoeba (string ("Bill"));
	Amoeba* grandchild32 = new Amoeba (string ("Hilary"));

	// This will seem a bit backward, since we have an "add child"
	// instead of an "add parent".

	// First do Mike's kids.
	child1->AddChild (grandchild11);
	child1->AddChild (grandchild12);

	// Next do Marge's kids.
	child3->AddChild (grandchild31);
	child3->AddChild (grandchild32);

	// Now add Mike, Homer, and Marge to me.
	me->AddChild (child1);
	me->AddChild (child2);
	me->AddChild (child3);

	// Now add me to my parent.
	parent->AddChild (me);

	// Now add my brother and sister.
	parent->AddChild (brother);
	parent->AddChild (sister);

	// We won't need these any more now, will we?
	parent = 0;
	grandparent = 0;
	brother = 0;
	sister = 0;
	child1 = 0;
	child2 = 0;
	child3 = 0;
	grandchild11 = 0;
	grandchild12 = 0;
	grandchild31 = 0;
	grandchild32 = 0;

	// Print my name and my parent's name.
	cout << "Hi, my name is " << me->Name () << endl;
	cout << "Meet my parent " << me->Parent ()->Name () << endl;
}
1 Note: this is a computer science class, not a biology class. Any similarity between Amoeba objects and micro-organisms living or dead is purely coincidental.
TOC PREV NEXT