Scribd Logo
Upload

Welcome to Scribd!

  • 144 views

    DSA2 Arrays (061808)

    Uploaded by

    redbutterfly
    Arrays allow storing and accessing a collection of data of the same type using indexes. They address limitations of primitive data types by allowing storing multiple values of a type together in contiguous memory locations that can be accessed using indexes. This document discusses key aspects of arrays in Java including primitive data types, creating and initializing arrays, array indexing to access elements, and using loops to iterate through arrays. It provides examples of declaring and using single, multi-dimensional, and nested arrays and calculating element addresses.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    DSA2 Arrays (061808)

    Uploaded by

    redbutterfly
    144 views18 pages
    Arrays allow storing and accessing a collection of data of the same type using indexes. They address limitations of primitive data types by allowing storing multiple values of a type together in contiguous memory locations that can be accessed using indexes. This document discusses key aspects of arrays in Java including primitive data types, creating and initializing arrays, array indexing to access elements, and using loops to iterate through arrays. It provides examples of declaring and using single, multi-dimensional, and nested arrays and calculating element addresses.

    Original Title

    DSA2 Arrays(061808)

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Arrays allow storing and accessing a collection of data of the same type using indexes. They address limitations of primitive data types by allowing storing multiple values of a type together in contiguous memory locations that can be accessed using indexes. This document discusses key aspects of arrays in Java including primitive data types, creating and initializing arrays, array indexing to access elements, and using loops to iterate through arrays. It provides examples of declaring and using single, multi-dimensional, and nested arrays and calculating element addresses.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    144 views18 pages

    DSA2 Arrays (061808)

    Uploaded by

    redbutterfly
    Arrays allow storing and accessing a collection of data of the same type using indexes. They address limitations of primitive data types by allowing storing multiple values of a type together in contiguous memory locations that can be accessed using indexes. This document discusses key aspects of arrays in Java including primitive data types, creating and initializing arrays, array indexing to access elements, and using loops to iterate through arrays. It provides examples of declaring and using single, multi-dimensional, and nested arrays and calculating element addresses.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 18

    Data Structures and

    Algorithms (Arrays)

    Jose Rizal University, Mandaluyong City, Philippines


    References:

    • Data Structures and Algorithms in JAVA


    Goodrich and Tamassia (2004) John Wiley &
    Sons, Inc.
    • Data Structures & Algorithm Analysis
    in C Mark Allan Weiss. (1993) Benjamin
    Cummings Publishing Company,
    Inc./Jemma, Inc., Philippines

    2
    First, a look at primitive
    data types
    The primitive or built-in variable types in Java are shown below:

    3
    Questions

    • How important are these primitive data


    types in developing our programs?
    • What limitations regarding the use of
    primitive data types can you imagine?

    4
    Introducing Arrays
    Arrays are a very useful data structure provided by Java and other
    programming languages.
    – An array is a variable compose of a finite, ordered set of homogeneous
    elements, i.e. elements of the same data type
    – Individual elements of this sequence can be uniformly
    referenced/updated/ etc. since it consumes a consecutive set of
    memory locations
    – is a set of pairs - index and a value 0

    – forms 1
    2
    • one-dimensional array
    3
    • n-dimensional array
    4
    5
    Question:
    Based on the definition above, how can arrays address the limitations
    of using primitive data types ?

    5
    Creating Arrays
    • Arrays in Java are handled as objects (hence allocated
    on heap)
    • 2 data types
    – base type or component type
    – index type
    • All data types (primitive and user-defined objects) can
    be put into arrays
    • To create an array, use the new keyword
    • Java has special syntax for array type declaration:
    int[] a = new int[5];
    – int[] indicates a is array of integer variables
    – int[5] indicates a will have 5 elements
    • Each cells in the array are assigned default values (0 /
    null / etc.) when array created
    6
    Array Indexing
    • Java provides a special syntax for uniformly accessing cells in an
    array
    – Assume previous declaration of a:
    • int[] a = new int[5];
    – This in effect creates five int variables “named”:
    • a[0] a[1] a[2] a[3] a[4]
    – To modify contents of cell #2 to 6:
    • a[2] = 6;
    • This access mechanism is called array indexing
    • 2 basic operations
    – extraction and storing
    • In Java, the same as with C and C++, array cells are indexed
    beginning at 0 and going up to n-1 (n is number of cells)
    • Beware of index numbers that exceed the array structure.
    • Also, beware of starting the indexing at 0!

    7
    Example

    If we use the following codes:


    int[] arr1 = new int[5];
    arr1[2] = 6;

    Which cell in arr1 would contain the value


    6?

    8
    Cell Index numbers

    0 1 2 3 4

    9
    Handling arrays using
    loops
    Loops Are Useful for Processing Arrays

    • Loop counter can be used to iterate


    through index values
    • Each iteration of loop thus processes a
    different array element

    10
    Examples of handling
    arrays
    int i;
    int[] arr1 = new int[5];
    arr1[2] = 6;
    for (i=0; i<5; i++)
    {
    arr1[i] = i * 10;
    }

    11
    Exercise Questions

    • In the above coding, how would you change


    the size of the array to accommodate 10
    integer values instead of 5?
    • What would happen if:
    – instead of i++, i– was used in the for loop
    statement?
    – if instead of i=0, i=1 was used?
    – If instead of i<5, i<=5 was used?
    • How would you describe the process of
    assigning values into each cell in the array
    without using a for loop?
    12
    If an array is declared to be A[n], then:
    n = number of elements

    If an array is declared to be A[n][m], then:


    n*m = number of elements

    If given n-dimensional array declaration,


    A[b][c][d][e]..[n] = ∏b,c,..n
    13
    • To determine the ith element of a single-dimension
    array: A[i] = α + (i) * esize
    where:
    α - base or starting address
    i - element
    esize - element size in bytes

    • 2-dimensional arrays:
    A[i][j] = α + [(i) * (UB2) + (j)] * esize
    where: UB2 = upper bound of the 2nd dimension.

    14
    • 3-dimensional arrays:
    A[i][j][k] = α + [(i) * (UB2) *(UB3) + (j)*(UB3)
    + (k)] * esize
    where: UB2 = upper bound of the 2nd dimension;
    UB3 = upper bound of the 3rd dimension
    esize = element size in bytes

    Typical esize: integer - 4 bytes


    char - 1 byte
    float - 4 bytes

    15
    Examples

    1. Given A[10][3][3][6], α = 2000, esize=4


    bytes:
    a. find the formula to represent an
    element in a 4-dimensional array.
    b. find the total number of elements
    c. find the address of A[2][2][0][4]

    16
    Examples

    2. Given X[8][3][6][2][3],α = 3000, esize = 3


    bytes
    a. find the total number of elements
    b. find the address of X[0][2][5][1][2]

    17
    Examples

    3. Consider the following declaration:


    class Myclass {
    int A;
    char [] B = new char[10];
    float C;
    char D;
    }
    Myclass class1 = new matrix [121][4][5];
    matrix A1;
    A. Compute the address of element A1[120][3][3] given that the
    base address is 2000.
    B. Assume that we do not the size of Myclass in number of bytes
    but we know that the address of A1[20][2][3] is 2160. Give the
    size of Myclass in bytes. Assume the base address is 2000.

    18

    You might also like