Transforming Education
Arrays in C-II
Concepts
● Address Calculation in 1-D and N-D arrays
● Sparse Matrix Representation using Arrays
3
Questions for this session
We will answer the following questions in this session-
● How are elements stored in an Array?
● Can we access their memory addresses?
● What happens if most of the array elements have zero
value?
4
How are elements Can we access their
stored in an Array??? memory
addresses???
5
Address Calculation in 1-D Array
int arr[6] = {15,7,11,44,93,20};
6
Address Calculation in 1-D Array (Contd…)
Address of A[ i ] = Base(A) + W * ( i – LB )
B = Base address of an array
W = Storage Size of an element stored in the array (in bytes)
i = Subscript of the element whose address is to be found
LB = Lower limit / Lower Bound of the subscript (assume 0, if not specified)
7
Example: Address Calculation in 1-D Array
Question:
Given an array A[1300…..1900] with the following details-
● Base address= 1020
● Size of each element= 2 bytes in the memory.
Find the address of element A[1570].
Solution:
The given values are: B = 1020, LB = 1300, W = 2, i = 1570
Address of A[i] = Base(A) + W * ( i – LB )
Address of A[1570] = 1020 + 2 * (1570 – 1300)
= 1020 + 2 * 270
= 1020 + 540
= 1560
8
Address Calculation in 2-D Array
Arranging elements in 2-D array-
● Row major ordering
● Column major ordering
9
Address Calculation in 2-D Array (Contd…)
Row major address calculation:
LOC (A [i,j]) = Base (A) + W * [N * (i- LR) + (j-LC)]
Column major address calculation:
LOC (A [i,j]) = Base (A) + W * [(i- LR) + M * (j-LC)]
10
Example: Address Calculation in 2-D Array
Question: Each element in an array X [-15………….10, 15……………40] requires one byte of
storage. If beginning location is 1500 determine the location of X [15][20].
Solution:
Step 1: Calculating number of rows and columns in the matrix
Number or rows say M = (UR – LR) + 1 = [10 - (- 15)] +1 = 26
Number or columns say N = (UC – LC) + 1 = [40 – 15)] +1 = 26
(i) Column Major Wise Address Calculation
The given values are: Base(X) = 1500, W = 1 byte, i = 15, j = 20, L R = -15, LC = 15, M = 26
Address of A [ i ][ j ] = Base(X) + W * [ (i - LR ) + M * (j - LC) ]
= 1500 + 1 * [(15 - (-15)) + 26 * (20 – 15)] = 1500 + 1 * [30 + 26 * 5] = 1500 + 1 * [160] = 1660
11
Example: Address Calculation in 2-D Array (Contd…)
(ii) Row Major Wise Address Calculation
The given values are: Base(X) = 1500, W = 1 byte, i = 15, j = 20, L R = -15, LC = 15, N = 26
Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
= 1500 + 1* [26 * (15 - (-15))) + (20 – 15)] = 1500 + 1 * [26 * 30 + 5] = 1500 + 1 * [780 + 5] = 1500 + 785
= 2285
12
What happens if
most of the array
elements have zero
value?
13
Sparse Matrix
● Most of the elements in a matrix have zero value
● Disadvantage-
○ Amount of memory space it consumes
● Solution-
○ Triple Representation
14
InClass Activity: Address Calculation in Matrix
Instructions:
Activity Type- Exercise
Students can divide themselves into groups of 2
Time Allotted for this activity is 15 minutes
Question:
Let A be a two-dimensional array declared as follows:
A: array [1 …. 10] [1 …… 15] of integer;
Assuming that each integer takes one memory location, the array is stored in row-major order and the
first element of the array is stored at location 100, what is the address of the element A[i][j]?
(a) 15i + j + 84 (b) 15j + i + 84
(c) 10i + j + 89 (d) 10j + i + 89
15
Solution: Address Calculation in Matrix
Let A be a 2D array, A: array [b1 …. u1] [b2 …… u2], then
To find the location of A[i][j] for a 2D array stored in Row-major order
use the following formula:
Loc A[i][j] = L + W * [ (i - b1) (u2 - b2 +1) + (j - b2) ]
L - base address of the array, i.e. address of the first element of the
array
W - Memory Size, here each integer takes only 1 memory location
therefore W = 1
Loc A[i][j] = 100 + [ (i - 1) (15 - 1 +1) + (j - 1) ] x 1
= 100 + (i - 1) 15 + j -1 = 15i + j + 84
16
Learning Outcomes
In this session, you have learnt to:
1. State the formulas used for calculating addresses in 1-D and N-D arrays
2. Define the basic concepts of Sparse Matrix
3. Illustrate the use of formulas for calculating address locations in different types of arrays
4. Summarize the use of Array data structure for efficient representation of Sparse Matrices in
memory
Go through the following learning resources on the platform
● Arrays in C-II
17
Q&A
If you have more questions, please post them in the community on
the platform.
18
What Next?
In the next session the following concepts will be covered
● Operations in Arrays
○ Traversal
○ Insertion
○ Deletion
Go through the following learning resources on the platform
• Array Operations
19
