Detailed Notes on Arrays and Their Representations
1. ARRAYS
An array is a collection of elements, all of the same type, placed in contiguous memory locations.
Each element can be accessed by an index.
Advantages of Arrays:
- Easy access to elements using indices
- Memory efficiency for fixed-size data
- Supports matrix and vector computations
Types of Arrays:
- One-dimensional (1D)
- Two-dimensional (2D)
- Multi-dimensional (3D and higher)
--------------------------------------------------
2. REPRESENTATION OF SINGLE-DIMENSIONAL ARRAYS
Definition:
A one-dimensional array is a linear list of elements.
Declaration (in C/C++):
int arr[5] = {1, 2, 3, 4, 5};
Memory Layout:
Assume the base address of arr is 1000 and each int takes 4 bytes:
arr[0] = 1 -> 1000
arr[1] = 2 -> 1004
arr[2] = 3 -> 1008
...
Formula for Address of arr[i]: Base + i * Size_of_element
Example:
Accessing elements using loops:
for(int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
--------------------------------------------------
3. REPRESENTATION OF TWO-DIMENSIONAL ARRAYS
Definition:
A two-dimensional array is like a matrix of rows and columns.
Declaration:
int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
Memory Representation:
Two approaches:
- Row-major order (used by C/C++): Stores rows sequentially
- Column-major order (used by Fortran): Stores columns sequentially
Address Calculation (Row-major):
Address(A[i][j]) = Base + ((i * number_of_columns) + j) * Size
Example:
matrix[1][2] = 6
Memory layout: 1 2 3 4 5 6
--------------------------------------------------
4. TRIANGULAR ARRAYS
Used for matrices where only upper or lower triangle is needed.
Lower Triangular Matrix:
Only elements where row >= column are non-zero.
Example 3x3:
[1 0 0]
[2 3 0]
[4 5 6]
Efficient Representation:
Only store non-zero values: [1, 2, 3, 4, 5, 6]
Index Mapping:
For 1D representation of lower triangle:
Index = (i*(i+1))/2 + j (where i >= j)
--------------------------------------------------
5. SPARSE MATRICES
Definition:
A matrix is sparse if most of its elements are zero.
Why use special representation?
To save memory and improve efficiency.
Representation Methods:
1. Triplet Array Format:
Store only non-zero elements with their row and column indices.
Example matrix:
[0 0 3]
[0 0 0]
[0 7 0]
Triplet form:
Row Col Val
0 2 3
2 1 7
2. Linked List Representation:
Each node contains (row, col, value, next pointer).
Useful for dynamic operations like insertion/deletion.
Structure:
struct Node {
int row, col, val;
Node* next;
};
Benefits of Sparse Representation:
- Saves memory
- Faster matrix operations on non-zero elements
--------------------------------------------------
Conclusion:
Arrays are a foundational data structure. Specialized techniques like triangular and sparse matrix
representations enhance storage and computation efficiency.
