ARRAY
Arrays are defined as the collection of similar type of data items
stored at contiguous memory locations.
Arrays are the derived data type, which can store the primitive type of
data such as int, char, double, float, etc.
Array is the simplest data structure where each data element can be
randomly accessed by using its index number.
For example, if we want to store the marks of a student in 6 subjects,
then we don't need to define different variable for the marks in
different subject. instead of that, we can define an array which can
store the marks in each subject at a the contiguous memory locations.
Example- The array marks[10] defines the marks of the student in 10
different subjects where each subject marks are located at a particular
subscript in the array i.e. marks[0] denotes the marks in first subject,
marks[1] denotes the marks in 2nd subject and so on.
Properties of the Array:
* Each element is of same data type and carries a same size i.e. int = 4
bytes.
* Elements of the array are stored at contiguous memory locations where
the first element is stored at the smallest memory location.
* Elements of the array can be randomly accessed since we can calculate
the address of each element of the array with the given base address
and the size of data element.
Example-int arr[10]; char arr[10]; float arr[5]
Need of Array:
The most of the cases requires to store the large number of data of
similar type. To store such amount of data, we need to define a large
number of variables. It would be very difficult to remember names of
all the variables while writing the programs. Instead of naming all the
variables with a different name, it is better to define an array and store
all the elements into it.
Following example illustrates, how array can be useful in writing code
for a particular problem.
Suppose we have marks of a student in six different subjects. The
problem intends to calculate the average of all the marks of the student.
Advantages of Array
Array provides the single name for the group of variables of the same
type therefore, it is easy to remember the name of all the elements of an
array.
Traversing an array is a very simple process, we just need to increment
the base address of the array in order to visit each element one by one.
Any element in the array can be directly accessed by using the index.
Types of Array
ONE DIMENSIONAL ARRAY
A one dimensional array is one in which only one subscript
specification is needed to specify a particular element of the array.
Data type var [index];
Int num[10];
Int num[10]={1,3,5,7,9,11,13,15,17,19};
char word[10]={‘h’,’e’,’l’,’l’,’o’};
MULTI DIMENSIONAL ARRAY
Array are defined is similar way as one dimensional array. The number
of square bracket is more in one multi dimensional array. There will be
two pairs of square bracket for two dimensional array, three pairs for 3
dimensional array and so on.
Data type var [index][index];
int x[2][4];
char name[4][10];
Address calculation of Array:
As we have mentioned, all the data elements of an array are stored at
contiguous locations in the main memory.
The name of the array represents the base address or the address of first
element in the main memory.
Each element of the array is represented by a proper indexing.
In the following image, we have shown the memory allocation of an
array arr of size 5.
The base address of the array is 100th byte.
This will be the address of arr[0].
Here, the size of int is 4 bytes therefore each element will take 4 bytes
in the memory.
Address of element a[k]=B+W * K or B + W * ( K - first index)
B=Base address
W=Size of each element of the array
K=No. of required element in the array (index of element)
Example
If the box address of the first element of the array is 2000 and each element of
the array occupies 4 bytes in the memory, then address of fifth element of a
one –dimensional array a[10]
A[K]=B + W * K
A[5] =2000+5x4
=2020
Example
In an array, A[-10 ..... +2 ], Base address (BA) = 999, size of an element = 2
bytes, find the location of A[-1].
L[K]=B + W * ( K - first index)
L(A[-1]) = 999 + 2 * [(-1) - (-10)]
= 999 + 18
= 1017
Example:
Consider the linear array x(2:20), y(-4:10) and z(15)
a) Find the number of element in each array
b) Suppose base address is 500 and W=4 word per memory cell. Find the
address of X[10], X[6] and X[25].
Address calculation of 2D Array
Row-Major implementation: In row major implementation elements
of array are read from the keyboard row-wise. It means that the
complete first row is stored and then complete second row is stored and
so on.
A[i][j]=B+W [n(i-L1)+(j-L2)]
Column-Major implementation: In this implementation the elements
of an array are read from the keyboard column wise. It means that the
complete first column is stored and then complete second column is
stored and so on.
A[i][j] = B+W (m (j-L2)+(i-L1))
B = Base address
W = Size of element
m = No. of rows=U1-L1+1
n = no. of column=U2-L2+1
L1 = lower bound of row
L2 = lower bound of column
U1 = upper bound for rows
U2 = upper bound for column
Example:
The Array Data [10, 15] is stored in memory in row major order. If
base address is 200 and column size is 1. Calculate the address of
element data[7,12].
=B+W[n(i-L1)+(j-L2)]
=200+1[15(7-0)+(12-0)]
=200+1[105+12]
=200+117
=317
How is physical memory allocated for a 2-D array? If each element of
an array D [20][50] requires 4 bytes of storage, base address of DATA
is 2000 determine the location of D [10][10], when the array is stored.
(i) Row major. (ii) Column major.
Example:
(1) Calculate the address of X[4][3] in a two dimensional array X[1...5, 1...4]
stored in row major order in the main memory. Assume the base address to be
1000 and each element required 4 bytes of storage.
(2) Calculate the address of X[0][30] in a two dimensional array X[-20...20,
10...35] stored in column major order in the main memory. Assume the base
address to be 500 and each element required 1 bytes of storage.
Example:
If an array B[11][8] is stored as column wise and B[2][2]
is stored at 1024 and B[3][3] at 1084. Find the address
of B[5][3] and B[1][1].
Inserting Element in an array-
Algorithm:
INSERT(LA,N,K,DATA)
LA= Linear array
N= Number of Elements
K= Positive Integer such that K<=N
DATA= Element which we have to insert in the kth Position.
Initialize the value of J
1) Set j:=N-1
2) Repeat steps 3 and 4 while J>=K
3) [Move Jth element downward]
Set LA[J+1]=LA[J]
4) J=J-1 [END of step 2 loop]
5) Set LA[K]=ITEM
6) Set N=N+1
7) EXIT
Deleting a Element from Linear Array-
Algorithm:
DELETE (LA, N, K, DATA)
1) Set DATA=LA[K]
2) Repeat for J=K to N-1 [move J+1st element upward]
3) Set LA[J]=LA[J+1]
4) j=j+1 [END of loop]
5) Reset the number N of elements in LA.
6) Set N=N-1
7) Exit