COMP 110 - Loops and Arrays

COMP 110 Note Set #5: Loops, Arrays Outline of Noteset #5 Review and Miscellaneous Topics Command Line Interfaces: Input Command then Branch to the Handler for the Command Nested Loops (two loops for two dimensional data, three loops for three dimensional data) ASCII “Art” to visualize two dimensional info Modulo Based Calculations Test for Primeness Sieve of Eratosthenes Using loops to generate a series Using comparisons to find the minimum/maximum of a few values. Preview of Methods and Functions Simulations Preview of Objects and References Arrays Motivation for Using Arrays Declaring and Allocating Space for Arrays How to Index the Elements of Arrays The length Property of Arrays Rectangular vs Jagged 2-Dimensional Arrays The Linear Search Problem and its Solution The Binary Search Problem and its Solution The Min/Max Array Value Problem and its Solution Changing the Storage of Arrays Dynamically in the Middle of a Program Higher Dimensional Arrays Streaming Data vs. Stored Data File I/O Using a Scanner to Read from a File Using a PrintWriter to Write to a File COMP 110 1 Note Set #5 One More Application of Branches: Command Line Interfaces The part of a software application that deals with the I/O is called the user interface. Usually, the application is being run under the control of a human sitting in front of the display with their hands on the keyboard and mouse. In your future software development experience, you’ll write plenty of software that isn’t controlled directly by a human user, but for now we assume that a human is in the loop. Real commercial software applications today almost always provide a graphical user interface or GUI (pronounced “goo-ey”). A GUI interacts with the user by providing standard shapes on the screen that the user can interact with using either the keyboard or mouse: buttons, check boxes, text boxes, menus, scrollbars, etc. It’s hard to believe that this is a recent innovation and that earlier generations of software applications only provided a command-line interface, much like DOS command prompt interface your applications are using in the lab. It might seem as if you are being required to learn out-of-date technology, but in fact, the instructors believe that this is the best way to introduce you to programming. GUI design is fascinating and fun, but until you learn a solid foundation of programming basics, it is a major distraction and simply not relevant at this stage. To prove to you that command line interfaces are not totally useless, you will design in lab an application that provides the user a series of options or choices. The choices will be provided to the user by printing a list of the options (a menu). The program then waits for the user’s response, and validates it. Finally, the application executes the operation or task requested by the user and loops to ask for the next choice or option. One of the options must be “quit”, which the user will eventually select, at which point the program terminates. This style of interaction between your program and the user is sometimes called a command interpreter loop, and is very common in a wide range of applications, even applications that have GUIs. The structure (in pseudocode) of such an application is as follows: perform any needed initialization do { print out a greeting to the user and list the available options read in the option chosen by the user if (option #1 was chosen) { perform task for option #1 } else if (option #2 was chosen) { perform task for option #2 } ... } while (option chosen is not “quit”); For simplicity, the interaction can set up a simple “code”, ie, the application will number the possible choices, and will ask the user to enter the number corresponding to the desired choice. // during initialization int response; // inside do-while loop response = Integer.parseInt(in.readLine()); if (response == 1) { ... } else if (response == 2) { ...} ... COMP 110 2 Note Set #5 Example: Command-Line Calculator Example Run % java Calculator Calculator 1.0 Enter first value: Enter second value: Enter operation + - * / %: Result = 437 Another calculation? Enter first value: Enter second value: Enter operation + - * / %: Result = 13 Another calculation? Thanks, bye! % _ 19 23 * yes 217 17 % no Future Improvements A command line interpreter for a calculator can be streamlined if we allow the user to simply enter the entire expression on a single line. Rather than prompting the user with a long-winded questions, we reduce the prompt to a single character. The program simply assumes that the user of the application will understand what to do when application runs without having to be prompted in such detail. Example Run % java Calculator Calculator 2.0 > 19 * 23 437 > 217 % 17 13 > quit Bye % _ In this version of the calculator, the user has a simpler interface, but the program must do more work to parse the information entered on a single line. In the first version, each input was captured separately. In the second version, the program captures a line at a time. This line must be parsed or tokenized to break it down into its pieces before performing the requested calculation. COMP 110 3 Note Set #5 Summary on Choosing and Controlling Loops If the number of iterations is known (symbolically) in advance (before the loop begins to execute): • use a for loop • use 1-based counting for loop control (if possible) If the number of iterations is not known in advance: • use a while loop • counting cannot be used for loop control if the number of iterations is not known in advance, so use another technique such as sentinel-based iteration Nested Loops A loop might be useful for printing out a single row or column of numbers. Suppose you wanted to print out multiples of 10 for 15 rows. First, set up a loop that will execute for 15 iterations. This is best done by creating a counter and counting from 1 to 15. for (int i=1; i<=15; i++) { ... print out something } Now figure out what that “something” to print is. Create a table that shows the relationship between the value of the index variable (ie, which iteration it is) and the value to be printed out that iteration i 1 2 3 ... 15 output 10 20 30 ... 150 A moment’s thought will reveal that the relationship between output and i is “i*10”. That is, on the ith iteration, print out the value of “i*10”. for (int i=1; i<=15; i++) { System.out.println(i*10); } Output is 10 20 30 ... 150 Now let’s modify the loop to print out several columns on every row for (int i=1; i<=15; i++) { for (int j=1; j<=10; j++) { System.out.print( i*10 + j - 1 + " "); } System.out.println(""); } COMP 110 4 Note Set #5 Output is 10 11 12 13 20 21 22 23 30 31 32 33 40 41 42 43 50 51 52 53 60 61 62 63 70 71 72 73 80 81 82 83 90 91 92 93 100 101 102 110 111 112 120 121 122 130 131 132 140 141 142 150 151 152 14 15 16 17 24 25 26 27 34 35 36 37 44 45 46 47 54 55 56 57 64 65 66 67 74 75 76 77 84 85 86 87 94 95 96 97 103 104 105 113 114 115 123 124 125 133 134 135 143 144 145 153 154 155 18 19 28 29 38 39 48 49 58 59 68 69 78 79 88 89 98 99 106 107 116 117 126 127 136 137 146 147 156 157 108 118 128 138 148 158 109 119 129 139 149 159 The outer loop (the “i” loop) is controlling the number of rows The inner loop (the “j” loop) is controlling the number of columns This is an example of nested loops (one loop inside another loop). Note the following points: Each loop must be controlled by a separate counter. In this case the outer loop is controlled by “i”, and the inner loop is controlled by “j”. • For every iteration of the outer loop, the inner loop is executed in its entirety, from initial value to its limit. The next iteration of the outer loop reinitializes the inner loop. • The individual values on a line must be separated by white space. • At the conclusion of every outer loop iteration, we print an newline to put each row on a separate line. • Here’s a table that traces the value of the counters for both the inner and outer loops, plus the calculation of the value to be output. outer loop counter “i” 1 2 3 ... 15 COMP 110 inner loop counter j 1 2 3 4 5 ... 9 10 1 2 3 4 5 ... 9 10 1 2 3 4 5 ... 9 10 ... 1 2 3 4 5 ... 9 10 10*i + j – 1 (the output value) 10 11 12 13 14 ... 19 20 21 22 23 24 ... 29 30 31 32 33 34 ... 39 151 152 153 154 ... 159 5 Note Set #5 Double Loop Application Example: Draw a Square of Dimension n Problem: input integer n; then draw a hollow square of asterisks of size n Example Run C:\> java DrawSquare Please enter dimension of square: 5 ***** * * * * * * ***** C:\> java DrawSquare Please enter dimension of square: 10 ********** * * * * * * * * * * * * * * * * ********** C:\> Hint: Use a doubly nested loop. Outer loop counts the number of rows. For each row you need a second loop to print out the contents of that row. Note that the first and last row fit one pattern, all other rows fit a second pattern. COMP 110 6 Note Set #5 Modulo-Based Operations (Calculations that Require the % Operator) For numerical accuracy in many arithmetic calculations, real or floating point calculations using the double data type in Java are preferred. But many significant problems in mathematics involve only integers. Note that it is a syntax error to use the modulo operator on any type except integer operands. Even/Odd One of the most common uses for the % operation is to test a value for evenness/oddness. Remember that this is only necessary when we are manipulating values symbolically. If our programs worked only with constants, we could obviously see from just looking at the number if it was even or odd. But if we create an int variable and assign to it a value input by the user, then we need another way to find out. There is no predefined “check-for-even” operation or method in Java. But it is easy to come up with a simple way to find out. All we have to do is divide the number being checked by 2, and look at the remainder. 2 3 4 5 6 ... 2/2: 3/2: 4/2: 5/2: 6/2: q == 1, r == 0 (2%2 == 0) ==> even q == 1, r == 1 (3%2 == 1) ==> odd q == 2, r == 0 (4%2 == 0) ==> even q == 2, r == 1 (5%2 == 1) ==> odd q == 3, r == 0 (6%2 == 0) ==> even The obvious relationship is that if the remainder is 0, then the number is even. If the remainder is 1, then the number is odd. Since the only possible values of remainder when dividing an int by 2 are 0 and 1, this covers all the cases. int x; Input x; if (x%2 == 0) { ... x is even ... } else { ... x is odd ... } COMP 110 7 Note Set #5 A more general problem that is related to the test for evenness is the test for “primeness” or primality. By definition, a number is prime if • it is an integer greater than 2 (technically, 2 is not prime) and • it is divisible only by 1 and itself (all integers are divisible by 1 and themselves). Primeness is a property that is limited by definition to integer values. As a clue for how to start turning this into a program, notice that asking is n is divisible by m ? is the same as asking is n % m == 0 ? But which values of m need to be checked against this relationship? Example: Is 5 prime? Check for divisibility by 1, 2, 3, 4, and 5: 5 % 1 ==> 0 5 % 2 ==> 1 5 % 3 ==> 2 5 % 4 ==> 1 5 % 5 ==> 0 5 is divisible by 1 5 is not divisible by 2 5 is not divisible by 3 5 is not divisible by 4 5 is divisible by 5 Since 5 is divisible only by 1 and itself , 5 is prime. Equivalently: Since 5 is not divisible by 2, 3, and 4, then 5 is prime. Technically, this process can be sped up. For starters, we don’t need to check 1 and 5. We can suggest some other improvements shortly. Example: Is 6 prime? Check for divisibility by 2, 3, 4, and 5 (can skip 1 and 6) 6 % 2 ==> 0 6 is divisible by 2 ... No need to check any further, 6 is not prime In other words, we might start off with a lot of potential divisors to check, but as soon as we find any divisor, there’s no point in checking any of the others, since we already know the answer to the original question, ie, the number can’t be prime because we just found a divisor. So how to describe the general algorithm? Given an integer value n (n > 2) • Define the range R as the integer values 2 through n – 1 (inclusive) • Consider in turn each integer m in the range R • If n%m != 0 for all m in range R, then n is prime. • If n%m == 0 for any m in range R, then n is not prime Once such an m is found, there is no need to check any further. But until then, must keep checking. So, this primeness check is an example of a problem that requires a loop to solve. In our previous examples of writing algorithm steps, we saw that if an algorithm step used words like “if ... then ... else ... otherwise”, this step is translated into a branch or decision point in Java. Here’s another guideline: if an algorithm step uses words like “for each ... for every ...” when referring to a set of values, the algorithm step will be translated into a loop in Java. COMP 110 8 Note Set #5 Let’s write a slightly more detailed version of the above algorithm: Input n (the value to be tested for primeness) for every m from 2 to n – 1 calculate n%m if n%m is not zero, let the loop continue to the next value of m if n%m == 0, then we can conclude that n is not prime (no need to check other values of m) once all values of m (2 thru n – 1) have been checked, then we can conclude that n is prime Here’s one implementation of the solution: Scanner in = ...; System.out.print(“Please enter an int value to (> 2): ”); int n = in.nextInt(); // input (add bulletproofing) for (int m=2; m <= n – 1; m++) { if (n%m == 0) { System.out.println(n + “ is not prime.”); System.exit(0); } } System.out.println(n + “ is prime.”); Note that the overall structure of the program is a counter-controlled for loop. Nested inside the loop is a branch. If the branch condition “n%m == 0” is true, then we have determined that the value in question “n” is not prime. We print out a result message, and then exit the program, because there’s no need to check the other values of m. Once a divisor of n is found, meaning n is not prime, no amount of additional checking can ever change n back to a prime number. The interesting thing is what happens if the branch condition “n%m == 0” is not true. In this case, we seem to do nothing. But actually, we do nothing only for the current iteration of the loop. What we are really doing is letting the loop quietly advance to the next iteration. So a little thought will reveal that there are only two ways for the program to terminate: • we find an m for which n%m == 0 • we check every m from 2 through n – 1 without finding a value for which n%m == 0. If the program “survives” until the loop terminates, we have to conclude that the latter situation occurred, so n must be prime. Another way to say the same thing is to use the idea of the boolean and (&&). For some number n to be prime, the expression ( (n%2 != 0) && (n%3 != 0) && (n%4 != 0) && ... (n%n-1 != 0) ) If we evaluate the subexpressions from left to right, as soon as we find one that evaluates to false, the whole expression is false (n is not prime) and we don’t need to continue. On the other hand, if we make all the way to the end and all the subexpressions were true, then the whole expression is true (and n is prime). But as we’ve seen, any expression that requires a “...” must be implemented as a loop within our program. There’s no magic instruction that tells the computer to fill in the missing details. COMP 110 9 Note Set #5 A slightly modified version of the loop is to wait until the end of the program to print any input. To make this change, we’ll use a boolean variable “isprime” as a “flag” that records the result of the check as soon as the result is known. But we’ll wait until after the loop has ended to look at the flag and determine if the result was true or false (ie, prime or not prime). Scanner in = ...; System.out.print(“Please enter an integer > 2: int n = in.nextInt(); ”); boolean isprime = true; for (int m=2; m <= n – 1; m++) { if (n % m == 0) { isprime = false; break; } } if (isprime==true) System.out.println(“The value ” + n + “ is prime.”); else System.out.println(“The value ” + n + “ is not prime.”); This organization has some advantages over the previous version. Primarily, the previous version used an “exit()” statement that terminated the entire program. This might be a problem if there are additional processing steps for the program after the prime calculation. The second version is made more general by using a “break” statement. Instead of terminating the entire program, the break terminates just the loop. Execution continues with the first statement after the end of the loop. Further Improvements When we first learn to write programs, we have to learn the difference between “good” or “high-quality” programs and “bad” or “poor-quality” programs. There are several ways to measure quality. Obviously, the most important measure is correctness. A program that compiles and runs but doesn’t calculate the correct answer to a problem is totally worthless. Beyond correctness, we look for generality and clarity of style (proper indentation and use of comments, etc.). As we become more advanced programmers, we will gradually have to wory about efficiency (this topic is covered in COMP 182). This means, suppose we have two programs that both solve some problem and both are correct, but program #1 takes 1 minute to compute the solution and program #2 takes 1 hour. Clearly, program #1 is going to be more popular with potential customers. The author of program #1 will make a lot of money, and the author of program #2 will not. The problem with our prime number program is that we could make it a little more efficient. To check that a number n is prime, we look for divisors of n over the range 2 through n – 1. But divisors always come in pairs. For example, let’s look at a few non-prime numbers and their divisors. Example: 12. If we search for possible divisors of 12 starting at 2 and going through 11, we find the following pairs: COMP 110 10 Note Set #5 Examples of Up-Down Factor Pairs 12 = 2*6 3*4 4*3 6*2 20 = 2 * 10 4*5 5*4 10 * 2 As you can see, if n is divisible by 2, then n/2 represents the largest divisor of n. What this means for our algorithm for primeness is that once we check all possible divisors up to n/2, and n is still prime, we don’t need to check any further. After we pass n/2, there are no other possible divisors. So our algorithm can be changed to look like this: Input n for (int m=2; m<=n/2; m++) { ... } This results in a more efficient program. For an arbitrary prime number, the number of iterations of the loop required to confirm that n is prime can be cut roughly in half. This may not seem like a big improvement for small n, but for large n (say n = 5474211), the speed up could be significant. Question: the search for factors can terminate even before n/2. What’s the optimal stopping point? The previous approach can be called exhaustive trial division. We figure out if a number is prime by dividing it by every possible candidate factor. If we find a number that divides it evenly, we conclude it is not prime. If we can’t find a factor, it is prime. A different approach is called the Sieve of Eratosthenes. Rather than testing a single number for primeness, this algorithm, first described by Eratosthenes (276BC-194BC) in Alexandria, works by generating a list of all integers starting at 2 up to some chosen limit, identifying the next number in the table as prime, eliminating all multiples of that number from the table, and so on. When done, the numbers remaining in the table are prime. Implementation of this algorithm in Java is best done with arrays. We’ll revisit it when we study arrays later in this noteset. COMP 110 11 Note Set #5 Algebraic Expressions with Subscripts There are many expressions in algebra that use a notations such as summation symbols and subscripts. This is a notation that says “take the expression i2, substitute in the values 1 through n and sum up all the resulting terms”. In other words, this is just a shorthand mathematical notation for the expression 12 + 22 + 32 + ... + n2 Given a specific value for n, this expression can be evaluated to a numerical value n 1 2 3 4 ... Value 12 = 1 12 + 22 = 5 12 + 22 + 32 = 14 12 + 22 + 32 + 42 = 30 ... Suppose you had to write a program to evaluate this expression for a specific value of n. Using a for loop with a counter control variable and an accumulator, it’s actually quite easy. There’s a natural relationship between loops and summation notation in algebra. Input n (and validate that n >= 1) Initialize sum (the accumulator) to 0 for i from 1 to n sum = sum + i*i Output sum So, in general, any expression from algebra that contains a summation symbol can be implemented in a program with a loop to control the index and an accumulator to hold the result. The accumulator must be initialized to zero, and the result is then incrementally calculated (“accumulated”) each time through the loop. Also note that in this particular case, a closed-form expression is known for the summation expression. n Value closed form result 1 12 = 1 (2*i+1)(i+1)i/6 2 12 + 22 = 5 (2*i+1)(i+1)i/6 3 12 + 22 + 32 = 14 (2*i+1)(i+1)i/6 4 12 + 22 + 32 + 42 = 30 (2*i+1)(i+1)i/6 ... ... In other words, a loop is not required to find the answer for this problem, since a closed-form solution is known. But in the general case, a loop based program can calculate the answer if the closed form expression is not known. So, the moral of the story is that expressions involving summation notation can be easily translated into a Java program using a loop and an accumulator. If you can reduce the summation expression to a closed form, you won’t need to write a loop. But if you can’t find a closed form, then a loop plus accumulator approach will find the answer in the general case. Input n (and validate that n >= 1) Initialize sum (the accumulator) to 0 for i from 1 to n sum = sum + Output sum COMP 110 12 Note Set #5 Other Calculations that Use the Loop Index Variable Instead of using an accumulator, you might want to print out a table of related values. For example, print out a table of the squares and cubes of the first 20 integers. Using the skeleton of the previous example, we can modify it just slightly to solve this problem. The solution takes advantage of the value of the for loop counter variable to automatically generate the integers from 1 to n. Then, inside the body of the loop, we just calculate the necessary expression as a function of the counter variable. Input n, the number of rows in the table (validate that n >= 1) for i from 1 to n output i2 and i3 output newline In more detail Scanner in = ... ; System.out.print("Please enter number of rows (int >= 1): int n = in.nextInt(); // add validation ... "); System.out.println("n\tn^2\tn^3"); // output header before beginning loop for (int i=1; i<=n; i++) { System.out.println(i + "\t" + i*i + "\t" + i*i*i); // output table rows, columns separated by tab } Example run: Please enter number of rows (int >= 1): n n^2 n^3 1 1 1 2 4 8 3 9 27 4 16 64 5 25 125 6 36 216 7 49 343 8 64 512 9 81 729 10 100 1000 11 121 1331 12 144 1728 13 169 2197 14 196 2744 15 225 3375 16 256 4096 17 289 4913 18 324 5832 19 361 6859 20 400 8000 COMP 110 13 20 Note Set #5 Using Branches to Find Minimum (or Maximum) Value Given two inputs handled symbolically, we can use a simple if-else statement to determine which is larger or smaller. For example here’s the algorithm for finding the minimum: Input a, b if (a < b) a is the minimum else b is the minimum Translating these statements into a Java Program we get: Scanner in = ...; double a = in.nextDouble(); double b = in.nextDouble(); if (a < b) { System.out.println("minimum value = " + a); } else { System.out.println("minimum value = " + b); } What about finding the minimum of 3 values? This will require several nested branches (or compound comparisons): Input a, b, c if (a < b) if (a < c) a is else c is else if (b < c) b is else c is the minimum the minimum the minimum the minimum Translation into Java is left as an exercise. Another approach is to use compound comparisons Input a, b, c if (a < b) && (a < c) a is the minimum else if (b < a) && (b < c) b is the minimum else c is the minimum (or just (b” or “>=” for maximum calculation. As always, it’s natural to wonder how to generalize this algorithm to compute the min/max of an arbitrary number of values, not just 3. Clearly, the general solution will involve loops and/or arrays. We’ll get back to the general solution later, after we’ve introduced arrays. COMP 110 14 Note Set #5 Computations Using Functions We’ve looked at some simple functions such as polynomials in both the lecture and the lab. The functions that we are considering for now all have a nice closed-form expression that can be easily evaluated for any input. The notation for functions in math is y = f(x) Some example functions are the polynomials from lab project 3. Here’s a specific polynomial of degree 2. y = f(x) = x2 – 8x + 7 To determine the value of the polynomial, we create a program that prompts the user to enter the coefficients, and one or more values of x, then calculate the corresponding values of y, and output them as the result. The version of the program we wrote in lab 3 is good, but it’s a little inconvenient if we want to evaluate the polynomial for a large number of different x values. In other words, what if we wanted to plot the polynomial and evaluate it for 10 or 20 or 100 different values of x? Let’s create a little table of x vs. y values for the above polynomial. X f(x) 0 7 1 0 2 -5 3 -8 4 -9 5 -8 6 -5 7 0 8 7 9 16 10 27 We could extend the table for more values, but this table is large enough to make the point that after we’ve chosen a polynomial or any other function, we may want to repeatedly reevaluate it for many different x values. Moreover, it’s convenient to pick a series of regularly spaced x values. In this example, we’re looking at x on the range 0 to 11: {0, 1, 2, 3, 4, ... 9, 10, 11}. Once the x vs. y info is available it can be displayed graphically as a plot, or can be further analyzed. 30 25 20 15 10 Series1 5 0 -5 0 5 10 15 -10 -15 [You can use your mathematic knowledge to confirm that the plot has the correct characteristics, such as roots at x=1 and x=7, derivative is 0 at x=4, etc.] How would we modify the program written for project 3 to solve this problem? Hopefully, it will be apparent from the table that the x values can be easily generated by a loop, and that the polynomial can be reevaluated every time through the loop. COMP 110 15 Note Set #5 The algorithm for the Horner’s Rule Polynomial lab was something like this: input degree for (i from 0 through degree) // input degree+1 coefficients input ith coefficient do input x evaluate polynomial output result ask user if more evaluation is wanted while (user answers “y”) The new approach is input degree for (i from 0 through degree) input ith coefficient input first x value (eg, 0) input step size (eg, 1) input number of steps (eg, 10) for (i from first x to x + number of steps) evaluate polynomial for x = i output result Instead of repeatedly asking the user for a random series of x values, we ask the user to give 3 numbers: • the starting value (for example, x starts at 0) • the step size (usually 1, but other values are possible) • the number of steps (for example, 10 or 20) With this information, it is simple to set up a loop with correct control. The program is more automated now, and could be used to reevaluate the polynomial for 10s or 100s of regularly spaced values of x. So in conclusion, notice how functions and loops can be combined to get a more complete view of the “shape” of the function. Then general structure is to use a loop to generate the “x” values, then reevaluate the function every time through the loop: int start, stop, numsteps, stepsize, y; Input start, numsteps, stepsize stop = start + numsteps*stepsize; for (int i=start; ijavac Test.java C:\tempdir>java Test Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException at Test.main(Test.java:6) Note that out of bounds exceptions are only detected at runtime, not compile time. The compiler checks for a syntactically correct arrangement of symbols on the line, but it has a limited ability to check more complex relationships between the symbols. Another very common exception that you might run into when working with arrays is a null pointer exception. This happens when you attempt to use an array after it’s been declared but before space has been allocated with the “new” operation. int[] x; x[0] = 5; x[1] = 4; ... // declare the reference variable “x” // exception generated here – can’t use the array before allocating space To fix this error, add the statement that allocates space for the array: int[] x; x = new int[10]; x[0] = 5; x[1] = 4; ... COMP 110 // declare the reference variable “x” // allocate space // okay, space exists 22 Note Set #5 More on Initializing Arrays What if we want to initialize each element of the array to a different value, instead of a bunch of 0s? It might not be possible to use a for loop in this case, and we’re back to using a long series of individual assignment statements. int[] data = new int[10]; data[0] = 5; data[1] = 27; data[2] = 32; data[3] = 16; data[4] = 97; data[5] = 76; data[6] = 81; data[7] = 20; data[8] = 6; data[9] = 48; We can do the same thing by replacing the “new” statement, i.e., the statement that allocates the space, with an aggregate initialization expression that allocates the space and assigns initial values in one operation. The initialization statement looks like this: int[] data = { 5, 27, 32, 16, 97, 76, 81, 20, 6, 48 }; With an aggregate initialization, the length of the array is inferred from the number of expressions provided. Multidimensional Arrays In the examples above the arrays have all been one dimensional, similar to a vector in mathematics, or a single row or column of a table. For data that is logically arranged in rows and columns, we need a two dimensional array, an array with both rows and columns: int[][] tbl; tbl = new int[5][4]; or as one statement: int[][] tbl = new int[5][4]; This statement creates a two dimensional array with 5 rows and 4 columns. Each index or dimension is indicated with its own set of square brackets []. By convention, in a two-dimensional array, the first index is considered to be the row index, and the second index is the column index. 0 1 0 1 2 3 4 2 3 54 Notice that both the rows and columns are indexed with 0-based counting. 5 rows means that the rows are numbered from 0 to 4, and 4 columns means the columns are numbered from 0 to 3. To assign a value to a specific array element, indicate the name of the array plus a row index and a column index, then assign a value to that element: tbl[2][3] = 54; // see picture above Arrays with more than two dimensions are possible but not as common as 1 and 2 D arrays. We won’t go beyond 2D arrays in this course. COMP 110 23 Note Set #5 Aggregate Initialization of a Rectangular 2D Array A 2D array can use aggregate initialization as follows: int[][] value = {{1,2,3},{4,5,6},{7,8,9},{10,11,12}}; This creates an array of 4 rows and 3 columns. Each row is described by a series of values inside { } brackets. Expressions for multiple rows are separated by commas and enclosed in another set of { } brackets. Each row expression should contain the same number of values. Once a 2D array has been created, it can be printed by two nested loops. In the following example, the outer loop uses r as the loop counter and as the row index for the array. The inner loop uses c as the counter and as the column index. for (int r=0; r m) m = data[i]; } System.out.println(“max value is ” + m); There are several variations to this approach. For example, suppose you want to keep track of not only the min or max but the index at which the min or max was found. You must remember the “i” value within the loop as well as the actual value at that index. In fact, you can remember only the index value and recover the value stored at that index later. COMP 110 31 Note Set #5 Changing the Length of an Array in the Middle of a Program A major topic in programming and computer science is data structures. The next course after COMP 110 is COMP 182, and data structures are the main theme of the course. A data structure is a kind of variable that can hold a set of data values and make it easy for the program to manage that data by performing operations such as • insert a new value into the set • delete an item from the set • find out if some value is in the set or not • ... We could say that an array is a very simple data structure. But it is so simple that many of the operations that a real data structure supports are not really supported by an array. The problem is that an array has many limitations. Once an array has been allocated space and values have been assigned to each element, for example, it’s not possible to insert new values at the tail end of the array because there’s no room. int[] data = new int[5]; data[0] = 26; data[1] = 18; data[2] = 6; data[3] = 45; data[4] = 73; data 26 0 18 6 45 73 1 2 3 4 Here, we created an array of length 5, then assigned 5 values to elements with index 0 through 4. Now suppose we discovered that there’s actually a 6th value we’d like to store into the array. We’re out of luck because the array has a length of exactly 5, so there’s no more room. What we can do, though, is create a new array that is larger, copy the values from the old array into the new larger array, then add the new value at the end of the new larger array. int[] temp = new int[6]; // create a temporary array of length = 6 for (int i=0; i