|
稀疏矩阵 设矩阵Amn中有s个非零元素若s远远小于矩阵元素的总数(即s<<m×n)则称A为稀疏矩阵 稀疏矩阵的压缩存储为了节省存储单元可只存储非零元素由于非零元素的分布一般是没有规律的因此在存储非零元素的同时还必须存储非零元素所在的行号列号才能迅速确定一个非零元素是矩阵中的哪一个元素稀疏矩阵的压缩存储会失去随机存取功能 其中每一个非零元素所在的行号列号和值组成一个三元组(ijaij)并由此三元组惟一确定 稀疏矩阵进行压缩存储通常有两类方法顺序存储和链式存储链式存储方法【参见参考书目】 三元组表 将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)并依次存放在向量中这种稀疏矩阵的顺序存储结构称为三元组表 注意 以下的讨论中均假定三元组是按行优先顺序排列的 【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b) （）三元组表的类型说明 为了运算方便将矩阵的总行数总列数及非零元素的总数均作为三元组表的属性进行描述其类型描述为 #define MaxSize //由用户定义 typedef int DataType //由用户定义 typedef struct { //三元组 int ij//非零元的行列号 DataType v //非零元的值 }TriTupleNode typedef struct{ //三元组表 TriTupleNode data[MaxSize] //三元组表空间 int mnt //矩阵的行数列数及非零元个数 }TriTupleTable () 压缩存储结构上矩阵的转置运算 一个m×n的矩阵A它的转置矩阵B是一个n×m的矩阵且 A[i][j]=B[j][i]≤i<m≤j<n 即A的行是B的列A的列是B的行 【例】下图中的B和上图中的A互为转置矩阵 ①三元组表表示的矩阵转置的思想方法 第一步根据A矩阵的行数列数和非零元总数确定B矩阵的列数行数和非零元总数 第二步当三元组表非空（A矩阵的非零元不为）时根据A矩阵三元组表的结点空间data（以下简称为三元组表）将A的三元组表a>data置换为B的三元组表b>data ②三元组表的转置 方法一:简单地交换a>data中i和j中的内容得到按列优先顺序存储倒b>data;再将b>data重排成按行优先顺序的三元组表 方法二:由于A的列是B的行因此按a>data的列序转置所得到的转置矩阵B的三元组表b>data必定是按行优先存放的 按这种方法设计的算法其基本思想是对A中的每一列col(≤col≤a>n)通过从头至尾扫描三元组表a>data找出所有列号等于col的那些三元组将它们的行号和列号互换后依次放人b>data中即可得到B的按行优先的压缩存贮表示具体实现参见【动画演示】 ③具体算法 void TransMatrix(TriTupleTable *bTriTupleTable *a) {//*a*b是矩阵AB的三元组表表示求A转置为B int pqcol b>m=a>n b>n=a>m //A和B的行列总数互换 b>t=a>t //非零元总数 if(b>t<=) Error(A=) //A中无非零元退出 q= for(col=col<a>ncol++) //对A的每一列 for(p=p<a>tp++) //扫描A的三元组表 if(a>data[p]．j==col){ //找列号为col的三元组 b>data[q)．i=a>data[p]j b>data[q]．j=a>data[p]i b>data[q]．v=a>data[p]v q++ } } //TransMatrix ④算法分析 该算法的时间主要耗费在col和p的二重循环上 若A的列数为n非零元素个数t则执行时间为O(n×t)即与A的列数和非零元素个数的乘积成正比 通常用二维数组表示矩阵时其转置算法的执行时间是O(m×n)它正比于行数和列数的乘积 由于非零元素个数一般远远大于行数因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间 带行表的三元组表为了方便某些矩阵运算在按行优先存储的三元组表中加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置这就是带行表的三元组表 （）类型描述 #define MaxRow l //在三元组表定义前加入此最大行定义 typedef struct { TriTupleNode data[MaxSize] int RowTab[MaxRow]//行表应保证m≤MaxRow int mnt; }RTriTupleTable （）带行表的三元组表的操作 ① 对于任给行号i(≤i≤m)能迅速地确定该行的第一个非零元在三元组表中的存储位置为RowTab[i] ② RowTab[i](≤i≤m)表示第i行之前的所有行的非零元数 ③ 第i行上的非零元数目为RowTab[i+]RowTab[i](≤i≤m) ④ 最后一行(即第ml行)的非零元数目为tRowTab[m](t为矩阵的非零元总数) 注意 若在行表中令RowTab[m]=t（要求MaxRow>m）会更方便 些且t可省略 带行表的三元组表可改进矩阵的转置算法具体【参阅其它参考书】 ．稀疏矩阵压缩存储方式分析 （） 三元组表和带行表的三元组表的特点 相应的算法描述较为简单但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵运算就显得不太适合 【例】执行将矩阵B相加到矩阵A上的运算时某位置上的结果可能会由非零元变为零元但也可能由零元变为非零元这就会引起在A的三元组表中进行删除和插人操作从而导致大量结点的移动对此类运算采用链式存储结构为宜 （）稀疏矩阵的链式结构 稀疏矩阵的链式结构有十字链表等方法适用于非零元变化大的场合 比较复杂可【参阅其它参考书】 |
