JAVA:
An Introduction to Problem Solving & Programming, 7th
Ed. By Walter Savitch.
ISBN 0133862119©
2015 Pearson Education, Inc., Upper Saddle River, NJ. All Rights Reserved
Listing 11.1 |
public class RecursiveCountdown
{
public static void main(String[] args)
{
countDown(3);
}
public static void countDown(int num)
{
if (num <= 0)
{
System.out.println();
}
else
{
System.out.print(num);
countDown(num - 1);
}
}
}
|
Listing 11.2 |
import java.util.Scanner;
public class RecursionDemo
{
public static void main (String [] args)
{
System.out.println ("Enter an integer:");
Scanner keyboard = new Scanner (System.in);
int number = keyboard.nextInt ();
System.out.println ("The digits in that number are:");
displayAsWords (number);
System.out.println ();
System.out.println ("If you add ten to that number, ");
System.out.println ("the digits in the new number are:");
number = number + 10;
displayAsWords (number);
System.out.println ();
}
/**
Precondition: number >= 0
Displays the digits in number as words.
*/
public static void displayAsWords (int number)
{
if (number < 10)
System.out.print (getWordFromDigit (number) + " ");
else //number has two or more digits
{
displayAsWords (number / 10);
System.out.print (getWordFromDigit (number % 10) + " ");
}
}
// Precondition: 0 <= digit <= 9
// Returns the word for the argument digit.
private static String getWordFromDigit (int digit)
{
String result = null;
switch (digit)
{
case 0:
result = "zero";
break;
case 1:
result = "one";
break;
case 2:
result = "two";
break;
case 3:
result = "three";
break;
case 4:
result = "four";
break;
case 5:
result = "five";
break;
case 6:
result = "six";
break;
case 7:
result = "seven";
break;
case 8:
result = "eight";
break;
case 9:
result = "nine";
break;
default:
System.out.println ("Fatal Error.");
System.exit (0);
break;
}
return result;
}
}
|
Listing 11.3 |
import java.util.Scanner;
public class IterativeDemo
{
public static void main (String [] args)
< The rest of main is the same as in Listing 11.1 . >
/**
Precondition: number >= 0
Displays the digits in number as words.
*/
public static void displayAsWords (int number)
{
int divisor = getPowerOfTen (number);
int next = number;
while (divisor >= 10)
{
System.out.print (getWordFromDigit (next / divisor) +
" ");
next = next % divisor;
divisor = divisor / 10;
}
System.out.print (getWordFromDigit (next / divisor) + " ");
}
// Precondition: n >= 0.
// Returns 10 raised to the power n.
private static int getPowerOfTen (int n)
{
int result = 1;
while (n >= 10)
{
result = result * 10;
n = n / 10;
}
return result;
}
private static String getWordFromDigit (int digit)
// The rest of getWordFromDigit is the same as in Listing 11.1
}
|
Listing 11.4 |
import java.util.Scanner;
public class RecursionDemo2
{
public static void main (String [] args)
{
System.out.println ("Enter a nonnegative number:");
Scanner keyboard = new Scanner (System.in);
int number = keyboard.nextInt ();
System.out.println (number + " contains " +
getNumberOfZeros (number) + " zeros.");
}
/**
Precondition: n >= 0
Returns the number of zero digits in n.
*/
public static int getNumberOfZeros (int n)
{
int result;
if (n == 0)
result = 1;
else if (n < 10)
result = 0; //n has one digit that is not 0
else if (n % 10 == 0)
result = getNumberOfZeros (n / 10) + 1;
else //n % 10 != 0
result = getNumberOfZeros (n / 10);
return result;
}
}
|
Listing 11.5 |
import java.util.Scanner;
public class CountDown
{
private int count;
public static void main (String [] args)
{
CountDown countDowner = new CountDown ();
countDowner.getCount ();
countDowner.showCountDown ();
}
public void getCount ()
{
System.out.println ("Enter a positive integer:");
Scanner keyboard = new Scanner (System.in);
count = keyboard.nextInt ();
if (count <= 0)
{
System.out.println ("Input must be positive.");
System.out.println ("Try again.");
getCount (); //start over
}
}
public void showCountDown ()
{
System.out.println ("Counting down:");
for (int left = count ; left >= 0 ; left--)
System.out.print (left + ", ");
System.out.println ("Blast Off!");
}
}
|
Listing 11.6 |
/**
Class for searching an already sorted array of integers.
*/
public class ArraySearcher
{
private int [] a;
/**
Precondition: theArray is full and is sorted
from lowest to highest.
*/
public ArraySearcher (int [] theArray)
{
a = theArray; //a is now another name for theArray.
}
/**
If target is in the array, returns the index of an occurrence
of target. Returns -1 if target is not in the array.
*/
public int find (int target)
{
return binarySearch (target, 0, a.length - 1);
}
//Uses binary search to search for target in a[first] through
//a[last] inclusive. Returns the index of target if target
//is found. Returns -1 if target is not found.
private int binarySearch (int target, int first, int last)
{
int result;
if (first > last)
result = -1;
else
{
int mid = (first + last) / 2;
if (target == a [mid])
result = mid;
else if (target < a [mid])
result = binarySearch (target, first, mid - 1);
else //(target > a[mid])
result = binarySearch (target, mid + 1, last);
}
return result;
}
}
|
Listing 11.7 |
import java.util.Scanner;
public class ArraySearcherDemo
{
public static void main (String [] args)
{
int [] anArray = new int [10];
Scanner keyboard = new Scanner (System.in);
System.out.println ("Enter 10 integers in increasing order,");
System.out.println ("one per line.");
for (int i = 0 ; i < 10 ; i++)
anArray [i] = keyboard.nextInt ();
System.out.println ();
for (int i = 0 ; i < 10 ; i++)
System.out.print ("a[" + i + "]=" + anArray [i] + " ");
System.out.println ();
System.out.println ();
ArraySearcher finder = new ArraySearcher (anArray);
String ans;
do
{
System.out.println ("Enter a value to search for:");
int target = keyboard.nextInt ();
int result = finder.find (target);
if (result < 0)
System.out.println (target +
" is not in the array.");
else
System.out.println (target + " is at index " +
result);
System.out.println ("Again?");
ans = keyboard.next ();
}
while (ans.equalsIgnoreCase ("yes"));
System.out.println (
"May you find what you're searching for.");
}
}
|
Listing 11.8 |
/**
Class for sorting an array of integers from smallest to largest
using the merge sort algorithm.
*/
public class MergeSort
{
/**
Precondition: Every indexed variable of the array a has a value.
Postcondition: a[0] <= a[1] <= ... <= a[a.length - 1].
*/
public static void sort (int [] a)
{
if (a.length >= 2)
{
int halfLength = a.length / 2;
int [] firstHalf = new int [halfLength];
int [] lastHalf = new int [a.length - halfLength];
divide (a, firstHalf, lastHalf);
sort (firstHalf);
sort (lastHalf);
merge (a, firstHalf, lastHalf);
}
//else do nothing. a.length == 1, so a is sorted.
}
//Precondition: a.length = firstHalf.length + lastHalf.length.
//Postcondition: All the elements of a are divided
//between the arrays firstHalf and lastHalf.
private static void divide (int [] a, int [] firstHalf,
int [] lastHalf)
{
for (int i = 0 ; i < firstHalf.length ; i++)
firstHalf [i] = a [i];
for (int i = 0 ; i < lastHalf.length ; i++)
lastHalf [i] = a [firstHalf.length + i];
}
//Precondition: Arrays firstHalf and lastHalf are sorted from
//smallest to largest; a.length = firstHalf.length +
//lastHalf.length.
//Postcondition: Array a contains all the values from firstHalf
//and lastHalf and is sorted from smallest to largest.
private static void merge (int [] a, int [] firstHalf,
int [] lastHalf)
{
int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
while ((firstHalfIndex < firstHalf.length) &&
(lastHalfIndex < lastHalf.length))
{
if (firstHalf [firstHalfIndex] < lastHalf [lastHalfIndex])
{
a [aIndex] = firstHalf [firstHalfIndex];
firstHalfIndex++;
}
else
{
a [aIndex] = lastHalf [lastHalfIndex];
lastHalfIndex++;
}
aIndex++;
}
//At least one of firstHalf and lastHalf has been
//completely copied to a.
//Copy rest of firstHalf, if any.
while (firstHalfIndex < firstHalf.length)
{
a [aIndex] = firstHalf [firstHalfIndex];
aIndex++;
firstHalfIndex++;
}
//Copy rest of lastHalf, if any.
while (lastHalfIndex < lastHalf.length)
{
a [aIndex] = lastHalf [lastHalfIndex];
aIndex++;
lastHalfIndex++;
}
}
}
|
Listing 11.9 |
public class MergeSortDemo
{
public static void main (String [] args)
{
int [] anArray = {7, 5, 11, 2, 16, 4, 18, 14, 12, 30};
System.out.println ("Array values before sorting:");
for (int i = 0 ; i < anArray.length ; i++)
System.out.print (anArray [i] + " ");
System.out.println ();
MergeSort.sort (anArray);
System.out.println ("Array values after sorting:");
for (int i = 0 ; i < anArray.length ; i++)
System.out.print (anArray [i] + " ");
System.out.println ();
}
}
|
Listing 12.1 |
import java.util.ArrayList;
import java.util.Scanner;
public class ArrayListDemo
{
public static void main (String [] args)
{
ArrayList<String> toDoList = new ArrayList<String>();
System.out.println (
"Enter items for the list, when prompted.");
boolean done = false;
Scanner keyboard = new Scanner (System.in);
while (!done)
{
System.out.println ("Type an entry:");
String entry = keyboard.nextLine ();
toDoList.add (entry);
System.out.print ("More items for the list? ");
String ans = keyboard.nextLine ();
if (!ans.equalsIgnoreCase ("yes"))
done = true;
}
System.out.println ("The list contains:");
int listSize = toDoList.size ();
for (int position = 0 ; position < listSize ; position++)
System.out.println (toDoList.get (position));
}
}
|
Listing 12.2 |
import java.util.HashSet;
public class HashSetDemo
{
public static void main(String[] args)
{
HashSet<Integer> intSet = new HashSet<Integer>();
intSet.add(2);
intSet.add(7);
intSet.add(7); // Ignored since 7 is already in the set
intSet.add(3);
printSet(intSet);
intSet.remove(3);
printSet(intSet);
System.out.println("Set contains 2: " +
intSet.contains(2));
System.out.println("Set contains 3: " +
intSet.contains(3));
}
public static void printSet(HashSet<Integer> intSet)
{
System.out.println("The set contains:");
for (Object obj : intSet.toArray())
{
Integer num = (Integer) obj;
System.out.println(num.intValue());
}
}
}
|
Listing 12.3 |
import java.util.HashMap;
public class HashMapDemo
{
public static void main(String[] args)
{
HashMap<String, Integer> mountains = new HashMap<String, Integer>();
mountains.put("Everest",29029);
mountains.put("K2",28251);
mountains.put("Kangchenjunga",28169);
mountains.put("Denali",20335);
printMap(mountains);
System.out.println("Denali in the map: " +
mountains.containsKey("Denali"));
System.out.println();
System.out.println("Changing height of Denali.");
mountains.put("Denali", 20320); // Overwrites old value for Denali
printMap(mountains);
System.out.println("Removing Kangchenjunga.");
mountains.remove("Kangchenjunga");
printMap(mountains);
}
public static void printMap(HashMap<String, Integer> map)
{
System.out.println("Map contains:");
for (String keyMountainName : map.keySet())
{
Integer height = map.get(keyMountainName);
System.out.println(keyMountainName +
" --> " + height.intValue() + " feet.");
}
System.out.println();
}
}
|
Listing 12.4 |
public class ListNode
{
private String data;
private ListNode link;
public ListNode ()
{
link = null;
data = null;
}
public ListNode (String newData, ListNode linkValue)
{
data = newData;
link = linkValue;
}
public void setData (String newData)
{
data = newData;
}
public String getData ()
{
return data;
}
public void setLink (ListNode newLink)
{
link = newLink;
}
public ListNode getLink ()
{
return link;
}
}
|
Listing 12.5 |
public class StringLinkedList
{
private ListNode head;
public StringLinkedList ()
{
head = null;
}
/**
Displays the data on the list.
*/
public void showList ()
{
ListNode position = head;
while (position != null)
{
System.out.println (position.getData ());
position = position.getLink ();
}
}
/**
Returns the number of nodes on the list.
*/
public int length ()
{
int count = 0;
ListNode position = head;
while (position != null)
{
count++;
position = position.getLink ();
}
return count;
}
/**
Adds a node containing the data addData at the
start of the list.
*/
public void addANodeToStart (String addData)
{
head = new ListNode (addData, head);
}
/**
Deletes the first node on the list.
*/
public void deleteHeadNode ()
{
if (head != null)
head = head.getLink ();
else
{
System.out.println ("Deleting from an empty list.");
System.exit (0);
}
}
/**
Sees whether target is on the list.
*/
public boolean onList (String target)
{
return find (target) != null;
}
// Returns a reference to the first node containing the
// target data. If target is not on the list, returns null.
private ListNode find (String target)
{
boolean found = false;
ListNode position = head;
while ((position != null) && !found)
{
String dataAtPosition = position.getData ();
if (dataAtPosition.equals (target))
found = true;
else
position = position.getLink ();
}
return position;
}
}
|
Listing 12.6 |
public class StringLinkedListDemo
{
public static void main (String [] args)
{
StringLinkedList list = new StringLinkedList ();
list.addANodeToStart ("One");
list.addANodeToStart ("Two");
list.addANodeToStart ("Three");
System.out.println ("List has " + list.length () +
" entries.");
list.showList ();
if (list.onList ("Three"))
System.out.println ("Three is on list.");
else
System.out.println ("Three is NOT on list.");
list.deleteHeadNode ();
if (list.onList ("Three"))
System.out.println ("Three is on list.");
else
System.out.println ("Three is NOT on list.");
list.deleteHeadNode ();
list.deleteHeadNode ();
System.out.println ("Start of list:");
list.showList ();
System.out.println ("End of list.");
}
}
|
Listing 12.7 |
public class StringLinkedListSelfContained
{
private ListNode head;
public StringLinkedListSelfContained ()
{
head = null;
}
/**
Displays the data on the list.
*/
public void showList ()
{
ListNode position = head;
while (position != null)
{
System.out.println (position.data);
position = position.link;
}
}
/**
Returns the number of nodes on the list.
*/
public int length ()
{
int count = 0;
ListNode position = head;
while (position != null)
{
count++;
position = position.link;
}
return count;
}
/**
Adds a node containing the data addData at the
start of the list.
*/
public void addANodeToStart (String addData)
{
head = new ListNode (addData, head);
}
/**
Deletes the first node on the list.
*/
public void deleteHeadNode ()
{
if (head != null)
head = head.link;
else
{
System.out.println ("Deleting from an empty list.");
System.exit (0);
}
}
/**
Sees whether target is on the list.
*/
public boolean onList (String target)
{
return find (target) != null;
}
// Returns a reference to the first node containing the
// target data. If target is not on the list, returns null.
private ListNode find (String target)
{
boolean found = false;
ListNode position = head;
while ((position != null) && !found)
{
String dataAtPosition = position.data;
if (dataAtPosition.equals (target))
found = true;
else
position = position.link;
}
return position;
}
private class ListNode
{
private String data;
private ListNode link;
public ListNode ()
{
link = null;
data = null;
}
public ListNode (String newData, ListNode linkValue)
{
data = newData;
link = linkValue;
}
}
}
|
Listing 12.8 |
/**
Returns an array of the elements on the list.
*/
public String [] toArray ()
{
String [] anArray = new String [length ()];
ListNode position = head;
int i = 0;
while (position != null)
{
anArray [i] = position.data;
i++;
position = position.link;
}
return anArray;
}
|
Listing 12.9 |
/**
Linked list with an iterator. One node is the "current node."
Initially, the current node is the first node. It can be changed
to the next node until the iteration has moved beyond the end
of the list.
*/
public class StringLinkedListWithIterator
{
private ListNode head;
private ListNode current;
private ListNode previous;
public StringLinkedListWithIterator ()
{
head = null;
current = null;
previous = null;
}
public void addANodeToStart (String addData)
{
head = new ListNode (addData, head);
if ((current == head.link) && (current != null))
//if current is at old start node
previous = head;
}
/**
Sets iterator to beginning of list.
*/
public void resetIteration ()
{
current = head;
previous = null;
}
/**
Returns true if iteration is not finished.
*/
public boolean moreToIterate ()
{
return current != null;
}
/**
Advances iterator to next node.
*/
public void goToNext ()
{
if (current != null)
{
previous = current;
current = current.link;
}
else if (head != null)
{
System.out.println (
"Iterated too many times or uninitialized iteration.");
System.exit (0);
}
else
{
System.out.println ("Iterating with an empty list.");
System.exit (0);
}
}
/**
Returns the data at the current node.
*/
public String getDataAtCurrent ()
{
String result = null;
if (current != null)
result = current.data;
else
{
System.out.println (
"Getting data when current is not at any node.");
System.exit (0);
}
return result;
}
/**
Replaces the data at the current node.
*/
public void setDataAtCurrent (String newData)
{
if (current != null)
{
current.data = newData;
}
else
{
System.out.println (
"Setting data when current is not at any node.");
System.exit (0);
}
}
/**
Inserts a new node containing newData after the current node.
The current node is the same after invocation as it is before.
Precondition: List is not empty; current node is not
beyond the entire list.
*/
public void insertNodeAfterCurrent (String newData)
{
ListNode newNode = new ListNode ();
newNode.data = newData;
if (current != null)
{
newNode.link = current.link;
current.link = newNode;
}
else if (head != null)
{
System.out.println (
"Inserting when iterator is past all " +
"nodes or is not initialized.");
System.exit (0);
}
else
{
System.out.println (
"Using insertNodeAfterCurrent with empty list.");
System.exit (0);
}
}
/**
Deletes the current node. After the invocation,
the current node is either the node after the
deleted node or null if there is no next node.
*/
public void deleteCurrentNode ()
{
if ((current != null) && (previous != null))
{
previous.link = current.link;
current = current.link;
}
else if ((current != null) && (previous == null))
{ //At head node
head = current.link;
current = head;
}
else //current == null
{
System.out.println (
"Deleting with uninitialized current or an empty list.");
System.exit (0);
}
}
// The methods length, onList, find, and showList, as well as the private inner class
// ListNode are the same as in Listing 12.7.
// The method toArray is the same as in Listing 12.8.
}
|
Listing 12.10 |
public class LinkedListException extends Exception
{
public LinkedListException ()
{
super ("Linked List Exception");
}
public LinkedListException (String message)
{
super (message);
}
}
|
Listing 12.11 |
public class Sample<T> { private T data; public void setData (T newValue) { data = newValue; } public T getData () { return data; } } |
Listing 12.12 |
import java.util.ArrayList; public class LinkedList <E> { private ListNode head; public LinkedList () { head = null; } //The methods showList, length, and deleteHeadNode are the same //as in Listing 12.5 public void addANodeToStart (E addData) { head = new ListNode (addData, head); } public boolean onList (E target) { return find (target) != null; } private ListNode find (E target) { boolean found = false; ListNode position = head; while ((position != null) && !found) { E dataAtPosition = position.data; if (dataAtPosition.equals (target)) found = true; else position = position.link; } return position; } public ArrayList<E> toArrayList () { ArrayList<E> list = new ArrayList<E> (length ()); ListNode position = head; while (position != null) { list.add (position.data); position = position.link; } return list; } private class ListNode { private E data; private ListNode link; public ListNode () { link = null; data = null; } public ListNode (E newData, ListNode linkValue) { data = newData; link = linkValue; } } } |
Listing 12.13 |
import java.util.ArrayList;
public class LinkedListDemo
{
public static void main (String [] args)
{
LinkedList<String> stringList = new LinkedList<String>();
stringList.addANodeToStart ("Hello");
stringList.addANodeToStart ("Good-bye");
stringList.showList ();
LinkedList<Integer> numberList =
new LinkedList<Integer>();
for (int i = 0 ; i < 10 ; i++)
numberList.addANodeToStart (i);
numberList.deleteHeadNode ();
ArrayList < Integer > list = numberList.toArrayList ();
int listSize = list.size ();
for (int position = 0 ; position < listSize ; position++)
System.out.print (list.get (position) + " ");
System.out.println ();
}
}
|