| Presentation slides for | |
| Java Software Solutions | |
| Foundations of Program Design | |
| Third Edition | |
| by John Lewis and William Loftus | |
| Java Software Solutions is published by Addison-Wesley | |
| Presentation slides are copyright 2002 by John Lewis and William Loftus. All rights reserved. | |
| Instructors using the textbook may use and modify these slides for pedagogical purposes. | |
| Arrays are objects that help us organize large amounts of information | ||
| Chapter 6 focuses on: | ||
| array declaration and use | ||
| passing arrays and array elements as parameters | ||
| arrays of objects | ||
| sorting elements in an array | ||
| multidimensional arrays | ||
| the ArrayList class | ||
| polygons and polylines | ||
| more button components | ||
| An array is an ordered list of values |
| A particular value in an array is referenced using the array name followed by the index in brackets | |||||
| For example, the expression | |||||
| scores[2] | |||||
| refers to the value 94 (which is the 3rd value in the array) | |||||
| That expression represents a place to store a single integer which can be used wherever an integer variable can be used | |||||
| For example, value in an array can be assigned a value, printed, or used in a calculation | |
| scores[2] = 89; | |
| scores[first] = scores[first] + 2; | |
| mean = (scores[0] + scores[9])/2; | |
| System.out.println (“Top = “ + scores[5]); |
| An array stores multiple values of the same type | |||||
| That type can be primitive types or object references | |||||
| Therefore, we can create an array of integers, or an array of characters, or an array of String objects, etc. | |||||
| In Java, the array itself is an object | |||||
| Therefore the name of the array is a object reference variable, and the array itself must be instantiated | |||||
| The scores array could be declared as follows: | |||||
| int[] scores = new int[10]; | |||||
| Note that the type of the array does not specify its size, but each object of that type has a specific size | |||||
| The type of the variable scores is int[] (an array of integers) | |||||
| It is set to a new array object that can hold 10 integers | |||||
| See BasicArray.java (page xxx) | |||||
| Some examples of array declarations: | |||||
| float[] prices = new float[500]; | |||||
| boolean[] flags; | |||||
| flags = new boolean[20]; | |||||
| char[] codes = new char[1750]; | |||||
| Once an array is created, it has a fixed size | |||||
| An index used in an array reference must specify a valid element | |||||
| That is, the index value must be in bounds (0 to N-1) | |||||
| The Java interpreter throws an ArrayIndexOutOfBoundsException if an array index is out of bounds | |||||
| This is called automatic bounds checking | |||||
| For example, if the array codes can hold 100 values, it can be indexed using only the numbers 0 to 99 | |||||
| If count has the value 100, then the following reference will cause an exception to be thrown: | |||||
| System.out.println (codes[count]); | |||||
| It’s common to introduce off-by-one errors when using arrays | |||||
| Each array object has a public constant called length that stores the size of the array | |||||
| It is referenced using the array name (just like any other object): | |||||
| scores.length | |||||
| Note that length holds the number of elements, not the largest index | |||||
| See ReverseOrder.java (page xxx) | |||||
| See LetterCount.java (page xxx) | |||||
| The brackets of the array type can be associated with the element type or with the name of the array | |||||
| Therefore the following declarations are equivalent: | |||||
| float[] prices; | |||||
| float prices[]; | |||||
| The first format generally is more readable | |||||
| An initializer list can be used to instantiate and initialize an array in one step | |||||
| The values are delimited by braces and separated by commas | |||||
| Examples: | |||||
| int[] units = {147, 323, 89, 933, 540, | |||||
| 269, 97, 114, 298, 476}; | |||||
| char[] letterGrades = {'A', 'B', 'C', 'D', ’E'}; | |||||
| Note that when an initializer list is used: | |||||
| the new operator is not used | |||||
| no size value is specified | |||||
| The size of the array is determined by the number of items in the initializer list | |||||
| An initializer list can only be used only in the declaration of an array | |||||
| See Primes.java (page xxx) | |||||
| An entire array can be passed as a parameter to a method | |||||
| Like any other object, the reference to the array is passed, making the formal and actual parameters aliases of each other | |||||
| Changing an array element within the method changes the original | |||||
| An array element can be passed to a method as well, and follows the parameter passing rules of that element's type | |||||
| The elements of an array can be object references | |||||
| The following declaration reserves space to store 25 references to String objects | |||||
| String[] words = new String[25]; | |||||
| It does NOT create the String objects themselves | |||||
| Each object stored in an array must be instantiated separately | |||||
| See GradeRange.java (page xxx) | |||||
| The signature of the main method indicates that it takes an array of String objects as a parameter | |||||
| These values come from command-line arguments that are provided when the interpreter is invoked | |||||
| For example, the following invocation of the interpreter passes an array of three String objects into main: | |||||
| > java DoIt pennsylvania texas california | |||||
| These strings are stored at indexes 0-2 of the parameter | |||||
| See NameTag.java (page xxx) | |||||
| Objects can have arrays as instance variables | |||||
| Therefore, many useful structures can be created simply with arrays and objects | |||||
| The software designer must determine carefully an organization of data and objects that makes sense for the situation | |||||
| See Tunes.java (page xxx) | |||||
| See CDCollection.java (page xxx) | |||||
| See CD.java (page xxx) | |||||
| (Figure 6.3 here) |
| Sorting is the process of arranging a list of items in a particular order | |||||
| There must be some value on which the order is based | |||||
| There are many algorithms for sorting a list of items | |||||
| These algorithms vary in efficiency | |||||
| We will examine two specific algorithms: | |||||
| Selection Sort | |||||
| Insertion Sort | |||||
| The approach of Selection Sort: | ||
| select a value and put it in its final place into the sort list | ||
| repeat for all other values | ||
| In more detail: | ||
| find the smallest value in the list | ||
| switch it with the value in the first position | ||
| find the next smallest value in the list | ||
| switch it with the value in the second position | ||
| repeat until all values are in their proper places | ||
| An example: | |||||
| original: 3 9 6 1 2 | |||||
| smallest is 1: 1 9 6 3 2 | |||||
| smallest is 2: 1 2 6 3 9 | |||||
| smallest is 3: 1 2 3 6 9 | |||||
| smallest is 6: 1 2 3 6 9 | |||||
| See SortGrades.java (page xxx) | |||||
| See Sorts.java (page xxx) -- the selectionSort method | |||||
| Swapping is the process of exchanging two values | |
| Swapping requires three assignment statements | |
| temp = first; | |
| first = second; | |
| second = temp; | |
| The approach of Insertion Sort: | ||
| pick any item and insert it into its proper place in a sorted sublist | ||
| repeat until all items have been inserted | ||
| In more detail: | ||
| consider the first item to be a sorted sublist (of one item) | ||
| insert the second item into the sorted sublist, shifting the first item as needed to make room to insert the new addition | ||
| insert the third item into the sorted sublist (of two items), shifting items as necessary | ||
| repeat until all values are inserted into their proper positions | ||
| An example: | |||||
| original: 3 9 6 1 2 | |||||
| insert 9: 3 9 6 1 2 | |||||
| insert 6: 3 6 9 1 2 | |||||
| insert 1: 1 3 6 9 2 | |||||
| insert 2: 1 2 3 6 9 | |||||
| See Sorts.java (page xxx) -- the insertionSort method | |||||
| Integers have an inherent order, but the order of a collection of objects must be defined by the person defining the class | |||||
| Recall that a Java interface can be used as a type name and guarantees that a particular class implementes particular methods | |||||
| We can use the Comparable interface and the CompareTo method to develop a generic sort for a set of objects | |||||
| See SortPhoneList.java (page xxx) | |||||
| See Contact.java (page xxx) | |||||
| See Sorts.java (page xxx) | |||||
| Both Selection and Insertion sorts are similar in efficiency | |||||
| The both have outer loops that scan all elements, and inner loops that compare the value of the outer loop with almost all values in the list | |||||
| Therefore approximately n2 number of comparisons are made to sort a list of size n | |||||
| We therefore say that these sorts are of order n2 | |||||
| Other sorts are more efficient: order n log2 n | |||||
| A one-dimensional array stores a simple list of values | |||||
| A two-dimensional array can be thought of as a table of values, with rows and columns | |||||
| Because each dimension is an array of array references, the arrays within one dimension can be of different lengths | |||||
| Sometimes these are called ragged arrays | |||||
| A two-dimensional array element is referenced using two index values | |
| value = scores [3][6] | |
| To be precise, a two-dimensional array in Java is an array of arrays | |
| (Figure 6.6 here) | |
| See TwoDArray.java (page xxx) | |
| See SodaSurvey.java (page xxx) | |
| An array can have many dimensions | |||||
| If it has more than one dimension, it is called a multidimensional array | |||||
| Each dimension subdivides the previous one into the specified number of elements | |||||
| Each array dimension has its own length constant | |||||
| The ArrayList class is part of the java.util package | |||||
| Like an array, it can store a list of values and reference them with an index | |||||
| Unlike an array, an ArrayList object grows and shrinks as needed | |||||
| Items can be inserted or removed with a single method invocation | |||||
| It stores references to the Object class | |||||
Some Methods of the ArrayList Class
| (Figure 6.8 here) | |
| See Beatles.java (page xxx) |
| The ArrayList class is implemented using an array. | |
| The array expands beyond its initial capacity to accommodate additional elements | |
| Methods manipulate the array so that indexes remain continuous as elements are added or removed | |
| (Figure 6.9 here) | |
| Arrays often are helpful in graphics processing | |||||
| Polygons and polylines are shapes that can be defined by values stored in arrays | |||||
| A polyline is similar to a polygon except that its endpoints do not meet, and it cannot be filled | |||||
| See Rocket.java (page xxx) | |||||
| The Polygon class, defined in the java.awt package can be used to define and draw a polygon | |
| Two versions of the overloaded drawPolygon and fillPolygon methods take a single Polygon object as a parameter | |
| A Polygon object encapsulated the coordinates of the polygon |
Some Methods of the Polygon Class
| (Figure 6.9 here) |
| A check box is a button that can be toggled on or off | |
| A check box is represented by the JCheckBox class | |
| A change of state generates an item event | |
| See StyleOptions.java (page xxx) | |
| See StylePanel.java (page xxx) |
| A Font object is defined by the font name, the font style, and the font size | |
| The style of a font can be plain, bold, italic, or bold and italic together | |
| The itemStateChanged method of the listener responds when a check box changes state |
| A set of radio buttons represents a set of mutually exclusive options | |
| When a radio button from a group is selected, the other button currently on in the group is toggled off | |
| A radio button generates an action event | |
| See QuoteOptions.java (page xxx) | |
| See QuotePanel.java (page xxx) |
| Chapter 6 has focused on: | ||
| array declaration and use | ||
| passing arrays and array elements as parameters | ||
| arrays of objects | ||
| sorting elements in an array | ||
| multidimensional arrays | ||
| the ArrayList class | ||
| polygons and polylines | ||
| more button components | ||