CS Labs: Lab 10

CS Labs: Lab 10

To accompany Chapter 10 of An Introduction to Object-Oriented Programming with Java by C. Thomas Wu.

An Array of Arrays

Read all of these instructions before beginning the exercises.
There are 11 checkpoints in this lab.

Copy the lab materials to your account by entering 

             cp -r /home/Classes/Cs1/Labs/Lab10 .
Everything you need for the lab exercises today is contained in this new directory. For this lab, get out some paper and writing implements.

Arrays of primitive types versus arrays of objects

Consider the following complete program: 
public class Demo {
    public static void main (String [] args) {

       int [] a;
       a = new int[4];

       a[0] = 3;
       for (int i = 1; i < 4; i++) 
           a[i] = a[0];
       a[1] = 6;
       for (int i = 0; i < 4; i++)
          System.out.println(a[i]);
    }
}
Using paper and pencil, trace out what what happens. What will the output be?

1 Show us your trace and the anticipated output.

Change directory into Lab10 and go into the subdirectory MyArray. Edit the class Demo that contains the above code. Compile this program and see if your prediction agrees with the results.

Now, edit the Demo class and replace the lines 

       int[] a;
       a = new int[4];
with 
       StringBuffer[] a;
       a = new StringBuffer[4];
and also replace 
       a[0] = 3;
with 
       a[0] = new StringBuffer("Sasparilla");
Finally, replace 
       a[1] = 6;
with 
       a[1].setCharAt(0, 'J');
Predict what the output should be now. Draw a state-of-memory diagram to help you visualize what's happening. Then, run the program and see what you get.

2 Explain why the program behaves differently than the original program.

Our Own List class

Go into subdirectory DoReMi and edit the List class. Examine the implementation of this class.

Notice that there are two versions of the List constructor. The main() method creates a List object using the constructor that takes no arguments and calls the printList() method on this object. Compile and run this program and observe the results.

Now, change your main() method to construct a List object using the constructor that takes a size. Use a size of 3 as the argument, but do not change anything else. Compile and run this program and observe the results.

3 Explain why the outputs of the printList() method differ in these two examples.

Add a line to the end of your second List() constructor that asks the user to input strings into your data array by calling the readList() method. Do not change main(). When you run your program, you should be prompted for three input strings, after which the strings will be displayed on your terminal window.

Next, modify the printList() method so that each string in the data array is printed 4 words per line, with each word on a line separated from the previous word by one space. So, for example, if the following list of 14 words is used to populate the data array 

early to bed and early to rise makes a person healthy wealthy and wise
The output should appear as 
early to bed and
early to rise makes
a person healthy wealthy
and wise
You will only need to make minor changes to the printList()method. Hint: The modulus operator may be helpful here.

Having made your changes to printList(), modify your main() method to construct a List object using the default constructor. Change the initial strings in the data array from their current values of "Do", "Re", "Mi" ... to "early", "to", "bed", ....

4 Show us your modifications and your running program.

A List Class with a Problem Method

Go into the ProblemList directory and edit the List class. The main() method creates a List object using the default constructor and calls the reverseList() method on the object. The reverseList() method is intended to do an in-place reversal of the list. (For reverseList()to work in-place means that it doesn't create any new objects; it just shuffles around the positions of the existing objects in the array.) For example, if the data list has the following five elements 
position   0    1    2    3    4
    data  "Do" "Re" "Mi" "Fa" "So"
first data[0] and data[4] should be exchanged to give 
position   0    1    2    3    4
    data  "So" "Re" "Mi" "Fa" "Do"
then data[1] and data[3] should be exchanged to give 
position   0    1    2    3    4
    data  "So" "Fa" "Mi" "Re" "Do"
and data[2] (because it is in the middle) should be left alone. This in-place reversal should also work for an array with an even number of elements, since for such an array there simply isn't any "middle" element.

Compile and run your program. Observe that something is wrong. Trace your program's behavior by carefully showing what happens in each iteration of the loop in reverseList(). Using your trace, find and fix the problem. Your fix should only modify reverseList() and should still do an in-place reversal. Do not modify any other parts of your program.

5 When you are ready, show us your fix and your running program.

Passing Arrays to Methods

Go into subdirectory PassArray and edit the Demo class. The main() method creates and assigns values to a String array called stuff and prints out its values. After this, a static method empty() is called which returns a version of stuff with all the String objects in the array replaced with "???". This array becomes the value of a second array in the main() method, moreStuff. Both stuff and moreStuff are printed again. Notice that stuff has also been "emptied".

6 Draw a state of memory diagram to explain what is happening. Show us your diagram and explain.

Close project PassArray.

Deleting From an Array

Go into subdirectory PersonSearch. This is the code that is discussed in Chapter 10, section 2. Compile both classes and run the program. You will be asked to enter the name, gender, and age of five people. Keep track of the names you enter and their positions in the array.

The program searches the list and reports on the youngest and oldest people in the list.

Next, you will be asked to enter a "Name to search:". To answer this question, enter either a new name, or one that you entered previously. The program reports the position in the list if found or that the name was not found. Run your program at least twice: once with a name to search that you know is in the array (and make sure the position the program reports is correct) and once with a name that you know is not in the array.

Change your program so that instead of searching for a name, you are asked to enter a "Name to delete:" and to delete the entry from the array.

First change the prompt to delete instead of search. Then add a section of code to Demo.java (after the code that searches for a particular person) that deletes that person from the array (only if the person was found). The deletion should be performed so that all the Persons following the deleted entry are moved to the previous positions in the array. For example, suppose the person array looks like the BEFORE picture below. After removing person B, the array should look like the AFTER picture.

In addition, modify Demo.java to display the names of persons in the array after the deletion has been performed.

Hint #1: You'll want to create a new array of the proper size to hold the reduced list.

Hint #2: There are (possibly!) two groups of references to be copied to the new array -- the group ahead of the item to be deleted, and the group following the item to be deleted. One simple approach is to treat the copying of each group as a separate task.

Hint #3: Don't forget to assign your person array to the new array after you have finished copying the correct elements.

7 Show us your program when you have made the revisions described above.

Keeping Track of an Array Position from a Search

Now modify the section of code in Demo that finds the oldest and youngest person so that it finds the positions in the array of the oldest and youngest. Since you know their positions, you can modify your code to print information about the youngest and oldest in the following manner (for example): 

Oldest  : Joe is 66 years old and is at position 3 in the list.
Youngest: Fran is 22 years old and is at position 1 in the list.
Strip out the part of the code that searches for a name to delete.

8 Show us your program when you have made these revisions.

Two Dimensional Arrays

Go into the subdirectory GraphPaper and edit the GraphPaper class. There is a main() method that constructs a GraphPaper instance.

Note that the instance variable graphPoints is an array of Points. Conceptually, the result of this is as follows, but the points are not actually 'displayed':


The array shown above contains 5 rows and columns of Points.

Complete the code in the paint() method to draw lines connecting the points, in order to produce a grid as seen in the following diagram:


Note that you need to draw only 2 * (NUM_SQUARES + 1) lines, with each line connecting the two points on opposite sides of the grid.

We suggest using the following procedure. Use two sequential for loops, one to go through the rows and draw the horizontal lines between each pair of points


and one to go through the columns and draw the vertical lines between each pair of points.


The method for drawing a line is a method on the Graphics object that is a parameter to the paint() method. To draw a line from from Point p (with coordinates (p.x, p.y)) to Point q (with coordinates (q.x, q.y)) use

g.drawLine(p.x, p.y, q.x, q.y).
Instead of 4 squares per row (as shown above), the graph paper will have 10 squares per row.

9 Run the program and show us how you successfully drew the lines.

Lists: the Bottomless Pit

Go into the subdirectory LotsOfPoints and edit the LotsOfPoints class. Examine the LotsOfPoints constructor. This program creates a random number of Points all with random coordinates, and stores them in a List that is implemented by constructing an ArrayList object.

Compile and run this program two or three times to see what it does.

Make the following change and addition:

  1. Instead of using a for loop in the paint() method to go through the list of points and draw each one, change the code to use an Iterator to go throught the list.

  2. Add code to the paint() method to draw the "average point". The average point has an x-coordinate that is the average of all the x-coordinates of all the points. Similarly, the y-coordinate of the average point is the average of all the y-coordinates for all the points. Use two int variables xSum and ySum to hold your cumulative sums. Notice that there is code that you will need to uncomment that will draw the average Point in a larger size and a different color once you have calculated its center.

10 Run the modified program for us and show your changes/additions to the code.

After the Lab

11 Show us that you have logged out, cleaned up, and pushed in your chairs for this last checkpoint.
Susan Haller and Timothy Fossum, University of Wisconsin-Parkside