Friday, 1 November 2013

Multidimensional Array

One-Dimensional Array
Two-Dimensional Array
Three-Dimensional Array

Some programming Language allows as many as 7 dimension 
\

Two-Dimensional Array 
A Two-Dimensional m x n array A is a collection of m . n data elements such that each element is specified by a pair of integer (such as J, K) called subscript with property that
  1 ≤ J ≤ m   and 1 ≤ K ≤ n



The element of A with first subscript J and second subscript K will be denoted by AJ,K    or A[J][K] 


2D Arrays

The elements of a 2-dimensional array a is shown as below 
a[0][0]     a[0][1]    a[0][2]    a[0][3]
a[1][0]     a[1][1]    a[1][2]    a[1][3]
a[2][0]     a[2][1]    a[2][2]    a[2][3]

Rows Of A 2D Array


rows Of A 2D Array
RElated post :Double link list
Columns Of A 2D Array


Columns Of A 2D Array

2D Array 


Let A be a two-dimensional array m x n
The  array  A will be represented in the memory by a block of m x n sequential memory location
Programming language will store array A either
Column by Column (Called Column-Major Order) Ex: Fortran, MATLAB
Row by Row  (Called Row-Major Order) Ex: C, C++ , Java 
2D Array in Memory
2D Array in Memory
LOC(LA[K]) = Base(LA) + w(K -1)

LOC(A[J,K]) of A[J,K]
  Column-Major Order
  LOC(A[J,K]) = Base(A) + w[m(K-1) + (J-1)]
  Row-Major Order

  LOC(A[J,K]) = Base(A) + w[n(J-1) + (K-1)]
Related post :Circular Link list

2D Array Example

Consider a 25 x 4 array A. Suppose the Base(A) = 200 and w =4. Suppose the programming store 2D array using row-major. Compute LOC(A[12,3])
LOC(A[J,K]) = Base(A) + w[n(J-1) + (K-1)]
LOC(A[12,3]) = 200 + 4[4(12-1) + (3 -1)] = 384 

An n-dimensional m1 x m2 x …. X mn  array B is a collection of m1.m2mn data elements in which each element is specified by a list of n integers – such as K1, K2, …., Kn – called subscript with the property that
  1≤K1≤m1,  1≤K2≤m2,  ….   1≤Kn≤mn
The Element B with subscript K1, K2, …,Kn will be denoted by

  BK1,K2, …,Kn      or   B[K1,K2,….,Kn] .
Let C be a n-dimensional array
Length Li of dimension i of C is the number of elements in the index set
  Li = UB – LB + 1
For a given subscript Ki,  the effective index Ei of Li is the number of indices preceding Ki in the index set
  Ei = Ki – LB 

Address LOC(C[K1,K2, …., Kn]) of an arbitrary element of C can be obtained as
  Column-Major Order
  Base( C) + w[((( … (ENLN-1 + EN-1)LN-2) + ….. +E3)L2+E2)L1+E1]
  Row-Major Order
  Base( C) + w[(… ((E1L2 + E2)L3 + E3)L4 + ….. +EN-1)LN +EN] .

Example :

MAZE(2:8, -4:1, 6:10)
Calculate the address of MAZE[5,-1,8]
Given: Base(MAZE) = 200, w = 4, MAZE is stored in Row-Major order
L1 = 8-2+1 = 7, L2 = 6, L3 = 5
E1 = 5 -2 = 3, E2 = 3, E3 = 2
Base( C) + w[(… ((E1L2 + E2)L3 + E3)L4 + ….. +EN-1)LN +EN]
E1L2 = 3 . 6 = 18
E1L2 + E2 = 18 + 3 = 21
(E1L2 + E2)L3 = 21 . 5 = 105
(E1L2+E2)L3 + E3 = 105 + 2 = 107
MAZE[5,-1,8] = 200 + 4(107) = 200 + 248 = 628 


Pointer, Pointer Array :

Let DATA be any array
A variable P is called a pointer if P points to an element in DATA i.e if P contains  the address of an element in DATA
An array PTR is called a pointer array if each element of PTR is a pointer.

Two Dimensional 4x9 or 9x4 array 

Two Dimensional 4x9 or 9x4 array


Now pointer representation

each pointer represent first element of corresponding rows 


YOU may like these

No comments:

Post a comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets