Java Programming: From Problem Analysis to Program Design Instructor’s Manual - Chapter 10
Chapter 10
Applications of Arrays and Strings
At a Glance
Instructor’s Manual Table of Contents
¨ Chapter Overview
¨ Chapter Objectives
¨ Teacher Notes
¨ Quick Quizzes
¨ Discussion Questions
¨ Projects to Assign
¨ Key Terms
Chapter Overview
In this chapter, students continue the discussion of arrays and learn how to use them effectively for processing lists. This chapter also discusses how to use the class Vector to overcome some limitations of arrays, and revisits the class String to show you additional methods for manipulating strings.
Chapter Objectives
In this chapter, students will:
· Learn how to implement the sequential search algorithm
· Explore how to sort an array using the selection sort algorithm
· Learn how to implement the binary search algorithm
· Become aware of the class Vector
· Learn more about manipulating strings using the class String
Teacher Notes
List Processing
A list is a set of values of the same type. It is convenient to store a list in an array, particularly a one-dimensional array. Because a list’s size can increase and decrease, the array you use to store the list should be declared to be the maximum size of the list.
Searching a list for a given item is one of the most common operations performed on a list. To search the list, you need:
1. The list, that is, the array containing the list.
2. The length of the list.
3. The item for which you are searching.
After the search is completed:
4. If the item is found, then report “success” and the location where the item was found.
5. If the item is not found, then report “failure.”
The following value-returning method will satisfy requirements (4) and (5): If the search item is found in the list, the method returns the location in the list where the search item is found; otherwise it returns -1, indicating an unsuccessful search. The parameters for this method are:
a. The array, list, containing the list
b. The length of the list, listLength (Note that listLength <= the size of the array.)
c. The item, searchItem, for which you are searching
This search algorithm is called the sequential search or linear search; sequentially search the array starting from the first array component. The item is compare with the elements in the array (the list) and the search continues until either the item is found or no more data is left in the list to compare with the item.
If the search item is the second item in the list, the sequential search makes two key comparisons (item comparisons) to determine whether the search item is in the list. Similarly, if the search item is the 900th item in the list, the sequential search makes 900 key comparisons to determine whether the search item is in the list. If the search item is not in the list, the sequential search makes 1000 key comparisons. If the searchItem for which we are searching is always at the bottom of the list, it will take many comparisons to find the searchItem. Also, if the searchItem for which we are searching is not in the list, then we will compare the searchItem with every element in the list. A sequential search is therefore not efficient for large lists. In fact, it can be proved that, on average, the number of key comparisons made by a sequential search is equal to half the size of the list. This search algorithm does not assume that the list is sorted. If the list is sorted, then you can somewhat improve the search algorithm.
In a selection sort, a list is sorted by selecting an element in the list and moving it to its proper position. This algorithm finds the location of the smallest element in the unsorted portion of the list and moves it to the top of the unsorted portion of the list. The first time we locate the smallest item in the entire list, the second time we locate the smallest item in the list starting from the second element in the list, and so on.
The general method to sort a list is:
void selectionSort(int[ ] list, int length)
{
int index, smallestIndex, minIndex, temp;
for(index = 0; index < length – 1; index++;){//control the wall, index after the wall
/* find the location, smallestIndex, of the smallest element in list[index]…list[length] */
smallestIndex = index; //assume first element is smallest
for(minIndex = index + 1; minIndex < length; minIndex++)//inner loop, control the remainder to //find the smallest
if(list[minIndex] < list[smallestIndex])
smallestIndex = minIndex;// index hold the smallest
/* Swap the smallest element, list[smallestIndex] with list[index] */
temp = list[smallestIndex];//the smallest value into temp
list[smallestIndex] = list[index];//location of smallest hold the previous value
list[index] = temp;
}
}
The general form of the method seqOrderedSearch to perform a sequential search on a sorted list:
int seqOrderedSearch(int[] list, int listLength, int searchItem)
{
int loc;
Boolean found = false;
for(loc = 0; loc < listLength; loc++)
if(list[loc] >= searchItem)
{
found = true;
break;
}
if(found)
if(list[loc] == searchItem)
return loc;
else
return -1;
else
return -1;
}
A binary search is much faster than a sequential search, but a binary search can only be performed on a sorted list. Binary search uses the divide and conquer technique to search the list. First the search item is compared with the middle element of the list. If the search item is less than the middle element of the list, the search is restricted to the first half of the list; otherwise the second half of the list is searched.
The following Java method implements the binary search algorithm. If the search item is found in the list, its location is returned. If the search item is not in the list, -1 is returned.
int binarySearch(int[] list, int listLength, int searchItem)
{
int first = 0;
int last = listLength -1;
int mid;
Boolean found = false;
while(first <= last & !found)
{
mid = (first +last) / 2;
if(list[mid] == searchItem)
found = true;
else
if(list[mid] > searchItem)
last = mid - 1;
else
first = mid +1;
}
if(found)
return mid;
else
return – 1;
} //end binarySearch
Note that in the binary search algorithm, each time through the loop two key (item) comparisons are made, except in the successful case the last time through the loop, when only one item key comparison is made.
Every iteration of the while loop cuts the size of the search list by half. In general, if L is a sorted list of size n, to determine whether an element is in L, the binary search makes at most 2 * log2n + 2 key (item) comparisons.
Quick Quiz
1. True or False: There is more than one way to search for an element in an array.
Answer: False
2. On average, the number of key comparisons it takes to find an element using sequential search is equal to half the number of elements
Answer: vectors
3. The first comparison in binary search is the search item with the ____ element.
Answer: middle
4. True or False: There are ____ key comparisons for every iteration in a binary search except the last one.
Answer: two
5. Binary search can only be performed on ____ lists.
Answer: sorted
The class Vector
In addition to arrays, Java provides the class Vector to implement a list. Unlike an array, the size of a Vector object can grow and shrink during program execution. Therefore, you do not need to worry about the number of data elements. The class Vector is contained in the package java.util. Some of the members of the class Vector are:
protected int elementCount;
protected Object elementData; //Array of references
public Vector()
public Vector(int size)
public void addElement(Object insertObj)
public void insertElementAt(Object insertObj, int index)
public Object clone()
public boolean contains(Object obj)
public void copyInto(Object[] dest)
public Object elementAt(int index)
public Object firstElement()
public Object lastElement()
public int indexOf(Object obj)
public int indexOf(Object obj, int index)
public boolean isEmpty()
public int lastIndexOf(Object obj)
public void removeAllElements()
public void removeElement(Object obj)
public void removeElementAt(int index)
public void setElementAt(Object obj, int index)
public int size()
public String toString()
Every element of a Vector object is a reference variable of the type Object. In Java, Object is a predefined class, and a reference variable of Object type can store the address of any object. Because every component of a Vector object is a reference, to add an element into a Vector object, you must first create the appropriate object and store the data into that object. You can then store the address of the object holding the data into a Vector object element. Values of primitive data types cannot be directly assigned to a Vector element. You must first wrap the primitive data type element into an appropriate wrapper class, such as the class Integer for int values.
Programming Example: Election Results
The input to this program is two files, one containing the candidates’ names and the other containing the voting data. Voting data is in the form:
Candidate_name region# number_of_votes_for_this_candidate
The output to this program is the elections results in a tabular form – each candidate’s name and the number of votes they received in each region and the total number of votes they received.
The solution to this program consists of:
1. Reading the candidates’ names into the array candidateName
2. A two-dimensional name consisting of the votes by Region
3. An array consisting of the total votes parallel to the candidateName array
4. Sorting the array candidatesName
5. Processing the voting data
6. Calculating the total votes received by each candidate
7. Outputting the results in tabular form
Some of the methods of this program are:
GetCandidateName, sortCandidateName, binSearch, processVotes, addRegionsVote, printHeading, printResults
The class String (Revisited)
Some additional methods of the class String that are especially useful are:
String(String str) char charAt(int index)
int indexOf(char ch) int indexOf(char ch, int pos)
int indexOf(String str) int indexOf(String str, int pos)
int compareTo(String str) String concat(String str)
boolean equals(String str) int length()
String toLowerCase() String toUpperCase()
String substring(int startIndex, int endIndex)
String replace(char charToBeReplaced, char charReplaceWith)
boolean startsWith(String str)
boolean endsWith(String str)
boolean regionMatches(int ind, String str, int strIndex, int len)
boolean regionMatches(Boolean ignoreCase, int ind, String str, int strIndex, int len)
Programming Example: Pig Latin Strings
When converting a word into Pig Latin, if the string begins with a vowel they string –way is added to it. If the first character is not a vowel, - and the substring up till the vowel is appended to the end of the string and ay is added to the end of the new string.
The input to this program is a string.
The output to this program is the input string translated into Pig Latin.
The solution to this program consists of the following methods:
isVowel, rotate, pigLatinString
Using these methods:
1. Get the str
2. Find the pig Latin form of str by using the method pigLatinString
3. Output the pig Latin form of str
Quick Quiz
1. The method startsWith is part of the class ____.
Answer: String
2. Lists in Java can be represented using arrays and ____.
Answer: vectors
3. A vector can grow and ____ during program execution.
Answer: shrink
- True or False: If an element in a vector does not exist, an ElementOutOfBounds exception is thrown.
Answer: False
5. True or False: The operator new is used to declare and instantiate vectors.
Answer: True
Discussion Questions
Some interesting topics of discussion in Chapter Ten include:
Ø Discuss the different searching algorithms and when each is appropriate to use.
Ø Discuss the difference between arrays and vectors and when each is appropriate to use.
Projects to Assign
1. Assign odd Exercises.
2. Assign Programming Exercises 3 and 5.
Key Terms
Ø Binary search: search algorithm that can be used on sorted lists; uses the divide and conquer method to find the search item. The item is first compared to the middle element and depending on whether the item is greater than or less than the middle item, it is compared to the middle item in the first or second half of the list until the item is found or all comparisons have been made.
Ø Item comparisons: the search item being compared to the items in a list.
Ø Key comparisons: item comparisons; the search item being compared to the items in the list.
Ø List: a set of values of the same type.
Ø Selection sort: sorting a list by selecting an element in the list and moving it to its proper position.
10-3