BBM 201
DATA STRUCTURES
Lecture 3:
Representation of Multidimensional Arrays
What is an Array?
• An array is a fixed size sequential collection of elements of identical types.
• A multidimensional array is treated as an array of arrays.
• Let a be a k-dimensional array; the elements of A can be accessed using
the following syntax:
A[ i1 ][ i2 ]…[ ik ]
The following loop stores 0 into each location in a two dimensional array A :
int row, column;
int A[3][4];
for (row = 0; row < 3; row++)
{
for (column = 0; column < 4; column++)
{
A[row][column] = 0;
}
}
Definition of a Multidimensional Array
• One-dimensional arrays are linear containers.
[0] [1] [2]
Multi-dimensional Arrays
[2]
[1]
[0]
[0] [1] [2] [3]
[0] [0]
[1] [1]
[2] [2]
[3]
[0] [1] [2] [3] [4]
abstract view
Definition of a Multidimensional Array
• One-dimensional arrays are linear containers.
int A[3]; [0] [1] [2]
A[1]=2; 2
Multi-dimensional Arrays
[2]
[1]
[0]
[0] [1] [2] [3]
[0] [0]
[1] [1]
[2] [2]
[3]
[0] [1] [2] [3] [4]
abstract view
Definition of a Multidimensional Array
• One-dimensional arrays are linear containers.
int A[3]; [0] [1] [2]
A[1]=2; 2
Multi-dimensional Arrays
[2]
[1]
[0]
[0] [1] [2] [3]
[0] [0]
5
[1] [1]
[2]
[2] -1
[3]
int A[3][4];
[0] [1] [2] [3] [4]
A[0][1]=5;
A[2][3]=-1; abstract view
Definition of a Multidimensional Array
• One-dimensional arrays are linear containers.
int A[3]; [0] [1] [2]
A[1]=2; 2
Multi-dimensional Arrays 7
[2]
[1]
[0]
[0] [1] [2] [3] 10
[0] [0]
5
[1] [1]
[2]
[2] -1
[3]
int A[3][4]; int A[4][5][3];
[0] [1] [2] [3] [4]
A[0][1]=5; A[1][4][1]=10;
A[2][3]=-1; abstract view A[0][1][2]=7;
Dynamic Allocation of 2d Arrays
A dynamically allocated 2d array
of dims: [3][5] could be considered
as a matrix with 3 rows and 5 columns
int** A;
A = new int*[3];
for(int i=0;i<3;i++)
A[i] = new int[5];
A: 1 0 12 -1 4
7 -3 2 5 6
-5 -2 2 9 7
Dynamic Allocation of 2d Arrays
A dynamically allocated 2d array But in reality, A holds a reference to
of dims: [3][5] could be considered an array of 3 items, where each item
as a matrix with 3 rows and 5 columns is a reference to an array of 5 items
int** A; 1
A = new int*[3];
0
for(int i=0;i<3;i++)
A[i] = new int[5]; 12
-1
4
7
A: 1 0 12 -1 4 A:
-3
7 -3 2 5 6
-5
2
-5 -2 2 9 7
-2 5
2 6
9
7
Dynamic Allocation behind the scenes…
1
0x2092a0
int** A; 0
A: 1 0 12 -1 4 0x2092a4
A = new int*[3];
for(int i=0;i<3;i++) 7 -3 2 5 6 0x2092a8 12
A[i] = new int[5]; -5 -2 2 9 7 0x2092ac -1
0x2092b0 4
64 bit addressing 0x2092c0 7
0x209280 0x2092a0 0x2092c4 -3
A: 0x209280 0x2092c8 2
0x209288 0x2092c0
0x2092cc 5
0x209290 0x2092e0
0x2092d0 6
0x2092e0 -5
0x2092e4 -2
0x2092e8 2
0x2092ec 9
0x2092f0 7
Array size
• In a d-dimensional array, which is declared as
<type> a[N1][N2]…[Nd];
i=d
∏
the number of items is: Ni
i=1
Example: What is the number of items in a[20][20][1]?
Storage Allocation
• The storage arrangement shown in this example uses the
array subscript, i.e. array indices.
Array declaration: int a[3][4];
Array elements:
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]
Two-Dimensional Storage Allocation
A 2d array declared in C++ as: A: 0xb0 1
int A[3][5]; 0
could be considered as a matrix A : 0xb0 12
A[0] : 0xb0
with 3 rows and 5 columns 0xb0 : 1 -1
0xb4 : 0 4
0xb8 : 12
A: 1 0 12 -1 4 0xbc : -1 0xc4 7
7 -3 2 5 6 0xc0 : 4
-3
-5 -2 2 9 7 A[1] : 0xc4
2
0xc4 : 7
0xc8 : -3 5
But in reality, it has a linear structure. 0xcc : 2
6
0xd0 : 5
0xd4 : 6
0xd8 -5
A[2] : 0xd8 -2
0xd8 : -5
0xdc : -2 2
0xe0 : 2
0xe4 : 9 9
0xe8 : 7 7
Two-Dimensional Storage Allocation
A 2d array declared in C++ as: Spoiler Alert: A: 0xb0 1
int A[3][5]; Row major ordering of elements 0
could be considered as a matrix A : 0xb0 12
A[0] : 0xb0
with 3 rows and 5 columns 0xb0 : 1 -1
0xb4 : 0 4
0xb8 : 12
A: 1 0 12 -1 4 0xbc : -1 0xc4 7
7 -3 2 5 6 0xc0 : 4
-3
-5 -2 2 9 7 A[1] : 0xc4
2
0xc4 : 7
0xc8 : -3 5
But in reality, it has a linear structure. 0xcc : 2
6
0xd0 : 5
0xd4 : 6
0xd8 -5
A[2] : 0xd8 -2
0xd8 : -5
0xdc : -2 2
0xe0 : 2
0xe4 : 9 9
0xe8 : 7 7
Memory Storage
• There are two types of placement for multidimensional
arrays in memory:
• Row major ordering
• Column major ordering
Raw Major Ordering
offset = irow * NCOLS + icol
[Link]
Column Major Ordering
offset = icol * NROWS + irow
[Link]
Memory Storage
• There are two types of placement for multidimensional
arrays in memory:
• Row major ordering
• Column major ordering
Example: In an array which is defined as A[N1][N2], if the memory
address of A[0][0] is α, then what is the memory address of A[i][0]
(according to row major ordering)?
N2
α + i * N2 N1
Multi-dimensional Arrays
• In row-major layout of multi-dimensional arrays, the last index is the fastest changing.
• In case of matrices the last index is columns, so this is equivalent to the previous
de nition.
d d
∑ ∏ j i
offset = nd + Nd(nd−1 + Nd−1(nd−2 + Nd−2( . . . + N2n1) . . . ))) = ( N )n
i=1 j=i+1
• For a matrix (2D):
offset = n2 + N2 ⋅ n1
• the last index is the fastest changing
[Link]
fi
Multi-dimensional Arrays
• In column-major layout of multi-dimensional arrays, the rst index is the fastest
changing.
• In case of matrices the rst index is rows, so this is equivalent to the previous
de nition.
d i−1
∑ ∏ j i
offset = n1 + N1(n2 + N2(n3 + N3( . . . + Nd−1nd ) . . . ))) = ( N )n
i=1 j=1
• For a matrix (2D):
offset = n1 + N1 ⋅ n2
• the rst index is the fastest changing
[Link]
fi
fi
fi
fi
3D row-major order layout
offset = n3 + N3 ⋅ (n2 + N2 ⋅ n1)
[Link]
3D row-major order layout
TODO: Figure out the 3D layout
for column-major order as an
exercise
The last index is the slowest
changing in column-major, and the
last index here is depth, not columns.
[Link]
Memory Storage
• For a three-dimensional array A[N1][N2][N3]
what is the memory storage like?
which slice?
• Example: char y[2][3][2]
which row? which column?
• Assuming row-major order, what is the memory address of
y[1][2][0], if the memory address of y[0][0][0] α?
Memory Storage
Suppose the memory address of a[0][0][0] is α;
the memory address of a[i][0][0] is:
α + i * N2 * N3
Therefore, the memory address of a[i][j][k] becomes:
α + i * N2 * N3 + j * N3 + k
The memory address of a[i1][i2][i3]…[in] is:
n
n
∏
aj = Nk 0≤ j≤n−1
∑
α+ ij aj where,
k=j+1
j=1
an = 1
Lower/Upper Triangular Matrix
Band Matrix
Sparse Matrix
Lower Triangular Matrix
Lower Triangular Matrix
• Does the definition of a special data structure for triangular matrix
provide any benefits over a typical matrix in terms of memory and
processing time?
• We can insert the items in a single dimensional array:
• ALT a00 a10 a11 a20 a21 a22 a30 a31 a32 a33
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
• Number of items in the array becomes:
1+ 2 +... + (n−1) + n = n(n+1)
2
Lower Triangular Matrix
• How can we find the position of u[i][j] in the array?
• Answer: i=1, there is one item in the 0th row, 2 items in the 1st row.
• i=2, there is one item in the 0th row, 2 items in the 1st row, 3 items in the 2nd row.
• Therefore the address of u[i][j] in the array is calculated as below:
i
k = ∑ (t) + ( j ) = (0 +1+ 2 +... + i) + ( j )
t=0
i(i +1)
= +( j)
2
Lower Triangular Matrix
void main(void){
int alt[MAX_SIZE];
int i, n;
cin>>n; //matrix size
readtriangularmatrix(alt,n);
for(i=0; i<=n*(n+1)/2-1; i++)
cout<< alt[i]<<“ ”;
i=gettriangularmatrix(3,0,n);
if(i==-2)
cout<<“\n invalid index\n”;
else if(i==-1)
cout<<“\n access to the upper triangular\n”;
else
cout<<“\n the position in ‘alt’ matrix:”<<i<<“ value:”<<
alt[i]<<“\n”;
Lower Triangular Matrix
void readtriangularmatrix(int alt[], int n) int gettriangularmatrix(int i, int j, int n){
{
int i, j, k; if(i<0 || i>=n || j<0 || j>=n){
if(n*(n+1)/2 > MAX_SIZE){ //invalid index;
cout<<“\n invalid array size \n”; return -2;
exit(-1); }
} else if(i>=j) //valid index
else return (i+1)*i/2+j;
for(i=0; i<=n-1; i++){ else return -1; //outside of the
k=(i+1)*i/2; triangular; value is zero
for(j=0; j<=i; j++) }
cin>>alt[k+j];
}
}
Upper Triangular Matrix
Upper Triangular Matrix
• How can we find the position of u[i][j] in the array?
i
k = ∑ (t) + ( j ) = (0 +1+ 2 +... + i) + ( j )
• Lower => t=0
i(i +1)
= +( j)
2
• Upper =>
Band Matrix
Matrix (n, a) : n by n matrix, non-zero entries are confined to a diagonal band,
comprising the main diagonal and zero or more diagonals (a-1) on either
side.
Band Matrix b
d00 d01 0 0 n=4
d10 d11 d12 0 a=3
b=2
A=
d20 d21 d22 d23
0 d31 d32 d33 4x4
a
Band Matrix b
d00 d01 0 0 n=4
d10 d11 d12 0 a=3
b=2
A=
d20 d21 d22 d23
0 d31 d32 d33 4x4
a
Band Matrix b
d00 d01 0 0 n=4
d10 d11 d12 0 a=3
b=2
A=
d20 d21 d22 d23
0 d31 d32 d33 4x4
# of elements below triangle (including diagonal)
# of elements above triangle
Band Matrix b
d00 d01 0 0 n=4
d10 d11 d12 0 a=3
b=2
A=
d20 d21 d22 d23
0 d31 d32 d33 4x4
# of elements on and below the diagonal
# of elements above the diagonal
Total # of elements
Band Matrix
• What is the number of items in the array?
• Number of items on and below the diagonal:
n+ (n−1) + (n− 2) +... + n− (a−1)
• Number of items above the diagonal:
(n−1) + (n− 2) +... + n− (b−1)
• Sum of these becomes:
Sum= n+ (n−1) + (n− 2) +... + n− (a−1) + (n−1) + (n− 2) +... + n− (b−1)
(a−1)a (b−1)b
= n(a+ b−1) − −
2 2
dij -> j-i
Band Matrix d00
d10
d01 0
d11 d12 0
0
d20 => d31 -> 2
A=
d20 d21 d22 d23 1 -2: below the main diagonal
n=4
a=3
0 d31 d32 d33 [1-a, b-1]
b=2 -2 -1 0
Fetch from Lower triangle: BAND[Ref[j-i+a-1]+j]
Fetch from Upper triangle: BAND[Ref[j-i+a-1]+i]
Ref
size: a+b-1
Band Matrix
void main(void){
int band[MAX_SIZE];
int search[MAX_SIZE];
int i, n, a, b;
cin>>n; cout<<“n:”<<n;
cin>>a; cout<<“a:”<<a;
cin>>b; cout<<“b:”<<b;
buildbandmatrix(band,search,a,b);
for(i=0; i<=n*(a+b-1)-a*(a-1)/2-b*(b-1)/2-1; i++)
cout<<band[i]<<“ “;
cout<<endl;
for(i=0; i<=a+b-2; i++)
cout<<search[i]<<“ “;
i=getbandmatrix(3,3,n,a,b,search);
if(i==2)
cout<<“\n invalid index“;
else if(i==1)
cout<<“\n item to be searched: 0“;
else
cout<<“\n item to be searched: “<<i<<“->”<< band[i];
Band Matrix
void buildbandmatrix(int band[], int search[], int n, int a, int b){
int i, k, itemnum;
if(n*(a+b-1)-a*(a-1)/2-b*(b-1)/2 > MAX_SIZE){
cout<<“\n not enough memory“;
exit(-1);
}
else{
itemnum=0;
for(i=-a+1; i<=b-1; i++){ //for each diagonal
search[i+a-1]=itemnum;
for(k=0; k<= n-abs(i)-1; k++) //for the current diagonal
cin>>band[search[i+a-1]+k];
itemnum = itemnum+(n-abs(i));
}
}
}
Band Matrix
void getbandmatrix(int i, int j, int n, int a, int b, int search[]){
if(i>=n || i<0 || j>=n || j<0){ //index overflow
cout<<“\n invalid index\n“;
return -2;
}
else{
if(j>i) //above the diagonal
if(j-i<b) //above the upper band
return(search[a-1+j-i]+i); //yes
else //no
return -1;
else if(i-j<a) //below or on the diagonal
return(search[j-i+a-1]+j);
else //not on the band
return -1;
}
Sparse Matrix
• Most of the elements are zero.
• It wastes space.
Sparsity: the fraction of zero elements.
Basic matrix operations:
1. Creation
2. Addition
3. Multiplication
4. Transpose
Sparse Matrix
Data Structure
#define MAX_TERMS 101 • a[0].row: row index
typedef struct{
int col; • a[0].col: column index
int row;
int value; • a[0].value: number of items in
}term;
term a[MAX_TERMS]; the sparse matrix
Rows and columns are in
ascending order!
Sparse Matrix Bookkeeping the parameters:
# of rows, # of cols, # of elms
Matrix Transpose
• Replacement of rows and columns in a matrix is called the
transpose of the matrix:
⎡ 1 3 ⎤ ⎡ 1 0 ⎤
'
A=⎢ ⎥ A =⎢ ⎥
⎣ 0 4 ⎦ ⎣ 3 4 ⎦
• The item a[i][j] becomes a[j][i].
Matrix Transpose
void transpose(term a[],term b[])
{
int n,i,j,currentb;
n=a[0].value; //number of items
b[0].row=a[0].col; //number of rows
b[0].col=a[0].row; //number of columns
b[0].value=n;
if(n>0){
currentb=1;
for(i=0; i<a[0].col; i++)
for(j=1; j<=n; j++) //find the ones with col i in a
if(a[j].col==i){
b[currentb].row=a[j].col;
b[currentb].col=a[j].row;
b[currentb].value=a[j].value;
currentb++;
}
}
}
Question: What is the complexity of this method?
Matrix Transpose
void transpose(term a[],term b[])
{
int n,i,j,currentb;
n=a[0].value; //number of items
b[0].row=a[0].col; //number of rows
b[0].col=a[0].row; //number of columns
b[0].value=n;
if(n>0){
currentb=1;
for(i=0; i<a[0].col; i++)
for(j=1; j<=n; j++) //find the ones with col i in a
if(a[j].col==i){
b[currentb].row=a[j].col;
b[currentb].col=a[j].row;
b[currentb].value=a[j].value;
currentb++;
}
}
}
Question: What is the complexity of this method? O(cols*n)
Question: What is the complexity of this method for a full matrix?
Matrix Transpose
void transpose(term a[],term b[])
{
int n,i,j,currentb;
n=a[0].value; //number of items
b[0].row=a[0].col; //number of rows
b[0].col=a[0].row; //number of columns
b[0].value=n;
if(n>0){
currentb=1;
for(i=0; i<a[0].col; i++)
for(j=1; j<=n; j++) //find the ones with col i in a
if(a[j].col==i){
b[currentb].row=a[j].col;
b[currentb].col=a[j].row;
b[currentb].value=a[j].value;
currentb++;
}
}
}
Question: What is the complexity of this method? O(cols*n)
Question: What is the complexity of this method for a full matrix? O(cols2*rows)
Fast Transpose
#define MAX_TERM 101
typedef struct{
int row;
int col;
int value;
} term;
term a[MAX_TERM];
void fastTranspose(term a[], term b[])
{
int ItemNum[MAX_COL], StartPos[MAX_COL];
int i,j,ColNum=a[0].col,TermNum=a[0].value;
b[0].value=TermNum;
if(TermNum>0){ //does the item exist?
for(i=0;i<ColNum;i++)
ItemNum[i]=0;
for(i=1;i<=TermNum;i++)
ItemNum[a[i].col]++;
StartPos[0]=1; // start from index 1
for(i=1;i<ColNum;i++)
StartPos[i]=StartPos[i-1]+ItemNum[i-1];
for(i=1;i<=TermNum;i++){
j=StartPos[a[i].col]++;
b[j].row=a[i].col;
b[j].col=a[i].row;
b[j].value=a[i].value;
}
}
}
Fast Transpose
• Execute the fastTranspose method.
• Question: What is the complexity of the method?
• Compare its complexity with the previous transpose
method.