DOC PREVIEW
Penn CIT 594 - Arrays

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

ArraysThe array data structureArray variations IArray variations IIArrays in Java IArrays in Java IIArrays in Java IIISubarraysArrays as ADTsTwo-dimensional arrays ITwo-dimensional arrays II2D arrays in JavaRagged arraysInserting an element into an arrayDeleting an element from an arrayConclusionsThe EndArrays2The array data structure•An array is an indexed sequence of components–Typically, the array occupies sequential storage locations–The length of the array is determined when the array is created, and cannot be changed–Each component of the array has a fixed, unique index•Indices range from a lower bound to an upper bound–Any component of the array can be inspected or updated by using its index•This is an efficient operation: O(1) = constant time3Array variations I•The array indices may be integers (C, Java) or other discrete data types (Pascal, Ada)•The lower bound may be zero (C, Java), one (Fortran), or chosen by the programmer (Pascal, Ada)•In most languages, arrays are homogeneous (all components must have the same type); in some (Lisp, Prolog) the components may be heterogeneous (of varying types)4Array variations II•In an object-oriented language, arrays may be objects (Java) or not objects (C++)•Arrays may carry additional information about themselves, such as type and length (Java), or may consist only of their components (C, C++)–I will use the terms reflective and non-reflective, respectively, to refer to these two types of arrays–This is not standard terminology, but it is consistent with other uses of the terms5Arrays in Java I•Array indices are integers•An array of length n has bounds 0 and n-1•Arrays are homogeneous–However, an array of an object type may contain objects of any subtype of that object•For example, an array of Animal may contain objects of type Cat and objects of type Dog•An array of Object may contain any type of object (but cannot contain primitives)6Arrays in Java II•Arrays are objects–Arrays are allocated by new, manipulated by reference, and garbage collected–However, the usual bracket notation a[i] is provided as syntactic sugar•Arrays are reflective–a.length is the length of array a–a.getClass() is the type of array a•An array of integers has type [I•An array of Strings has type [Ljava.lang.String;7Arrays in Java III•Here’s one way to visualize an array in Java:myArray0123 17 23948 3class tag[Ilength48Subarrays•A subarray is a consecutive portion of an array•Java provides no language support for subarrays•To use a subarray, you must keep track of (1) the array itself, (2) the lower bound, and (3) the upper bound•Typically, these will be three parameters to a method that does something with the subarray1 2 3 5 8 13 21 341[I 10 55array a0 1 2 3 4 5 6 7 8 9subarray a[2...6]9Arrays as ADTs•An array is an Abstract Data Type–The array type has a set of values•The values are all the possible arrays–The array type has a set of operations that can be applied uniformly to each of these values•The only operation is indexing•Alternatively, this can be viewed as two operations:–inspecting an indexed location–storing into an indexed location–It’s abstract because the implementation is hidden: all access is via the defined operations10Two-dimensional arrays I•Some languages (Fortran, Pascal) support two-dimensional (2D) arrays:•A two-dimensional array may be stored in computer memory in either of two ways:a cbi kje gfdlhlogical viewrowscolumnsa cb i kje gfd lhrow 0 row 1 row 2row major order:a ie k hdf cjb lgcol 0 col 1 col 2 col 3column major order:11Two-dimensional arrays II•In a 2D array, we generally consider the first index to be the row, and the second to be the column: a[row, col]0,0 0,1 0,2 0,3 0,41,0 1,1 1,2 1,3 1,42,0 2,1 2,2 2,3 2,43,0 3,1 3,2 3,3 3,40123 columns0 1 2 3 4rows•In most languages we don’t need to know the implementation--we work with this abstraction122D arrays in Java•Java doesn’t have “real” 2D arrays, but array elements can themselves be arrays:–int x[][] denotes an array x of array components, each of which is an array of integer components•We can define the above array like this:x = new int[5][8];and treat it as a regular 2D array•This is an array of 5 arrays–Each subarray is an array of 8 ints•However, we can do fancier things than this with arrays in Java13Ragged arrays int ragged[][] = new int[4][]; for (int i = 0; i < 4; i++) { ragged[i] = new int[i + 1];} for (int i = 0; i < 4; i++) { for (int j = 0; j < ragged[i].length; j++) { ragged[i][j] = 10 * i + j; }}0123 0 1 2 3 0102030112131 33223214Inserting an element into an array•Suppose we want to insert the value 8 into this sorted array (while keeping the array sorted)•We can do this by shifting all the elements after the mark right by one location–Of course, we have to discard the 30 when we do this1 3 3 7 12 14 17 19 22 30• Moving all those elements makes this a very slow operation!1 3 3 7 8 12 14 17 19 223015Deleting an element from an array•Deleting an element is similar--again, we have to move all the elements after it1 3 3 7 8 12 14 17 19 221 3 3 7 12 14 17 19 22 ?• This is a slow operation; we don’t want to do it very often•This leaves a “vacant” location at the end–How do we mark it vacant?•Every bit pattern represents a valid integer•We must keep a count of how many valid elements are in the array16Conclusions•Arrays have the following advantages:–Accessing an element by its index is very fast (constant time)•Arrays have the following disadvantages:–All elements must be of the same type–The array size is fixed and can never be changed–Insertion into arrays and deletion from arrays is very slow17The


View Full Document

Penn CIT 594 - Arrays

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Arrays
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Arrays and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Arrays 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?