山大数据结构_4概要课件.ppt
1.Arrays2.Matrices3.Special Matrices4.Sparse MatricesChapter4 Arrays and Matrices6/1/2023 11.矩阵ADT2.特殊矩阵3.稀疏矩阵本章重点6/1/2023 2数组的抽象数据类型描述抽象数据类型Array实例形如(index,value)的数据对集合，其中任意两对数据的index值都各不相同操作Create()：创建一个空的数组Store(index,value)：添加数据(index,value)，同时删除具有相同index值的数据对（如果存在）Retrieve(index)：返回索引值为index的数据对4.1 Arrays6/1/2023 3n 在C+中，值为整数类型的k维数组score可用如下语句来创建：int scoreu1u2u3.ukn 为实现与数组相关的函数Store和Retrieve，必须把数组索引i1i2i3.ik映射到0,n-1中的某个数map(i1,i2,i3,.,ik)，使得该索引所对应的元素值存储在以下位置：start+map(i1,i2,i3,.,ik)*sizeof(int)C+数组6/1/2023 4n 当数组维数为1时（即k=1），使用以下函数：map(i1)=i1一维数组6/1/2023 5行主映射和列主映射Row-and Column-Major Mappings6/1/2023 6n 行主次序所对应的映射函数为：map(i1,i2)=i1u2+i2n 其中u2是数组的列数。n 在行主映射模式中，在对索引i1i2进行编号时,第0，.i1-1行中的i1u2个元素以及第i1行中的前i2个元素都已经被编号。二维数组行主映射6/1/2023 7n 三维数组的行主映射函数为：map(i1,i2,i3)=i1u2u3+i2u3+i3三维数组行主映射6/1/2023 8templateclass 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)const;Array1D operator-()const;/一元减法操作符Array1D operator-(const Array1D&v)const;Array1D operator*(const Array1D&v)const;Array1D&operator+=(const T&x);一维数组的类定义6/1/2023 9private:int size;T*element;/一维数组;一维数组的类定义6/1/2023 10templateclass Array2D public:Array2D(int r=0,int c=0);Array2D(const Array2D&m);/复制构造函数Array2D()delete row;int Rows()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;Array2D operator*(const Array2D&m)const;Array2D&operator+=(const T&x);二维数组的类定义6/1/2023 11private:int rows,cols;/数组维数Array1D*row;/一维数组的数组;二维数组的类定义6/1/2023 12n 一个mn 的矩阵是一个m行、n 列的表，其中m 和n 是矩阵的维数。n 矩阵通常被用来组织数据。4.2 Metrices6/1/2023 13矩阵6/1/2023 14n 对于矩阵来说，最常见的操作就是矩阵转置、矩阵加、矩阵乘。n 一个mn 矩阵的转置矩阵是一个nm的矩阵MT，它与M之间存在以下关系：n MT(i,j)=M(j,i),1in，1jmn 仅当两个矩阵的维数相同时（即具有相同的行数和列数），才可以对两个矩阵求和。两个mn 矩阵A 和B 相加所得到的mn 矩阵C 如下：n C(i,j)=A(i,j)+B(i,j)，1in，1jm矩阵的操作6/1/2023 15矩阵的操作n 仅当一个mn 矩阵A 的列数与另一个qp 矩阵B 的行数相同时（即n=q），才可以执行矩阵乘法A*B。A*B 所得到的mp 矩阵C 满足以下关系：6/1/2023 16templateclass Matrix public:Matrix(int r=0,int c=0);Matrix(const Matrix&m);/复制构造函数Matrix()delete 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)const;Matrix operator*(const Matrix&m)const;Matrix&operator+=(const T&x);类matrix6/1/2023 17private:int rows,cols;/矩阵维数T*element;/元素数组;类matrix6/1/2023 18 特殊方阵n 对角矩阵(Diagonal Matrices)n 三对角矩阵(Tridiagonal Matrix)n 三角矩阵(Triangular Matrices)n 对称矩阵(Symmetric Matrices)4.3 Special Matrices6/1/2023 19n M是一个对角矩阵当且仅当ij时有M(i,j)=0。对角矩阵(diagonal)6/1/2023 20n M是一个三对角矩阵当且仅当|i-j|1时有M(i,j)=0。三对角矩阵(tridiagonal)6/1/2023 21n M是一个下三角矩阵当且仅当ij时有M(i,j)=0。下三角矩阵(lowertriangular)6/1/2023 22n M是一个上三角矩阵当且仅当ij时有M(i,j)=0。上三角矩阵(uppertriangular)6/1/2023 23n M是一个对称矩阵当且仅当对于所有的i和j有M(i,j)=M(j,i)。对称矩阵(symmetric)6/1/2023 246/1/2023 25n 可以采用二维数组来描述一个元素类型为T的nn对角矩阵D：T dnnn 使用数组元素di-1j-1来表示矩阵元素D(i,j)，这种描述形式所需要的存储空间n2*sizeof(T)。n 思考：节省空间的存贮方式？对角矩阵(diagonal)描述6/1/2023 26n 一个对角矩阵最多包含n个非0元素，所以可以采用如下所示的一维数组来描述对角矩阵：Tdnn 使用数组元素di-1来表示矩阵元素Di,i。根据对角矩阵的定义，所有未在一维数组中出现的矩阵元素均为0。对角矩阵描述方案6/1/2023 27templateclass DiagonalMatrixpublic:DiagonalMatrix(int size=10)n=size;d=new Tn;DiagonalMatrix()delete d;/析构函数DiagonalMatrix&Store(const T&x,int i,int j);T Retrieve(int i,int j)const;private:int n;/矩阵维数T*d;/存储对角元素的一维数组;DiagonalMatrix类6/1/2023 28templateDiagonalMatrix&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)di-1=x;return*this;复杂性？DiagonalMatrix类6/1/2023 29templateT DiagonalMatrix:Retrieve(inti,intj)const/返回D(i,j).if(i1|jn|jn)throw OutOfBounds();if(i=j)return di-1;else return 0;复杂性？DiagonalMatrix类6/1/2023 30n 在一个nn三对角矩阵T中，非0元素排列在如下的三条对角线上：n 1)主对角线i=j。n 2)主对角线之下的对角线(称低对角线)i=j+1。n 3)主对角线之上的对角线(称高对角线)i=j-1。三对角矩阵(tridiagonal)6/1/2023 31n 这三条对角线上的元素总数为?。n 行映射？n 列映射？n 对角线映射？三对角矩阵描述6/1/2023 32templateclass 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;/存储三对角矩阵的一维数组;TridiagonalMatrix类6/1/2023 33
