Page 55 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes
Example: Consider the previous example of array AUTO, which records the number of
automobiles sold each year from 1932 through 1984. Array AUTO appears in memory is pictured
in Figure 4.3. Assume, Base(AUTO) = 200 and w = 4 words per memory cell for AUTO.
Then the base addresses of following arrays are,

LOC(AUTO[1932]) = 200, LOC(AUTO[1933]) = 204, LOC(AUTO[1934]) = 208, …….
Let us find the address of the array element for the year K = 1965. It can be obtained by using
Equation (1.4b):

LOC(AUTO[1965]) = Base(AUTO) + w(1965 – lower bound) = 200 + 4(1965-1932) = 332
Again, we emphasize that the contents of this element can be obtained without scanning any
other element in array AUTO.

Figure 4.3: Array AUTO Appears in Memory

Source: http://www.csbdu.in/econtent/DataStructures/Unit1-DS.pdf

Task Analyse the uses of arrays.

4.1.2 Traversing Linear Arrays

Consider let A be a collection of data elements stored in the memory of the computer. Suppose
we want to either print the contents of each element of A or to count the number of elements of
A with a given property. This can be accomplished by traversing A, that is, by accessing and
processing (frequently called visiting) each element of A exactly once.
The following algorithm is used to traversing a linear array LA.
As we know already, here, LA is a linear array with lower bound LB and upper bound UB. This
algorithm traverses LA applying an operation PROCESS to each element of LA.
1. [Initialize counter] Set K:= LB.
2. Repeat Steps 3 and 4 while K< UB

3. [Visit element] Apply PROCESS to LA[K]

48 LOVELY PROFESSIONAL UNIVERSITY