课程名称：数据结构第8周，第8讲次摘 要第四章数组、集合和矩阵授课题目（章、节）第四节矩阵类第五节特殊矩阵第六节稀疏矩阵【目的要求】通过本讲课程的学习，了解矩阵类的设计实现方法，掌握特殊矩阵、稀疏矩阵的压缩存储方法。[重 点】稀疏矩阵的压缩存储方法。【难点】稀疏矩阵的转置算法。内容【本讲课程的引入】矩阵是工程设计中经常要用到的数学工具，这一次课我们就来讨论矩阵类的设计实现方法，以及对于一些特殊的矩阵如何进行压缩存储。【本讲课程的内容】4.4矩阵类矩阵是工程设计中经常使用的数学工具。矩阵用两维数组处理最为方便。我们也可以在向量类MyVector的基础上设计矩阵类。MyVector类创建的二维数组结构如图所示。w列h行这里设计的矩阵类Matrix使用MyVector类来创建上图所示结构的二维数组。public class Matrix(private MyVector values;private int h,w;public Matrix(int h,int w)(if(!(h>0&w>0))throw newArrayIndexOutofBoundsException("h or w<"+1);values=newMyVector(h):for(int i=O;i<h;i++)fMyVectorrow=newMyVector(w);values.add(row);for(int j= O: j<w; j++)(row.add(null) ;71this.h = h;
课程名称：数据结构 第 8 周，第 8 讲次 摘 要 授课题目（章、节） 第四章 数组、集合和矩阵 第四节 矩阵类 第五节 特殊矩阵 第六节 稀疏矩阵 【目的要求】通过本讲课程的学习，了解矩阵类的设计实现方法，掌握特殊矩阵、稀疏矩阵的压缩存储方法。 【重 点】稀疏矩阵的压缩存储方法。 【难 点】稀疏矩阵的转置算法。 内 容 【本讲课程的引入】矩阵是工程设计中经常要用到的数学工具，这一次课我们就来讨论矩 阵类的设计实现方法，以及对于一些特殊的矩阵如何进行压缩存储。 【本讲课程的内容】 4.4 矩阵类 矩阵是工程设计中经常使用的数学工具。 矩阵用两维数组处理最为方便。 我们也可 以在向量类 MyVector 的基础上设计矩阵类。 MyVector 类创建的二维数组结构如图所示。 这里设计的矩阵类 Matrix 使用 MyVector 类来创建上图所示结构的二维数组。 public class Matrix{ private MyVector values; private int h,w; public Matrix(int h,int w){ if(!(h > 0 && w > 0)) throw new ArrayIndexOutOfBoundsException("h or w < " + 1); values = new MyVector(h); for(int i = 0; i < h; i++){ MyVector row = new MyVector(w); values.add(row); for(int j = 0; j < w; j++){ row.add(null); } } this.h = h; . . . . . . w列 h行
this.w=w;public void set(int row,int col,Object value)if(!(row>=0&&col>=0&&row=0 &&col >=0 &&row< h && col<w))throw new ArrayIndexOutofBoundsException("h orw<"+"-1");MyVector selrow=(MyVector)values.get(row)return selrow.get(col):public int widthO(return w;小public int height ((return h;1public Matrix matrixAdd(Matrix anotherMatrix)(II!=widthO!=if(heightOanotherMatrix.heightOanotherMatrix.widthO)(throw new ArrayIndexOutOfBoundsException("Matrix h and w error");Matrix result = new Matrix(height (,widthO);for(int i= O;i< heightO;i++)(for(intj=O;j<widthO;j++)(Integer il = (Integer)get(i,j):Integer i2 = (Integer)(anotherMatrix.get(i,j));result.set(i,j,newInteger(il.intValueO+i2.intValue));1return result;public void printO ffor(int i=o;i<h:i++)for(int j=; j<w; j++){System.out.print(get(i,j)+""):System.out.printlnO:T
this.w = w; } public void set(int row,int col,Object value){ if(!(row >= 0 && col >= 0 && row = 0 && col >= 0 && row < h && col <w)) throw new ArrayIndexOutOfBoundsException("h or w < " + "-1"); MyVector selrow = (MyVector)values.get(row); return selrow.get(col); } public int width(){ return w; } public int height(){ return h; } public Matrix matrixAdd(Matrix anotherMatrix){ if(height() != anotherMatrix.height() || width()!= anotherMatrix.width()){ throw new ArrayIndexOutOfBoundsException("Matrix h and w error"); } Matrix result = new Matrix(height(),width()); for(int i = 0;i < height();i ++){ for(int j = 0;j < width(); j ++){ Integer i1 = (Integer)get(i,j); Integer i2 = (Integer)(anotherMatrix.get(i,j)); result.set(i,j,new Integer(i1.intValue()+i2.intValue())); } } return result; } public void print(){ for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ System.out.print(get(i,j)+" "); } System.out.println(); } }
4.5特殊矩阵特殊矩阵是指这样一类矩阵，其中有许多值相同的元素或有许多零元素，且值相同的元素或零元素的分布有一定规律。一般采用二维数组来存储矩阵元素。但是，对于特殊矩阵，可以通过找出矩阵中所有值相同元素的数学映射公式，只存储相同元素的一个副本，从而达到压缩存储数据量的目的。4.5.1特殊矩阵的压缩存储（1）n阶对称矩阵在一个n阶方阵A中，若元素满足下述性质：(l≤i,j≤n)aij=aji则称A为n阶对称矩阵。下图是一个5阶对称矩阵。71513all50800a21a2218926a31a32a3330251.....:70６13anl an22an3annⅡ阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素。在这个下三角矩阵中，第i行恰有i个元素，元素总数为n(n+1)/2，这样就可将n2个数据元素压缩存储在n(n+1)/2个存储单元中。假设以一维数组va作为n阶对称矩阵A的压缩存储单元，k为一维数组va的下标序号，aij为n阶对称矩阵A中i行j列的数据元素（其中1≤i，j≤n），其数学映射关系为：i(i-1)/2+j-1当i>=jK= -j(j-1)/2+i-1当i=jK= -（n(n+1)/2（或空）当j注：此时一维数组sa的数据元素个数为(n(n+1)/2)+1个，其中数组sa的最后一个位置存储A中数值不为0的那个常数。2采用不等长的二维数组Java语言支持不等长的二维数组，对于n阶对称矩阵，也可以通过只申请存储下三
4.5 特殊矩阵 特殊矩阵是指这样一类矩阵，其中有许多值相同的元素或有许多零元素，且值相同的 元素或零元素的分布有一定规律。 一般采用二维数组来存储矩阵元素。但是，对于特殊矩阵，可以通过找出矩阵中所有 值相同元素的数学映射公式，只存储相同元素的一个副本，从而达到压缩存储数据量的目 的。 4.5.1 特殊矩阵的压缩存储 （1）n 阶对称矩阵 在一个 n 阶方阵 A 中，若元素满足下述性质： aij=aji （1≦i,j≦n） 则称 A 为 n 阶对称矩阵。下图是一个 5 阶对称矩阵。 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 . 7 0 6 1 3 an1 an2 an3 .a nn n 阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元 素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般 性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素。 在这个下三角矩阵中，第 i 行恰有 i 个元素，元素总数为 n(n+1)/2，这样就可将 n2 个数据元素压缩存储在 n(n+1)/2 个存储单元中。 假设以一维数组 va 作为 n 阶对称矩阵 A 的压缩存储单元，k 为一维数组 va 的下标序 号，aij 为 n 阶对称矩阵 A 中 i 行 j 列的数据元素(其中 1≦i,j≦n )，其数学映射关系为： （2）n 阶三角矩阵 以主对角线划分， n 阶三角矩阵有 n 阶上三角矩阵和 n 阶下三角矩阵两种。 n 阶上三角矩阵的下三角（不包括主对角线）中的元素均为 0（或常数）。n 阶下三角 矩阵正好相反，它的主对角线上方均为 0（或常数）。 注：在大多数情况下， n 阶三角矩阵常数为零。 假设以一维数组 sa 作为 n 阶下三角矩阵 A 的压缩存储单元，k 为一维数组 va 的下标 序号，aij 为 n 阶下三角矩阵 A 中 i 行 j 列的数据元素(其中 1≦i,j≦n )，其数学映射关 系为： 注：此时一维数组 sa 的数据元素个数为(n(n+1)/2)+1 个，其中数组 sa 的最后一个位 置存储 A 中数值不为 0 的那个常数。 2 采用不等长的二维数组 Java 语言支持不等长的二维数组，对于 n 阶对称矩阵，也可以通过只申请存储下三 i(i-1)/2+j-1 当 i>=j j(j-1)/2+i-1 当 i=j n(n+1)/2 （或空） 当 i<j K=
角（或上三角）矩阵元素所需的二维数组，来达到压缩存储的目的。4.6稀疏矩阵对一个mXn的矩阵，设s为矩阵元素个数的总和，有s=m*n，设t为矩阵中非零元素个数的总和，满足t<<s的矩阵称作稀疏矩阵。符号“<<”读作小于小于。简单说，稀疏矩阵就是非零元素个数远远小于元素个数的矩阵。相对于稀疏矩阵来说，一个不稀疏的矩阵也称作稠密矩阵。4.6.1稀疏矩阵的压缩存储稀疏矩阵的压缩存储方法，是只存储矩阵中的非零元素。稀疏矩阵中每个非零元素及其对应的行下标和列下标构成一个三元组，稀疏矩阵中所有这样的三元组构成一个以三元组为数据元素的线性表。写出下图所示稀疏矩阵的压缩存储形式123456012290001000000233001400400240005018000061500-700解：用三元组线性表表示：((1,2,12],[1,3,9],(3,1,-3],[3,5,14),4,3,24),[5,2,18),[6,1,15],[6,4,-7]4.6.2数组结构的稀疏矩阵类1三元组类三元组的数组结构存储，就是把所有三元组存储在一个数组中。三元组是稀疏矩阵压缩存储方法的关键。首先设计三元组类：public class Threetpublic int row;public int col;public double value:Three(intr,int c,doublev)frow =r;col = c;value = v;1ThreeO(row=o;col= 0;value = 0.0;12.稀疏矩阵类public class SpaMatrixf//行数int rows;//列数int cols;
角（或上三角）矩阵元素所需的二维数组，来达到压缩存储的目的。 4.6 稀疏矩阵 对一个 m×n 的矩阵，设 s 为矩阵元素个数的总和，有 s=m*n，设 t 为矩阵中非零元素 个数的总和，满足 t＜＜s 的矩阵称作稀疏矩阵。符号“＜＜”读作小于小于。简单说，稀 疏矩阵就是非零元素个数远远小于元素个数的矩阵。相对于稀疏矩阵来说，一个不稀疏的 矩阵也称作稠密矩阵。 4.6.1 稀疏矩阵的压缩存储 稀疏矩阵的压缩存储方法，是只存储矩阵中的非零元素。稀疏矩阵中每个非零元素及 其对应的行下标和列下标构成一个三元组，稀疏矩阵中所有这样的三元组构成一个以三元 组为数据元素的线性表。 写出下图所示稀疏矩阵的压缩存储形式 解：用三元组线性表表示： {{1,2,12},{1,3,9},{3,1,-3},{3,5,14},{4,3,24},{5,2,18},{6,1,15},{6,4,-7}} 4.6.2 数组结构的稀疏矩阵类 1 三元组类 三元组的数组结构存储，就是把所有三元组存储在一个数组中。 三元组是稀疏矩阵压缩存储方法的关键。首先设计三元组类： public class Three{ public int row; public int col; public double value; Three(int r, int c, double v){ row = r; col = c; value = v; } Three(){ row = 0; col = 0; value = 0.0; } } 2.稀疏矩阵类 public class SpaMatrix{ int rows; //行数 int cols; //列数
//非零元个数int dNum;//数组MyVector v;//构造函数SpaMatrix(int max) (rows = cols = dNum = 0;v= newMyVector(max);1public void evaluate(int r, int c,int d, Threel item) throws Exceptionf//给矩阵赋值rows = r;cols = c;dNum = d;for(int i=o; i=" + ((Three)v.get(i)).value);71稀疏矩阵的转置运算：//转置public SpaMatrix transpose OSpaMatrixa=newSpaMatrix（v.size）：//创建矩阵对象//行数转为列数a. cols = rows;a.rows = cols;//列数转为行数a. dNum = dNum;//非零元个数不变for(int j=l;j<=cols; j++) (for(int i= O; i<a.dNum; i++)(if(((Three)v.get(i)).col==j){Three t = (Three)v.get(i) :a.v.add(new Three(t.col, t.row, t.value)):11小1/返回矩阵对象return a;
int dNum; //非零元个数 MyVector v; //数组 SpaMatrix(int max){ //构造函数 rows = cols = dNum = 0; v = new MyVector(max); } public void evaluate(int r, int c, int d, Three[] item) throws Exception{ //给矩阵赋值 rows = r; cols = c; dNum = d; for(int i = 0; i =" + ((Three)v.get(i)).value); } } } 稀疏矩阵的转置运算： public SpaMatrix transpose(){ //转置 SpaMatrix a = new SpaMatrix(v.size());//创建矩阵对象 a.cols = rows; //行数转为列数 a.rows = cols; //列数转为行数 a.dNum = dNum; //非零元个数不变 for(int j=1;j<=cols;j++){ for(int i = 0; i < a.dNum; i ++){ if(((Three)v.get(i)).col==j){ Three t = (Three)v.get(i); a.v.add(new Three(t.col, t.row, t.value)); } } } return a; //返回矩阵对象 }
【本讲课程的小结】矩阵的压缩存储问题是我们应该掌握的内容，特别是对于稀疏矩阵的这种三元组表示方法在我们后续的课程中还会涉及到，所以大家要着重理解。【本讲课程的作业】在Matrix类中添加成员函数实现矩阵相乘的操作
【本讲课程的小结】矩阵的压缩存储问题是我们应该掌握的内容，特别是对于稀疏矩阵的 这种三元组表示方法在我们后续的课程中还会涉及到，所以大家要着重理解。 【本讲课程的作业】 在 Matrix 类中添加成员函数实现矩阵相乘的操作