Chapter 4
Arrays and Matrix
4.1 1D-Array
1,One-dimensional array
? 1D-array is a limited sequence composed of n (n?0)
elements which are of the same data type.
? For example:
? Location of the element
Loc(a[i])=Loc(a[0])+i
35 27 49 18 60 54 77 83 41 02a
0 1 2 3 4 5 6 7 8 9
4.1 1D-Array
Class definition of 1D-Array(program 4-1)
template<class T>
class Array1D{
public:
Array1D(int size=0);
Array1D(const Array1D<T>& v);
~Array1D(){delete [] element;}
T& operator[](int i)const;
int Size(){return size;}
//some operation
4.1 1D-Array
private:
int size;
T*element; //1D array
};
4.1 1D-Array
1)Constructor for 1D array
Program 4-2
template<class T>
Array1D<T>::Array1D(int sz)
{ if(sz<0) throw BadInitializers();
size=sz;
element=new T[sz];
}
4.1 1D-Array
Template<class T>
Array1D<T>::Array1D(const Array1D<T>& v)
{//copy constructor for 1D array
size=v.size;
element=new T[size]; //get space
for(int i=0;i<size;i++) //copy elements
element[i]=v.element[i];
}
4.1 1D-Array
2)overloading the array indexing operator
Program 4.3
template<class T>
T& Array1D<T>::operator[](int i)const
{//return reference to element I.
if(i<0||i>=size)throw OutOfBounds();
return element[i];
}
4.1 1D-Array
3)Overloading the assignment operator
Program 4.4
template<class T>
Array1D<T>& Array1D<T>::operator=
(const Array1D<T>& v)
{if (this!=&v){//not self-assignment
size=v.size;
delete [] element; //free old space
element=new T[size];//get right amout
4.1 1D-Array
for(int i=0;i<size;i++) //copy elements
element[i]=v.element[i];
}
return *this;
}
4.2 2D-Array
Two-dimensional arrays are composed of n
rows and m columns.
a00 a01 a02……a 0 m-1
a10 a11 a12……a 1 m-1
a20 a21 a22……a 2 m-1
………….
an-10 an-11an-12…..a n-1 m-1
A[n][m]=
4.2 2D-Array
There are three ways to implement a 2D array
1) mapping the 2D-array to a 1D-array
a00 a01 a02……a 0 m-1
a10 a11 a12……a 1 m-1
a20 a21 a22……a 2 m-1
………….
an-10 an-11an-12…..a n-1 m-1
a00
a01
…
a0 m-1
a10
a11
….
an-1 m-1
Row major order
4.2 2D-Array
Location mapping:
a) row-major order
Loc(a[i][j])=Loc(a[0][0])+[i*m+j]*l
b) column-major order
Loc(a[i][j])=Loc(a[0][0])+[j*n+i]*l
4.2 2D-Array
2)using a pointer to a pointer to an element
For example:
X[0]
X[1]
X[2]
[0] [1] [2] [3] [4]
Memory structure for a three by five
array
4.2 2D-Array
3)using array of 1D-arrays
Each element of
the 2D array is a
1D array
4.2 2D-Array
An 3D-Array:
int a[m1][m2][m3]
Location mapping
Loc(a[i][j][k])=Loc(a[0][0][0])+i*m2*m3+j*m3+k
4.3 Matrix
1.definition,a m*n Matrix is a table with m
rows and n columns,m and n are the
dimensions of the matrix.
For example,a 5*4 matrix
7 2 0 9
0 1 0 5
6 4 2 0
8 2 7 3
1 4 9 6
1
2
3
4
5
1 2 3 4
4.3 Matrix
2.Matrix can be implemented with a two
dimensional array,
int x[m][n] or Array2D<int>x[m][n]
? use x(i,j) to index the matrix element,
i>=1&&i<=m&&j>=1&&j<=n
the private data member is rows,cols,
element
4.3 Matrix
Class definition of Matrix(program 4-12)
template<class T>
class Matrix {
public:
Matrix(int r=0,int c=0);
Matrix(const Matrix<T>&m);
~Matrix(){delete[] element;}
int Rows()const {return rows;}
4.3 Matrix
int Columns ()const{return cols;}
T& operator ()(int i,int j)const;
Matrix<T>& operator=(const Matrix<T>& m);
Matrix<T> operator+()const;
Matrix<T> operator+(const Matrix<T>& m)const;
Matrix<T> operator-()const;
Matrix<T> operator-(const Matrix<T>& m)const;
Matrix<T> operator*(const Matrix<T>& m)const;
Matrix<T>& operator+=(const T& x);
4.3 Matrix
private:
int rows,cols;//matrix dimensions
T* element; //element array
};
4.3 Matrix
Matrix constructor(program 4.13)
template<class T>
Matrix<T>::Matrix(int r,int c)
{//Matrix constructor
//validate r and c
if(r<0||c<0)throw BadInitializers();
if((!r||!c)&&(r||c)) throw BadInitializers();
//create the matrix
rows=r; cols=c; element=new T[r*c];
}
4.3 Matrix
Index a matrix(program 4.14)
template<class T>
T& Matrix<T>::operator()(int i,int j)const
{//return a reference to element (i,j).
if(i<1||i>rows||j<1||j>cols)throw OutofBounds();
return element[(i-1)*cols+j-1];
}
4.4 Special Matrix
A square matrix has the same number of rows
and columns,
Some special forms of square matrix that arise
frequently are:
? Diagonal,M(i,j)=0 for i!=j;
? Tridiagonal,M(i,j)=0 for|i-j|>1;
? Lower triangular,M(i,j)=0 for i<j;
? Upper triangular,M(i,j)=0 for i>j;
? Symmetric.M(i,j)=M(j,i);
4.4 Special Matrix
? For example:
2 0 0 0 2 1 0 0 2 0 0 0
0 1 0 0 3 1 3 0 5 1 0 0
0 0 4 0 0 5 2 7 0 3 1 0
0 0 0 6 0 0 9 0 4 2 7 0
(a)Diagonal (b) Tridiagonal ? Lower Triangular
2 1 3 0 2 4 6 0
0 1 3 8 4 1 9 5
0 0 1 6 6 9 4 7
0 0 0 0 0 5 7 0
(d)Upper Triangular (e)Symmetric
4.4 Special Matrix
1)Lower Triangular
Location mapping in row-major order:
Loc(a(i,j))=Loc(a(1,1))+[(1+2+3+……+i -1)+(j-1)]*l
=Loc(a(1,1))+(i*(i-1)/2+j-1)*l
a11
a21 a22
a31 a32 a33
……
an1 an2 ………a nn
4.4 Special Matrix
2)Upper Triangular
Location mapping in row-major order:
Loc(a(i,j))=Loc(a(1,1))+[?(n-k+1)+j-i]*l
a11 a12 ………a 1n
a22………a 2n
………..
ann
K=1
i-1
4.4 Special Matrix
3) Tridiagonal
Location mapping in row-major order:
Loc(a(i,j))=Loc(a(1,1))+[(i-1)*3-1+(j-i+1)]*l
a11 a12
a21 a22 a23
a32 a33 a34
……………
an,n-1 an,n
4.5 Sparse Matrices
1.Definition:
An m*n matrix is said to be sparse if,many”
of its elements are zero.
number of zero elements>>number of non-zero
elements
4.5 Sparse Matrices
An example of sparse matrix:
0 0 0 2 0 0
0 6 0 0 7 0
0 0 0 9 0 0
0 4 5 0 0 0
4.5 Sparse Matrices
2.Array representation
? The nonzero entries of an sparse matrix may
be mapped into a 1D array in row major order.
? The structure of each element is:
row col value
4.5 Sparse Matrices
? For example,
0 0 0 2 0 0
0 6 0 0 7 0
0 0 0 9 0 0
0 4 5 0 0 0
1 4 2
2 2 6
2 5 7
3 4 9
4 2 4
4 3 5
row col valuea:
MaxTerms-1
0
1
2
4.5 Sparse Matrices
We define the template class Term as follow:
template<class T>
class Term{
private:
int row,col;
T value;
}
4.5 Sparse Matrices
The private members the Class SparseMatrix:
? rows—the number of the rows
? Cols—the number of the columns
? Terms—the number of nonzero terms
? a—array of type Term
? MaxTerms—size of a
4.5 Sparse Matrices
The class SparseMatrix(Program 4.20)
template <class T>
class SparseMatrix
{friend ostream& operator<<
(ostream&,const SparseMatrix<T>&);
friend istream& operator>>
(istream&,SparseMatrix<T>&);
public:
SparseMatrix(int maxTerms=10);
~SparseMatrix(){delete[] a;}
4.5 Sparse Matrices
void Transpose(SparseMatrix<T> &b)const;
void Add(const SparseMatrix<T>&b,
SparseMatrix<T>& c)const;
private:
void Append(const Term<T>&t);
int rows,cols; //matrix dimensions
int terms //current number of nonzero terms
Term<T>*a; //term array
int MaxTerms; //size of array a
}
4.5 Sparse Matrices
1).SparseMatrix constructor(program 4.21)
Template <class T>
SparseMatrix<T>::SparseMatrix(int maxTerms)
{ if(maxTerms<1)throw BadInitializers();
MaxTerms=maxTerms;
a=new Term<T>[MaxTerms];
terms=rows=cols=0;
}
4.5 Sparse Matrices
2)SparseMatrix input and output codes
(program 4.22)
overload <<
template<class T>
ostream& operator<<(ostream& out,const
SparseMatrix<T>&x)
{//put *this in output stream.
4.5 Sparse Matrices
//put matrix characteristic
out<<“rows=“<<x.rows<<“columns=“<<x.cols<<endl;
out<<“nonzero terms=“<<x.terms<<endl;
//put terms,one per line
for(int i=0;i<x.terms;i++)
out<<“a(“<<x.a[i].row<<’,’<<x.a[i].col<<“)=“
<< x.a[i].value<<endl;
return out;
}
4.5 Sparse Matrices
overload >>
template<class T>
istream& operator>>(istream& in,SparseMatrix<T>& x)
{//input a sparse matrix
//input matrix characteristics
cout<<“Enter number of rows,columns,and terms”
<<endl;
in>>x.rows>>x.cols>>x.terms;
if(x.terms>x.MaxTerms)throw NoMem();
4.5 Sparse Matrices
for(int i=0;i<x.terms;i++){
cout<<“Enter row,column,and value of term”
<<(i+1)<<endl;
in>>x.a[i].row>>x.a[i].col>>x.a[i].value;
}
return in;
}
4.5 Sparse Matrices
0 0 0 2 0 0
0 6 0 0 7 0
0 0 0 9 0 0
0 4 5 0 0 0
3) Transposing a Sparse Matrix
For example 0 0 0 0
0 6 0 4
0 0 0 5
2 0 9 0
0 7 0 0
0 0 0 0
Before transpose after transpose
4.5 Sparse Matrices
1 4 2
2 2 6
2 5 7
3 4 9
4 2 4
4 3 5
row col value
2 2 6
2 4 4
3 4 5
4 1 2
4 3 9
5 2 7
row col valuea b.a
4.5 Sparse Matrices
0 0 0 2 0 0
0 6 0 0 7 0
0 0 0 9 0 0
0 4 5 0 0 0
RowNext[i]=ColSize[i-1]+RowNext[i-1]
0
2
1
2
1
0
ColSize[0]
[1]
[2]
[3]
[4]
[5]
[6]
0
0
2
3
5
6
RowNext[0]
[1]
[2]
[3]
[4]
[5]
[6]
4.5 Sparse Matrices
Transposing a Sparse Matrix
? The transposed matrix is returned in b.
? Array ColSize[i] is the number of nonzero
terms of the input matrix that are in column i.
? Array RowNext[i] denotes the location in b
for the next nonzero term that is in row i of the
transpose.
? The time complexity is O(cols+terms).
4.5 Sparse Matrices
3)template<class T>
void SparseMatrix<T>::
Transpose(SparseMatrix<T> &b)const
{//Return transpose of *this in b
//make sure b has enough space
if(terms>b.MaxTerms)throw NoMem();
4.5 Sparse Matrices
//set transpose characteristics
b.cols=rows;
b.rows=cols;
b.terms=terms;
//initialize to compute transpose
int*ColSize,*RowNext;
ColSize=new int[cols+1];
RowNext=new int [rows+1];
4.5 Sparse Matrices
//find number of entries in each column of *this
for(int i=1;i<=cols;i++) ColSize[i]=0;
for(int i=1;i<terms;i++)ColSize[a[i].col]++;
//find the starting point of each row of b
RowNext[1]=0;
for(int i=2;i<=cols;i++)
RowNext[i]=RowNext[i-1]+ColSize[i-1];
4.5 Sparse Matrices
//perform the transpose copying from *this to b
for(int i=0;i<terms;i++){
int j=RowNext[a[i].col]++;//position in b
b.a[j].row=a[i].col;
b.a[j].col=a[i].row;
b.a[j].value=a[i].value;
}
}
4.5 Sparse Matrices
3.Linked Representation
? The shortcoming of the 1D-array representation
is that the actual number of nonzero terms
cannot be computed because of some
operations(addition,subtraction,multiplication)
? A linked representation can solve this problem
4.5 Sparse Matrices
1)For example
0 0 0 2 0 0
0 6 0 0 7 0
0 0 0 9 0 0
0 4 5 0 0 0
4 2 0
2 6 5 7 0
4 9 0
2 4 3 5 0
col val link first
a.first
1
2
3
4 0
row
link
4.5 Sparse Matrices
2)Chain Node Types
? The chain defined by the unshaded nodes is
members of the class Chain<Cnode<T>>,
where Cnode is
and the chain node is
Col value
Col value link
4.5 Sparse Matrices
? The chain defined by the shaded nodes is a
member of the class Chain<Headnode<T>>
where Headnode<T> is,
a is an instance of Chain<Cnode<T>>
so,the chain node is,
row a
row link a
4.5 Sparse Matrices
3) Class definition
? Cnode
template<class T>
class Cnode{
public:
int operator!=(const Cnode<T>& y)
{return (value!=y.value);}
void Output(ostream& out)const
{out<<“column”<<col<<“value”<<value;}
4.5 Sparse Matrices
private:
int col;
T value;
};
4.5 Sparse Matrices
? HeadNode
template<class T>
class HeadNode{
public:
int operator!=(const HeadNode<T>& y)
{return (row!=y.row);}
void Output(ostream& out)const
{out<<“row”<<row;}
4.5 Sparse Matrices
private,
int row;
Chain<Cnode<T>> a;
};
4.5 Sparse Matrices
? Linked Matrix
template<class T>
class LinkedMatrix{
public:
LinkedMatrix(){}
~LinkedMatrix(){}
void Transpose(LinkedMatrix<T>& b)const;
void Add(const LinkedMatrix<T>& b,
LinkedMatrix<T>& c) const;
4.5 Sparse Matrices
private:
int rows,cols;
Chain<HeadNode<T>> a;//headnode chain
};