Page 53 - DCAP407_DATA_STRUCTURE

Data Structure

For row-major order,
LOC (M[J,K]) = Base(M) = w[Q(J-1) +(K-1) --- (2)
Again, w denotes the size of memory location for each element of the array M. P and K denotes the row
major order and column major order respectively for the array M.

In the two-dimensional a x b array M, the formulas are linear in J and K, and the address
LOC (M[J,K]) is time independent of J and K.

Consider that 25 students are given 4 tests. The students are numbered from 0-25
and the test score is assigned in a 25 x 4 matrix array - MARKS. Thus,
MARKS[13,2] contains the marks of the second test of the 14 student.
th
In particular, the third row of the array,
MARKS[3, 1], MARKS[3, 2], MARKS[3, 3], MARKS[3, 4]. This gives the score for all
the four tests of the third student.

Suppose Base (MARKS) = 100 and w=4 bytes, then, the program stores two-
dimensional arrays using row-major order. In this case, the row-major is 4. The
address of MARKS[10,2], that is the marks scored by the tenth student in the
second test are as per the formula:

LOC (M[J,K]) = Base(M) + w[Q(J-1) +(K-1)]
LOC (MARKS[13,2]) = 100 + 4[4(10-1) +(2-1)]
= 100 + 4[36+1]
LOC (MARKS[13,2]) = 248
3.3 Types of Array Operations
The operations performed on an array, are:

1. Adding operation
2. Sorting operation
3. Searching operation
4. Traversing operation
3.3.1 Adding Operation

Adding elements into an array is known as insertion. The insertion of data elements is done at the end
of an array. This is possible only if there is enough space in the array to add the additional elements.
The elements can also be inserted in the middle of the array. Here, the average half of the array
elements is moved to the next location to empty the block of memory, and to accommodate the new
element.

Consider an array a of size 5. If you need to add an element 8 at a[2]
position, then all the elements from a[3] have to be moved down (i.e. to
the next location).

46 LOVELY PROFESSIONAL UNIVERSITY