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

Cay S. Horstmann
Geof Pawlicki


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. Using Linked Lists

In this exercise, you should use the EmployeeList class of section 6.3, which has a cursor to traverse the links of the list. Build your program based on Elist3.java.

First, insert ten employees of your choice into the list. Then print the list. Next, perform "downsizing" by removing every second employee from the list. Finally, print the remaining staff.

Use the list cursor for the element removal. There is already a print method in the Elist3.java program.

P2. Programming 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 start from the program Elist2.java and directly modify the links 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.

import ccj.*;

public class PointTreeTest extends GraphicsApplet
{  public void run()
   {  PointTree t = new PointTree();

      t.insert(new Point(4,0));
      t.insert(new Point(2,1));
      t.insert(new Point(6,1));
      t.insert(new Point(1,2));
      t.insert(new Point(3,2));
      t.insert(new Point(5,2));
      t.insert(new Point(7,2));
      t.insert(new Point(0,3));
      t.draw();
   }
}


class PointNode
{  public PointNode(Point p)
   {  data = p;
      left = null;
      right = null;
   }
   
   public void insertNode(PointNode newRecord)
   {  if (newRecord.data.getX() < data.getX())
      {  if (left == null) left = newRecord;
          else left.insertNode(newRecord);
      }
      else if (newRecord.data.getX() > data.getX())
      {  if (right == null) right = newRecord;
         else right.insertNode(newRecord);
      }
      else  /* the x values are equal */
      {  if (newRecord.data.getY() < data.getY())
         {  if (left == null) left = newRecord;
            else left.insertNode(newRecord);
         }
         else 
         {  if (right == null) right = newRecord;
            else right.insertNode(newRecord);
         }
      }
   }

   public void drawNode() 
   {  /* your work here */
   }

   private Point data;
   private PointNode left;
   private PointNode right;
}

class PointTree
{  public PointTree()
   {  root = null;
   }

   public void insert(Point p)
   {  PointNode newRecord = new PointNode(p);
      if (root == null) root = newRecord;
      else root.insertNode(newRecord);
   }
   
   public void draw() 
   {  /* your work here */
   }

   private PointNode root;
}


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