Lecter Java: Program design - Chapter 8: Arrays

ArraysCopyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.BackgroundProgrammer often need the ability to represent a group of values as a listList may be one-dimensional or multidimensionalJava provides arrays and the collection classesConsider arrays firstBasic terminologyList is composed of elementsElements in a list have a common nameThe list as a whole is referenced through the common nameList elements are of the same type — the base typeElements of a list are referenced by subscripting (indexing) the common nameJava array featuresSubscripts are denoted as expressions within brackets: [ ]Base (element) type can be any typeSize of array can be specified at run timeIndex type is integer and the index range must be 0 ... n-1Where n is the number of elementsAutomatic bounds checkingEnsures any reference to an array element is validData field length specifies the number of elements in the listArray is an objectHas features common to all other objectsArray variable definition stylesWithout initializationArray variable definition stylesWith initializationExampleDefinitionschar[] c;int[] value = new int[10];CausesArray object variable c is un-initialized Array object variable v references a new ten element list of integersEach of the integers is default initialized to 0Considerint[] v = new int[10];int i = 7;int j = 2;int k = 4;v[0] = 1;v[i] = 5;v[j] = v[i] + 3;v[j+1] = v[i] + v[0];v[v[j]] = 12;System.out.println(v[2]);v[k] = stdin.nextInt();Considerint[] v = new int[10];int i = 7;int j = 2;int k = 4;v[0] = 1;v[i] = 5;v[j] = v[i] + 3;v[j+1] = v[i] + v[0];v[v[j]] = 12;System.out.println(v[2]);v[k] = stdin.nextInt();Considerint[] v = new int[10];int i = 7;int j = 2;int k = 4;v[0] = 1;v[i] = 5;v[j] = v[i] + 3;v[j+1] = v[i] + v[0];v[v[j]] = 12;System.out.println(v[2]);v[k] = stdin.nextInt();Considerint[] v = new int[10];int i = 7;int j = 2;int k = 4;v[0] = 1;v[i] = 5;v[j] = v[i] + 3;v[j+1] = v[i] + v[0];v[v[j]] = 12;System.out.println(v[2]);v[k] = stdin.nextInt();Considerint[] v = new int[10];int i = 7;int j = 2;int k = 4;v[0] = 1;v[i] = 5;v[j] = v[i] + 3;v[j+1] = v[i] + v[0];v[v[j]] = 12;System.out.println(v[2]);v[k] = stdin.nextInt();Considerint[] v = new int[10];int i = 7;int j = 2;int k = 4;v[0] = 1;v[i] = 5;v[j] = v[i] + 3;v[j+1] = v[i] + v[0];v[v[j]] = 12;System.out.println(v[2]);v[k] = stdin.nextInt();Considerint[] v = new int[10];int i = 7;int j = 2;int k = 4;v[0] = 1;v[i] = 5;v[j] = v[i] + 3;v[j+1] = v[i] + v[0];v[v[j]] = 12;System.out.println(v[2]);v[k] = stdin.nextInt();8 is displayedConsiderint[] v = new int[10];int i = 7;int j = 2;int k = 4;v[0] = 1;v[i] = 5;v[j] = v[i] + 3;v[j+1] = v[i] + v[0];v[v[j]] = 12;System.out.println(v[2]);v[k] = stdin.nextInt();Suppose 3 is extractedConsiderSegmentint[] b = new int[100];b[-1] = 0;b[100] = 0;CausesArray variable to reference a new list of 100 integersEach element is initialized to 0Two exceptions to be thrown-1 is not a valid index – too small100 is not a valid index – too largeIndexOutOfBoundsExceptionConsiderPoint[] p = new Point[3];p[0] = new Point(0, 0);p[1] = new Point(1, 1);p[2] = new Point(2, 2);p[0].setX(1);p[1].setY(p[2].getY());Point vertex = new Point(4,4);p[1] = p[0];p[2] = vertex;ConsiderPoint[] p = new Point[3];p[0] = new Point(0, 0);p[1] = new Point(1, 1);p[2] = new Point(2, 2);p[0].setX(1);p[1].setY(p[2].getY());Point vertex = new Point(4,4);p[1] = p[0];p[2] = vertex;ConsiderPoint[] p = new Point[3];p[0] = new Point(0, 0);p[1] = new Point(1, 1);p[2] = new Point(2, 2);p[0].setX(1);p[1].setY(p[2].getY());Point vertex = new Point(4,4);p[1] = p[0];p[2] = vertex;ConsiderPoint[] p = new Point[3];p[0] = new Point(0, 0);p[1] = new Point(1, 1);p[2] = new Point(2, 2);p[0].setX(1);p[1].setY(p[2].getY());Point vertex = new Point(4,4);p[1] = p[0];p[2] = vertex;ConsiderPoint[] p = new Point[3];p[0] = new Point(0, 0);p[1] = new Point(1, 1);p[2] = new Point(2, 2);p[0].setX(1);p[1].setY(p[2].getY());Point vertex = new Point(4,4);p[1] = p[0];p[2] = vertex;ConsiderPoint[] p = new Point[3];p[0] = new Point(0, 0);p[1] = new Point(1, 1);p[2] = new Point(2, 2);p[0].setX(1);p[1].setY(p[2].getY());Point vertex = new Point(4,4);p[1] = p[0];p[2] = vertex;ConsiderPoint[] p = new Point[3];p[0] = new Point(0, 0);p[1] = new Point(1, 1);p[2] = new Point(2, 2);p[0].setX(1);p[1].setY(p[2].getY());Point vertex = new Point(4,4);p[1] = p[0];p[2] = vertex;Explicit initializationSyntaxExplicit initializationExampleString[] puppy = { "nilla“, “darby“, "galen", "panther" };int[] unit = { 1 };Equivalent toString[] puppy = new String[4];puppy[0] = "nilla"; puppy[1] = “darby";puppy[2] = "galen"; puppy[4] = "panther";int[] unit = new int[1];unit[0] = 1;Array membersMember lengthSize of the arrayfor (int i = 0; i < puppy.length; ++i) { System.out.println(puppy[i]);}Array membersMember clone()Produces a shallow copyPoint[] u = { new Point(0, 0), new Point(1, 1)};Point[] v = u.clone(); v[1] = new Point(4, 30);Array membersMember clone()Produces a shallow copyPoint[] u = { new Point(0, 0), new Point(1, 1)};Point[] v = u.clone(); v[1] = new Point(4, 30);Array membersMember clone()Produces a shallow copyPoint[] u = { new Point(0, 0), new Point(1, 1)};Point[] v = u.clone(); v[1] = new Point(4, 30);Making a deep copyExamplePoint[] w = new Point[u.length];for (int i = 0; i < u.length; ++i) { w[i] = u[i].clone();}Making a deep copySearching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for a valueSystem.out.println("Enter search value (number): ");int key = stdin.nextInt();int i;for (i = 0; i < data.length; ++i) { if (key == data[i]) { break; }}if (i != data.length) { System.out.println(key + " is the " + I + "-th element");}else { System.out.println(key + " is not in the list");}Searching for the minimum valueSegmentint minimumSoFar = sample[0];for (int i = 1; i < sample.length; ++i) { if (sample[i] < minimumSoFar) { minimumSoFar = sample[i]; }}ArrayTools.java method sequentialSearch()public static int sequentialSearch(int[] data, int key) { for (int i = 0; i < data.length; ++i) { if (data[i] == key) { return i; } } return -1; }Considerint[] score = { 6, 9, 82, 11, 29, 85, 11, 28, 91 };int i1 = sequentialSearch(score, 11);int i2 = sequentialSearch(score, 30);ArrayTools.java method sequentialSearch()public static int sequentialSearch(int[] data, int key) { for (int i = 0; i < data.length; ++i) { if (data[i] == key) { return i; } } return -1; }Considerint[] score = { 6, 9, 82, 11, 29, 85, 11, 28, 91 };int i1 = sequentialSearch(score, 11);int i2 = sequentialSearch(score, 30);ArrayTools.java method putList()public static void putList(int[] data) { for (int i = 0; i < data.length; ++i) { System.out.println(data[i]); } } Considerint[] score = { 6, 9, 82, 11, 29, 85, 11, 28, 91 };putList(score);public static int[] getList() { Scanner stdin = new Scanner(System.in); int[] buffer = new int[MAX_LIST_SIZE]; int listSize = 0; for (int i = 0; (stdin.hasNextInt()) && i < MAX_LIST_SIZE; ++i) { buffer[i] = stdin.nextInt(); ++listSize; } int[] data = new int[listSize]; for (int i = 0; i < listSize; ++i) { data[i] = buffer[i]; } return data;} ArrayTools.java method getList()ArrayTools.java – outlinepublic class ArrayTools { // class constant private static final int MAX_LIST_SIZE = 1000; // sequentialSearch(): examine unsorted list for key public static int binarySearch(int[] data, int key) { ... // valueOf(): produces a string representation public static void putList(int[] data) { ... // getList(): extract and return up to MAX_LIST_SIZE values public static int[] getList() throws IOException { ... // reverse(): reverses the order of the element values public static void reverse(int[] list) { ... // binarySearch(): examine sorted list for a key public static int binarySearch(char[] data, char key) { ...}Demo.javaimport java.util.*;public class Demo { // main(): application entry point public static void main(String[] args) { System.out.println(""); System.out.println("Enter list of integers:"); int[] number = ArrayTools.getList(); System.out.println(""); System.out.println("Your list"); ArrayTools.putList(number); ArrayTools.reverse(number); System.out.println(""); System.out.println("Your list in reverse"); ArrayTools.putList(number); System.out.println(); }}SortingProblemArranging elements so that they are ordered according to some desired schemeStandard is non-decreasing orderWhy don't we say increasing order?Major tasksComparisons of elementsUpdates or element movementSelection sortingAlgorithm basisOn iteration i, a selection sorting methodFinds the element containing the ith smallest value of its list v and exchanges that element with v[i]Example – iteration 0Swaps smallest element with v[0]This results in smallest element being in the correct place for a sorted resultSelection sortingAlgorithm basisOn iteration i, a selection sorting methodFinds the element containing the ith smallest value of its list v and exchanges that element with v[i]Example – iteration 0Swaps smallest element with v[0]This results in smallest element being in the correct place for a sorted resultSelection sortingAlgorithm basisOn iteration i, a selection sorting methodFinds the element containing the ith smallest value of its list v and exchanges that element with v[i]Example – iteration 1Swaps second smallest element with v[1]This results in second smallest element being in the correct place for a sorted resultSelection sortingAlgorithm basisOn iteration i, a selection sorting methodFinds the element containing the ith smallest value of its list v and exchanges that element with v[i]Example – iteration 1Swaps second smallest element with v[1]This results in second smallest element being in the correct place for a sorted resultArrayTools.java selection sortingpublic static void selectionSort(char[] v) { for (int i = 0; i < v.length-1; ++i) { // guess the location of the ith smallest element int guess = i; for (int j = i+1; j < v.length; ++j) { if (v[j] < v[guess]) { // is guess ok? // update guess to index of smaller element guess = j; } } // guess is now correct, so swap elements char rmbr = v[i]; v[i] = v[guess]; v[guess] = rmbr; }}Iteration i// guess the location of the ith smallest element int guess = i;for (int j = i+1; j < v.length; ++j) { if (v[j] < v[guess]) // is guess ok? // update guess with index of smaller element guess = j;}// guess is now correct, swap elements v[guess] and v[0]Multidimensional arraysMany problems require information be organized as a two-dimensional or multidimensional listExamplesMatricesGraphical animationEconomic forecast modelsMap representationTime studies of population changeMicroprocessor designExampleSegmentint[][] m = new int[3][];m[0] = new int[4];m[1] = new int[4];m[2] = new int[4];ProducesExampleSegmentfor (int r = 0; r < m.length; ++r) { for (int c = 0; c < m[r].length; ++c) { System.out.print("Enter a value: "); m[r][c] = stdin.nextInt(); }}ExampleSegmentString[][] s = new String[4][];s[0] = new String[2];s[1] = new String[2];s[2] = new String[4];s[3] = new String[3];ProducesExampleSegmentint c[][] = {{1, 2}, {3, 4}, {5, 6}, {7, 8, 9}};ProducesMatricesA two-dimensional array is sometimes known as a matrix because it resembles that mathematical conceptA matrix a with m rows and n columns is represented mathematically in the following mannerMatrix additionDefinition C = A + Bcij = a1ib1j + ai2b2j + . . . + ainbnjcij is sum of terms produced by multipling the elements of a’s row i with b’s column cMatrix additionpublic static double[][] add(double[][] a, double[][] b) { // determine number of rows in solution int m = a.length; // determine number of columns in solution int n = a[0].length; // create the array to hold the sum double[][] c = new double[m][n]; // compute the matrix sum row by row for (int i = 0; i < m; ++i) { // produce the current row for (int j = 0; j < n; ++j) { c[i][j] = a[i][j] + b[i][j]; } } return c;}