Professional Web Hosting - Comcast Web Hosting Java Blog

318 Arrays Chapter 7 simplicity, the examples in this section use arrays that contain elements of type int. Please remember that a program can declare an array of any data type. 7.4.1 Allocating an Array and Initializing Its Elements The application of Figure 7.3 uses operator newto allocate dynamically an array of 10 int elements, which are initially zero (the default value in an array of type int). The program displays the array elements in tabular format in a JTextArea. Line 12 declares array a reference capable of referring to an array of int elements. Line 14 allocates the 10 elements of the array with newand initializes the reference. The program builds its output in the String called output that will be displayed in a JTextArea on a message dialog. Line 16 appends to output the headings for the columns displayed by the program. The columns represent the subscript for each array element and the value of each array element, respectively. Lines 19 20 use a for structure to append the subscript number (represented by counter) and value of each array element to output. Note the use of zero-based counting (remember, subscripts start at 0), so that the loop can access every array element. Also, note the expression array.lengthin the forstructure condition to determine the length of the array. In this example, the length of the array is 10, so the loop continues executing as long as the value of control variable counteris less than 10. For a 10-element array, the subscript values are 0 through 9, so using the less than operator

Chapter 7 Arrays 317 7.3 Declaring and Allocating Arrays Arrays are objects that occupy space in memory. All objects in Java (including arrays) must be allocated dynamically with operator new. For an array, the programmer specifies the type of the array elements and the number of elements as part of the new operation. To allocate 12 elements for integer array c in Fig. 7.1, use the declaration int c[] = new int[ 12 ]; The preceding declaration also can be performed in two steps as follows: int c[]; // declares the array c = new int[ 12 ]; // allocates the array When allocating an array, each element of the array receives a default value zero for the numeric primitive-data-type elements, false for boolean elements or null for references (any nonprimitive type). Common Programming Error 7.2 Unlike array declarations in several other programming languages (such as C and C++), Java array declarations must not specify the number of array elements in the square brackets after the array name; otherwise, a syntax error occurs. For example, the declaration int c[ 12 ]; causes a syntax error. A program can allocate memory for several arrays with a single declaration. The following declaration reserves 100 elements for String array b and 27 elements for String array x: String b[] = new String[ 100 ], x[] = new String[ 27 ]; When declaring an array, the type of the array and the square brackets can be combined at the beginning of the declaration to indicate that all identifiers in the declaration represent arrays, as in double[] array1, array2; which declares both array1 and array2 as arrays of double values. As shown previously, the declaration and initialization of the array can be combined in the declaration. The following declaration reserves 10 elements for array1 and 20 elements for array2: double[] array1 = new double[ 10 ], array2 = new double[ 20 ]; A program can declare arrays of any data type. It is important to remember that every element of a primitive data type array contains one value of the declared data type. For example, every element of an int array contains an intvalue. However, in an array of a nonprimitive type, every element of the array is a reference to an object of the array s declared data type. For example, every element of a String array is a reference to a String. In arrays that store references, the references have the value null by default. 7.4 Examples Using Arrays This section presents several examples using arrays that demonstrate declaring arrays, allocating arrays, initializing arrays and manipulating array elements in various ways. For Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

316 Arrays Chapter 7 Let us examine array cin Figure 7.1 more closely. The name of the array is c. Every array in Java knows its own length and maintains this information in a variable called length. The expression c.length accesses array c s length variable to determine the length of the array. The array s 12 elements are referred to as c[0], c[1], c[2], , c[11]. The value of c[0]is -45, the value of c[1] is 6, the value of c[2] is 0, the value of c[7] is 62and the value of c[11] is 78. To calculate the sum of the values contained in the first three elements of array cand store the result in variable sum, we would write sum = c[ 0 ] + c[ 1 ] + c[ 2 ]; To divide the value of the seventh element of array cby 2and assign the result to the variable x, we would write x=c[ 6]/ 2; Common Programming Error 7.1 It is important to note the difference between the seventh element of the array and array element seven. Because array subscripts begin at 0, the seventh element of the array has a subscript of 6, while array element seven has a subscript of 7 and is actually the eighth element of the array. This confusion is a source of off-by-one errors. The brackets used to enclose the subscript of an array are one of Java s many operators. Brackets are in the highest level of precedence in Java. The chart in Fig. 7.2 shows the precedence and associativity of the operators introduced so far. They are shown top to bottom in decreasing order of precedence with their associativity and type. See Appendix C for the complete operator precedence chart. Operators Associativity Type () [] . left to right highest ++ –right to left unary postfix ++ –+ -! (type) right to left unary * / % left to right multiplicative + -left to right additive < <= > >= left to right relational == != left to right equality & left to right boolean logical AND ^ left to right boolean logical exclusive OR | left to right boolean logical inclusive OR && left to right logical AND || left to right logical OR ?: right to left conditional = += -= *= /= %= right to left assignment Fig. 7.2Precedence and associativity of the operators discussed so far. Fig. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

Chapter 7 Arrays 315 7.2 Arrays An array is a group of contiguous memory locations that all have the same name and the same type. To refer to a particular location or element in the array, we specify the name of the array and the position number (or index or subscript) of the particular element in the array. Figure 7.1 shows an integer array called c. This array contains 12 elements. A program refers to any one of these elements by giving the name of the array followed by the position number of the particular element in square brackets ([]). The first element in every array has position number zero (sometimes called the zeroth element). Thus, the first element of array cis c[0], the second element of array cis c[1], the seventh element of array c is c[6], and, in general, the ith element of array cis c[i-1]. Array names follow the same conventions as other variable names. Formally, the position number in square brackets is called a subscript (or an index). A subscript must be an integer or an integer expression. If a program uses an expression as a subscript, the program evaluates the expression to determine the subscript. For example, if we assume that variable ais 5 and that variable bis 6, then the statement c[ a + b ] += 2; adds 2 to array element c[11]. Note that a subscripted array name is an lvalue it can be used on the left side of an assignment to place a new value into an array element. c[ 0 ] Name of array (Note that all elements of c[ 1 ] this array have the same name, c) c[ 2 ] c[ 3 ] c[ 4 ] c[ 5 ] c[ 6 ] c[ 7 ] c[ 8 ] c[ 9 ] Position number (index or subscript) of the c[ 10 ] element within array c c[ 11 ] -45 6 0 72 1543 -89 0 62 -3 1 6453 78 Fig. 7.1A 12-element array. Fig. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

314 Arrays Chapter 7 Outline 7.1 Introduction 7.2 Arrays 7.3 Declaring and Allocating Arrays 7.4 Examples Using Arrays 7.4.1 Allocating an Array and Initializing Its Elements 7.4.2 Using an Initializer List to Initialize Elements of an Array 7.4.3 Calculating the Value to Store in Each Array Element 7.4.4 Summing the Elements of an Array 7.4.5 Using Histograms to Display Array Data Graphically 7.4.6 Using the Elements of an Array as Counters 7.4.7 Using Arrays to Analyze Survey Results 7.5 References and Reference Parameters 7.6 Passing Arrays to Methods 7.7 Sorting Arrays 7.8 Searching Arrays: Linear Search and Binary Search 7.8.1 Searching an Array with Linear Search 7.8.2 Searching a Sorted Array with Binary Search 7.9 Multiple-Subscripted Arrays 7.10 (Optional Case Study) Thinking About Objects: Collaboration Among Objects Summary Terminology Self-Review Exercises Answers to Self-Review Exercises Exercises Recursion Exercises Special Section: Building Your own Computer 7.1 Introduction This chapter serves as an introduction to the important topic of data structures. Arrays are data structures consisting of related data items of the same type. Arrays are static entities, in that they remain the same size once they are created, although an array reference may be reassigned to a new array of a different size. Chapter 19, Data Structures, introduces dynamic data structures, such as lists, queues, stacks and trees, that can grow and shrink as programs execute. Chapter 20, Java Utilities Package and Bit Manipulation, discusses class Vector, which is an array-like class whose objects can grow and shrink in response to a Java program s changing storage requirements. Chapter 21, The Collections API, introduces Java s predefined data structures that enable the programmer to use existing data structures for lists, queues, stacks and trees rather than reinventing the wheel. The Collections API also provides class Arrays, which defines a set of utility methods for array manipulation. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

7 Arrays Objectives To introduce the array data structure. To understand the use of arrays to store, sort and search lists and tables of values. To understand how to declare an array, initialize an array and refer to individual elements of an array. To be able to pass arrays to methods. To understand basic sorting techniques. To be able to declare and manipulate multiple- subscript arrays. With sobs and tears he sorted out Those of the largest size Lewis Carroll Attempt the end, and never stand to doubt; Nothing s so hard, but search will find it out. Robert Herrick Now go, write it before them in a table, and note it in a book. Isaiah 30:8 Tis in my memory lock d, And you yourself shall keep the key of it. William Shakespeare Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

312 Methods Chapter 6 6.41 Exercise 6.31 through Exercise 6.33 developed a computer-assisted instruction program to teach an elementary school student multiplication. This exercise suggests enhancements to that program. a) Modify the program to allow the user to enter a grade-level capability. A grade level of 1 means to use only single-digit numbers in the problems, a grade level of 2 means to use numbers as large as two digits, etc. b) Modify the program to allow the user to pick the type of arithmetic problems he or she wishes to study. An option of 1 means addition problems only, 2 means subtraction problems only, 3 means multiplication problems only, 4 means division problems only and 5 means to intermix randomly problems of all these types. 6.42 Write method distance, to calculate the distance between two points (x1, y1) and (x2, y2). All numbers and return values should be of type double. Incorporate this method into an applet that enables the user to enter the coordinates of the points. 6.43 What does the following method do? // Parameter b must be a positive // integer to prevent infinite recursion public int mystery( int a, int b ) { if ( b == 1 ) return a; else return a + mystery( a, b - 1 ); } 6.44 After you determine what the program in Exercise 6.43 does, modify the method to operate properly after removing the restriction of the second argument being nonnegative. Also, incorporate the method into an applet that enables the user to enter two integers, and test the method. 6.45 Write an application that tests as many of the math-library methods in Fig. 6.2 as you can. Exercise each of the methods by having your program print out tables of return values for a diversity of argument values. 6.46 Find the error in the following recursive method, and explain how to correct it: public int sum( int n ) { if ( n == 0 ) return 0; else return n + sum( n ); } 6.47 Modify the craps program of Fig. 6.9 to allow wagering. Initialize variable bankBalance to 1000 dollars. Prompt the player to enter a wager. Check that wager is less than or equal to bankBalance, and if not, have the user reenter wager until a valid wager is entered. After a correct wager is entered, run one game of craps. If the player wins, increase bankBalanceby wager, and print the new bankBalance. If the player loses, decrease bankBalance by wager, print the new bankBalance, check if bankBalance has become zero, and if so, print the message “Sorry. You busted!” As the game progresses, print various messages to create some chatter, such as “Oh, you’re going for broke, huh?” or “Aw c’mon, take a chance!”or “You’reupbig.Now’sthetime tocashin yourchips!”. Implement the chatter as a separate method that randomly chooses the string to display. 6.48 Write an applet that uses a method circleArea to prompt the user for the radius of a circle and to calculate and print the area of that circle. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

Chapter 6 Methods 311 Fig. 6.23 The Towers of Hanoi for the case with four disks. Write an applet to solve the Towers of Hanoi problem. Allow the user to enter the number of disks in a JTextField. Use a recursive towermethod with four parameters: a) the number of disks to be moved, b) the peg on which these disks are initially threaded, c) the peg to which this stack of disks is to be moved, and d) the peg to be used as a temporary holding area. Your program should display in a JTextAreawith scrolling functionality the precise instructions it will take to move the disks from the starting peg to the destination peg. For example, to move a stack of three disks from peg 1 to peg 3, your program should print the following series of moves: 1 . 3 (This notation means move one disk from peg 1 to peg 3.) 1 . 2 3 . 2 1 . 3 2 . 1 2 . 3 1 . 3 6.38 Any program that can be implemented recursively can be implemented iteratively, although sometimes with more difficulty and less clarity. Try writing an iterative version of the Towers of Hanoi. If you succeed, compare your iterative version with the recursive version you developed in Exercise 6.37. Investigate issues of performance, clarity and your ability to demonstrate the correctness of the programs. 6.39 (Visualizing Recursion) It is interesting to watch recursion in action. Modify the factorial method of Fig. 6.12 to print its local variable and recursive-call parameter. For each recursive call, display the outputs on a separate line, and add a level of indentation. Do your utmost to make the outputs clear, interesting and meaningful. Your goal here is to design and implement an output format that helps a person understand recursion better. You may want to add such display capabilities to the many other recursion examples and exercises throughout the text. 6.40 The greatest common divisor of integers xand yis the largest integer that evenly divides into both xand y. Write a recursive method gcdthat returns the greatest common divisor of xand y. The gcdof xand yis defined recursively as follows: If yis equal to 0, then gcd(x,y)is x; otherwise, gcd(x,y)is gcd(y,x%y), where %is the modulus operator. Use this method to replace the one you wrote in the applet of Exercise 6.28. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

310 Methods Chapter 6 responses typed by the student. After the student types 10 answers, your program should calculate the percentage of correct responses. If the percentage is lower than 75%, print Pleaseaskyourinstructorforextrahelp and reset the program so another student can try the program. 6.34 Write an applet that plays the guess the number game as follows: Your program chooses the number to be guessed by selecting a random integer in the range 1 to 1000. The applet displays the prompt Guessanumberbetween1and1000 next to a JTextField. The player types a first guess into the JTextField and presses the Enter key. If the player’s guess is incorrect, your program should display Toohigh.Tryagain.or Toolow.Tryagain. in the status bar to help the player zero in on the correct answer and should clear the JTextField so the user can enter the next guess. When the user enters the correct answer, display Congratulations.You guessed the number! in the status bar and clear the JTextField so the user can play again. [Note: The guessing technique employed in this problem is similar to a binary search.] 6.35 Modify the program of Exercise 6.34 to count the number of guesses the player makes. If the number is 10 or fewer, print Eitheryouknowthesecretoryougotlucky! If the player guesses the number in 10 tries, print Aha!Youknowthesecret! If the player makes more than 10 guesses, print You should be able to do better! Why should it take no more than 10 guesses? Well, with each good guess the player should be able to eliminate half of the numbers. Now show why any number from 1 to 1000 can be guessed in 10 or fewer tries. 6.36 Write a recursive method power(base,exponent) that when invoked returns base exponent For example, power(3,4)=3*3*3*3. Assume that exponent is an integer greater than or equal to 1. (Hint: The recursion step should use the relationship base exponent = base base exponent - 1 and the terminating condition occurs when exponent is equal to 1, because base1 = base Incorporate this method into an applet that enables the user to enter the base and exponent.) 6.37 (Towers of Hanoi) Every budding computer scientist must grapple with certain classic problems, and the Towers of Hanoi (see Fig. 6.23) is one of the most famous. Legend has it that in a temple in the Far East, priests are attempting to move a stack of disks from one peg to another. The initial stack has 64 disks threaded onto one peg and arranged from bottom to top by decreasing size. The priests are attempting to move the stack from this peg to a second peg under the constraints that exactly one disk is moved at a time and at no time may a larger disk be placed above a smaller disk. A third peg is available for temporarily holding disks. Supposedly, the world will end when the priests complete their task, so there is little incentive for us to facilitate their efforts. Let us assume that the priests are attempting to move the disks from peg 1 to peg 3. We wish to develop an algorithm that will print the precise sequence of peg-to-peg disk transfers. If we were to approach this problem with conventional methods, we would rapidly find ourselves hopelessly knotted up in managing the disks. Instead, if we attack the problem with recursion in mind, it immediately becomes tractable. Moving n disks can be viewed in terms of moving only n 1 disks (and hence the recursion) as follows: a) Move n 1 disks from peg 1 to peg 2, using peg 3 as a temporary holding area. b) Move the last disk (the largest) from peg 1 to peg 3. c) Move the n 1 disks from peg 2 to peg 3, using peg 1 as a temporary holding area. The process ends when the last task involves moving n = 1 disk (i.e., the base case). This task is accomplished by simply moving the disk, without the need for a temporary holding area. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01

Chapter 6 Methods 309 6.28 The greatest common divisor (GCD) of two integers is the largest integer that evenly divides each of the two numbers. Write a method gcd that returns the greatest common divisor of two integers. Incorporate the method into an applet that reads two values from the user. Display the result of the method in the status bar. 6.29 Write a method qualityPointsthat inputs a student s average and returns 4 if a student’s average is 90 100, 3 if the average is 80 89, 2 if the average is 70 79, 1 if the average is 60 69 and 0 if the average is lower than 60. Incorporate the method into an applet that reads a value from the user. Display the result of the method in the status bar. 6.30 Write an applet that simulates coin tossing. Let the program toss a coin each time the user presses the Toss button. Count the number of times each side of the coin appears. Display the results. The program should call a separate method flip that takes no arguments and returns false for tails and true for heads. [Note: If the program realistically simulates coin tossing, each side of the coin should appear approximately half the time.] 6.31 Computers are playing an increasing role in education. Write a program that will help an elementary school student learn multiplication. Use Math.randomto produce two positive one-digit integers. The program should then display a question in the status bar, such as How much is 6 times 7? The student then types the answer into a JTextField. Next, the program checks the student’s answer. If it is correct, draw the string “Verygood!”on the applet and ask another multiplication question. If the answer is wrong, draw the string “No.Please try again.” on the applet and let the student try the same question again repeatedly until the student finally gets it right. A separate method should be used to generate each new question. This method should be called once when the applet begins execution and each time the user answers the question correctly. All drawing on the applet should be performed by the paint method. 6.32 The use of computers in education is referred to as computer-assisted instruction (CAI). One problem that develops in CAI environments is student fatigue. This problem can be eliminated by varying the computer’s dialogue to hold the student’s attention. Modify the program of Exercise 6.31 so the various comments are printed for each correct answer and each incorrect answer as follows: Responses to a correct answer Very good! Excellent! Nice work! Keep up the good work! Responses to an incorrect answer No. Please try again. Wrong. Try once more. Don’t give up! No. Keep trying. Use random-number generation to choose a number from 1 to 4 that will be used to select an appropriate response to each answer. Use a switch structure in the paint method to issue the responses. 6.33 More sophisticated computer-aided instruction systems monitor the student s performance over a period of time. The decision to begin a new topic is often based on the student s success with previous topics. Modify the program of Exercise 6.32 to count the number of correct and incorrect Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01