Page 54 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 4: Arrays

Let us now consider the other figure 4.2. Notes
(b) An automobile company uses an array AUTO to record the number of automobiles sold
each year from 1932 through 1984.

Rather than beginning the index set with 1, it is more useful to begin the index set with
1932, so we may learn that,
AUTO[K] = number of automobiles sold in the year K

Then, LB = 1932 is the lower bound and UB=1984 is the upper bound of AUTO.

4.1.1 Representation of Linear Arrays

Consider LA be a linear array in the memory of the computer. As we know that the memory of
the computer is simply a sequence of addressed location as pictured in Figure 4.2 as given
below.
Figure 4.2: Computer Memory

Source: http://www.csbdu.in/econtent/DataStructures/Unit1-DS.pdf
Let us use the following notation when calculate the address of any element in linear arrays in
memory,
LOC(LA[K]) = address of the element LA[K] of the array LA.
The elements LA are stored in successive memory cells.
Accordingly, the computer does not need to keep track of the address of every element of LA,
but needs to keep track only of the address of the first element of LA, which is denoted by:
Base(LA)
and 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) (a)
where w is the number of words per memory cell for the array LA.
Let us observe that the time to calculate LOC(LA[K]) is essentially the same for any value of K.

Notes Given any subscript K, one can locate and access the content of LA[K] without
scanning any other element of LA.

LOVELY PROFESSIONAL UNIVERSITY 47