Name:......................................................................... Student No:...................................

The following code outlines a class to manage an ordered linked list of integers.

class ListElement {
  // A very simple class describing each node of the list
 public:
  int element;
  ListElement * next;
};

class OrdIntList {

  ListElement * head; // a pointer to the head of the list

 public:
  OrdIntList(); // constructor
  ~OrdIntList(); // destructor

  // methods that act on OrdIntList

  void DeleteList();
    // delete the entire list
  void RemoveElement(int value);
    // delete all nodes with that have 'value' as their data element
  void Add(int newdata);
    // add a new element to the list such that an ascending order is maintained
  void PrintList();
    // print the list to the screen separating elements with a single space
  bool Contains(int value);
    // check if an element is in the list
  int Count();
    // count the number of elements in the list
  int ElementCount(int value);
    // count the number of occurances of 'value' in the list
  int ReturnNth(int n);
    // return the nth integer in the list (if the list has >n elements)
  int ReturnLoc(int value);
    // return the location of the first occurance of 'value' in the list (if
    // it is in the list)
  void RemoveDuplicates();
    // Remove any duplicates from the list
  int CalcAverage();
    // find the average value of integers in the list
};

OrdIntList::OrdIntList(){
  head = NULL; // Initialise the list (mark the end of the list
               // with NULL).
}

OrdIntList::~OrdIntList(){
  DeleteList();
}

Problem 7A.1 Write C++ code to implement the OrdIntList::PrintList() method.

Problem 7A.2 Devise an algorithm for the OrdIntList::RemoveElement(int value) method. Show, using pictures and text, how your algorithm works for as many different cases as necessary. Cases include such possibilities as the list being empty, value being at the head of the list, value being in the middle of the list, value being at the end of the list, multiple occurances of value occurring in the list, multiple occurances of value occurring side by side in the list, etc. Finally, write C++ code to implement your algorithm.

When the exam is finished, attempt Problem 7.3.

Problem 7.3 Here is the outline of a class to maintain a sorted list of integers in a binary tree. Use pictures and text to describe algorithms for OrdIntTree::Contains(int value) and OrdIntTree::Add(int newdata). I want to see lots of pictures! If you are an exceptional student, you may have time to write a C++ implementation of your program during the lab. Otherwise, finish off this question before the next lab.

class BinTreeNode {
  // A very simple class describing each node of the binary tree
 public:
  int data; // data held at each node
  BinTreeNode * left; // pointer to left subtree
  BinTreeNode * right; // pointer to right subtree
};

class OrdIntTree {

  BinTreeNode * root; // a pointer to the root of the tree

 public:
  OrdIntTree(); // constructor
  ~OrdIntTree(); // destructor

  // methods that act on OrdIntTree

  void DeleteTree(BinTreeNode * current);
    // delete the entire tree
  void Add(int newdata);
    // add a new element to the tree such that children to the left of a
    // parent have lower integers and children to the right have higher integers
  bool Contains(BinTreeNode * current, int value);
    // check if 'value' is in the tree
  void PrintTree(BinTreeNode * current);
    // print the tree structure to the screen
  void PrintOrdered(BinTreeNode * current);
    // print the sorted list to the screen
};

OrdIntTree::OrdIntTree(){
  root = NULL; // Initialise the tree (set root to NULL).
}

OrdIntTree::~OrdIntTree(){
  DeleteTree(root);
}

End of Lab Sheet