计计1313刘汝佳刘汝佳矩阵的表示矩阵的表示矩阵的基本运算矩阵的基本运算小结和应用举例小结和应用举例三角矩阵的压缩表示法三角矩阵的压缩表示法稀疏矩阵的三元组表示法稀疏矩阵的三元组表示法稀疏矩阵的十字链表表示法稀疏矩阵的十字链表表示法矩阵在形式上最直接的表示是一个二维数组但矩阵在形式上最直接的表示是一个二维数组但是在一些特殊的场合中我们需要引入一些特殊是在一些特殊的场合中我们需要引入一些特殊的方法来表示一些特殊的矩阵。在本节中大家的方法来表示一些特殊的矩阵。在本节中大家还将了解到以下几种表示方法还将了解到以下几种表示方法::structTMatrixstructTMatrixintnmintnmintnumbersMAXN1MAXN1intnumbersMAXN1MAXN1我们用二维数组很容易表示一个矩阵。加上矩阵的维数我们用二维数组很容易表示一个矩阵。加上矩阵的维数MM和和NN我们可以定义一个我们可以定义一个TMatrix结构结构::这就是矩阵的二维数组表示法。这就是矩阵的二维数组表示法。怎么样容易吧怎么样容易吧1NN阶上三角矩阵对称矩阵和反对称矩阵阶上三角矩阵对称矩阵和反对称矩阵都只需要储存主对角线以上的共都只需要储存主对角线以上的共N1N/2N1N/2个元素。个元素。因此我们可以用一个大小为因此我们可以用一个大小为N1N/2N1N/2的一维数组来表示。的一维数组来表示。不过我们需要一个公式把每个元素不过我们需要一个公式把每个元素原来的位置原来的位置ijij映射到一维数组的下标映射到一维数组的下标kk。。2我们从上到下从左到右地储存各个元我们从上到下从左到右地储存各个元素如下图素如下图44343324232214131211aaaaaaaaaa10987654321aaaaaaaaaaAAijij前面的数的个数为前面的数的个数为计算得计算得::1111jlniljiink12221在前面的二维数组表示法中我们表示在前面的二维数组表示法中我们表示一个一个NMNM的矩阵需要的矩阵需要NMNM个内存单元。个内存单元。如果已知矩阵中存在着大量的如果已知矩阵中存在着大量的00元素那元素那么这种表示方法是很浪费空间的。么这种表示方法是很浪费空间的。由于非零元素的个数由于非零元素的个数LL十分有限我们可十分有限我们可以只储存下这以只储存下这LL个元素的位置和大小占个元素的位置和大小占用的空间便会少得多。用的空间便会少得多。显然表示稀疏矩阵最直接的方法就是显然表示稀疏矩阵最直接的方法就是仅记录下非零元素的个数仅记录下非零元素的个数LL和这和这LL个元素个元素的位置的位置rowcolrowcol和大小和大小valuevalue即下面这即下面这个结构个结构structTMatrix2intlintrowMAXLcolMAXLvalueMAXL1三元组表示法比较好的解决了稀疏矩阵的空间存储问三元组表示法比较好的解决了稀疏矩阵的空间存储问题却忽视了稀疏矩阵可能进行了一些基本操作。题却忽视了稀疏矩阵可能进行了一些基本操作。考虑两个稀疏矩阵考虑两个稀疏矩阵AA和和BB相加的问题。对于运算结果矩相加的问题。对于运算结果矩阵阵CC来说可能会因为正负抵消而产生出很多新的零元来说可能会因为正负抵消而产生出很多新的零元素和非零元素导致三元组需要进行一些插入和删除素和非零元素导致三元组需要进行一些插入和删除操作。当这些操作很频繁的时候程序的速度会明显操作。当这些操作很频繁的时候程序的速度会明显变慢。变慢。在某些特定情况下我们需要对元素进行检索由于在某些特定情况下我们需要对元素进行检索由于三元组的元素之间联系并不紧密所以检索很不方便。三元组的元素之间联系并不紧密所以检索很不方便。2为了加强同一行和同一列之间元素的联系我为了加强同一行和同一列之间元素的联系我们把每一行分别做成一个链表把每一列也分们把每一行分别做成一个链表把每一列也分别做成一个链表。别做成一个链表。通过对链表的遍历我们可以很方便的按顺序通过对链表的遍历我们可以很方便的按顺序访问到某一特定行或列的所有元素。插入和删访问到某一特定行或列的所有元素。插入和删除操作也很方便。除操作也很方便。这样我们了建立一种十字型的链表结构每这样我们了建立一种十字型的链表结构每个结点有上下左右四个指针和自身的位个结点有上下左右四个指针和自身的位置坐标大小共置坐标大小共77个域。个域。3结点类型如下定义结点类型如下定义structTnodeintrowcolintvalueTnodeleftrightupdownrowcolrowcol分别为该非零元素的位置分别为该非零元素的位置valuevalue为它的值。为它的值。leftrightupdownleftrightupdown分别为指向四个方向的后继元素。分别为指向四个方向的后