My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Resources » Articles/Knowledge Sharing » Computer & Technology »
Array in C Language
|
An array is a list of a finite number of homogeneous data elements.The number of elements in an array is called the length or size of an array.Length of an array can be obtained from the index set by the formula :
Length=UB-LB+1
Where UB is the largest index , called the upper bound and LB is the smallest index , called the lower bound.Suppose int Arr[10] is an integer array .Upper bound of this array is 9 and lower bound of this array is 0 ,so the length is 9-0+1=10.
In an array ,the elements are stored successive memory cells.Computer does not need to keep track of the address of every elements in memory.It will keep the address of the first location only and that is known as base address of an array. Using the base address , address of any other location of an array can be calculated by the computer.Suppose Arr is an array whose base address is Base(Arr) and w is the number of memory cells required by each elements of the array Arr.The address of Arr[k] – k being the index value can be obtained by using the formula :
Address(Arr[k])=Base(Arr)+w(k-Lower Bound)
Two Dimensional Array :- Suppose Arr is a two dimensional row X col array.The first dimension of Arr contains the index set 0,1,2, … row-1 ( the lower bound is 0 and the upper bound is row-1) and the second dimension contains the index set 0,1,2,… col-1( with lower bound 0 and upper bound col-1.)
The length of each dimension is to be calculated .The multiplied result of both the lengths will give you the number of elements in the array.
Representation of two dimensional array in memory :-
Let’s assume Arr is an two dimensional 2 X 2 array .The array may be stored in memory one of the following way :-
1. Column by column I,e column major order
2. Row by row , I,e in row major order
The following figure shows both representation of the above array.
By row-major order we mean that the elements are so arranged that the subscript at the extreme right varies fast than the subscript at it’s left., while in column-major order , the subscipt at the extreme left changes rapidly , then the subscipt at it’s right and so on.
1,1
2,1
1,2
2,2
1,1
1,2
2,1
2,2
Column major Row major
Now we know that computer keeps track of only the base address. So the address of any specified location , for example Arr[j,k] of a two dimensional array Arr[m,n] can be calculated by using the following formula :-
(Column major order ) Address(Arr[j,k])= base(Arr)+w[m(k-1)+(j-1)]
(Row major order) Address(Arr[j,k])=base(Arr)+w[n(j-1)+(k-1)]
For example Arr(25,4) is an array with base value 200.w=4 for this array.The address of Arr(12,3) can be calculated using row-major order as
Address(Arr(12,3) )= 200+4[4(12-1)+(3-1)]
=200+4[4*11+2]
=200+4[44+2]
=200+4[46]
=200+184
=384
Again using column-major order
Address(Arr(12,3) )= 200+4[25(3-1)+(12-1)]
=200+4[25*2+11]
=200+4[50+11]
=200+4[61]
=200+244
=444
Suppose Arr[2,4,3] is a multidimensional array and the array is represented in column-major order.The following left diagram represents .Right diagram represents the row-major order representation.
1,1,1
2,1,1
1,2,1
2,2,1
1,3,1
…….
2,4,3
1,1,1
1,1,2
1,1,3
1,2,1
1,2,2
….
2,4,3
The above array can also be represented as Arr[1:2,1:3,1:4] or as Arr[1,2][1,3][1,4] etc..Each pair of values within the third bracket indicates the index values of one dimeniom.The first value indicates the lower bound and the second value indicates the upper bound of one dimension.So length of each dimension can also be calculated.
Suppose L1,L2 ans L3 are the length of first , second and third dimension of an array Arr[a:b,c:d,e:f].You want to calculate the address of any specified location Arr[x,y,z]. Effective index E1 for the first dimension is :-E1=x-a . Similarly E2=y-c and E3=z-e.If the array is arranged in row-major order then the address of Arr[x,y,z] will be :-
Base(Arr)+w((E1L2+E2)L3+E3)
[Base(Arr)+w((…((E1L2+E2)L3+E3)L4+E4)L5+E5)….))]
Again if the same array is arranged in column – major order the address of the same location would be
Base(Arr)+w((E3L2+E2)L1+E1)
[Base(Arr)+w((…(EnLn-1+En-1)Ln-2)+En-2)Ln-3)+….+E3)L2+E2)L1+E1)]
Suppose an array is given as Arr[2:8,-4:1,6:10] and we have to display the address of Arr[5,-1,8] (w=4 , given and base address is 200)
Here L1 = 8-2+1=7
L2 = 1-(-4)+1=6
L3 = 10-6+1=5
So the array contains L1*L2*L3=7*6*5=210 elements.
E1 = 5-2=3
E2= -1-(-4)=3
E3=8-6=2
So applying row – major order we can calculate the address as follows :-
Address= Base(Arr)+w((E1L2+E2)L3+E3)
=200+4((3*6+3)5+2)
=200+4((21)5+2)
=200+4(105+2)
=200+4(107)
= 200+428
= 628
Again if the array is arranged in column-major ordwr then the address is :
Address=Base(Arr)+w((E3L2+E2)L1+E1)
=200+4((2*6+3)7+3)
=200+4(15*7+3)
=200+4(108)
=200+432
=632
Obtain the formula Base(Arr)+w((E1L2+E2)L3+E3) for a row-major order .
E1 is the effective index of the first dimension of the location whose address is to be calculated and L2 is the length of the second dimension.If the array were an one dimensional array then it would take E1 number of memory blocks.If it were a two dimensional array then it would take L2 number of E1 locations (L2 being the length of the second dimension ) plus the effective index of the second dimension.So the number of locations would become E1L2+E2.But ultimately the array is three dimensional so the number of memory blocks will be L3 number of (E1L2+E2) plus effective index of the third dimension.Multiplying this number by ‘w’ , memory space for each memory block , total memory space required for that array with specific index values will be obtained.Now if we add the base address value with the total memory space value , we will get the address of the location.
Assume a three dimensional array is declared as A[-5:10][0:12][-10:1].The starting address of the first element of the array is x.The array elements are stored in column-major order.Find the memory location where A[2][4][1] is stored.
E1=2-(-5)=7
E2=4-0=4
E3=1-(-10)=11
L1=10-(-5)=15
L2=12-0=12
L3=1-(-10)=11
Address= Base(Arr)+w((E3L2+E2)L1+E1)
x+w((11*12+4)15+7)
x+w((132+4)15+7)
=x+w(136*15+7)
? Assume that a 3-dimensional array is declared as X[p1:q1][p2:q2][p3:q3]
obtain the addressing formulae for the element X[i][j][k]-assuming row-order representation of the array elements and each element occupies m bytes.
Length of the first dimention is L1=q1-p1, length of the second dimention is L2=q2-p2 and length of the third dimension L3 =q3-p3.
Effective index of each dimension starting from first is E1=i-p1 , E2=j-p2 and E3=k-p3.
So in array X[i][j][k] , there are E1 * L2 plus E2 number of locations, if it were a two dimentional array.But it is a three dimensional array , so for every unit of length of the third dimension there are E1 * L2 plus E2 number of locations.For L3 unit of length , there will be (E1 * L2 plus E2)*L3 locations plus E3.Each elements occupies m bytes.So total bytes will be m((E1 * L2 +E2)*L3 +E3).Ultimately the address will be
Base+ m((E1 * L2 +E2)*L3 +E3).
? Assume that a 2-dimensional array is declared as X[p1:q1][p2:q2]
obtain the addressing formulae for the element X[i][j]-assuming column-order representation of the array elements and each element occupies m bytes.
Length of the first dimention is L1=q1-p1,length of the second dimention is L2=q2-p2 .
Effective index of each dimension starting from first is E1=i-p1 , E2=j-p2 .
So in array X[i][j] , there are E2 number of locations for every unit of length of the first dimension (means row) .So there are E2 * L1 number of locations for L1 length..Again E1 is the effective length of the row, so for every unit of row index the number of locations will be incremented by 1 upto E1.So the number of locations will be E2L1+E1 .m being the value in bytes occupied by each location , the address will be
Base+ m(E2 * L1 +E1).
|
Responses
|
No responses found. Be the first to respond and make money from revenue sharing program.
|
|
Advertise Here
|