CSci 2101 Data Structures: Problem set 2

Problem 1 (7 points)

Problem 2 (10 points)

• An array of integers to keep track of how many times each of the sums has occurred (how many elements do you need in this array?)
• An array of doubles which will store the percent of the times each value of the sum has occurred (you only need to compute these percentages at the end of the program, after the loop).

• Put the line import java.util.*; as the very first line of your program file.
• In the beginning of main declare and initialize the random number generator:
  Random r = new Random();
  You only need to do this once in your program.
• In order to get a random integer between 0 and n (including 0, not including n) you need to call the method nextInt on r:
  k = r.nextInt(n);
  (where k is an integer variable to store the result). You need to figure out what to do to get the numbers between 1 and 6.

Problem 3 (15 points)

// Queue implementation with arrays

public class CharQueue {
	private char [] items = new char [100];
	private int first = -1; // in the book this is called 'head'
	private int last = 0;   // in the book this is called 'tail'
	private int length = 0;
	
	// a constructor, need for every class
	public CharQueue() {
		// do nothing	
	}

	// add the code for isEmpty

	// add the code for dequeue

	// add the code for enqueue
	
}

Use the file ShowQueue.java to test the queue. Modify the testing file as needed.

Problem 4 (10 points)

Important: You have to create copies of the nodes, not share the nodes between the two lists. To make sure that nodes are not shared, change one of the lists, and print out both lists to make sure that the second one hasn't changed. This way of copying (where all the elements that a data structure consists of are copied and not shared) is called a deep copy, as opposed to a shallow copy (where the elements are shared).

Problem 5 (5 points)

public class WeirdLists {
    public static void main(String [] args) {
	// creating nodes
	Node one = new Node(1);
	Node two = new Node(2);
	Node three = new Node(3);
	Node four = new Node(4);

	LinkedList listOne = new LinkedList();
	LinkedList listTwo = new LinkedList();

	// adding elements to list 1
	listOne.addFront(one);
	listOne.addFront(two);

	// add one element to list 2 
	listTwo.addFront(three);	

	// changing node one
	one.setNext(three);

	// changing something in the second list
	listTwo.getFirst().setNext(four);
	
	// what will be printed?

	System.out.println("Printing listOne:");
	Node n = listOne.getFirst();
	while (n != null) {
	    System.out.println(n.getData());
	    n = n.getNext();
	}

	System.out.println("Printing listTwo:");
	n = listTwo.getFirst();
	while (n != null) {
	    System.out.println(n.getData());
	    n = n.getNext();
	}
	
    }
}

Problem 6 (15 points)

The first class is DoubleNode which is similar to the class Node, but has a reference to the previous element, as well as the to next one. The DoubleNode class has the following methods:

1. a constructor with one integer parameter to set the data. The references to the next and the previous DoubleNodes are set to null.
2. public int getData()
3. public void setNext(DoubleNode dn)
4. public DoubleNode getNext()
5. public void setPrev(DoubleNode dn)
6. public DoubleNode getPrev()

1. a constructor with no parameters,
2. public boolean isEmpty()
3. public DoubleNode getFirst() returns the reference to the first DoubleNode in the list. If there is no such node, returns null. The list doesn't change.
4. public DoubleNode getLast() returns the reference to the last DoubleNode in the list. If there is no such node, returns null. The list doesn't change.
5. public void addFront(DoubleNode dn) Adds a new node to the front of the list.
6. public void addBack(DoubleNode dn) Adds a new node to the back of the list.
7. public void removeFront() Removes the first element from the list. Doesn't return anything.
8. public void removeBack() Removes the last element from the list. Doesn't return anything.

• Starting from the front going towards the end,
• Starting at the end (using getLast() method) and going to the front (the elements would be printed in reverse order)