Computing Concepts with C++ Essentials Laboratory Notebook
Chapter 13 - An Introduction to Data Structures


Your name:
Your email address:
Your student ID number:

Once this form has been customized for your institution, you can use this button to send your lab work. Be sure to read the instructions before starting your work.


Lab Objectives

To gain experience with


P1. Pointers

Write a program that creates a vector ringof pointers toCircle objects, that is, a vector<Circle*> ring;. Your job is to fill rings with five pointers to circles that are configured like the interlocking Olympic rings.

Initialize the vector by allocating five circles on the heap with new and calling push_back to append the resulting pointers to the vector.

Write a loop that displays all elements in rings on the graphics screen

Write a loop that deletes all heap objects whose pointers are stored in rings

4. Combine the code into a main program that prints out the Olympic rings.

Note: In this example, there was no advantage to using a vector<Circle*>. It would have been easier to use a vector<Circle>. The purpose of this exercise was to get you used to the pointer notation and dynamic allocation.

This is a worthwhile exercise since the next lab (on inheritance) uses a vector<Card*> to hold a vector of cards (such as an ID card, a phone card, and so on). In that lab, it is essential that you use a vector of pointers--a vector<Card> will not be sufficient.

P2. Linked Lists

One very natural operation that is not already a feature of the EmployeeList class in the textbook is appending an element to the tail of a list.

Provide a new member function append(Employee e) for the Employee class which will append the employee e to the end of the original list.

For example, if the list a contains Harriet, Jim and Carolyn, and e is Harry, then the command a.append(e) changes a to contain Harriet, Jim, Carolyn and Harry.

In this exercise, you must modify the pointers of the list. You may not use the list cursor.

.

Test the append function by writing a main function that prints a list and then appends Employee objects to a list. Then print out the combined list.


P3. Binary Search Trees

In this example, we turned the EmployeeTree class of the textbook into a class PointTree. The nodes of this tree store objects of type Point instead of Employee objects.

Carefully consider the PointNode class' insert() algorithm, then explain which nodes are visited to insert the point (2,4) in the following tree. Draw the resulting tree. Note that "less than" means simply that the x-coordinate of one node is less than another's.


                           (0,0)
                         /       \
                   (-5,3)         (2,1)
                  /      \       /    \     
              (-5,20)  (-4,4) (1,0)  (3,5)

The main function of the following example inserts a number of points into a tree. Add a draw function to the PointTree class (which calls a draw_node function of the PointNode class) that draws each node of the tree as follows:

{short description of image}

Give the code for the draw_node and draw functions of the PointNode and PointTree classes.


#define CCC_WIN
#include "ccc.h"

class PointNode
/* PURPOSE: Node containing Point data for use with PointTree class
 */
{
public:
        void insert_node(PointNode* new_record);
        void draw_node() const;
private:
        Point data;
        PointNode* left;
        PointNode* right;
friend class PointTree;
};

/****************************************************************************/

class PointTree
/* PURPOSE: Binary Search Tree that stores PointNode data
 */

{
public:
        PointTree();
        void insert(Point e);
        void draw() const;
private:
        PointNode* root;
};

/*..........................................................................*/

void PointNode::insert_node(PointNode* new_record)
/* PURPOSE: Recursive in-order traversal to insert a new node in a tree
 */
{  if ((*new_record).data.get_x() < data.get_x())
        {  if (left == NULL) left = new_record;
                else (*left).insert_node(new_record);
        }
   else if ((*new_record).data.get_x() > data.get_x())
   {  if (right == NULL) right = new_record;
                else (*right).insert_node(new_record);
        }
   else  // the x values are equal
   {  if ((*new_record).data.get_y() < data.get_y())
           {  if (left == NULL) left = new_record;
                else (*left).insert_node(new_record);
           }
      else 
      {  if (right == NULL) right = new_record;
                else (*right).insert_node(new_record);
        }
   }
}

/*..........................................................................*/

PointTree::PointTree()
{  root = NULL;
}

/*..........................................................................*/

void PointTree::insert(Point p)
/* PURPOSE: Insert a PointNode into the Tree
 */
{  PointNode* new_record = new PointNode;
        (*new_record).data = p;
        (*new_record).left = NULL;
        (*new_record).right = NULL;
        if (root == NULL) root = new_record;
        else (*root).insert_node(new_record);
}

/*--------------------------------------------------------------------------*/

int main()

/* PURPOSE: Store and display 10 point nodes
 */
{  PointTree t;
  
   t.insert(Point(4,0));
   t.insert(Point(2,1));
   t.insert(Point(6,1));
   t.insert(Point(1,2));
   t.insert(Point(3,2));
   t.insert(Point(5,2));
   t.insert(Point(7,2));
   t.insert(Point(0,3));
   t.draw();
   return EXIT_SUCCESS;
}


Don't forget to send your answers when you're finished.