Module 1
ARRAY DATA
STRUCTURES
Presenter:
Er. Manpreet Kaur
Definition and Declaration
● An array is a finite collection of similar elements stored in adjacent
memory locations.
Declaration of the Arrays:
In C++, array can be declared as:
datatype-name array-name[array-size];
Examples of one-dimensional array declaration:
1. int a[20], b[3],c[7];
2. float f[5], c[2];
3. char m[4], n[20];
Memory Space required by an array
● Compiler determines the size required for an array with the
help of the number of elements of an array and the size of the
data type present in the array (depending on elements
datatype, 1, 4 or 8 bytes of memory is allocated for each
elements).
● For example: 'int n[6]' will allocate 12 bytes space for 6
integers:
Total Memory Required = No. of elements * Memory space for each element
=6 * 2 Bytes
Initialization of Arrays
● Initialization of an array is the process of assigning
initial values.
Examples:
int arr[5] = {73, 98, 86, 61, 96};
float b[3]={2.0, 5.5, 3.14};
char name[4]= {‘c’,’o’,’l’,’o’, ‘r’};
Subscripting (Indexing)
● A subscript is a bracketed expression [ ].
● Index − Each location of an element in an array has a
numerical index, which is used to identify the element.
● First element of array has index 0.
■ arr[0]
● Second element of array has index 1, and so on.
■ arr[1], arr[2], arr[3], arr[4]
● Last element has an index one less than the size of the
array.
Figure 1. Array
Length or Size of the Array
● The number n of elements is called length or size of array.
● The Length or the number of data elements of the array can be
obtained from the index set by Length = UB – LB + 1 where UB
(Upper Bound) is the largest index called the upper bound and
LB (Lower Bound) is the smallest index called the lower bound
of the array.
○ Note that Length = UB when LB = 1
● Example: in array arr, there are 5 elements. UB = index of last
element = 4, LB = index of 1st element = 0.
● Length L = 4 - 0 + 1 = 5 //size is 5 elements
Representation of 1-D Array in Memory
● LA = name of linear array
● k = index of element for which we want to find the memory address.
● LOC (LA[k]) = address of element LA[k] of the array LA.
● The elements of LA are stored in the successive memory cells.
● 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, denoted by Base (LA).
● Base (LA) = the base address of LA.
● Formula using which computer calculates the address of any element of
LA:
○ LOC (LA[k]) = Base (LA) + w (k-lower bound)
Where w is the number of words per memory cell for the array LA
OPERATIONS ON ARRAYS
Various operations that can be performed on an array:
● Traversing
● Insertion
● Deletion
● Sorting
● Searching
● Merging
Traversing Linear Array:
Algorithm: (Traversing a Linear Array) 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].
4. [Increase Counter] Set k := k + 1. [End of step 2 loop]
5. Exit.
Inserting into Linear Array
Algorithm for Insertion: INSERT (LA, N, K, ITEM)
Here, LA = linear array with N elements and
K is a positive integer such that K<=N.
The algorithm inserts an element ITEM into the Kth position in LA.
1. [Initialize counter] Set J := N.
2. Repeat Steps 3 and 4 while J >= K
3. [Move Jth element downward.] Set LA [J + 1] := LA [J].
4. [Decrease counter] Set J := J-1 [End of step 2 loop]
5. [Insert element] Set LA [K] := ITEM.
6. [Reset N] Set N := N+1
7. EXIT.
Deletion from a Linear Array
Algorithm for Deletion: DELETE (LA, N, K, ITEM)
Here LA is a Linear Array with N elements and K is the positive integer
such that K<=N. This algorithm deletes the Kth element from LA.
1. Set ITEM := LA [k].
2. Repeat for J = K to N – 1.
[Move J + 1st element upward] Set LA [J] := LA [J +1].
[End of loop]
3. [Reset the number N of elements in LA] Set N := N-1.
4. EXIT
Multidimensional Array
● Array having more than one subscript variable is called
MultiDimensional array.
● Multi Dimensional Array is also called as Matrix.
● Two Dimensional (2-D) Array requires Two Subscript
Variables and stores the values in the form of matrix.
● One Subscript Variable denotes the ―Row of a matrix.
● Another Subscript Variable denotes the ―Column of a
matrix
Representation of 2-D Arrays
● 2-D Arrays may be represented in Row-major form or
Column-major form.
● In Row-major form, all the elements of the first row are
printed, then the elements of the second row and so on up to
the last row.
● In Column-major form, all the elements of the first column
are printed, then the elements of the second column and so
on up to the last column.
Figure 2. Representation of 2-D Arrays
Row-Major Representation
In this example, nrows = 4, ncols = 3 (the size of the array).
Suppose that the program needs to access the element a[i][j]
(where i is the row = 2 and j is the column = 1). This element is
highlighted in yellow. The calculation is as follows:
a[i][j] = i * ncols + j
a[2][1] = 2 * 3 + 1 = 7
a[2][1] = RM[7]
Column-Major Representation
In this example, nrows = 4, ncols = 3 (the size of the array).
Suppose that the program needs to access the element a[i][j]
(where i is the row = 2 and j is the column = 1). This element is
highlighted in yellow. The calculation is as follows:
a[i][j] = i + j * nrows
a[2][1] = 2 + 1 * 4 = 6
a[2][1] = CM[6]
Sparse matrix
● Matrix with relatively a high proportion of zero entries are
called sparse matrix.
● We can classify sparse matrices into two types:
○ Triangular matrices and
○ Tridiagonal matrices
● It is sometimes necessary to omit blocks of zeros in a matrix as
shown in figure below:
Figure 3. Types of Sparse Matrix
Figure 4. Types of Triangular Matrix
REFERENCES:
1. “Data Structures with C (Schaum's Outline Series)”, Seymour Lipschutz, 1st
edition,McGraw Hill
2. “Fundamentals of Data Structures”, Illustrated Edition by Ellis Horowitz,
SartajSahni, Computer Science Press.
3. Algorithms, Data Structures, and Problem Solving with C++”, Illustrated
Edition by Mark Allen Weiss, Addison-Wesley Publishing Company
