DATA STRUCTURES – ARRAYS (GENERAL CONCEPTS)
Introduction
Data structure is the arrangement of data as per the
requirements.
Every data structure has its own behavior and properties
Data structures may be of different types:
Simple data structures like arrays
Arrays : it stores data values of same type in a sequence.
Compound data structures like stacks, queues, linked lists.
Stacks : data is stored and programmed in such a manner that
element can be added and removed from one end. It uses the principle of LIFO.
Queues : data is stored and programmed to allow addition from
one end of the list while deletion is done from the other end. It uses the
principle of FIFO.
Linked lists: these data structures allows a lot of flexibility
and each element is linked to one another. Logically the elements in the list
are sequential but physically they may or may not be in a sequence.
Simple data structures
Arrays are linear
and the simplest form of data structures. They contain finite number of
elements of similar data types(homogeneous). Each data element/ value of an
array is referenced by its subscript/ index value. An index value is a number n which denotes the respective position
in the list from the beginning.
The first element has an index value 0. Index value indicates
that how many elements do we need to shift.
So, general properties
of arrays are :-
·
Arrays generally have a finite number of elements of
same data type
·
The elements are stored in a succession
·
Elements are referenced by their respective position
from the beginning of the list.
·
The fixed number of elements that an array can store
is called the length of the array.
Conceptually, every array has its own index set. This index
set defines the least and maximum integer value that an index can have. The
lowermost value is called the lowerbound(L) whereas the highest value is called
the upper bound(U) of the array index. The length of the array can be found
using :
U-L+1
In C++, the lowerbound
is 0. The elements of an array AR of size n are referred to as :
AR[0}, AR[1],
AR[2], ……AR[N-1]
The highest index value of array of size n is n-1 whereas the
lowest value is zero. Therefore the
length of an array M[N] has index values starting from 0 to N-1. Length of this array is : N -1 -0+1 =N
An array AR of size 5 is represented as :
|
AR[0]
|
AR[1]
|
AR[2]
|
AR[3]
|
AR[4]
|
|
|
|
|
|
|
For example : if we assume an integer array M[10] then
its lower bound is 0 and upper bound is 9. The
length of the array is : U – L
+1
9 –
0 + 1
= 10
Let us try some problems based on arrays.
1.
Consider an integer array P[10] . Write a function in
C++ to find sum of all its elements.
Solution : void sum(int P[ ])
{ int sum =0;
for(int i=0;i<10;i++)
sum=sum+P[i];
cout<<”
sum is : “<<sum;
}
2.
Write a function in C++ to display only even numbers
of an array.
Solution : void even(int a[], int s)
{ int k;
for( k=0; k<s; k++)
if(a[k]%2==0)
cout<<a[k];
}
Representation of a linear array in the memory:-
As studied in class XI also, we will discuss how array
elements are stored in the memory. All the elements of an array are stored in a
continuous succession one after another in the memory.
Memory map of array in memory of an integer array AR[10]
having is as follows :-
|
Address
|
Array index
|
AR
|
|
200
|
AR[0]
|
|
|
|
||
|
202
|
AR[1]
|
|
|
|
||
|
204
|
AR[2]
|
|
|
|
||
|
206
|
AR[3]
|
|
|
|
||
|
208
|
AR[4]
|
|
|
|
||
|
210
|
AR[5]
|
|
|
|
||
|
212
|
AR[6]
|
|
|
|
||
|
214
|
AR[7]
|
|
|
|
||
|
216
|
AR[8]
|
|
|
|
||
|
218
|
AR[9]
|
|
|
|
Since each integer requires two bytes therefore address of
every next element is two more than the previous element.
If we assume an array ST[10] of characters then the size of
individual element of the arrya is 1 byte and therefore address of every adjacent
element in the array will differ by one. Figure below show the same
diagrammatically
|
Array index
|
ST[0]
|
ST[1]
|
ST[2]
|
ST[3]
|
ST[4]
|
ST[5]
|
ST[6]
|
ST[7]
|
ST[8]
|
ST[9]
|
|
Array
|
|
|
|
|
|
|
|
|
|
|
|
Address
|
404
|
405
|
406
|
407
|
408
|
409
|
410
|
411
|
412
|
413
|
Therefore data type of an array defines the size of each
element of the array.
SEQUENTIAL ALLOCATION AND ADDRESS CALCULATION
One dimensional Array
An array AR of length 5 having size of each element as 1 byte
is store in a succession in the memory. The computer does not store address of
all the elements in the array. Rather, it stores the address of the first
element called as the Base Address while the rest of the elements are
identified as per their index value.
The index value tells the number of elements preceded by the
element whose address we wish to refer to. Address of element with index value
m can be calculated as :
Address of AR[i]= Base Address
+ size of individual element X m
For example , an array
S[15] of integers has the base address
330. Find the address of 5th element of the array.
Sol: Subscript /
index value of 5th element is 4.
So, m=4
Base address = 330
Size of each element – 2 Bytes ( size of each integer element
in the array is 2 Bytes)
Therefore,
Address AR[4] = 330 +
2 X 4
= 330 + 8 =
338
Example 2. In an
array K[20] of type float the address of K[5] is 4020. Find the address of K[15].
Sol: Address of
K[5] = Base Address + Size X 5
Base
address = Address of
M[5]- (sizeX5)
=
4020 – 4 X 5 = 4020 + 20 =
4080
Two dimensional Array
As values in one – dimensional
array are referenced by one index value,
an element of a two dimensional array is referenced with two index
values. A two dimensional array may be considered as a single dimensional array
and again each element of this array is a one dimensional array. Every element
of this two dimensional array have arrays of same size. A two dimensional array
is also called a matrix.
A two dimensional matrix of size R XC is a collection of R
element and each element further consists of c elements.
An element of a two dimensional matrix is specified with its
row number and then column number.
Representation of two dimensional array in memory
Though we always present a two dimensional array/ matrix as a
rectangular grid of elements but in memory it is stored in a sequential manner.
A matrix of size RXC requires memory for R.C elements. For example, a matrix of
size 2X3 requires space for 6 elements. The figure below shows how data is
stored in two ways in the memory
|
|
|||||||||||||||||
|
Column Major
|
Row Major
|
Let us understand it with the help of an example. Consider
following 2 dimensional array of integers and its first element is stored at
address 2076:
|
1
|
2
|
3
|
4
|
|
5
|
6
|
7
|
8
|
|
9
|
10
|
11
|
12
|
The storage in row major form is:
|
206
|
208
|
210
|
212
|
214
|
216
|
218
|
220
|
222
|
224
|
226
|
228
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
|
Row1
|
Row2
|
Row3
|
|||||||||
We notice that elements of first
row are stored followed by elements of second row and so on till the last row
in ROW –MAJOR form. The computer does not store address of all the elements of
an individually instead it store the address of the very first element called
as base address of the array and then calculates the address of rest of the
elements by performing calculations. Most general formula for calculating the
address of an element as
base address + size of
each element X number of elements preceding it.
In case of row major form the address of an element at
location [m][n] of a two dimensional array Ar[R][C] having R rows and C columns
can be evaluated as :
Address of
element[m][n]=BA +S X [mXC + n]
The above formula derivation may be explained as follows :
|
0,0
|
0,1
|
0,2
|
……..
|
|
|
|
 0,C-1 |
![Right Arrow: N elements preceding [m][n] element](file:///C:/Users/admin/AppData/Local/Temp/msohtmlclip1/01/clip_image010.gif) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m,n
|
|
|
|
….
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
R,0
|
|
|
|
|
|
|
R-1, C-1
|
Total elements before [m][n] element is : mXC + n
If we assume an array to be of size R rows and C columns
stored in row major form then the element at [m][n] is having m rows and n
columns before it. Since the array is row major, there are m rows each having C
elements in it ( m X C elements) and n elements are preceding it.
For example, if we assume an integer array A[10][20] stored
in row major form with base address 2000, then address of element A[5][8] is
calculated as follows :
In the above
example R=10 , C= 20
m=5
, n = 8, s=2, BA=2000
address ofA[5][8] =
2000 +
2 X [ 5X20 + 8]
=
2000 + 2 X[ 100 +8 ]
= 2000+ 2 X [108]
= 2000 +
2 X 108
= 2000 +
216
=
2216
Representation of 2 – dimensional array in column major form:
The storage in column major form is :
|
206
|
208
|
210
|
212
|
214
|
216
|
218
|
220
|
222
|
224
|
226
|
228
|
|
1
|
5
|
9
|
2
|
6
|
10
|
3
|
7
|
11
|
4
|
8
|
12
|
|
Column1
|
Column2
|
Column3
|
Column 4
|
||||||||
In case of column major form the address of an element at
location [m][n] of a two dimensional array Ar[R][C] having R rows and C columns
can be evaluated as :
Address of
element[m][n]=BA +S X [nXR +m]
For example, if we assume an integer array A[10][20] stored
in row major form with base address 2000, then address of element A[5][8] is
calculated as follows :
In the above
example R=10 , C= 20
m=5
, n = 8, s=2, BA=2000
address of A[5][8] = 2000
+ 2 X [ 8X10 + 5]
= 2000
+ 2 X[ 80 + 5 ]
= 2000 +
2 X [85]
= 2000 +
2 X 85
= 2000 +
170
=
2170
An element
Try out the following code :.
#include<iostream.h>
void main()
{ int
ar[10]={2,3,4,5};
for(int
i=0;i<10;i++)
cout<< i+1<<” element : “<<ar{i];
}
Following are some very common operations with arrays :
1.
Locating an element
2.
Traversing
3.
Insertion
4.
Deletion
5.
Searching
6.
Sorting
7.
Merging
Insertion in an array
Consider
the following example :
#include<iostream.h>
void main()
{
Int
ar[10]={ 12,13,14,15};
cout<<ar[0];
cout<<a[1];
}
Output :
1213
In the
example shown above only first four index positions of array are assigned
VALUES WHILE REMAINING six places are initialized with junk values . some more
values can be added either at the beginning , end or any other place in between
the array.
Inserting an element at the end of the array is simply done
by adding a new at the next index value while inserting an element in the
between or in the beginning requires shifting of trailing array elements
carefully provided the array has enough memory allocated to it.
Let us assume an array of size 10 having 8 values in it
|
[0]
|
[1]
|
[2]
|
[3]
|
[4]
|
[5]
|
[6]
|
[7]
|
[8]
|
[9]
|
|
2
|
4
|
8
|
9
|
10
|
12
|
15
|
20
|
|
|
In case a value 6 is
to be inserted at index value 2 then it is required to shift all the values
from index value 2 to one position higher.
|
[0]
|
[1]
|
[2]
|
[3]
|
[4]
|
[5]
|
[6]
|
[7]
|
[8]
|
[9]
|
|
2
|
4
|
8
|
8
|
9
|
10
|
12
|
15
|
20
|
|
|
[0]
|
[1]
|
[2]
|
[3]
|
[4]
|
[5]
|
[6]
|
[7]
|
[8]
|
[9]
|
|
2
|
4
|
6
|
8
|
9
|
10
|
12
|
15
|
20
|
|
Value at index ‘2’ is overwritten by the new value to be
inserted.
Program to insert an element in a sorted array at an appropriate position .
#include<iostream.h>
void insertar(int a[
], int num, int val) //n is the number of elements in the array
{ int i=num-1;
while (i>=0
&& a[i]>val)
{
a[i+1]=a[i]; //
shift the element
one position towards right
i--;
}
a[i+1]=val; //insertion of item at appropriate
place
}
void main()
{ int
a[20]={1,2,3,5,7,12,15,19,24},count=9;
int i=0;
cout<<“Original array is:\n”;
for(i=0;i<count;i++)
cout<<a[i]<<”, “;
insertar(a,count++, 10);
cout<<”\n
Array after inserting 10 is:\n”;
for(i=0; i<count; i++)
cout<<a[i]<<”, “;
}
Deleting a value from an array.
Element at position K in array A having N number of elements
is to be deleted
Algorithm
1.
Declare a variable M to store the value of element to
be deleted.
2.
M=A[K];
3.
Declare counter variable CTR.
4.
CTR=K;
5.
A[CTR]=A[CTR+1];
6.
CTR=CTR+1;
7.
If CTR<N go to step 5 else goto step 8
8.
Reset the number of elements as N=N-1;
For example if we wish to remove element at index value 5
then we may overwrite the value at next index of the array.
|
A[0]
|
A[1]
|
A[2]
|
A[3]
|
A[4]
|
A[5]
|
A[6]
|
A[7]
|
A[8]
|
A[9]
|
|
|
|
|
|
|
|
|
|
|
|
12
|
14
|
16
|
23
|
25
|
26
|
28
|
32
|
35
|
46
|
|
|
|
|
|
|
|
|
|
|
Store the value to be deleted at Index value in a variable .
N=a[5];
|
A[0]
|
A[1]
|
A[2]
|
A[3]
|
A[4]
|
A[5]
 |
A[6]
|
A[7]
|
A[8]
|
A[9]
|
|
|
|
|
|
|
|
|
|
|
|
12
|
14
|
16
|
23
|
25
|
26
|
28
|
32
|
35
|
46
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ü
|
Ü
|
Ü
|
Ü
|
|
|
|
|
|
|
|
|
|
|
|
A[0]
|
A[1]
|
A[2]
|
A[3]
|
A[4]
|
A[5]
|
A[6]
|
A[7]
|
A[8]
|
A[9]
|
|
|
|
|
|
|
|
|
|
|
|
12
|
14
|
16
|
23
|
25
|
26
|
28
|
32
|
35
|
46
|
|
|
|
|
|
|
|
|
|
|
Program to delete an integer element at position k in an
array having n elements.
#include<iostream.h>
void
deletar(int a[ ], int n, int item) //n is the number of elements already
present in the array
{int i=0;
while(i<n
&& a[i]<item)
i++;
if (a[i]==item) // given item is found
{while (i<n)
{a[i]=a[i+1]; //
shift the (i+1)th element
one position towards left
i++;
}
cout<<”\n
Given item is successfully deleted”;
}
else
cout<<”\n
Given item is not found in the array”;
n--;
}
void main()
{int
a[10]={2,4,5,7,8,11,12,15},n=8;
int i=0;
cout<<“Original
array is :\n”;
for(i=0;i<n;i++)
cout<<a[i]<<”,
“;
delete_item(a,n,11);
cout<<”\nArray
after deleting 11 is:\n”;
for(i=0; i<n;
i++)
cout<<a[i]<<”,
“;
}
If there is no extra space in the array then new element can
only be inserted by overwriting the existing values.
ARRAY TRAVERSAL
Traversing an array is reading every element of the array one
by one till all the elements are read in a sequential manner.
Program to traverse all the elements of an array
#include<iostream.h>
void main()
{ int ar[20],i,n;
cout<<”\n enter the number of elements
of the array :” ;
cin>>n; //number
of elements in the array
if((n<=20) //
checking the length of array should not exceed its maximum capacity
{
cout<<”\n enter the elements of the array : ”;
for(i=0;i<n;i++) // loop to accept n
elements of the array
cin>>ar[i];
cin>>ar[i];
cout<<”\n elements of the array
are :”;
for(i=0;i<n;i++)
cout<<endl<<ar[i];
}
else
cout<<”\n
array may have upto 20 elements”;
}
Let us try out some operations on 2 dimensional arrays :
Operations of 2 dimensional matrices
Addition of two 2-dimensional arrays
A two dimensional array of numbers is also referred to as a
matrix. Matrix addition is commutative and associative.
The elements with same indices of both the matrices are added
respectively. For example, if A and B are two matrices with m rows and n
columns then resultant matrix C will also have m rows and c columns.
|
A
|
+
|
B
|
=
|
C
|
|||||||||
|
A00
|
A01
|
A02
|
A03
|
|
B00
|
B01
|
B02
|
B03
|
|
A00+B00
|
A01+B01
|
A02+B02
|
A03+B03
|
|
A10
|
A11
|
A12
|
A13
|
|
B10
|
B11
|
B12
|
B13
|
|
A10+B10
|
A11+B11
|
A12+B12
|
A13+B13
|
|
A20
|
A21
|
A22
|
A23
|
|
B20
|
B21
|
B22
|
B23
|
|
A20+B20
|
A21+B21
|
A22+B22
|
A23+B23
|
#include<iostream.h>
#include<conio.h>
void main()
{
int a[2][3],b[2][3],c[2][3],d,e,f;
cout<< "First matrix.\n";
for (d=1;d<=2;d++)
{
for
(e=1;e<=3;e++)
{ cout<<
"Enter the number: ";
cin>>
a[d][e]; }
}
cout<< "\n
Second matrix.\n";
for (d=1;d<=2;d++)
{
for
(e=1;e<=3;e++)
{ cout<<
"Enter the number: ";
cin>>
b[d][e]; }
}
cout<< "\nSum of matrices : \n";
for (d=1;d<=2;d++)
{
for
(e=1;e<=3;e++)
{
cout<< a[d][e]+b[d][e]
<< '\t';
}
cout<< endl;
}
getch();
}
SUBTRACTION OF TWO MATRICES
Subtraction in 2-dimensional array subtraction is similar to
matrix subtraction and is not commutative in nature.
The elements with same indices of both the matrices are subtracted
respectively. For example, if A and B are two matrices with m rows and n
columns then resultant matrix C will also have m rows and c columns.
|
A
|
+
|
B
|
=
|
C
|
|||||||||
|
A00
|
A01
|
A02
|
A03
|
|
B00
|
B01
|
B02
|
B03
|
C
|
A00-B00
|
A01-B01
|
A02-B02
|
A03-B03
|
|
A10
|
A11
|
A12
|
A13
|
|
B10
|
B11
|
B12
|
B13
|
|
A10-B10
|
A11-B11
|
A12-B12
|
A13-B13
|
|
A20
|
A21
|
A22
|
A23
|
|
B20
|
B21
|
B22
|
B23
|
|
A20-B20
|
A21-B21
|
A22-B22
|
A23-B23
|
#include<iostream.h>
#include<conio.h>
void main()
{
int a[2][3],b[2][3],c[2][3],d,e,f;
cout<< "First matrix.\n";
for (d=1;d<=2;d++)
{
for
(e=1;e<=3;e++)
{ cout<<
"Enter the number: ";
cin>>
a[d][e]; }
}
cout<< "\n
Second matrix.\n";
for (d=1;d<=2;d++)
{
for
(e=1;e<=3;e++)
{ cout<<
"Enter the number: ";
cin>>
b[d][e]; }
}
cout<< "\n
Difference of matrices(a-b) : \n";
for (d=1;d<=2;d++)
{
for
(e=1;e<=3;e++)
{
cout<<
a[d][e]+b[d][e] << '\t';
}
cout<< endl;
}
getch();
}
Transpose of a matrix
Transpose of a matrix is interchanging of rows and
columns. Example below shows the
transpose of the given matrix num[3][3].
|
Matrix num[3][3]
|
|
Transpose of matrix num[3][3]
|
||||
|
1
|
2
|
3
|
|
1
|
4
|
7
|
|
4
|
5
|
6
|
|
2
|
5
|
8
|
|
7
|
8
|
9
|
|
3
|
6
|
9
|
The elements stored in a column of matrix are now the elements of the row in the
transpose matrix.
Program to find the transpose of the matrix
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int a[3][3],i,j;
cout<<"Enter the matrix"<<endl;
for(i=0;i<3;i++)
{for(j=0;j<3;j++)
cin>>a[i][j];
}
cout<<"matrix is"<<endl;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(i==0||i==1&&j==2)
{int t=a[i][j];
a[i][j]=a[j][i];
a[j][i]=t;
}
}
}
cout<<"transpose of the matrix
is"<<endl;
for(i=0;i<3;i++)
{for(j=0;j<3;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
getch();
}
Product of two matrices
Product of two matrices is also not commutative . There are
certain rules for multiplication of two matrices. One of the most important
rule is that the number of rows of the first matric must be equal to the number
of rows of the second matrix.
Program to find product of two matrices :
#include<iostream.h>
void prod(int a[10][10], int r1, int c1,int b[10][10],
int c2, int c[10][10])
{
int i,j,k;
for
(i=0;i<r1;i++)
for(j=0;j<c2;j++)
{
c[i][j]=0;
for(k=0;k<c1;k++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
}
}
void inptmat(int a[][10],int r, int c)
{ int i,j;
cout<<"\n enter the elements of the matrix: ";
for(i=0;i<r;i++)
for(j=0;j<c;
j++)
cin>>a[i][j];
}
void main()
{
int
i,j,m[10][10], n[10][10], p[10][10];
int r1, c1,
r2, c2;
cout<<"\n enter the number of rows and columns of first
matrix : ";
cin>>
r1>>c1;
cout<<"\n enter the number of rows and columns of Second
matrix : ";
cin>>
r2>>c2;
if(c1==r2)
{ cout<<"\n FIRST MATRIX";
inptmat(m,r1,c1);
cout<<"\n SECOND MATRIX";
inptmat(n,r2,c2);
}
prod(m,r1,c1,n,c2,p);
cout<<"\n The matrix after the product is ; ";
for(i=0;i<r1;i++)
{
cout<<endl;
for(int
j=0;j<c2; j++)
cout<<"\t"<<p[i][j];
}
}
No comments:
Post a Comment