第3章 稀疏矩阵和广义表课件.ppt

第三章 稀疏矩阵和广义表;行与第4列交点位置上的元素9对应的行号和列号分别为2和4。 图3-1 矩阵和稀疏矩阵;2. 稀疏矩阵的三元组线性表表示 在计算机中存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元 素，因而能够较容易地实现矩阵的各种运算，如转置运算、加法运算、乘法运算等。但对于稀疏矩阵来说，采用二维数组的存储方法既浪费大量的存储单元用来存放零元素，又要在运算中花费大量的时间来进行零元素的无效计算，显然是不可取的。一种较好的方法是：只考虑存储占元素中极少数的非零元素。 对于稀疏矩阵中的每个非零元素，可用它所在的行号、列号以及元素值这三元组(i,j,aij)来表示。若把所有的三元组按照行号为主序（即为主关键字）、列号为辅序（即为次关键字，当行号相同时再考虑列号次序）进行排列，则就构成了一个表示稀疏矩阵的三元组线性表。图3-1(b)稀疏矩阵所对应的三元组线性表表示为： ((1,1,3),(1,4,5),(2,3,-2),(3,1,1),(3,3,4),(3,5,6),(5,3,-1)) 稀疏矩阵采用三元组线性表表示后，可以使用顺序或链接方式存储，从而比采用二维数组存储要大大地节省存储空间。; 3. 稀疏矩阵的运算概述 对稀疏矩阵的运算与对一般用二维数组所表示的矩阵的运算相同，通常为求一个稀疏矩阵的转置，计算两个矩阵的和，计算两个矩阵的乘积等。一个矩阵的转置结果仍是一个矩阵，该矩阵中的第i行与第j列交点位置上的元素等于被转置矩阵中第j行与第i列交点位置上的元素。两个矩阵的和仍然是一个矩阵，该矩阵中的第i行第j列位置上的元素等于两个相加矩阵中对应位置上的元素之和。两个相乘矩阵的乘积仍然是一个矩阵，该矩阵中的第i行第j列位置上的元素等于第一个乘数矩阵中的第i行与第二个乘数矩阵中的第j列上对应元素乘积之累加和。假定第一个乘数矩阵为A[m][n]，第二个乘数矩阵为B[n][p]，乘积结果矩阵为C[m][p]，则C中任一元素C[i][j]等于 ，其中1≤i≤m，1≤j≤p。; (3) 按照一定格式输出稀疏矩阵 void OutputMatrix(Matrix M) (4) 返回稀疏矩阵M的转置矩阵 Matrix TransposedMatrix(Matrix M (5) 返回稀疏矩阵M1和M2之和，要求两个矩阵的行、列数均分别相同 Matrix AddMatrix(Matrix M1, Matrix M2) (6) 返回稀疏矩阵M1和M2之乘积，要求M1的列数等于M2的行数 Matrix MultiplyMatrix(Matrix M1, Matrix M2);3.1.2 稀疏矩阵的存储结构 1. 顺序存储 稀疏矩阵的顺序存储就是对其相应的三元组线性表进行顺序存储。假定每个非零元素的三元组用如下记录结构定义： struct Triple { int row, col; ElemType val; }; 其中row和col用来分别存储元素的行号和列号，val用来存储元素值。 一个稀疏矩阵的顺序存储类型定义如下： struct SMatrix { int m, n, t; struct Triple sm[MaxTerms+1]; };; 其中m,n和t域分别用来存储稀疏矩阵的行数、列数和非零元素的个数，sm数组域用来顺序存储每个三元组元素，假定下标为0的元素sm[0]不用，从下标为1起使用。MaxTerms为一个事先定义的全局常量，其值要大于等于非零元素的个数t，由它决定sm数组的大小。例如，若用SMatrix类型的对象存储图3-1(b)所示的稀疏矩阵，则m,n和t域的值应分别为5,6和7，sm数组中的内容如图3-2所示。 ; 2. 链接存储 稀疏矩阵的链接存储就是对其相应的三元组线性表进行链接存储。下面介绍两种链接存储方法。 (1) 带行指针向量的链接存储 在这种链接存储中，需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为： struct TripleNode { int row, col; /*存储行号和列号*/ Elem