Chapter 4 Array and Matrices

Presentation on theme: "Chapter 4 Array and Matrices"— Presentation transcript:

1 Chapter 4 Array and Matrices

2 Contents 4.1 array 4.2 matrices 4.3 special matrices
4.4 sparse matrices

3 Why Matrices? Array is a standard type declaration of C++, however, the size and representation is unchanged. We want use object to represent a matrix for the purpose of saving space when the matrix is sparse, providing functions to hand exception and calculating on its elements within a package.

4 4.1 Array 4.1.1 The abstract data type 4.1.2 indexing a C++ array
row and column major mappings The class Array1D The class Array2D

5 4.1.1 Represent an array as an abstract data type
AbstrctDataType Array { Instances Set of (index,value) pairs, no two pairs have the same index. Operations Create()：create an empty array Store(index,value)：add this pair to set deleting existing pair (if nay) with the same index Retrieve(index)：return the pair with this index value

6 4.1.2 C++ array k dimension array score：
The index must be of the form: [i1][i2][i3]…[ik] k dimension array score： int score[u1][u2][u3]…[uk]. (ui---正的常量或有常量表示的表达式） 0≤ij＜uj ≤ j ≤k The number of element of score: n=u1u2u3…uk The memory needed: //assumed the data type is integer n x sizeof(int) bit, where sizeof(int) is the number of bits to store an integer. The memory reserved by c++ : //store in a continual area start -----start + sizeof(score) -1

7 4.1.3 Row and Column Mapping In order to implement Store and Retrieve，we need to map the index values to bytes in [start, start + n*sizeof(score)-1]: [i1][i2]…[ik]  start + map(i1,i2,…ik) * sizeof(int) map(i1,i2,…ik): n-1 For one demission array, the mapping function is map(i1) = i1 Since for a two demission array, e.g. int score[3][6], the indices are of the form: [0][0] [0][1] [0][2] [0][3] [0][4] [0][5] [1][0] [1][1] [1][2] [1][3] [1][4] [1][5] [2][0] [2][1] [2][2] [2][3] [2][4] [2][5]

8 The mapping function is
map(i1 ,i2 ) = i1u2 + i2

9 行主映射和列主映射 行主映射(row major mapping) Int s[u1][u2] Map function
s[0][0] 1 s[0][1] ……. s[0][u2-1] s[1][0] s[1][1] s[1][u2-1] map(i1,i2) s[i1][i2] s[u1-1][0] s[u1-1][1] s[u1-1][u2-1] 行主映射(row major mapping) Int s[u1][u2] Map function map(i1,i2)= u2 * i1 + i2

10 行主映射和列主映射 列主映射 Column major mapping 映射函数: map(i1,i2)= u1 * i2 + i1
s[0][0] 1 s[1][0] ……. s[u1-1][0] s[0][1] s[1][1] s[u1-1][1] map(i1,i2) s[i1][i2] s[0][u2-1] s[1][u2-1] s[u1-1][u2-1] 列主映射 Column major mapping 映射函数: map(i1,i2)= u1 * i2 + i1 在 C++ 使用的是哪一种? 行主映射!

11 行主映射和列主映射 对三维数组 (int score[u1][u2][u3]) 索引按行主次序排列 int score[3][2][4]：
[0][0][0],[0][0][1],[0][0][2],[0][0][3],[0][l][0],[0][l][l],[0][1][2],[0][1][3], [1][0][0],[l][0][l],[1][0][2],[1][0][3],[1][1][0],[1][1][1],[1][1][2],[1][1][3], [2][0][0],[2][0][1],[2][0][2],[2][0][3],[2][1][0],[2][1][1],[2][l][2],[2][1][3] 首先列出所有第一个坐标为0的索引，然后是第一个坐标为1的索引，⋯。 第一个坐标相同的所有索引按其第二个坐标的递增次序排列，前两个坐标相同的所有索引按其第三个坐标的递增次序排列。 映射函数: row major mapping map(i1,i2,i3) = i1u2u3+i2u3+i3 列主映射，映射函数 ？

12 Why Class Array1D Class Array1D definition
Permit users use indexes that fall outside range E.g. For an array int a[9]，to access a[-3]，a[9] and a[90] is permitted even if -3，9 and 90 are invalid indexes. Define the operation, e.g. +/-, cout << a << endl, on array (as an object). Class Array1D definition Let each instance X be a one-dimensional array. The elements of X is stored in X.element， X.element [i] denotes the ith element of X，0≤i<size。

13 4.1.4 Class Array1D template<class T> class Array1D { public:
Array1D(int size = 0); //normal constructor Array1D(const Array1D<T>& v); // 复制构造函数 Copy constructor ~Array1D() {delete []element;} T& operator[](int i) const; int Size() {return size;} Array1D<T>& operator=(const Array1D<T>& v); Array1D<T> operator+() const; // unary for changing sign Array1D<T> operator+(const Array1D<T>& v) const; Array1D<T> operator-() const; // unary minus for changing sign Array1D<T> operator-(const Array1D<T>& v) const; Array1D<T> operator*(const Array1D<T>& v) const; Array1D<T>& operator+=(const T& x); private: int size; T *element; //一维数组 };

14 构造函数和复制构造函数 template<class T>// Constructor
Array1D<T>::Array1D(int sz) {// create an one dimension array with size sz if (sz<0) throw BadInitializers(); size=sz; element=new T[sz]; } template<class T> // copy constructor Array1D<T>::Array1D(const Array1D<T>& v) {//create an array with the size of array v and then assign the value with the array v size=v.size; element=new T[size]; // 申请空间 for (int i=0; i<size; i++) // 复制元素 element[i]=v.element[i];

15 一维数组元素的操作 这里我们要把用类定义的数组看成为对象，内部的数组对外面是隐蔽的，若X,Y为定义的两个类，X[3]+Y[6] ，[].+,-,*,等都要通过函数调用的形式实现，因此要定义相应的函数。

16 Index operator‘[]’and ‘=’
template<class T> T& Array1D<T>::operator[](int i) const {// 返回指向第i个元素的引用 if (i < 0 || i >= size) throw OutOfBounds(); return element[i]; } Array1D<T>& Array1D<T>::operator=(const Array1D<T>& v) {// 重载赋值操作符=, 使得可以执行矩阵级别的赋值 if (this != &v) {// avoid x=x size=v.size; delete [] element; // 释放原空间 element = new T[size]; // 申请空间 for (int i = 0; i < size; i++) //复制元素 element[i]=v.element[i]; return *this;

17 operator‘–’//减法和正负号 template<class T> // subtract (矩阵级别的减法）
Array1D<T> Array1D<T>:: operator-(const Array1D<T>& v) const {// 返回w = (*this) - v if (size != v.size) throw SizeMismatch(); Array1D<T> w(size); // 使用前面定义的函数来创建结果数组w for (int i = 0; i < size; i++) w.element[i]=element[i]-v.element[i]; return w; } template<class T> //改变符号 Array1D<T> Array1D<T>::operator-() const {// 返回w = -(*this) // Array1D<T> w(size); // 创建结果数组w w.element[i] = -element[i];

18 操作符 ‘+=’//y=x+y template<class T> // addition on the level of array Array1D<T>& Array1D<T>::operator+=(const T& x) { //把x 加到( * this )的每个元素上 for (int i = 0; i < size; i++) element[i] += x; return *this; }

19 4.1.5 Class Array2D template<class T> class Array2D { public:
Array2D(int r = 0, int c = 0); Array2D(const Array2D<T>& m); // 复制构造函数 ~Array2D() {delete [] row;} int Rows() const {return rows;} int Columns() const {return cols;} Array1D<T>& operator[](int i) const; Array2D<T>& operator=(const Array2D<T>& m); Array2D<T> operator+() const; // 一元加法操作符 Array2D<T> operator+(const Array2D<T>& m) const; Array2D<T> operator-() const; // 一元减法操作符 Array2D<T> operator-(const Array2D<T>& m) const; Array2D<T> operator*(const Array2D<T>& m) const; Array2D<T>& operator+=(const T& x); private: int rows, cols; // 数组维数 Array1D<T> *row; // row[i]是类型为Array1D的一维数组，它代表二维数组的第i行。 };

20 构造函数 template<class T> Array2D<T>::Array2D(int r, int c)
{// 二维数组的构造函数 // 合法的r 和c if (r < 0 || c < 0) throw BadInitializers(); if ((!r || !c) && (r || c)) //必须两个都大于0 throw BadInitializers(); rows = r; cols = c; row = new Array1D<T> [r]; // 分配维数=r， 并且c=0一维数组 for (int i = 0; i < r; i++) // 产生2维数组 row[i].ReSize(c); } Array1D<T> Array1D<T> :: ReSize(int sz) { delete [ ] element; size = sz; element = new T [size]; return *this;}

21 Element of array X X[i][j] is parsed as (x.operator[i]).operator[j], so Array2D<T>::operator [] is invoked first with i, and return an object Y, typeof(Y)::operator[] is invoked with parameter j

22 复制构造函数 Copy constructor function
template<class T> Array2D<T>::Array2D(const Array2D<T>& m) {// 二维数组的复制构造函数 rows = m.rows; cols = m.cols; row = new Array1D<T> [rows];//分配指向一维数组的数组 for (int i = 0; i < rows; i++) // 复制每一行 row[i] = m.row[i]; //ARRAY1D的行赋值函数 }

23 index operator‘[]’ template<class T>
Array1D<T>& Array2D<T>::operator[](int i) const { //二维数组的第一个索引i if (i < 0 || i >= rows) throw OutOfBounds(); return row[i]; //the ith row of X } X[i][j], x[i] 调用 Array2D<T>::operator[], 对应于X.row[i], 因为X.row[i][j]是对应Array1D<T>::operator[],即在i行上找出第j个元素。 在使用形式上和C++的二维数组是一样的，但在解析上不同。

24 操作符 ‘-’ template<class T>
Array2D<T> Array2D<T>:: operator-(const Array2D<T>& m) const {//返回w = (*this) - m. if (rows != m.rows || cols != m.cols) throw SizeMismatch(); Array2D<T> w(rows,cols); //创建存放结果的数组w for (int i = 0; i < rows; i++) w.row[i] = row[i] - m.row[i]; return w; }

25 操作符 ‘*’ template<class T>
Array2D<T> Array2D<T>:: operator*(const Array2D<T>& m) const { // 矩阵乘，返回w = (*this) * m. if (cols != m.rows) throw SizeMismatch(); // 创建存放结果的数组w Array2D<T> w(rows, m.cols); for (int i = 0; i < rows; i++) for (int j = 0; j < m.cols; j++) T sum = (*this)[i][0] * m[0][j]; for (int k = 1; k < cols; k++) sum += (*this)[i][k] * m[k][j]; w[i][j] = sum; } return w;

26 4.2 Matrix Definition and Operations Class Matrix

27 4.2.1 Definition and Operations
mxn 矩阵:a table with m rows and n columns. M(i,j):the element of M at i row and jth column, 1≤i≤m，1≤j≤n . Operations 转置Transpose 矩阵加 sum 矩阵乘 product

28 矩阵操作 转置 Transpose MT(i,j)=M(j,i), 1≤i≤n, 1≤j≤m 矩阵加 sum 矩阵乘 product
A , B : m x n matrice C=A+B C(i,j) = A(i,j) + B(i,j), 1≤i≤m, 1≤j≤n 矩阵乘 product A : m x n matrix; B: n x q matrix. C= A*B : m x q matrix

29 4.2.2 The Class Matrix Matrix representation. T M[m][n]
two dimensional array with type T T M[m][n] M(i,j): M[i-1][j-1] P46 程序2-19 矩阵加法 P49 程序2-22 矩阵转置 P52 程序2-24 两个n*n矩阵相乘 P53 程序2-25 一个m*n矩阵与一个n*p矩阵相乘 使用类 Array2D Array2D<T> M(m,n)

30 4.2.2 Class Matrix 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;} 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); private: int rows, cols; // 矩阵维数 T *element; // 元素数组 };

31 构造函数 template<class T> Matrix<T>::Matrix(int r, int c)
{// Matrix constructor // 合法的r 和c if (r < 0 || c < 0) throw BadInitializers(); if ((!r || !c) && (r || c)) //都大于零 throw BadInitializers(); rows = r; cols = c; element = new T [r*c] //using a one-dimensional array element to store a row*cols matrix

32 Matrix 操作符‘（）’ template<class T>
T& Matrix<T>::operator()(int i, int j) const {// 返回一个指向元素(i,j)的引用 if (i< 1||i>rows||j<1||j>cols) throw OutOfBounds(); return element[(i-1)*cols +j-1]; }

33 操作符 ‘-’ template<class T>
Matrix<T> Matrix<T>:: operator-(const Matrix<T>& m) const {//返回w = (*this) - m. if (size != v.size ) throw SizeMismatch(); Matrix<T> w(rows,cols); //创建存放结果的数组w for (int i = 0; i < rows*clos; i++) w.element[i] = element[i] - m.element[i]; return w; }

34 Matrix 操作符‘*’ template<class T>
Matrix<T> Matrix<T>:: operator*(const Matrix<T>& m) const {// 矩阵乘法，返回w =(*this)*m. if (cols!=m.rows) throw SizeMismatch(); Matrix<T> w(rows, m.cols); // 结果矩阵 // 为*this, m和w定义游标 // 并设定初始位置为(1,1) int ct=0, cm=0, cw=0;//对三个数组的下标指针

35 Matrix 操作符 ‘*’ ct element m
for (int i=1; i<=rows; i++) { // 对所有的i和j计算w(i,j) for (int j=1; j<=m.cols; j++) { // 计算出结果的第i行 T sum=element[ct]*m.element[cm]; //计算w(i,j)的第一项 for (int k=2; k<=cols; k++) { //累加其余项 ct++; // 指向* this第i行的下一个元素 cm+=m.cols; //指向m 的第j 列的下一个项 sum+=element[ct]*m.element[cm } //reset to start of row and next column w.element[cw++]=sum; //保存w(i,j) ct-=cols-1; //返回到第i行行首地址 cm=j; //定位在第j+1列起始地址 }// reset to start of next row and first column ct+=cols; // 向前跨步cols位置，进入下一行的行首 cm=0; // 重新回归至第一列起始 } return w; ct element cm m

36 4.3 Special Matriice特殊矩阵 Definitions and Applications
4.3.2 对角矩阵 (diagonal) 4.3.3 三对角矩阵 (Tridiagonal) 4.3.4 三角矩阵 (upper and lower triangular) 4.3.5 对称矩阵 Symmetric

37 4.3.1 定义和应用 方阵(square matrix)是指具有相同行数和列数的矩阵. 常用方阵： 对角矩阵（diagonal）:
当且仅当 i≠j时，有M(i,j) = 0 三对角矩阵(tridiagonal): 当且仅当|i-j|>1时，有M(i,j) = 0 下三角矩阵(lower triangular): 当且仅当i<j时，有M(i,j) = 0 上三角矩阵(upper triangular): 当且仅当i>j时，有M(i,j) = 0 对称矩阵(symmetric): 当且仅当对于所有的i和j，有M(i,j) = M(j,i)

38 特殊矩阵 对角矩阵 三对角矩阵 下三角矩阵 上三角矩阵 对称矩阵

39 特殊矩阵 nxn 特殊矩阵描述 使用二维数组 使用矩阵 需要 n2 x sizeof(T) 字节空间

40 4.3.2 对角矩阵 矩阵描述 D(i,j) — d[i-1] i =j D(i,j) — 0 i≠j T d[n]
对角矩阵 矩阵描述 T d[n] D(i,j) — d[i-1] i =j D(i,j) — i≠j 可以用一维数组表示，故需要 n x sizeof(T)字节空间，因为存储是一维，故必须定义store, retrieve函数获取相应的数值，而不是定义运算符()。

41 类DiagonalMatrix template<class T> class DiagonalMatrix { public:
DiagonalMatrix(int size = 10) // 构造函数 {n = size; d = new T [n];} ~DiagonalMatrix() {delete [] d;} // 析构函数 DiagonalMatrix<T>& Store(const T& x, int i, int j); T Retrieve(int i, int j) const; private: int n; //矩阵维数 T *d; // 存储对角元素的一维数组 } ;

42 类DiagonalMatrix 中的操作 template<class T>
DiagonalMatrix<T>& DiagonalMatrix<T>:: Store(const T& x, int i, int j) {// 把x存为D(i,j) . if (i<1 ||j<1||i>n||j>n) throw OutOfBounds(); if (i!=j &&x!=0) throw MustBeZero(); if (i==j) d[i-1]=x; return *this; } template <class T> T DiagonalMatrix<T>::Retrieve(int i, int j) const {//返回D(i,j) . if (i<1||j<1||i>n||j>n) throw OutOfBounds(); if (i==j) return d[i-1]; else return 0;

43 4.3.3 三对角矩阵 非三条0元素对角线 : 三条对角线上的3n-2个元素: T t[3n-2], 我们可以用一维数组t表示
三对角矩阵 非三条0元素对角线 : 主对角线 : i = j 主对角线之下的对角线（称低对角线） : i = j+1 主对角线之上的对角线（称高对角线） : i = j-1 三条对角线上的3n-2个元素: T t[3n-2], 我们可以用一维数组t表示 映射 //寻找对应关系 按行映射 [2,1,3,1,3,5,2,7,9,0] 按列映射 [2,3,1,1,5,3,2,9,7,0] 按对角线的次序映射： [3,5,9,2,1,2,0,1,3,7] 从下向上按对角线存储到t

44 矩阵坐标和存储位置的映射 [3,5,9,2,1,2,0,1,3,7] i-j=1 i-j=0 i-j=-1
i = 2,3,…,n; 1, 2, n; , 2, n-1 A=0,1,…,n-2；n-1,n-2,…,2n-2；2n-1,2n,…,2n+n-3 下对角线 主对角线 i-j = -1 ( 上对角线） = 0 （主对角线 = 1 （下对角线） [3,5,9,2,1,2,0,1,3,7]

45 三对角矩阵 … t[i-2] i-j=1 D(i,j) t[n+i-2] i=j t[2*n+i-2] i-j=-1
读程序4-18

46 TridiagonalMatrix类 程序4-18 template<class T>
class TridiagonalMatrix { public : TridiagonalMatrix(int size = 10) {n = size; t = new T [3*n-2];} //构造函数 ~TridiagonalMatrix() {delete [] t;} //析构函数 TridiagonalMatrix<T>& Store (const T& x, int i, int j); T Retrieve(int i, int j) const; private : int n; // 矩阵维数 T *t; // 存储三对角矩阵的一维数组 } ;

47 template<class T>
TridiagonalMatrix<T>& TridiagonalMatrix<T>:: Store(const T& x, int i, int j) {// 把x存为D(i , j) if (i<1||j<1||i>n||j>n) throw OutOfBounds(); switch (i-j) { case 1: // 低对角线 t[i-2] = x; break; case 0: // 主对角线 t[n+i-2] = x; break; case -1: // 高对角线 t[2*n+i-2] = x; break; default: if(x!=0) throw MustBeZero(); } return *this; template <class T> T TridiagonalMatrix<T>:: Retrieve(int i, int j) const {// 返回D (i, j) if (i<1||j<1||i>n||j>n) throw OutOfBounds(); switch (i-j) { case 1: //低对角线 return t[i-2]; case 0: // 主对角线 return t[n+i-2]; case -1: // 高对角线 return t[2*n+i-2]; default: return 0; }

48 三角矩阵 下三角矩阵 上三角矩阵 非0区域的元素总数： 1+2+…+n = = n(n+1)/2

49 4.3.4 三角矩阵 矩阵描述 映射 使用1维数组  T t[n(n+1)/2] 按行映射 ?
三角矩阵 矩阵描述 使用1维数组  T t[n(n+1)/2] 映射 按行映射 ?  [2,5,1,0,3,1,4,2,7,0] 按列映射 ?  [2,5,0,4,1,3,2,1,7,0]

50 下三角矩阵 Mapping based on row based index 读程序4-19 L(i,j) = 0 i < j
L(i,j) = t[i(i-1)/2 + j-1] i ≥ j 等比级数之和1-(i-1) 层之和，再加上i层的j-1 读程序4-19

51 LowerMatrix类 程序4-19 LowerMatrix类 template<class T>
class LowerMatrix { public : LowerMatrix(int size = 10) {n = size; t = new T [n*(n+1)/2];} ~LowerMatrix() {delete [] t;} LowerMatrix<T>& Store(const T& x, int i, int j); T Retrieve(int i, int j) const; private : int n; // 矩阵维数 T *t; // 存储下三角矩阵的一维数组 } ;

52 template<class T>
LowerMatrix<T>& LowerMatrix<T>:: Store(const T& x, int i, int j) { // 把x 存为L ( i , j ) . if (i<1||j<1||i>n||j>n) throw OutOfBounds(); // 当且仅当i ≥ j 时(i,j) 位于下三角 if (i >= j) t[i*(i-1)/2+j-1] = x; else if (x != 0) throw MustBeZero(); return *this; } template <class T> T LowerMatrix<T>::Retrieve(int i, int j) const //返回L ( i , j ) . if ( i<1||j<1||i>n||j>n) throw OutOfBounds(); if (i >= j) return t[i*(i-1)/2+j-1]; else return 0;

53 上三角矩阵 按列映射 L(i,j) = ? i > j L(i,j) = ? i ≤ j

54 对称矩阵 矩阵描述 : 存储矩阵的上三角或下三角指只存一半的元素

55 4.4 稀疏矩阵 如果一个m×n矩阵中有“许多”元素为0，则称该矩阵为稀疏矩阵（sparse）。
4.4 稀疏矩阵 如果一个m×n矩阵中有“许多”元素为0，则称该矩阵为稀疏矩阵（sparse）。 不是稀疏的矩阵被称为稠密矩阵（dense）。 在稀疏矩阵和稠密矩阵之间并没有一个精确的界限。 我们规定若一个矩阵是稀疏矩阵，则其非0元素的数目应小于n2/3，在有些情况下应小于n2/5， 对角矩阵,三对角矩阵（n×n）：稀疏矩阵 三角矩阵：稠密矩阵 描述： 数组描述 链表描述

56 数组描述 可以按行主次序把稀疏矩阵中非零元素映射到一维数组a[]中,但显然不能仅存其值，要row,col,value都记，故定义数组元素为三元组，命名为term Row=4, col = 8, term =9

57 terms template<class T> class Term { private: int row, col;
T value; };

58 template<class T>
class SparseMatrix { friend ostream& operator<< {ostream&, const SparseMatrix<T>&); friend ostream& operator>> Public: SparseMatrix (int maxTrerms = 10); ~SparseMatrix() {delete [] a;} 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 };

59 Template<class T>
SparseMatrix<T>::SparseMatrix (int maxTerms) {//Constructor an empty matrix if (maxTerms < 1) throw BadIntializers(); MaxTerms = maxTerms; a = new Term<T> [MaxTerms]; terms = rows = cols =0; }

60 //overload << (重载<<） 输出 Template<class T>
Ostream& operator << (ostream& out,const SparseMatrix<T>& x) // put *this in output stream //put matrix characteristics 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; } //e.g., a(1,4)=2 60

61 //overload >> Template<class T> istream& operator >> (istream& in,SparseMatrix<T>& x) // input a sparse matrix //input matrix characteristics cout << “Enter number of rows, colums, and terms “ << endl; in >> x.rows >> x.cols >> x.terms; if (x.terms > x.MaxTerms) throw NoMem(); // input terms 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; }

62 类SparseMatrix中的矩阵转置操作
a[] row col value

63 类SparseMatrix中的矩阵转置操作— 1
template<class T> void SparseMatrix<T>::Transpose(SparseMatrix<T> &b) const {// 把*this的转置结果送入b // 确信b有足够的空间 if (terms>b.MaxTerms) throw NoMem(); // 设置转置特征转换，行数与列数互换 b.cols=rows; b.rows=cols; b.terms=terms;

64 类SparseMatrix中的矩阵转置操作— 2
// 初始化， 注意，rows,cols为原矩阵的行与列数 int *ColSize, *RowNext; ColSize=new int[cols+1]; RowNext=new int[cols+1]; // 计算*this每一列的非0元素数 for (int i=1; i<=cols; i++) //初始化 ColSize[i]=0; for (int=0; i<terms; i++) //计算每列非0元素个数 ColSize[a[i].col]++; // RowNext[i] denotes the position in b for next nonzero term that is in row i, // 给出b中每一行的起始点 RowNext[1]=0 for (int i=2; i<=cols; i++) RowNext[i]= RowNext[i-1]+ColSize[i-1];

65 类SparseMatrix中的矩阵转置操作— 3
// 执行转置操作 for (int i=0; i<terms; i++) { int j=RowNext[a[i].col]++; // 在b中的位置 b.a[j].row=a[i].col; b.a[j].col=a[i].row; b.a[j].value=a[i].value; }

66 两个稀疏矩阵相加 两个矩阵*this和b相加，所得到的结果放入c中。 实现思想：
从左至右依次扫描两个矩阵中的元素。在扫描过程中使用了两个游标：ct（矩阵*this的游标）和cb（矩阵b的游标），若同时（i，j有值，并且其和数不为零，修改，加入c；否则，只有a,b中某个矩阵有值，简单append 到c;

67 append template<class T>
void SparseMatrix<T>::Append(const Term<T>& t) {//把一个非0元素t添加到*this之中 if (terms >= MaxTerms) throw NoMem(); a[terms] = t; terms++ ; }

68 两个稀疏矩阵相加—“Add” template<class T>
void SparseMatrix<T>::Add(const SparseMatrix<T> &b, SparseMatrix<T> &c) const {//计算c = (*this)+b. //验证可行性 if (rows != b.rows || cols != b.cols) throw SizeMismatch(); //不能相加 //设置结果矩阵c的特征 c.rows = rows; c.cols = cols; c.terms = 0; //初值 //定义*this 和b的游标 int ct = 0, cb = 0;

69 //在*this 和b 中遍历 while (ct < terms && cb < b.terms) { //每一个元素的行主索引 int indt = a[ct].row*cols+a[ct].col;// i*n+j// 计算下标的整数值 int indb = b.a[cb].row*cols+b.a[cb].col; if (indt < indb) {//b 的元素在后 c.Append(a[ct]) ; ct++;} //*this的下一个元素 else {if (indt == indb) {//位置相同 //仅当和不为0时才添加到c中 if (a[ct].value+b.a[cb].value) { Term<T> t; //工作变量 t.row = a[ct].row; t.col = a[ct].col; t.value = a[ct].value+b.a[cb].value; c.Append(t) ; } ct++; cb++;} //*this 和b的下一个元素 else {c.Append(b.a[cb]); cb++;} //b的下一个元素 }

70 //复制剩余元素 for (; ct < terms; ct++) c.Append(a[ct]) ; for (; cb < b.terms; cb++) c Append(b.a[cb]) ; }

71 Linked Representation
A shortcoming of one-dimensional array representation of a sparse matrix is that we need to know the number of terms, which may be changed after the operation +,-,* and so on. We can use linked representation to overcome this problem

72 链表描述

73 The presentation The there are two kinds of chains
1) headchain: each node in headchain has three fields-row (corresponding to the unempty row in matrix), link (pointer to next head node) and a chain corresponding to the nonzero elements in the row, a.first pointers the first element in the chain). The definitions of Cnode, and HeadNode use the extensional Chain (include append, erase, zero, et al)

74 Chain node type template<class T> class CNode { public:=
int operator != (const CNode<T>& y) {return (value != y.value);} //值不相等 void Output (ostream& out) cound {out << “colum “ << col << “value “ << value;} private: int col; T value; } ;

75 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;} //输出行数 private: int row; Chain <CNode <T> > a;//row chain, Cnode<T> as a type };

76 template<class T>
class LinkedMatrix { Public: linkedMatrix(){} ~LinkedMatrix(){} void Transpose (LinkedMatrix<T> &b) const; void Add (const LinkedMatrix<T> &b, LinkedMatrix<T> &c) const; private: int rows, cols; // matrix dimensions Chain <HeadNode <T> > a; //head node chain //where HeadNode<T> as a type of Chain. } ;

77 Template<class T>
istream& operator >> (istream& in, LinkedMatrix<T>& x) // input matrix x from the stream in x.a.Erase() ; //delete all nodes from x // get matrix characteristics int terms ; // number of terms to be input cout << “Enter number of rows, columns, and terms “ << endl; in >> x.rows >> x.cols >> x.terms; // create fictional row zero HeadNode<T> H; //head nodes for current row H.row = 0;

78 // get terms of matrix x for (int i = 0; i <x.terms; i++) cout << “Enter row, column, and value of term “ << i <<endl; int row, col T value; in >> row >> col >> value; //check if new term is part of current row if (row > H.row ) {// start a new row // append head node H of current row to head node // chain x.a only if row not zero if (H.row) x.a.Append(H); H.row =row; H.a.Zero();}// set CNode chain be empty

79 //add new term to row chain
CNode<T> *c= new CNode<T>; c->col = col; c->value = value; H.a.Append(*c); } //take care of last row of matrix if (H.row) x.a.Append(H); H.a.Zero();// 最后一行的头结点的指针为0 return in;

80 Overload << To output a linked matrix, we use a chain iterator to move down the head node chain one node at a time. At each node of this head node chain, the row chuan is output.

81 Template<class T>
ostream& operator << (ostream& out, const LinkedMatrix<T>& x) // put matrix x into the output stream out. ChainInterator<Headnode<T>>p; //headnode iterator //output matrix demisions out << “rows =“ << x.rows << columns = “ << x.cols << endl; // set h to point to first head node HeadNode<T> *h = p.initialize(x.a); if (!h) (out << “No nonzero terms” << endl; return out;} //output one row at a time while (h) { out << “row “ << h_>row << endl; out << h->a << endl ; // h-> a is a linked chain, << is defined //in program 3.13, so output row chain denoted by h->a h=p.next(); }// next head node return out; }

82 The Function Transpose
We use bins to collect the terms if the input matrix *this that belong in the same row of the result. Bin[i] is the chain for the terms in all rows such that the column value of the nodes is i, which will be the elements of the ith row of the result matrix b. The detail references to Program 4.30.

83 作业 P219: 29,30 P237:36,43