CSC152 2004F, Class 21: Arrays Admin: * Exams due. (Another point of extra credit b/c I got the due time wrong.) * Somewhat harder than I anticipated, partially my fault * You can create more than one constructor * I happily answered a wide variety of questions * Parent weekend: Embarrass Eric Becking! * New assignment due Monday. * Monday: Go over the exam. Overview: * Arrays: A "primitive" data structure. * Syntax and semantics in Java. * Example use: Summing values. * Example use: Improving Fibonacci. Key topics: * Abstract data types and data structures * Two different, but related, things * ADTs can be the types of fields * Both relate to the way you organize data * Abstract data types are *abstract* * Focus on the methods we use to access the data * Data structures are *concrete* * Focus on the way we arrange data in memory * Example: Scheme List * Lists provide the methods: null, cons, car, cdr, empty? * Implemented with pairs * In general, we will design ADTs and then look at ways to implement them * Two general implementation strategies: Like lists, like vectors * To implement like vectors, we need a "primitive" data type like vectors * In Java, that primitive but compound data type is the array /Array ADT Issues/ * Philosophy * Mutable collection of values indexed by number * Accept that we lose "dynamicism": Arrays don't change size * Methods * Create a new vector * Get the ith element in an array * Modify the ith element. (Vectors are mutable, lists are dynamic) * Get their size /Implementation/ * "Hidden": Java gives it to you (as does Scheme) * Chunk of contiguous memory /Syntax and Semantics/ * Type TYPEOFCONTENTS[] * E.g., the type of an array of doubles is double[] grades = ... * Observation: String[] in main is an array of strings * To create a new array (NOT a vector) new TYPE[SIZE] * E.g., double[] grades = new double[12]; * Alternate way to create an array, including the initial values new TYPE[] { VALUES_SEPARATED_BY_COMMAS } * E.g., double[] grades = new double[] { 81.0, 83.0, 99.9 }; * To access the ith element NAME[i] * To change the ith element NAME[i] = EXP * To get the number of elements, NAME.length /Sample One: Fun with Grading/ * See code /Questions/ * Can you make it bigger or smaller? * Only by assigning a new array to the same name and copying values over. * What are the default values if you use new TYPE[SIZE] * It depends on the type * Integer: 0 * Boolean: I don't know, probably false * Real: 0.0 * Object (or any subclass): null * Strings are objects, so null * Can we have heterogenous arrays * Not of primitive types * Sort of with objects Object[] foo = new Object[100]; I can put in a Point and a String and a BigInteger and ... Object[] bar = new BigInteger[100]; I can put in BigIntegers and subclasses of BigInteger /Sample Two: Fibonacci Numbers/ Fib 0 = 0 Fib 1 = 1 nth element = (n-1)st element + (n-2)nd element 0 1 1 2 3 5 8 13 21 34 ... Why do we care? * Something to do with primes? * Follow patterns in nature: The Golden Ratio * Lots of other fun math