Data Structure Midterm Lesson Arrays

Data Structure Midterm Lesson Arrays

• 1.
  Introduction to Arrays
• 2.
  2 What are 1-Darrays?    An array is an object that is used to store a list of values of the same type.  It is made out of a contiguous block of memory that is divided into a number of "slots“ or varia  Each slot can be accessed by using its index (or subscript).  If there are N slots in an array, the indexes will be 0 through N-1.  The diagram on the right shows a 5-element array. The indexes are from 0 to 4  An array that uses a single subscript is called a one dimensional array.  Two dimensional arrays, three dimensional arrays, and higher dimensional arrays also exist:
• 3.
  3 1-D Array Declaration For any type T, T[ ] is a class, whose instances are arrays of type T.  Thus, the following statement declares a reference variable, b, of type T array: T[] b;  For any positive integer n, the following expression creates a new T[ ] object of size n and stores its reference in b: b = new T[n] ;  As usual, the two expressions can be combined together as: T[] b = new T[n] ;  For example, the following declares an int[] , grades, of size 10: int[ ] grades = new int[10];
• 4.
  4 1-D Array Declaration(cont’d)  The declaration of an array of size n creates n variables of the base type T.  These variables are indexed starting from 0 to n-1. They are called subscripted variables.  A subscripted variable can be used anywhere an ordinary variable of the same type can be used.  The slots of an array are initialized to the default value for their type.  Each slot of a numeric array is initialized to zero.  Each array object has a public instance variable, length, that stores the size of the array.  Thus, the following statement prints 10, the size of grades: System.out.println(grades.length);  Once an array has been constructed, its length does not change.  Other examples of 1D-array declaration are: double[ ] price = new double[500]; // each element is initialized to 0.0 boolean[ ] flag = new boolean[20]; // each element is initialized to false
• 5.
  5 Accessing elements ofa 1-D Array  A particular variable is accessed by indexing the array reference with the index (subscript) of the variable in square brackets: grades[4] = 20;  The following example, re-initializes each variable with twice its index: int[] grades = new int[10]; for(int i = 0; i < grades.length; i++) grades[i] = 2*i;  The use of grades.length instead of 10 makes the code more general.
• 6.
  6 Accessing elements ofa 1-D Array (cont'd )  The following prints the values of the array re-initialized by the example in the previous slide. for(int i = 0; i < grades.length; i++) System.out.print(grades[i] + “ “);  Output: 0 2 4 6 8 10 14 16 18  Note: Trying to access an element with an invalid index causes a run-time error: ArrayIndexOutOfBoundsException: int x = grades[10]; // causes run-time error
• 7.
  7 Accessing elements ofa 1-D Array (cont'd )  The indexes (subscripts) of an array must always be of integer type except long (int, char, short, byte).  An array index can be any expression that evaluates to an integer within the allowed index range: double[] val = new double[20]; int k = 3; val[0] = 1.5; val[1] = 10.0; val[2] = 15.5; val[k] = val[k-1] + val[k - 2]; // same as val[3] = val[2] + val[1] val[ k*2 + 3 ] = 24 + val[13]; // same as: val[ 9 ] = 24 + 0.0 System.out.println( "val[" + k + "] == " + val[k] ); // output: val[3] = 25.5 Note: the following are invalid because the index is not of type int, char, short, or byte: long k = 5L; val[k] = 33.2; val[8.0] = 75.5;
• 8.
  8 Using Subscripts withan Array Enhanced for loop » Cycle through array » Without specifying starting and ending points for loop control variable for(int val : scoreArray) System.out.println(val);
• 9.
  9 Initializer List  Initializerlist can be used to instantiate and initialize an array in one step: int[ ] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; char[ ] letterGrade = {’ A’ , ‘ B’ , ‘C’, ‘ D’ , ‘ F’ };  It is actually the compiler that fills the gap. Thus, in the first example, the compiler would add the following: int[] prime = new int[10]; prime[0] = 2; prime[1] = 3; ... prime[9] = 29;  Observe that when an initializer list is used:  The new operator is not required.  The size is not required; it is computed by the compiler.
• 10.
  10 Copying one arrayto another  Consider the following declarations: int[ ] array1 = {22, 3, 50, 7, 11, 13, 17}; int[ ] array2 = {3, 5, 8, 20, 0, 100, 40};  The assignment statement : array1 = array2; does not copy the contents of array2 to array1; it makes the reference array1 to refer to the array object referenced by array2. The object that was referenced by array1 becomes garbage.  To copy the contents of array2 to array1, code like the following is used: for(int k = 0; k < array2.length; k++) array1[k] = array2[k];
• 11.
  11 Array used asa Parameter Remember that a parameter is data that is supplied to a method just before it starts running. The following method prints the content of an int array passed to it as parameter: class MyArray { public void print (int[] x) { for(int i = 0; i < x.length; i++) System.out.print(x[i]+ " "); System.out.println(); } } The method is written using the parameter x to refer to the actual data that it will be supplied with. The method is written without referring to any particular data. When the print() method is running it has a reference to an array object in its parameter x.
• 12.
  12 Example(1) class ArrayDemo { publicstatic void main ( String[] args ) { MyArray operate = new MyArray(); int[] ar1 = { -20, 19, 1, 5, -1, 27 } ; System.out.print ("The array is: " ); operate.print( ar1 ); } } MyArray print(x) operate -20 19 1 5 -1 27 ar1 public static void print (int[] x) { for(int i = 0; i < x.length; i++) System.out.print(a[x]+ " "); System.out.println(); }
• 13.
  13 Parameter Connected toNew Data Could the main() method create a second array and use the print() method with it? Example (2): What is the output? class ArrayDemo { public static void main ( String[] args ) { MyArray operate = new MyArray(); int[] ar1 = { -20, 19, 1, 5, -1, 27 } ; int[] ar2 = {1, 2, 6, 3, 9, 5}; System.out.print("The array is: " ); operate.print( ar1 ); System.out.print("The second array is: " ); operate.print( ar2 ); } } The array is: -20 19 1 5 -1 27 The second array is: 1 2 6 3 9 5
• 14.
  14 Using Two-Dimensional and MultidimensionalArrays One-dimensional or single-dimensional array » Picture as column of values » Elements accessed using single subscript Two-dimensional arrays » Two or more columns of values » Rows and columns » Use two subscripts » Matrix or table int[][] someNumbers = new int[3][4];
• 15.
  15 View of aTwo-Dimensional Array in Memory
• 16.
  16 Using Two-Dimensional and MultidimensionalArrays (continued) int[][] rents = { {400, 450, 510}, {500, 560, 630}, {625, 676, 740}, {1000, 1250, 1600} }; public static void displayScores(int[] []scoresArray)
• 17.
  17 Using Two-Dimensional and MultidimensionalArrays (continued) Multidimensional arrays » More than two dimensions Create arrays of any size » Keep track of order of variables needed as subscripts » Don’t exhaust computer’s memory