数组和矩阵-1

1、2/25/20221数组和矩阵第四章2/25/20222数组矩阵特殊矩阵稀疏矩阵本章内容2/25/20223矩阵ADT特殊矩阵稀疏矩阵本章重点44.1 数组4.1.1 抽象数据类型4.1.2 C+数组4.1.3 行主映射和列主映射4.1.4 类Array1D4.1.5 类 Array2D2/25/20225数组的抽象数据类型描述抽象数据类型Array实例形如(index,value)的数据对集合，其中任意两对数据的index值都各不相同操作Create()：创建一个空的数组Store(index,value)：添加数据(index,value)，同时删除具有相同index值的数据对（如果存在）

2、Retrieve(index)：返回索引值为index的数据对4.1.1 Arrays2/25/20226n数组的索引: ni1i2i3ikn k维数组：nint scoreu1u2u3uk. (ui-正的常量或有常量表示的表达式）n0ijuj 0 j k n数组元素的个数: nn=u1u2u3uk n内存空间: nn x sizeof(int) 字节.nc+ 编译器为数组预留空间: nstart -start + sizeof(score) -14.1.2 C+数组74.1.3 行主映射和列主映射l为了实现与数组相关的函数Store和Retrieve，必须确定索引值在start, start

3、+n*sizeof(score)-1中的相应位置 :li1i2ik start + map(i1,i2,ik) * sizeof(int)lmap(i1,i2,ik): 0-n-1l对一维数组： lmap(i1) = i1l对二维数组2/25/20228行主映射和列主映射Row- and Column-Major Mappings9行主映射和列主映射行主映射Int su1u2映射函数: map(i1,i2)= u2 * i1 + i2在行主映射模式中，在对索引i1i2进行编号时,第0，.i1-1行中的i1u2个元素以及第i1行中的前i2个元素都已经被编号。0 s001s01. .U2-1s0u

4、2-1U2s10U2+1s11 .s1u2-1.map(i1,i2) si1i2.su1-10su1-11 .U2*(u1-1)+u2-1su1-1u2-110行主映射和列主映射列主映射映射函数: map(i1,i2)= u1 * i2 + i1在列主映射模式中，在对索引i1i2进行编号时,第0，.i2-1列中的i2u1个元素以及第i2列中的前i1个元素都已经被编号。在 C+ 使用的是哪一种?行主映射!0 s001s10 .u1-1su1-10s01s11 .su1-11.map(i1,i2) si1i2.s0u2-1s1u2-1 .u1 * (u2-1) + (u1-1)su1-1u2-1行

5、主映射与列主映射2/25/202211u1*u2u2u2*u1u12/25/202212n三维数组的行主映射函数为：map(i1,i2,i3)=i1u2u3+i2u3+i3三维数组行主映射u1*u2*u3u2*u3u313行主映射和列主映射对三维数组 (int scoreu1u2u3) 索引按行主次序排列 int score324：000,001,002,003,0l0,0ll,012,013,100,l0l,102,103,110,111,112,113,200,201,202,203,210,211,2l2,213首先列出所有第一个坐标为0的索引，然后是第一个坐标为1的索引， 。第一个坐标

6、相同的所有索引按其第二个坐标的递增次序排列，前两个坐标相同的所有索引按其第三个坐标的递增次序排列。映射函数:map(i1,i2,i3) = i1u2u3+i2u3+i3列主映射，映射函数 ？14u尽管C+支持一维数组，但这种支持很不够。u可以使用超出正常范围之外的索引值来访问数组。u例如对int a9，C+可以访问数组元素a-3，a9和a90，尽管-3，9和90是非法的索引u也不能对一维数组进行诸如加法和减法等操作。u为了克服这些不足，定义了类Array1D。u该类的每个实例X都是一个一维数组。uX的元素存储在数组X.element之中，u第i个元素位于X.element i，0isize。2

7、/25/202215templateclass Array1D public:Array1D(int size = 0);Array1D(const Array1D& v); / 复制构造函数Array1D() delete element;T& operator(int i) const;int Size() return size;Array1D& operator=(const Array1D& v);Array1D operator+() const; / 一元加法操作符Array1D operator+(const Array1D& v) co

8、nst;Array1D operator-() const; / 一元减法操作符Array1D operator-(const Array1D& v) const;Array1D operator*(const Array1D& v) const;Array1D& operator+=(const T& x);private:int size;T *element; /一维数组;4.1.4 一维数组的类定义16构造函数和复制构造函数 templateArray1D:Array1D(int sz)/ 一维数组的构造函数 if (sz0) throw BadInit

9、ializers(); size=sz; element=new Tsz; templateArray1D:Array1D(const Array1D& v)/ 一维数组的复制构造函数 size=v.size; element=new Tsize; / 申请空间 for (int i=0; isize; i+) / 复制元素 elementi=v.elementi;17操作符 = templateT& Array1D:operator(int i) const/ 返回指向第i个元素的引用if (i = size) throw OutOfBounds();return eleme

10、nti; templateArray1D& Array1D:operator=(const Array1D& v)/ 重载赋值操作符= if (this != &v) / 不是自我赋值 size=v.size; delete element; / 释放原空间 element = new Tsize; / 申请空间 for (int i = 0; i size; i+) /复制元素 elementi=v.elementi; return *this;18操作符 templateArray1D Array1D: operator-(const Array1D& v)

11、 const/ 返回w = (*this) - v if (size != v.size) throw SizeMismatch(); Array1D w(size); / 创建结果数组w for (int i = 0; i size; i+) w.elementi=elementi-v.elementi; return w; templateArray1D Array1D:operator-() const/ 返回w = -(*this)Array1D w(size); / 创建结果数组wfor (int i = 0; i size; i+) w.elementi = -elementi;r

12、eturn w;19操作符 += templateArray1D& Array1D:operator+=(const T& x) /把x 加到( * this )的每个元素上 for (int i = 0; i size; i+) elementi += x; return *this; 204.1.5 类 Array2Dtemplateclass Array2D public:Array2D(int r = 0, int c = 0);Array2D(const Array2D& m); / 复制构造函数Array2D() delete row;int Rows()

13、const return rows;int Columns() const return cols;Array1D& operator(int i) const;Array2D& operator=(const Array2D& m);Array2D operator+() const; / 一元加法操作符Array2D operator+(const Array2D& m) const;Array2D operator-() const; / 一元减法操作符Array2D operator-(const Array2D& m) const;Array2

14、D operator*(const Array2D& m) const;Array2D& operator+=(const T& x);private:int rows, cols; / 数组维数Array1D *row; / rowi是类型为Array1D的一维数组，它代表二维数组的第i行。;21构造函数templateArray2D:Array2DArray2D(int r, int c)/ 二维数组的构造函数/ 合法的r 和c if (r 0 | c 0) throw BadInitializers(); if (!r | !c) & (r | c) th

15、row BadInitializers(); rows = r; cols = c; row = new Array1D r; / 分配r个具有缺省大小的一维数组 for (int i = 0; i r; i+) / 调整每个元素的大小 rowi.ReSize(c);Array1D Array1D : ReSizeReSize(int sz) delete element; size = sz; element = new T size; return *this;22复制构造函数templateArray2D:Array2DArray2D(const Array2D& m)/ 二维数

16、组的复制构造函数 rows = m.rows; cols = m.cols; row = new Array1D rows;/分配指向一维数组的数组 for (int i = 0; i rows; i+) / 复制每一行 rowi = m.rowi; /ARRAY1D的 = 23 操作符 templateArray1D& Array2D:operator(int i) const /二维数组的第一个索引if (i = rows) throw OutOfBounds(); return rowi; Array2D x;Xij24操作符 -templateArray2D Array2D:

17、operator-operator-(const Array2D& m) const/返回w = (*this) - m. if (rows != m.rows | cols != m.cols) throw SizeMismatch(); Array2D w(rows,cols); /创建存放结果的数组w for (int i = 0; i rows; i+) w.rowi = rowi - m.rowi; return w;25操作符 *templateArray2D Array2D: operator*(const Array2D& m) const/ 矩阵乘，返回w =

18、 (*this) * m.if (cols != m.rows) throw SizeMismatch();/ 创建存放结果的数组wArray2D w(rows, m.cols);for (int i = 0; i rows; i+) for (int j = 0; j m.cols; j+) T sum = (*this)i0 * m0j; for (int k = 1; k cols; k+) sum += (*this)ik * mkj; wij = sum; return w;264.2 矩阵4.2.1 定义和操作4.2.2 类 Matrix274.2.1 定义和操作mxn 矩阵:m行

19、和n列的表.M(i,j):矩阵M 中第i 行、第j 列1im，1jn 的元素 .常用矩阵操作转置矩阵加矩阵乘 28矩阵操作转置：一个mn 矩阵的转置矩阵是一个nm的矩阵MTMT(i,j)=M(j,i), 1in, 1jm矩阵加：仅当两个矩阵的维数相同时，才可对矩阵求和A , B : m x n 矩阵C=A+BC(i,j) = A(i,j) + B(i,j), 1im, 1jnn1kqj1 m,i1 j)B(k, * k)A(i, j)C(i,矩阵乘：仅当一个矩阵A 列数与另一个矩阵B 的行数相同，才可执行A*BnA : m x n 矩阵; B: n x q 矩阵. nC= A*B : m x

20、q 矩阵 294.2.2 类Matrixn矩阵描述.n 使用二维数组nT Mmnn M(i,j): Mi-1j-1nP46 程序2-19 矩阵加法nP49 程序2-22 矩阵转置nP52 程序2-24 两个n*n矩阵相乘nP53 程序2-25 一个m*n矩阵与一个n*p矩阵相乘n 使用类 Array2D nArray2D M(m,n)nM(i,j): Mi-1j-1 2/25/202230templateclass Matrix public:Matrix(int r = 0, int c = 0);Matrix(const Matrix& m); /复制构造函数Matrix() de

21、lete element;int Rows() const return rows;int Columns() const return cols;T& operator()(int i, int j) const;Matrix& operator=(const Matrix& m);Matrix operator+() const; / 一元加法Matrix operator+(const Matrix& m) const;Matrix operator-() const; / 一元减法Matrix operator-(const Matrix& m)

22、 const;Matrix operator*(const Matrix& m) const;Matrix& operator+=(const T& x);private:int rows, cols; / 矩阵维数T *element; / 元素数组;4.2.2 类matrix31Matrix 操作符（） templateT& Matrix:operator()(int i, int j) const/ 返回一个指向元素(i,j)的引用if (irows|jcols) throw OutOfBounds();return element(i-1)*cols +

23、j-1; 读 P139 程序4-13 Matrix 构造函数读 P140 程序4-15 Matrix 减法操作符32Matrix 操作符*templateMatrix Matrix: operator*(const Matrix& m) const/ 矩阵乘法，返回w =(*this)*m. if (cols!=m.rows) throw SizeMismatch(); Matrix w(rows, m.cols); / 结果矩阵 / 为*this, m和w定义游标 / 并设定初始位置为(1,1) int ct=0, cm=0, cw=0;33Matrix 操作符 *for (int

24、i=1; i=rows; i+) / 对所有的i和j计算w(i,j)for (int j=1; j=m.cols; j+) / 计算出结果的第i行 T sum=elementct*m.elementcm; /计算w(i,j)的第一项 for (int k=2; k1时，有M(i,j) = 0下三角矩阵下三角矩阵(lower triangular): 当且仅当ij时，有M(i,j) = 0对称矩阵对称矩阵(symmetric):当且仅当对于所有的i和j，有M(i,j) = M(j,i)2/25/2022372/25/202238n可以采用二维数组来描述一个元素类型为T的nn对角矩阵D：T dnn

25、n使用数组元素di-1j-1来表示矩阵元素D(i,j)，这种描述形式所需要的存储空间n2*sizeof(T)。n思考：节省空间的存贮方式？4.3.2对角矩阵(diagonal)描述394.3.2 对角矩阵u 矩阵描述uT dnuD(i,j) di-1 i =juD(i,j) 0 iju需要 n x sizeof(T)字节空间2/25/202240templateclass DiagonalMatrixpublic:DiagonalMatrix(int size=10) n = size;d = new Tn;DiagonalMatrix()delete d;/析构函数DiagonalMatri

26、x& Store(const T&x,int i,int j);T Retrieve(int i,int j) const;private:int n;/矩阵维数T *d;/存储对角元素的一维数组;DiagonalMatrix类2/25/202241templateDiagonalMatrix &DiagonalMatrix:Store(const T&x,int i,int j)/把x存为D(i,j).if(i1|jn|jn)throw OutOfBounds();if(i!=j & x!=0) throw MustBeZero();if(i=j) d

27、i-1=x;return *this; 复杂性？DiagonalMatrix类-Store2/25/202242templateT DiagonalMatrix:Retrieve(inti,intj) const/返回D(i,j).if(i1|jn|jn)throw OutOfBounds();if(i=j) return di-1;else return 0; 复杂性？DiagonalMatrix类-Retrieve434.3.3 三对角矩阵三条非0元素对角线 :主对角线 : i = j主对角线之下的对角线（称低对角线） : i = j+1主对角线之上的对角线（称高对角线） : i = j-

28、1三条对角线上的3n-2个元素: T t3n-2映射 按行映射 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,744三对角矩阵按照对角线的次序（从最下面的对角线开始）进行映射D(2,1)- t0D(3,2)- t1D(n,n-1) - tn-2D(1,1)- tn-1D(2,2)- tn.D(n, n)- t(n-2)+n = t2n-2D(1,2)- t2n-1D(2,3)- t2nD(n-1,n) - t(2n-2)+(n-1) = t3n-3 ti-2 i=j+1D(i,j) tn+i-2 i

29、=j t2*n+i-2 i=j-1 0 |i-j|1读程序4-182/25/202245templateclass TridiagonalMatrixpublic:TridiagonalMatrix(int size=10)n=size;t=new T3*n-2;TridiagonalMatrix()delete t;TridiagonalMatrix& Store(const T&x,int i,int j);T Retrieve(int i,int j) const;private:int n;/矩阵维数T *t;/存储三对角矩阵的一维数组;TridiagonalMatri

30、x类46templateTridiagonalMatrix& TridiagonalMatrix: Store(const T& x, int i, int j)/ 把x存为D(i , j)if (i1|jn|jn) throw OutOfBounds();switch (i-j) case 1: / 低对角线 ti-2 = x; break; case 0: / 主对角线 tn+i-2 = x; break; case -1: / 高对角线 t2*n+i-2 = x; break; default: if(x!=0) throw MustBeZero(); return *t

31、his;template T TridiagonalMatrix: Retrieve(int i, int j) const/ 返回D (i, j)if (i1|jn|jn) throw OutOfBounds();switch (i-j) case 1: /低对角线 return ti-2; case 0: / 主对角线 return tn+i-2; case -1: / 高对角线 return t2*n+i-2; default: return 0; 2/25/202247n行映射描述map(i,j)=(i-1)*3-1+(j-i+1)=2i+j-34.3.2 三对角矩阵描述2/25/202248n在一个三角矩阵中，非0元素都位于所示的“非0”区域。对于这两种情况，非0区域的元素总数均为：4.3.3 三角矩阵494.3.4 三角矩阵矩阵描述使