Arrays

Useful for B.Sc students

1. ARRAYS IN ARRAYS IN
DATASTRUCTURES USING ‘C’DATASTRUCTURES USING ‘C’
Dr. C. SarithaDr. C. Saritha
Lecturer in ElectronicsLecturer in Electronics
SSBN Degree & PG CollegeSSBN Degree & PG College
ANANTAPURANANTAPUR

2. OverviewOverview
What is Array?What is Array?
Types of Arrays.Types of Arrays.
Array operations.Array operations.
Merging of arrays.Merging of arrays.
Arrays of pointers.Arrays of pointers.
Arrays and Polynomials.Arrays and Polynomials.

3. ARRAYARRAY
An array is a linear data structure. Which An array is a linear data structure. Which
is a finite collection of similar data items is a finite collection of similar data items
stored in successive or consecutive stored in successive or consecutive
memory locations.memory locations.
For example an array may contains all For example an array may contains all
integer or character elements, but not integer or character elements, but not
both. both.

4. Each array can be accessed by using array Each array can be accessed by using array
index and it is must be positive integer value index and it is must be positive integer value
enclosed in square braces.enclosed in square braces.
This is starts from the numerical value 0 and This is starts from the numerical value 0 and
ends at 1 less than of the array index value. ends at 1 less than of the array index value.
For example an array[n] containing n For example an array[n] containing n
number of elements are denoted by number of elements are denoted by
array[0],array[1],…..array[n-1]. where ‘0’ is array[0],array[1],…..array[n-1]. where ‘0’ is
called lower bound and the ‘n-1’ is called called lower bound and the ‘n-1’ is called
higher bound of the array.higher bound of the array.

5. Types of ArraysTypes of Arrays
Array can be categorized into different Array can be categorized into different
types. They are types. They are
 One dimensional arrayOne dimensional array
 Two dimensional arrayTwo dimensional array
 Multi dimensional arrayMulti dimensional array

6. One dimensional array:-One dimensional array:-
One dimensional array is also called as One dimensional array is also called as
linear array. It is also represents 1-D linear array. It is also represents 1-D
array.array.
 the one dimensional array stores the data the one dimensional array stores the data
elements in a single row or column.elements in a single row or column.
The syntax to declare a linear array is as The syntax to declare a linear array is as
fallowsfallows
Syntax:Syntax: <data type> <array name> <data type> <array name>
[size];[size];

7. Syntax for the initialization of the linear array Syntax for the initialization of the linear array
is as fallowsis as fallows
Syntax: Syntax:
<data type><array name>[size]={values};<data type><array name>[size]={values};
Example: Example:

int arr[6]={2,4,6,7,5,8}; int arr[6]={2,4,6,7,5,8};

Values Values

array name array name

array sizearray size
data type data type

8. Memory representation of the one Memory representation of the one
dimensional array:-dimensional array:-
a[0] a[1] a[2] a[3] a[4] a[5]a[0] a[1] a[2] a[3] a[4] a[5]
100 102 104 106 108 110100 102 104 106 108 110
The memory blocks a[0],a[1],a[2],a[3 ],a[4] , The memory blocks a[0],a[1],a[2],a[3 ],a[4] ,
a[5] with base addresses 1,102,104,106,108, a[5] with base addresses 1,102,104,106,108,
110 store the values 2,4,6,7,5,8 respectively.110 store the values 2,4,6,7,5,8 respectively.
22 44667755 88

9. Here need not to keep the track of the Here need not to keep the track of the
address of the data elements of an array to address of the data elements of an array to
perform any operation on data element. perform any operation on data element.
We can track the memory location of any We can track the memory location of any
element of the linear array by using the element of the linear array by using the
base address of the array.base address of the array.
To calculate the memory location of an To calculate the memory location of an
element in an array by using formulae.element in an array by using formulae.
Loc (a[k])=base address +w(k-lower Loc (a[k])=base address +w(k-lower
bound)bound)

10. Here k specifies the element whose Here k specifies the element whose
location to find.location to find.
W means word length.W means word length.
ExEx: We can find the location of the : We can find the location of the
element 5, present at a[3],base address is element 5, present at a[3],base address is
100, then100, then
loc(a[3])=100+2(3-0)loc(a[3])=100+2(3-0)
=100+6=100+6
=106.=106.

11. Two dimensional array:-Two dimensional array:-
A two dimensional array is a collection of A two dimensional array is a collection of
elements placed in rows and columns.elements placed in rows and columns.
The syntax used to declare two The syntax used to declare two
dimensional array includes two dimensional array includes two
subscripts, of which one specifies the subscripts, of which one specifies the
number of rows and the other specifies number of rows and the other specifies
the number of columns. the number of columns.
These two subscripts are used to These two subscripts are used to
reference an element in an array.reference an element in an array.

12. Syntax to declare the two dimensional Syntax to declare the two dimensional
array is as fallows array is as fallows
Syntax:Syntax:
<data type> <array name> [row size] <data type> <array name> [row size]
[column size]; [column size];

Syntax to initialize the two dimensional Syntax to initialize the two dimensional
array is as fallowsarray is as fallows
Syntax:Syntax:
<data type> <array name> [row size] <data type> <array name> [row size]
[column size]={values};[column size]={values};

13. ExampleExample::
int num[3][2]={4,3,5,6,,8,9};int num[3][2]={4,3,5,6,,8,9};
oror
int num[3][2]={{4,3},{5,6},{8,9}}; int num[3][2]={{4,3},{5,6},{8,9}};

valuesvalues
column size column size
row size row size
array name array name
data typedata type

14. Representation of the 2-D Representation of the 2-D
array:-array:-
Rows Rows columnscolumns
00
thth
column 1st column column 1st column

00
thth
row row


11
stst
row row

22
ndnd
row row
a[0][0]a[0][0] a[0][1]a[0][1]
a[1][0]a[1][0] a[1][1]a[1][1]
a[2][0]a[2][0] a[2][1]a[2][1]

15. Memory representation of a 2-D array is Memory representation of a 2-D array is
different from the linear array.different from the linear array.
 in 2-D array possible two types of memory in 2-D array possible two types of memory
arrangements. They are arrangements. They are




Row major arrangement Row major arrangement
Column major arrangementColumn major arrangement
Memory representation of 2-D Memory representation of 2-D
array:-array:-

16. Row major arrangement: Row major arrangement:
00
thth
row 1 row 1
stst
row 2 row 2
ndnd
row row
502 504 506 508 510 512 502 504 506 508 510 512
Column major arrangement:Column major arrangement:
00
thth
column 1 column 1
stst
column column
502 504 506 508 510 512 502 504 506 508 510 512
443355 66 88 99
445588336699

17. We can access any element of the array We can access any element of the array
once we know the base address of the array once we know the base address of the array
and number of row and columns present in and number of row and columns present in
the array.the array.
In general for an array a[m][n] the address In general for an array a[m][n] the address
of element a[i][j] would be,of element a[i][j] would be,
 In row major arrangementIn row major arrangement
Base address+2(i*n+j)Base address+2(i*n+j)
In column major arrangementIn column major arrangement
Base adress+2(j*m+i) Base adress+2(j*m+i)

18. Ex:
we can find the location of the element 8
then an array a[3][2] , the address of
element would be a[2][0] would be
In row major arrangement
loc(a[2][0])=502+2(2*2+0)
=502+8
=510
In column major arrangement
loc(a[2][0])=502+2(0*3+2)
=502+4
=506

19. Multi dimensional arrays:-
An array haves 2 or more subscripts, that An array haves 2 or more subscripts, that
type of array is called multi dimensional type of array is called multi dimensional
array.array.
The 3 –D array is called as The 3 –D array is called as
multidimensional array this can be thought multidimensional array this can be thought
of as an array of two dimensional arrays.of as an array of two dimensional arrays.
Each element of a 3-D array is accessed Each element of a 3-D array is accessed
using subscripts, one for each dimension.using subscripts, one for each dimension.

20. Syntax for the declaration and Syntax for the declaration and
initialization as fallows Syntaxinitialization as fallows Syntax
<data type><array name>[s1][s2][s3] <data type><array name>[s1][s2][s3]
={values}; ={values};


Ex:Ex:
int a[2][3][2]={
{ {2,1},{3,6},{5,3} },
{ {0,9},{2,3},{5,8} }
};


21. Memory representation of 3-D
array:-
In multi dimensional arrays permits only In multi dimensional arrays permits only
a row major arrangement.a row major arrangement.

00
thth
2-D array 1 2-D array 1
stst
2-D array 2-D array

10 12 14 16 18 20 22 24 26 28 30 3210 12 14 16 18 20 22 24 26 28 30 32
21133665533009922335588

22. For any 3-D array a [x][y][z], the element For any 3-D array a [x][y][z], the element
a[i][j][k] can be accessed as a[i][j][k] can be accessed as
Base address+2(i*y*z +j*z+ k)Base address+2(i*y*z +j*z+ k)
Array a can be defined as int a [2][3][2] , Array a can be defined as int a [2][3][2] ,
element 9 is present at a[1][0][1] element 9 is present at a[1][0][1]
Hence address of 9 can be obtained asHence address of 9 can be obtained as
=10+2(1*3*2+0*2+1)=10+2(1*3*2+0*2+1)
=10+14=10+14
=24=24

23. ARRAY OPERATIONSARRAY OPERATIONS
There are several operations that can be There are several operations that can be
performed on an array. They areperformed on an array. They are
InsertionInsertion
DeletionDeletion
TraversalTraversal
ReversingReversing
SortingSorting
SearchingSearching

24. Insertion:Insertion:
Insertion is nothing but adding a new Insertion is nothing but adding a new
element to an array.element to an array.
Here through a loop, we have shifted the Here through a loop, we have shifted the
numbers, from the specified position, one numbers, from the specified position, one
place to the right of their existing place to the right of their existing
position.position.
Then we have placed the new number at Then we have placed the new number at
the vacant place.the vacant place.

25. Ex:Ex:
for (i=4;i>= 2;i++)for (i=4;i>= 2;i++)
{{
a[i]=a[i-1];a[i]=a[i-1];
}}
a[i]=num;a[i]=num;

26. Before insertion :Before insertion :
0 1 2 3 40 1 2 3 4
After insertion:After insertion:

0 1 2 3 4 0 1 2 3 4
Fig:Fig: shifting the elements to the right while shifting the elements to the right while
Insuring an element at 2Insuring an element at 2
ndnd
position position
1111131314144 4 00
111112121313141444

27. Deletion:Deletion:
Deletion is nothing but process of remove Deletion is nothing but process of remove
an element from the array.an element from the array.
Here we have shifted the numbers of Here we have shifted the numbers of
placed after the position from where placed after the position from where
the number is to be deleted, one place to the number is to be deleted, one place to
the left of their existing positions.the left of their existing positions.
The place that is vacant after deletion of The place that is vacant after deletion of
an element is filled with ‘0’.an element is filled with ‘0’.

28. ExEx::
for (i=3;i<5;i++)for (i=3;i<5;i++)
{{
a[i-1]=a[i];a[i-1]=a[i];
} }
a[i-1]=0;a[i-1]=0;

29. Before deletion: Before deletion:
0 1 2 3 40 1 2 3 4
After deletion:After deletion:

0 1 2 3 40 1 2 3 4
Fig:Fig: shifting the elements to the left while shifting the elements to the left while
deleting 3deleting 3
rdrd
element in an array. element in an array.
1111121213131414 44
11111313141444 00

30. Traversal:Traversal:
Traversal is nothing but display the Traversal is nothing but display the
elements in the array.elements in the array.
Ex:Ex:
for (i=0;i<5;i++)for (i=0;i<5;i++)
{{
Printf (“%d\t”, a[i]);Printf (“%d\t”, a[i]);
}}

1111121214144400

31. Reversing:Reversing:
This is the process of reversing the elements This is the process of reversing the elements
in the array by swapping the elements.in the array by swapping the elements.
Here swapping should be done only half Here swapping should be done only half
times of the array size.times of the array size.
Ex:Ex:
for (i=0;i<5/2;i++)for (i=0;i<5/2;i++)
{ {
int temp=a[i];int temp=a[i];
a[i]=a[5-1-1];a[i]=a[5-1-1];
a[5-1-i]=temp;a[5-1-i]=temp;
}}

32. Before swapping:Before swapping:

0 1 2 3 40 1 2 3 4
After swapping:After swapping:
0 1 2 3 40 1 2 3 4
Fig:Fig: swapping of elements while reversing an swapping of elements while reversing an
array.array.



1111121213131414 00
00 1414131312121111

33. Sorting:Sorting:
Sorting means arranging a set of data Sorting means arranging a set of data
in some order like ascending or in some order like ascending or
descending order.descending order.

34. Ex:Ex: for (i=0;i<5;i++) for (i=0;i<5;i++)
{{
for (j=i+1;j<5;j++)for (j=i+1;j<5;j++)
{{
if (a[i]>a[j])if (a[i]>a[j])
{{
temp=a[i];temp=a[i];
a[i]=a[j];a[i]=a[j];
a[j]=temp;a[j]=temp;
} } }} } }

35. 17172525131322 11
1 1 22131317172525
Before sorting:Before sorting:

0 1 2 3 40 1 2 3 4
After sorting:After sorting:
0 1 2 3 40 1 2 3 4

36. Searching:Searching:
Searching is the process of finding the Searching is the process of finding the
location of an element with a given location of an element with a given
element in a list..element in a list..
Here searching is starts from 0Here searching is starts from 0
thth
element element
and continue the process until the given and continue the process until the given
specified number is found or end of list is specified number is found or end of list is
reached.reached.

37. Ex:Ex:
for (i=0;i<5;i++)for (i=0;i<5;i++)
{{
if (a[i]==num)if (a[i]==num)
{{
Printf(“\n element %d is present at %dPrintf(“\n element %d is present at %d
th th
position”,num,i+1);position”,num,i+1);
return;return;
}}if (i==5)}}if (i==5)
Printf (“the element %d is not present in the Printf (“the element %d is not present in the
array ”,num);array ”,num);

38. 111112121313141444 1313
111112121313141444 1313
1313111112121313141444

39. Merging of arraysMerging of arrays
Merging means combining two sorted list Merging means combining two sorted list
into one sorted list.into one sorted list.
Merging of arrays involves two steps:Merging of arrays involves two steps:
They areThey are
 sorting the arrays that are to be sorting the arrays that are to be
merged.merged.
Adding the sorted elements of both Adding the sorted elements of both
the arrays a to a new array in sorted the arrays a to a new array in sorted
order.order.

40. Ex:Ex:
Before merging:Before merging:
11
stst
array 2 array 2
ndnd
array array
After merging:After merging:
22881111
1122338811111313
11331313

41. Arrays of pointersArrays of pointers
A pointer variable always contains an A pointer variable always contains an
address.address.
An array of pointer would be nothing but An array of pointer would be nothing but
a collection of addresses.a collection of addresses.
The address present in an array of pointer The address present in an array of pointer
can be address of isolated variables or can be address of isolated variables or
even the address of other variables.even the address of other variables.

42. An array of pointers widely used for An array of pointers widely used for
stoning several strings in the array.stoning several strings in the array.
The rules that apply to an ordinary array The rules that apply to an ordinary array
also apply to an array of pointer as well.also apply to an array of pointer as well.
The elements of an array of pointer are The elements of an array of pointer are
stored in the memory just like the elements stored in the memory just like the elements
of any other kind of array.of any other kind of array.
Memory representation of the array of Memory representation of the array of
integers and an array of pointers integers and an array of pointers
respectively.respectively.

43. Fig1Fig1:Memory representation of an array of :Memory representation of an array of
integers and integer variables I and j.integers and integer variables I and j.
a[0] a[1] a[2] a[3] i j a[0] a[1] a[2] a[3] i j
100 102 104 106 200 312 100 102 104 106 200 312
Fig2:Fig2:Memory representation of an array of Memory representation of an array of
pointers. pointers.
b[0] b[1] b[2] b[3] b[4] b[5]b[0] b[1] b[2] b[3] b[4] b[5]
8112 8114 8116 8118 8120 8122 8112 8114 8116 8118 8120 8122


33445566
100100102102104104106106200200312312
11 99

44. Arrays and polynomialsArrays and polynomials
Polynomials like 5xPolynomials like 5x
44
+2 x+2 x
33
+7x+7x
22
+10x-8 +10x-8
can be maintained using an array.can be maintained using an array.
To achieve each element of the array To achieve each element of the array
should have two values coefficient and should have two values coefficient and
exponent.exponent.

45. While maintaining the polynomial it is While maintaining the polynomial it is
assumes that the exponent of each assumes that the exponent of each
successive term is less than that of the successive term is less than that of the
previous term.previous term.
Once we build an array to represent Once we build an array to represent
polynomial we can use such an array to polynomial we can use such an array to
perform common polynomial operations perform common polynomial operations
like addition and multiplication.like addition and multiplication.

46. Addition of two polynomialsAddition of two polynomials::
Here if the exponents of the 2 terms Here if the exponents of the 2 terms
beinf compared are equal then their beinf compared are equal then their
coefficients are added and the result is coefficients are added and the result is
stored in 3stored in 3
rdrd
polynomial. polynomial.
If the exponents of the 2 terms are not If the exponents of the 2 terms are not
equal then the term with the bigger equal then the term with the bigger
exponent is added to the 3 rd exponent is added to the 3 rd
polynomial.polynomial.

47. If the term with an exponent is present in If the term with an exponent is present in
only 1 of the 2 polynomials then that only 1 of the 2 polynomials then that
term is added as it is to the 3term is added as it is to the 3
rdrd

polynomial.polynomial.
Ex:Ex:
11
stst
polynomial is 2x polynomial is 2x
66
+3x+3x
55
+5x+5x
22

22
ndnd
polynomial is 1x polynomial is 1x
66
+5x+5x
22
+1x+2+1x+2
Resultant polynomial isResultant polynomial is
3x3x
66
+3x+3x
55
+10x+10x
22
+1x+2+1x+2

48. Multiplication of 2 polynomials:Multiplication of 2 polynomials:
Here each term of the coefficient of the 2Here each term of the coefficient of the 2
ndnd

polynomial is multiplied with each term of the polynomial is multiplied with each term of the
coefficient of the 1coefficient of the 1
stst
polynomial. polynomial.
Each term exponent of the 2Each term exponent of the 2
ndnd
polynomial is polynomial is
added to the each tem of the 1added to the each tem of the 1
stst
polynomial. polynomial.
Adding the all terms and this equations placed Adding the all terms and this equations placed
to the resultant polynomial.to the resultant polynomial.

49. Ex:Ex:
11
stst
polynomial is polynomial is
1x1x
44
+2x+2x
33
+2x+2x
22
+2x+2x
22
ndnd
polynomial is polynomial is
2x2x
33
+3x+3x
22
+4x+4x
Resultant polynomial isResultant polynomial is
2x2x
77
+7x+7x
66
+14x+14x
55
+18x+18x
44
+14x+14x
33
+8x+8x
22

50. THE ENDTHE END