Chapter xx .edu
Chapter 10
Arrays
Chapter Overview
Arrays are one of the fundamental means of structuring large amounts of data. We have touched on structures that act similar to arrays (Strings and ArrayList), but this is where we dive into indexed structures.
We start by assuming we have an array filled with data and examine the kinds of things we can do with it. Only after we’ve proved its usefulness do we bother with the details of creating and filling the array. Later sections deal with dynamic arrays, arrays of primitive types, and multi-dimensional arrays.
This chapter has a large example woven through it rather than including one that stands alone.
Table of Contents
Chapter Overview 1
Table of Contents 1
Chapter Objectives 2
Introduce/Review the Concepts 2
10.1 Using Arrays 2
10.1.1 Visualizing an Array 4
10.1.2 Accessing One Array Element 4
10.1.3 Swapping Array Elements 5
10.1.4 Processing All the Elements in an Array 6
10.1.5 Processing Matching Elements 7
10.1.6 Searching for a Specified Element 8
10.1.7 Finding an Extreme Element 9
10.1.8 Sorting an Array 10
10.1.9 Comparing Arrays and Files 12
10.2 Creating an Array 12
10.1.1 Declaration 13
10.1.2 Allocation 13
10.1.3 Initialization 13
10.3 Passing and Returning Arrays 15
10.4 Dynamic Arrays 17
10.4.1 Partially Filled Arrays 17
10.4.2 Resizing Arrays 18
10.4.3 Combining Approaches 20
10.5 Arrays of Primitive Types 21
Case Study 1: Number of Friends in Common 22
Case Study 2: Distribution of Number of Friends 23
Introduce/Review the Concepts 24
10.6 Multi-Dimensional Arrays 24
10.6.1 2D Array Algorithms 25
10.6.2 Allocating and Initializing a 2D Array 26
10.6.3 Arrays of Arrays 26
10.7 GUI: Animation 27
Summary 29
10.8 Patterns 29
10.9 Summary and Concept Map 30
Assignments 31
Key Terms 31
Chapter Objectives
| |[pic] |
Introduce/Review the Concepts
10.1 Using Arrays
| is a Web site to network people. An |[pic] |
|individual may post information about themselves, | |
|including pictures, audio clips, blog entries, etc. Online| |
|friends are listed, along with their pictures. Friends may| |
|also add messages to the web page. | |
|Obviously, there are many lists here: | |
|MySpace needs a list of all of the people enrolled. | |
|Each person has a list of all their friends, a list of all| |
|their blog entries, a list of all the pictures, a list of | |
|all the comments their friends have made, etc. | |
|We want to learn how to manipulate lists like this in a | |
|Java program. | |
The file myspace.txt contains information from 1,500 people with pages at (with identifiers changed to protect their identity). For each person, the data includes a fictitious name and id number, their actual gender, age, home town, country, date of last login, and a list of their friends (capped at 40).
Teaching Tip
Just for fun, consider generating your own data file with students from your class. The program that crawls MySpace is included in the instructor materials. It’s called HarvestMySpace. There’s a method named anonymize that should be commented out if you want your students to see their actual network. The program currently does not harvest the name.
|FYI: The program does a level-order traversal of the |[pic] |
|friendship tree (graph, actually). The shallowest | |
|spanning tree looks roughly as shown on the right. The| |
|lowest level is not necessarily completely filled. | |
|For the data provided, the original person has 28 | |
|friends listed, 520 friends of friends, and 951 | |
|friends of friends of friends. | |
|We could use an ArrayList for this (if you covered them in|[pic] |
|Chapter 8). But how is an ArrayList implemented? With one| |
|of the more fundamental programming constructs, present in| |
|almost every programming language: the array. | |
10.1.1 Visualizing an Array
We’ll start assuming we have an array populated with data. We’ll discuss creating arrays and filling them with data later.
|Items to discuss: |[pic] |
|persons is a reference variable. | |
|“Fields” are specified with numbers (the index). | |
|Index can be a literal or a calculated value (huge | |
|advantage!). | |
|A public final instance variable, length, says how many | |
|elements there are. | |
|Index values run between 0 and length-1. | |
|It’s easy to specify how many elements should be in the | |
|array. | |
10.1.2 Accessing One Array Element
|The lines of code appear in pairs – the first without |[pic] |
|arrays and the second the same task with arrays. The | |
|conclusion should be that you can do anything with one | |
|element in the array that you can do with a simple | |
|variable of the same type. | |
10.1.3 Swapping Array Elements
|Trace this carefully to help students become more familiar|[pic] |
|with arrays – particularly that they can use variables to | |
|access elements. Note the assumption that we are calling a| |
|particular method call: swap(1,2). It could just as easily| |
|be swap(5, 2). | |
| |[pic] |
10.1.4 Processing All the Elements in an Array
|Doing something with all the elements in the array is a |[pic] |
|common activity. Note that these examples work no matter | |
|if there are 4 people in the array or 4 million. | |
|This is the first use of the length instance variable. | |
|Point out that both tasks have the same structure to loop | |
|over all the elements. | |
|The foreach loop is a handy shortcut. |[pic] |
10.1.5 Processing Matching Elements
|Quick Quiz |[pic] |
|1. Change countMinors to use a for-each loop. | |
|public int countMinors2() | |
|{ int count = 0; | |
|for(Person p : this.persons) | |
|{ if (p.getAge() < 18) | |
|{ count += 1; | |
|} | |
|} | |
|return count; | |
|} | |
|2. Write a method with two parameters, minAge and gender. It prints | |
|the names and ages of all the persons who match the gender and are at | |
|least minAge years old. | |
/** Print the names and ages of persons meeting age and gender criteria. */
public void print(int minAge, Gender gender)
{ for(Person p : this.persons)
{ if (p.getAge() >= minAge && p.getGender() == gender)
{ System.out.println(p.getName() + " " + p.getAge());
}
}
}
10.1.6 Searching for a Specified Element
|Early returns out of loops is a contentious subject among CS |[pic] |
|educators. After years of struggling to get my students to | |
|write loops without an early return, I read a paper by Eric | |
|Roberts at Stanford (see | |
|). I was persuaded. If| |
|you’re not, delete this slide and go with the next one. | |
| | |
|Issues to discuss: | |
|Two cases: element is found, element isn’t found. | |
|What to return in each case. | |
|Checking for not-found case in the client code. |[pic] |
|That return immediately terminates execution of the method (in | |
|the early return version). | |
10.1.7 Finding an Extreme Element
|I’ve found that good naming can really help with this |[pic] |
|algorithm. Naming the holder variable youngestSoFar or | |
|minSoFar or ___SoFar helps emphasize the process that’s | |
|happening and the possibility that the value might change.| |
| | |
| | |
|Issues: | |
|This compares the first element to itself. | |
|Fails if the array happens to be empty. | |
|If more than one meets the criteria… |[pic] |
|Sometimes it’s useful to return the index instead of the | |
|object. | |
10.1.8 Sorting an Array
|The diagrams at the bottom show a sample array to start |[pic] |
|with (left) and the way it should finish (right). The | |
|arrays of letters below each one is an abbreviation we’ll | |
|use in a trace. Notice that the letters are the same as | |
|the first initial in the more complete picture. | |
| |[pic] |
|Take a few moments to trace the algorithm. Note that the |[pic] |
|“sorted part” starts out completely empty! That’s OK. | |
|Point out the patterns in the pcode. A variation of | |
|process all elements (the overall loop), find an extreme, | |
|and swap. | |
|Here’s a version of the code that uses helper methods to |[pic] |
|make the code clear. | |
| |[pic] |
|Here’s the algorithm again, written as a single method. It|[pic] |
|sorts by age, to get rid of the complexities of comparing | |
|strings. | |
| | |
|You may want to mention that the Java library has sorting | |
|methods in the class java.util.Arrays. Using them is | |
|considerably easier than writing your own sort method and | |
|the code probably runs faster. Using them relies on | |
|polymorphism (Chapter 12). More coverage then. | |
10.1.9 Comparing Arrays and Files
|Arrays and files are sometimes confused by students |[pic] |
|because they both store many records. Take a moment to | |
|contrast them. | |
|Summarize to say they’re complimentary. Use a file for | |
|long-term storage. Read them into an array for processing,| |
|then write them to a file again. (Yes, this simplifies | |
|files – they can be random access; we often read only the | |
|record from the file that we need rather than the whole | |
|thing into an array, etc. But don’t needlessly complicate | |
|things for them.) | |
10.2 Creating an Array
|Here’s the overview of what we need to do. |[pic] |
10.1.1 Declaration
10.1.2 Allocation
|If you know the size of the array at compile time, the |[pic] |
|declaration and allocation can be combined. If you don’t, | |
|keep them separate. | |
10.1.3 Initialization
|You might do this for small arrays. What about large |[pic] |
|ones? | |
|Problem: how do you know how large to make the array? |[pic] |
| | |
|Reading the array twice is s-l-o-w. It works, but we can | |
|do better! | |
|Here’s another approach: store the number of records at |[pic] |
|the beginning of the file. | |
| | |
|Note: We’ll explore still another approach when we learn | |
|how to reallocate an array. | |
10.3 Passing and Returning Arrays
|The general principle we want to illustrate is that you |[pic] |
|can pass arrays to methods and return them from a method. | |
|We’ll do this by considering an interesting algorithm, | |
|extracting a subset from an array. | |
|Note that returning the values in an array gives us a lot | |
|of flexibility (compared to, for example, printing them). | |
|A couple of things to note: |[pic] |
|An array can be allocated and used within a method – just | |
|like any other temporary variable. | |
|That array (subset) can be passed as an argument to a | |
|method (fillSubset). | |
|An array can be returned, too. | |
|The fillSubset algorithm is tricky! Spend some time |[pic] |
|tracing it. | |
|Here’s the code for fillSubset. The helper method |[pic] |
|countSubset is left as an exercise for the students. | |
|Notes: | |
|The array is passed in as a parameter. Perhaps review that| |
|ss is an alias to the array declared in extractSubset. | |
|Changes made via ss will be reflected in the object | |
|(array) it references. | |
|We have two ints, one to keep track of our progress in | |
|each array. | |
|Once the subset array is full, we can stop the loop. | |
10.4 Dynamic Arrays
So far, we haven’t added anything to an array; nor have we deleted elements. To be useful, that needs to change. For example, MySpace must be able to add new members to its overall list. Each member’s page has an associated list of friends, blog entries, etc., which may also have elements added or deleted.
We’ll look at two main approaches, with their pitfalls. Finally, we’ll see that the best solution is a combination of the two.
10.4.1 Partially Filled Arrays
|Talking points: |[pic] |
|The two parts of an array. When we add an element, one | |
|part grows, one part shrinks. | |
|Either part of the array may be empty. | |
|By convention, 0..size-1 holds the valid entries and | |
|size..length-1 is space for growth. | |
|This explicitly separates the size (number of elements | |
|stored) from the length (number of elements it can store).| |
• size can be interpreted two different ways:
• The number of elements currently stored in the array.
• The index of the next empty/free position in the array.
|Note the use of this.size rather than this.persons.length |[pic] |
|to determine the number of elements to print. | |
|Quick Quiz | |
|Modify add.. | |
|public void add(Person p) | |
|{ if (this.size < this.length) | |
|{ this.persons[this.size] = p; | |
|this.size += 1; | |
|} else | |
|{ System.out.println(…); | |
|} | |
Inserting into a Sorted Array
|This problem forms the basis of Problem 10.8. Decide how |[pic] |
|thoroughly you want to discuss it. | |
|One point that can trip up students is that the elements | |
|need to be shuffled down, starting with the last element | |
|and moving up. | |
Problems with Partially Filled Arrays
Discussion
Partially filled arrays allow us to add and delete elements, as we wanted. But what are the problems with partially filled arrays?
1. There is still a hard upper limit that can’t be exceeded.
2. Wasted space.
10.4.2 Resizing Arrays
|The diagram fades out the old array to illustrate it being|[pic] |
|replaced with the new one. | |
|The array is not sorted, so we just add the new element at| |
|the end. If it were sorted, an algorithm like the one just| |
|discussed could be incorporated. | |
| |[pic] |
|The code to do this is not hard! To the rest of the |[pic] |
|program, it appears as if the array simply has one more | |
|element than it did before. | |
| | |
|But, there is a problem here. Step 2 takes a lot of time! | |
|150,000 elements is not particularly many, yet it takes |[pic] |
|nearly 13 minutes! | |
10.4.3 Combining Approaches
|The key is to enlarge the array by more than a single |[pic] |
|element. It’s often doubled (a carryover from convenience | |
|of analysis, I think). You could have less wasted space | |
|(but more time to insert) by enlarging by, say 25%, | |
|instead of 100%. Just make sure you enlarge by at least 1!| |
|The same run-time experiment as shown on the earlier slide|[pic] |
|gives a time of 0.047 seconds to insert 150,000 elements. | |
|Much better than nearly 13 minutes and only slightly worse| |
|than 0.015 seconds for the pure partially filled array. | |
10.5 Arrays of Primitive Types
|Declarations are like arrays of objects: |[pic] |
|«type»[ ] «varName» | |
|where «type» is int or double or … | |
|Declaration, allocation, initialization is the same. | |
Case Study 1: Number of Friends in Common
|Teaching Tip |[pic] |
|You might start this one with a role play. Get two | |
|volunteers. Hand each one a list of their “friends” and | |
|ask them how many are in common. | |
|Or have them stand back-to-back in front of the chalkboard| |
|so they can’t see the other’s list. Put the lists on the | |
|board so the rest of the class can see both. | |
|To discuss: |[pic] |
|Using an array of int is not that different from using an | |
|array of objects. | |
|numFriendsInCommon asks other whether myFriend is one of | |
|its friends. When other checks this (by running | |
|hasFriend), it’s using other’s list of friend IDs. | |
Case Study 2: Distribution of Number of Friends
|This chart shows that lots of people – more than 400 – |[pic] |
|have 0 friends listed in the MySpace data. It also shows | |
|that it’s quite rare to have more than about 15 friends. | |
|That said, remember that the program harvesting the data | |
|limits each person to 40 friends and that it only lists | |
|friends who are in the list of 1,500 people. So this says | |
|nothing about real friendship patterns on MySpace. Sigh. | |
Teaching Tip
Here’s another opportunity for a role play. Ask for a volunteer. Tell him/her that you’re going to read off a list of numbers between 1 and 10. At the end, you want to know how many of each number there were. Make it obvious that the chalkboard can be used.
Chances are good that the student will make a chart and enter a tick for each number you read. We just need to automate that process. We’ll use an array of numbers to represent the chart.
The key point here is that in this case, the indices to the array actually mean something. The value of nums[1] is the number of times 1 has shown up in the data.
|Java trivia: The elements in a newly allocated array are |[pic] |
|initialized to their default value – 0 for integers, null | |
|for objects. Hence, no initialization is required here. | |
| | |
|Once again, the point of this case study is that sometimes| |
|the indices mean something more than just the position in | |
|the list. In this case, the number of friends that a | |
|person has. | |
Introduce/Review the Concepts
10.6 Multi-Dimensional Arrays
|This reverts to the example in the book. A charitable |[pic] |
|organization (Big Brother/Big Sister) has a summary of | |
|donations by source for each month of the year. | |
| | |
|Here’s a more accurate view. The indices are integers, as |[pic] |
|with 1d arrays. If they mean something (as in the | |
|previous section), we need to maintain that meaning | |
|outside of the array (by convention, in another array that| |
|lists the names of the months, etc). | |
10.6.1 2D Array Algorithms
|Talking points: |[pic] |
|Nested loop structure. | |
|Finding the number of rows vs. finding the number of | |
|columns. | |
|The role of print vs. println. | |
|We see the same nested loop structure here. Very common |[pic] |
|for 2D arrays! | |
|Just because an array has 2 dimensions doesn’t necessary |[pic] |
|imply that we use all of them or have 2 nested loops! | |
10.6.2 Allocating and Initializing a 2D Array
|Use the same steps for a 2D array as for a 1D array: |[pic] |
|declare, allocate, initialize. | |
|Point out differences: | |
|Another set of brackets to declare and allocate. | |
|Another loop to initialize. | |
10.6.3 Arrays of Arrays
|The rectangular table view of 2D arrays works most of the |[pic] |
|time. Sometimes it’s helpful to view the way it’s | |
|actually stored in the computer: as an array of arrays. | |
|This allows things like: | |
|Swapping two entire rows of the array with 3 assignment | |
|statements. | |
|Passing an entire row of the array to a method. | |
|Having rows of different lengths. | |
10.7 GUI: Animation
|Same example as the book (. Other ideas welcome… |[pic] |
|Problem 10.16 is a wonderful assignment using 2D arrays to| |
|manipulate images. If you assign that, this could be | |
|replaced with an introduction to the assignment. | |
| | |
|Consider running the finished program to demonstrate. | |
|The parameters to the constructor are removed here to |[pic] |
|allow more focus on the array and threads. Same for the | |
|array’s direction of traversal. | |
|Discussion points: | |
|Allocation and initialization of the array. | |
|currentImage is an index into the array giving the image | |
|to display. | |
|Construction of the image file names. | |
|implements Runnable is set up for stuff on the next slide.| |
|Parameters to increase flexibility would be nice – see the| |
|text! | |
|paintComponent gets the image to display out of the array,|[pic] |
|and then draws it on the graphics canvas. | |
|The run method selects the next image, calls repaint, | |
|waits – over and over and over. | |
|Here’s the main method to put it all together. |[pic] |
| | |
|It’s probably worth noting that another form of animation | |
|takes the same image and redraws it at different locations| |
|on the screen – like the robots moving from intersection | |
|to intersection. That does not require an array of | |
|different images! | |
Summary
10.8 Patterns
|There are many array-based patterns that are not included |[pic] |
|here or in the text. Consider assigning some for homework.| |
| |[pic] |
| |[pic] |
10.9 Summary and Concept Map
| |[pic] |
| |[pic] |
Assignments
Give students practice in seeing and generalizing patterns by assigning parts of Written Exercise 10.3.
One or two smaller programming assignments might include 10.5, 10.8, 10.9, or 10.10.
For practice with 2D arrays, the image manipulation program in Programming Project 10.16 can’t be beat. For beginning practice with arrays, the robot bucket brigade in 10.13 gives the comfort of a robots problem. 10.15 gives more of a mathematical bent, while 10.17 gives lots of practice working with existing classes and reading documentation (and, of course, arrays!).
Key Terms
column-major order—A 2D array algorithm that accesses the array such that the column changes more slowly than the row. See also: row-major order.
index—The position of one element within an ordered collection, such as an array, a string, or an ArrayList.
key—A value used to uniquely identify another value.
partially filled array—An array that uses the elements with indices 0..n-1 to store values, where n ≤ s, the size of the array. n is stored in an auxiliary variable.
random access—A property of an information collection where every item can be accessed as easily and as fast as every other item.
row-major order—A 2D array algorithm that accesses the array such that the row changes more slowly than the column. See also: column-major order.
search—The process of attempting to locate one value in a collection of values.
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.