Bài giảng Chapter 10: Arrays

Chapter 10Arrays©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Chapter 10 ObjectivesAfter you have read and studied this chapter, you should be able toManipulate a collection of data values, using an array.Declare and use an array of primitive data types in writing a program.Declare and use an array of objects in writing a program.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Chapter 10 Objectives, cont.After you have read and studied this chapter, you should be able toDefine a method that accepts an array as its parameter and a method that returns an array.Describe how a two-dimensional array is implemented as an array of arrays.Manipulate a collection of objects, using lists and maps.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.1 Array BasicsIn Java, an array is an indexed collection of data values of the same type.Arrays are useful for sorting and manipulating a collection of values.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.1Sample array: Monthly rainfall averages and their variation from the annual average.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.1 Array BasicsSquare brackets [] are used to declare an array.To declare an array, we may attach the brackets to either the data type or the variable name. An array named rainfall of type double, may be stated either asdouble [] rainfall;ordouble rainfall [];©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.1 Array BasicsIn Java, an array is a reference data type. We use the new operator to allocate the memory to store the values in an array.rainfall = new double [12]; //creates an array of size 12.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.2An array of 12 double values.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.1 Array BasicsWe use a single identifier to refer to the whole collection in the array.We use an indexed expression to refer to the individual values of the collection. Arrays use zero-based indexing.An individual value in an array is called an array element.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.3An array of 12 double values after all 12 are assigned values.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.1 Array BasicsAn array has a public constant length for the size of an array.for (i=0; i oldest.getAge() ) { //found an older person oldest = person[i]; }}System.out.println("Oldest : " + oldest.getName() + " is " + oldest.getAge() + " years old."); ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.2 Arrays of ObjectsSystem.out.println("Youngest: " + youngest.getName() + " is " + youngest.getAge() + " years old.");//----- Search for a particular person ------// String searchName = JOptionPane.showInputDialog(null, "Name to search:"); int i = 0; while ( i < person.length && //still more persons to search !person[i].getName().equals( searchName ) ) { i++; } ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.2 Arrays of Objects if (i == person.length) { //not found - unsuccessful search System.out.println( searchName + " was not in the array" ); } else { //found - successful search System.out.println("Found " + searchName + " at position " + i); } }}©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.6An array of Person objects with two Person variables.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.2 Arrays of ObjectsDeleting objects from an array requires us to search for the Person object to be removed.When the object is located, there are two ways to delete the object.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.2 Arrays of ObjectsThe first approach is to set the array element to null. Because each array element is a reference to an object, setting the element to null accomplishes this task easily.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.7Approach 1 deletion: Setting a reference to null. The array length is 4.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.2 Arrays of ObjectsAny index position may be set to null, but this approach creates “holes” in the array.The second approach to deleting an object will order the elements so the real references occur at the beginning and the null references at the end.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.2 Arrays of ObjectsPacking the elements so the real references occur at the beginning and the null references occur at the end.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.2 Arrays of ObjectsWe must fill the holes. There are two possible approaches:If an object at position J is removed (i.e., set to null), then elements from position J+1 up to the last non-null reference are shifted one position lower. Finally, the last non-null reference is set to null.Replace the removed element by the last element in the array.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.8Approach 2 deletion: Replace the removed element with the last element in the array. The array length is 4.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.2 Arrays of ObjectsNote that assigning null to an array element will not erase the object. This operation does initiate a chain reaction that will eventually erase the object from memory.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.2 Arrays of ObjectsA single object may have multiple references pointing to it:Person p1, p2;p1 = new Person( );p2 = p1;©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.2 Arrays of ObjectsWhen an object has no references pointing to it, the system will erase the object and make the memory space available again.Erasing an object is called deallocation of memory.The process of deallocating memory is called garbage collection. Garbage collection is automatically performed in Java.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.3 Passing Arrays to MethodsArrays and objects are reference data types, so the rules for passing an object to a method and returning an object from a method apply to arrays.Consider an example method that returns the index of the smallest element in an array of real numbers:©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.3 Passing Arrays to Methodspublic int searchMinimum(double[] number) { int indexOfMinimum = 0; for (int i = 1; i < number.length; i++){ if (number[i] < number[indexOfMinimum]) { //found a smaller element indexOfMinimum = i; } }return indexOfMinimum;}To call this method (from a method of the same class), we write©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.3 Passing Arrays to Methodsdouble[] arrayOne;//create and assign values to arrayOne...//get the index of the smallest element of arrayOneint minOne = searchMinimum(arrayOne);//output the resultSystem.out.print(“Minimum value in Array One is ”);System.out.print(arrayOne[minOne] + “at position ” + minOne);...©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.3 Passing Arrays to MethodsRemember that when an array is passed to a method, only its reference is passed. A copy of the array is not created in the method.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.9APassing an array to a method means we are passing a reference to an array.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.9BPassing an array to a method means we are passing a reference to an array.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.10APassing an array to a method means we are passing a reference to an array.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.10BPassing an array to a method means we are passing a reference to an array.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.3 Passing Arrays to MethodsNext we will consider an example in which we return an array from a method.This method inputs double values and returns the values as an array of double.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.3 Passing Arrays to Methodspublic double[] readDoubles() { double[] number; int N = Integer.ParseInt( JOptionPane.showInputDialog(null, “How many input values?”)); number = new double[N]; for (int i = 0; i<N; i++){ number[i] = Double.parseDouble( JOptionPane.showInputDialog(null, “Number ” + i)); } return number;}©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.3 Passing Arrays to MethodsThe readDoubles method is called:double[] arrayOne;//assign values to arrayOnearrayOne = readDoubles();Because a new array is created by the method, we do not have to create an array from the calling side. Doing so will not cause an error, but it is a wasteful operation.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.3 Passing Arrays to MethodsFigures 10.11 and 10.12 examine the effects of creating a local array and not returning it.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.11AThe effect of creating a local array and not returning it.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.11BThe effect of creating a local array and not returning it.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.12AThe effect of creating a local array and not returning it.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.12BThe effect of creating a local array and not returning it.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.5 Two-Dimensional ArraysIn Java, data may be organized in a two-dimensional array. A table is an example of a two-dimensional array.In a two-dimensional array, two indices (in a table, one for the row and one for the column) are used to refer to the array element.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.5 Two-Dimensional ArraysTo declare our example array, we state:double[][] payScaleTable;or double payScaleTable[][];and create the array aspayScaleTable = new double[4][5];©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.15Examples of information represented as tables.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.5 Two-Dimensional ArraysTo refer to an element at the second column (column 1) of the third row (row 2), we saypayScaleTable[2][1]Nested-for loops are useful for manipulating two-dimensional arrays.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.16Accessing an element of a two-dimensional array.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.5 Two-Dimensional ArraysThe concept of the two-dimensional array in Java is just that: a concept. There is no explicit structure called the “two-dimensional array” in Java. The two-dimensional array concept is implemented by using an array of arrays.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.5 Two-Dimensional ArraysThe sample array creationpayScaleTable = new double[4][5];is a shorthand forpayScaleTable = new double [4][ ];payScaleTable[0] = new double [5];payScaleTable[1] = new double [5];payScaleTable[2] = new double [5];and so on.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.17AExecuting the statements on the left in sequence will create the array of arrays shown on the right.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 10.17B©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.5 Two-Dimensional ArraysThe expressionpayScaleTable.lengthrefers to the length of the payScaleTable array itself.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.5 Two-Dimensional ArraysThe expressionpayScaleTable[1].lengthrefers to the length of the array stored at row 1 of payScaleTable.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.5 Two-Dimensional ArraysAn array that is part of another array is called a subarray.An array of arrays may be initialized when it is created.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.5 Two-Dimensional ArraysSubarrays may be different lengths. ExecutingtriangularArray = new double[4][ ];for (int i = 0; i < 4; i++) triangularArray[i] = new double [i + 1]; results in an array that looks like:©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsThe java.util library contains high-power classes for maintaining a collection of objects. These classes are collectively referred to as the Java Collection Framework (JCF).©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsThe List interface is one useful feature that can help us manage large numbers of objects.An interface defines the behavior of a class; a list of public methods without method bodies.We cannot create an instance of an interface.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsTwo classes in the JCF implement the List interface:ArrayListLinkedListThe ArrayList class uses an array to manage data.The LinkedList class uses a technique called linked-node representation.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsTo use the List interface, we declare the variable as List and assign an instance of the class that implements the List interface to it:List myList;...myList = new ArrayList( );This approach permits a quick change of the implementation class if necessary.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsThe default constructor will create an empty list with an initial capacity of 10. It is possible to increase the capacity of a list. However, it is better to create a list with the actual capacity we need, if we know in advance what that capacity is.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsThe add method allows us to add objects to the list.The capacity method gives us the current capacity of a list.To find out the number of objects contained in a list, we use its size method.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsThe remove method takes an element’s index as its parameter and allows us to remove an element from a list.The get method allows us to access objects stored in a list by giving their index position in the list.The iterator method also allows us to scan the elements inside a list or other JCF collection classes.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsWhen we call a list’s iterator method, an Iterator object (an instance of a class that implements the Iterator interface) that supports two methods, hasNext and next, is returned.hasNext returns true if the iterator has more elements to access.Calling next if there are no more elements to access will result in an error.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsThe iterator method is supported by many other java.util classes.A list cannot include primitive data values as its elements, but wrapper classes can adapt the values to acceptable list objects.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsTwo classes implement the Map interface: HashMapTreeMapTreeMap implements a subinterface of Map called SortedMap, where the entries in the map are sorted.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsA map consists of entries. Each entry is divided into two parts:keyvalueDuplicate keys are not allowed in the map.Both the key and the value may be instances of any class.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsA map may be characterized as an expandable array with instances of any class as its indices. The main advantage of a map is its performance in locating an entry, given the key.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsWe create an instance of a map:Map table;...table = new TreeMap();We add the key-value pairs to the map: table.put(“CS0101”, “Great course. Take it.”);The first argument is the key. The second argument is the value.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsTo remove an entry from a map, we use its remove method and pass the key as the argument.To retrieve all entries in the map, we use the entrySet method.To access all entries in a map, we use the entrySet method to obtain a set of entries, then use the iterator method as in the ArrayList example.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.10.6 Lists and MapsThe getKey and getValue methods are two particularly useful methods in the interface.These method retrieve the map entry’s key and value, respectively.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.