Scribd Logo
Upload

Welcome to Scribd!

  • 8 views

    DSA Lecture01 - Arrays 1

    Uploaded by

    Engr Sameer Hani

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    DSA Lecture01 - Arrays 1

    Uploaded by

    Engr Sameer Hani
    8 views21 pages

    Original Title

    DSA-Lecture01_Arrays-1

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    8 views21 pages

    DSA Lecture01 - Arrays 1

    Uploaded by

    Engr Sameer Hani

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 21

    Data Structures

    and Algorithm

    SE-202
    Fall 2024
    Array
    Array
     Data structures are classified as either linear or nonlinear.
     A data structure is said to be linear if its elements form a

    sequence or a linear list. There are two basic ways of


    representing such linear structures in memory.
     One way is to have the linear relationship between the elements
    represented by means of sequential memory locations. These linear
    structures are called arrays.
     The other way is to have the linear relationship between the elements
    represented by means of pointers or links. These linear structures are
    called linked lists.
     Nonlinear structures are trees and graphs.
    Linear Array
    A linear array is a list of finite number n of
    homogeneous data elements such that :
     The elements of the array are referenced respectively
    by an index set consisting of n consecutive numbers.
     The elements of the array are stored respectively in
    successive memory locations.
     The number n of elements is called the length or size of
    the array.
    Linear Array
     Threenumbers define an array : lower bound,
    upper bound, size.
     The lower bound is the smallest subscript you can use
    in the array (usually 0)
     The upper bound is the largest subscript you can use in
    the array
     The size / length of the array refers to the number of
    elements in the array , It can be computed as upper
    bound - lower bound + 1
    Let, Array name is A then the elements of A is : a1,a2….. an
    Or by the bracket notation A[1], A[2], A[3],…………., A[n]
    Linear Arrays
    Example :
    A linear array DATA consisting of the name of six

    elements
    Linear Arrays
    Example :
    An automobile company uses an array AUTO to

    record the number of auto mobile sold each year from


    1932 through 1984.
    AUTO[K] = Number of auto mobiles sold in the

    year K
    LB = 1932

    UB = 1984

    Length = UB – LB+1 = 1984 – 1930+1 =55


    Representation of linear array in
    memory
     LetLA be a linear array in the memory of the
    computer. The memory of the computer is a
    sequence of addressed locations.
    Representation of linear array in
    memory
     The computer does not need to keep track of the
    address of every element of LA, but needs to keep
    track only of the first element of LA, denoted by
    Base(LA), called the base address of LA. Using this
    address Base(LA), the computer calculates the address
    of any element of LA by the following formula :
    LOC(LA[k]) = Base(LA) + w(K – lower bound)
    where w is the number of words per memory cell
    for the array LA
    Representation of linear array in
    memory
    Example :
    An automobile company uses an array
    AUTO to record the number of auto
    mobile sold each year from 1932
    through 1984. Suppose AUTO
    appears in memory as shown in
    figure. That is
    Base(AUTO) = ?, and
    w = ? words per memory cell for AUTO

    Find the address of the array


    element for the year K = 1935,1965
    Representation of linear array in
    memory
    SOLUTION

    LOC(AUTO[1965])= Base(AUTO) + w(1965 –


    lower bound)
    =200+4(1965-1932)=332
    Task
     Write a program in C++ to understand
    consecutive memory location for array, to
    understand why accessing every element is
    constant time (same) irrespective of value of k
    (we know computer uses above formula to find
    location of kth element as all elements are in
    consecutive memory space.)
    Traversing Linear Arrays
     Given DATA is a linear array with lower bound LB
    and upper bound UB . This algorithm traverses
    DATA applying print operation to each element of
    DATA.
    1. Set K : = LB.
    2. Repeat steps 3 and 4 while K<=UB:
    3. Print DATA[K]
    4. Set K : = K+1.
    5. Exit.
    Translating in C++
    int DATA={5,10,15,20,25};
    1. Set K : = LB. int K=0;
    2. Repeat steps 3 and 4 while(K<=4)
    while K<=UB: {
    3. Print DATA[K] cout<< DATA[K];
    4. Set K : = K+1. K = K+1;
    5. Exit. }
    Traversing Linear Arrays
     Given DATA is a linear array with lower bound
    LB and upper bound UB . This algorithm
    traverses DATA applying print operation to each
    element of DATA.
    Repeat for k = LB to UB:
    Apply PROCESS to LA [k]
    [End of loop]
    Exit
    Class Activity
    An automobile company uses an array AUTO to
    record the number of auto mobile sold each year
    from 1932 through 1984.
    a) Find the number NUM of years during which
    more than 300 automobiles were sold.
    b) Print each year and the number of automobiles
    sold in that year
    Questions??

    You might also like