Chapter4 Arrays and Matrices

Presentation on theme: "Chapter4 Arrays and Matrices"— Presentation transcript:

1 Chapter4 Arrays and Matrices
Special Matrices Sparse Matrices 2/24/2019

2 本章重点 矩阵ADT 特殊矩阵 稀疏矩阵 2/24/2019

3 4.1 Arrays 数组的抽象数据类型描述 抽象数据类型Array{ 实例
形如(index,value)的数据对集合，其中任意两对数据的index值都各不相同 操作 Create()：创建一个空的数组 Store(index,value)：添加数据(index,value)，同时删除具有相同index值的数据对（如果存在） Retrieve(index)：返回索引值为index的数据对 2/24/2019

4 C++数组 在C++中，值为整数类型的k维数组score可用如下语句来创建： int score[u1][u2][u3]...[uk]
为实现与数组相关的函数Store和Retrieve，必须把数组索引[i1][i2][i3]...[ik]映射到[0,n-1]中的某个数map(i1,i2,i3,...,ik)，使得该索引所对应的元素值存储在以下位置：start+map(i1,i2,i3,...,ik)*sizeof(int) 2/24/2019

5 一维数组 当数组维数为1时（即k=1），使用以下函数：map(i1)=i1 2/24/2019

6 行主映射和列主映射 Row- and Column-Major Mappings
2/24/2019

7 二维数组行主映射 行主次序所对应的映射函数为：map(i1,i2)=i1u2+i2 其中u2是数组的列数。
在行主映射模式中，在对索引[i1][i2]进行编号时,第0，...i1-1行中的i1u2个元素以及第i1行中的前i2个元素都已经被编号。 2/24/2019

8 行主映射 u1*u2 u2 2/24/2019

9 三维数组行主映射 三维数组的行主映射函数为：map(i1,i2,i3)=i1u2u3+i2u3+i3 u3 u1*u2*u3 u2*u3
2/24/2019

10 一维数组的类定义 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;} Array1D<T>& operator=(const Array1D<T>& v); Array1D<T> operator+() const; // 一元加法操作符 Array1D<T> operator+(const Array1D<T>& v) const; Array1D<T> operator-() const; // 一元减法操作符 Array1D<T> operator-(const Array1D<T>& v) const; Array1D<T> operator*(const Array1D<T>& v) const; Array1D<T>& operator+=(const T& x); 2/24/2019

11 一维数组的类定义 private: int size; T *element; //一维数组 }; 2/24/2019

12 2/24/2019

13 二维数组的类定义 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); 2/24/2019

14 二维数组的类定义 private: int rows, cols; // 数组维数
Array1D<T> *row; // 一维数组的数组 }; 2/24/2019

15 2/24/2019

16 2/24/2019

17 4.2 Metrices 一个m×n 的矩阵是一个m行、n 列的表，其中m 和n 是矩阵的维数。 矩阵通常被用来组织数据。
2/24/2019

18 矩阵 2/24/2019

19 矩阵的操作 对于矩阵来说，最常见的操作就是矩阵转置、矩阵加、矩阵乘。
一个m×n 矩阵的转置矩阵是一个n×m的矩阵MT，它与M之间存在以下关系： MT (i,j) = M(j,i ), 1≤i≤n，1≤j≤m 仅当两个矩阵的维数相同时（即具有相同的行数和列数），才可以对两个矩阵求和。两个m×n 矩阵A 和B 相加所得到的m×n 矩阵C 如下： C(i,j ) = A(i,j )+B(i,j)，1≤i≤n，1≤j≤m 2/24/2019

20 矩阵的操作 仅当一个m×n 矩阵A 的列数与另一个q×p 矩阵B 的行数相同时（即n = q），才可以执行矩阵乘法A*B。A*B 所得到的m×p 矩阵C 满足以下关系： 2/24/2019

21 类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); 2/24/2019

22 类matrix private: int rows, cols; // 矩阵维数 T *element; // 元素数组 };
2/24/2019

23 2/24/2019

24 2/24/2019

25 2/24/2019

26 2/24/2019

27 2/24/2019

28 复杂性分析 当T是一个内部数据类型时，矩阵构造函数复杂性为O( 1 )，而当T是一个用户自定义的类时，构造函数的复杂性为O( r o w s * c o l s )。复制构造函数的复杂性为O( r o w s * c o l s )，下标操作符的复杂性为 ( 1 )，乘法操作符的复杂性O( r o w s * c o l s * m . c o l s )。所有其他矩阵操作符的渐进复杂性分别与A r r a y 2 D类中对应操作符的渐进复杂性相同。 2/24/2019

29 4.3 Special Matrices 特殊方阵 对角矩阵(Diagonal Matrices )
三对角矩阵(Tridiagonal Matrix ) 三角矩阵(Triangular Matrices) 对称矩阵(Symmetric Matrices ) 2/24/2019

30 对角矩阵(diagonal) M是一个对角矩阵当且仅当i≠j时有M(i,j)=0。 2/24/2019

31 三对角矩阵(tridiagonal) M是一个三对角矩阵当且仅当|i-j|>1时有M(i,j)=0。 2/24/2019

32 下三角矩阵(lowertriangular)
M是一个下三角矩阵当且仅当i<j时有M(i,j)=0。 2/24/2019

33 上三角矩阵(uppertriangular)
M是一个上三角矩阵当且仅当i>j时有M(i,j)=0。 2/24/2019

34 对称矩阵(symmetric) M是一个对称矩阵当且仅当对于所有的i和j有M(i,j)=M(j,i)。 2/24/2019

35 2/24/2019

36 对角矩阵(diagonal)描述 可以采用二维数组来描述一个元素类型为T的n×n对角矩阵D： T d[n][n]
使用数组元素d[i-1][j-1]来表示矩阵元素D(i,j)，这种描述形式所需要的存储空间n2*sizeof(T)。 思考：节省空间的存贮方式？ 2/24/2019

37 对角矩阵描述方案 一个对角矩阵最多包含n个非0元素，所以可以采用如下所示的一维数组来描述对角矩阵： Td[n]
使用数组元素d[i-1]来表示矩阵元素D[i,i]。根据对角矩阵的定义，所有未在一维数组中出现的矩阵元素均为0。 2/24/2019

38 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;//存储对角元素的一维数组 }; 2/24/2019

39 DiagonalMatrix类 template<classT>
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; } 复杂性？ 2/24/2019

40 DiagonalMatrix类 template<classT> T DiagonalMatrix<T>::
Retrieve(inti,intj) 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; } 复杂性？ 2/24/2019

41 三对角矩阵(tridiagonal) 在一个n×n三对角矩阵T中，非0元素排列在如下的三条对角线上： 1)主对角线——i=j。
2/24/2019

42 三对角矩阵描述 这三条对角线上的元素总数为? 。 行映射？ 列映射？ 对角线映射？ 2/24/2019

43 TridiagonalMatrix类 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;//存储三对角矩阵的一维数组 }; 2/24/2019

44 TridiagonalMatrix类 template<class T>
TridiagonalMatrix<T>& TridiagonalMatrix<T>:: Store(const T& x,int i,int j) {//把x存为T(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;} 复杂性？ 2/24/2019

45 TridiagonalMatrix类 template<class T>
TTridiagonalMatrix<T>::Retrieve(int i,int j)const {//返回T(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; } } 复杂性？ 2/24/2019

46 三对角矩阵描述 行映射描述 map(i,j)=(i-1)*3-1+(j-i+1) =2i+j-3 2/24/2019

47 三角矩阵 在一个三角矩阵中，非0元素都位于所示的“非0”区域。对于这两种情况，非0区域的元素总数均为： 2/24/2019

48 三角矩阵 两种三角矩阵都可以用一个大小为n(n+1)/2的一维数组来进行描述。
按行映射?(在元素L(i, j)之前共有 ? 个元素位于非0区域?) 按列映射? 2/24/2019

49 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;//存储下三角矩阵的一维数组 }; 2/24/2019

50 对称矩阵(symmetric) 一个n×n的对称矩阵可以用一个大小为n(n+1)/2的一维数组来描述，可参考三角矩阵的存储模式来存储矩阵的上三角或下三角。 可以根据已存储的元素来推算出未存储的元素。 2/24/2019

51 4.4 Sparse Matrices 如果一个m×n 矩阵中有“许多”元素为0，则称该矩阵为稀疏矩阵。
不是稀疏的矩阵被称为稠密矩阵(den se)。 在稀疏矩阵和稠密矩阵之间并没有一个精确的界限。 本节中我们规定若一个矩阵是稀疏矩阵,则其非0元素的数目应小于n2/3。 2/24/2019

52 稀疏矩阵例子 某超级市场正在开展一项关于顾客购物品种的研究。为了完成这项研究，收集了10 00个顾客的购物数据，这些数据被组织成一个矩阵purchases，其中purchases (i, j) 表示顾客j 所购买的商品i 的数量。 假定该超级市场有10 000种不同的商品，那么purchases 将是一个10 000× 的矩阵。如果每个顾客平均购买了20种不同商品，那么在 个矩阵元素将大约只有20 000个元素为非0，并且非0元素的分布没有很明确的规律。 2/24/2019

53 类Term template <class T> class Term { private: int row, col;
T value; }； 2/24/2019

54 稀疏矩阵数组描述 2/24/2019

55 存贮空间 存储图4-10a 中的九个非0元素所需要的存储器字节数为21*sizeof(int)+ 9*sizeof(T)。
假定T是int 类型且sizeof(T) = 2，那么图4-10b 中的描述需60个字节，而采用4×8的数组则需要64个字节。 2/24/2019

56 存贮空间 对例4-5中的矩阵purchase，其一维数组描述需60000*sizeof(int)个字节，
如果一个整数占2个字节，则节省的空间为 字节。 2/24/2019

57 类SparseMatrix 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;} void Transpose(SparseMatrix<T> &b) const; void Add(const SparseMatrix<T> &b, SparseMatrix<T> &c) const; 2/24/2019

58 类SparseMatrix private: void Append(const Term<T>& t);
int rows, cols; //矩阵维数 int terms; // 非0元素数目 Term<T> *a; // 存储非0元素的数组 int MaxTerms; // 数组a的大小; } ; 2/24/2019

59 转置的例子 0,   0,   0,   3,   0,   0      4   ,0,   0,   0,   0,   1      0,   3,   0,   0,   0,   0      0,   0,   0,   0,   5,   0      0,   0,   1,   0,   0,   0      1,   0,   0,   2,   0,   0 数组a[]？ 2/24/2019

60 转置后的矩阵 0,   4,   0,   0,   0,   1      0   ,0,   3,   0,   0,   0      0,   0,   0,   0,   1,   0      3,   0,   0,   0,   0,   2      0,   0,   0,   0,   0,   0      0,   1,   0,   0,   0,   0 数组a[]？ 2/24/2019

61 转置一个稀疏矩阵 template<class T>
void SparseMatrix<T>:: Transpose(SparseMatrix<T> &b) const {//把*this 的转置结果送入b if (terms > b.MaxTerms) throw NoMem(); //b有足够空间? //设置转置特征 b.cols = rows; b.rows = cols; b.terms = terms; //初始化 int *ColSize, *RowNext; ColSize = new int[cols+1];//ColSize[i]表示矩阵a第i列中的非0元素数 RowNext = new int[rows+1];//RowNext[i]表示矩阵第i行的下一个非0元素在b中的位置 2/24/2019

62 转置一个稀疏矩阵 //计算*this每一列的非0元素数 for (int i = 1; i <= cols; i++) //初始化
ColSize[i] = 0; for (int = 0; i < terms; i++) ColSize[a[i].col]++; //给出b中每一行的起始点 RowNext[1] = 0; for (int i = 2; i <= cols; i++) RowNext[i] = RowNext[i - 1]+ColSize[i - 1]; 2/24/2019

63 转置一个稀疏矩阵 //执行转置操作 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; } 复杂性？ 2/24/2019

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

65 两个稀疏矩阵相加 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; 2/24/2019

66 两个稀疏矩阵相加 //在*this 和b 中遍历 while (ct < terms && cb < b.terms) {
//每一个元素的行主索引 int indt = a[ct].row*cols+a[ct].col; int indb = b.a[cb].row*cols+b.a[cb].col; if (indt < indb) {//b 的元素在后 c.Append(a[ct]) ; ct++;} //*this的下一个元素 2/24/2019

67 两个稀疏矩阵相加 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的下一个元素 } 2/24/2019

68 两个稀疏矩阵相加 //复制剩余元素 for (; ct < terms; ct++) c.Append(a[ct]) ;
for (; cb < b.terms; cb++) c Append(b.a[cb]) ; } 复杂性？ 2/24/2019

69 稀疏矩阵链接描述 链表描述的一种可行方案是把每行的非0元素串接在一起，构成一个链表。 2/24/2019

70 稀疏矩阵链接描述 2/24/2019

71 链表节点 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;} private: int col; T value; } ; 2/24/2019

72 行链表 template<class T> class HeadNode { public:
int operator !=(const HeadNode<T>& y) {return (row != y. r o w ) ; } void Output(ostream& out) const {out << "row " << row;} private: int row; Chain<CNode<T>> a; //行链表 } ; 2/24/2019

73 用链表描述稀疏矩阵的类定义 template<class T> class LinkedMatrix {
friend ostream& operator<<(ostream&, const LinkedMatrix<T>&); friend istream& operator>>(istream&, LinkedMatrix<T>&); public: LinkedMatrix( ) { } ~ LinkedMatrix( ) { } void Transpose(LinkedMatrix<T> &b) const; void Add(Const LinkedMatrix<T> &b, LinkedMatrix<T> &c) const; private: int rows, cols; //矩阵维数 Chain<HeadNode<T>> a; //头节点链表 } ; 2/24/2019

74 第四章 总结 行主映射，列主映射 矩阵ADT 对角矩阵 三对角矩阵 三角矩阵 对称矩阵 稀疏矩阵 2/24/2019