| |
| 稀疏矩阵指矩阵中非零元素很少，且分布没有规律。设二维数组Am×n有N个非零元素，N<<m*n，但它不是特殊矩阵（如对角矩阵）。对稀疏矩阵而言，只存储非零元素。用线性表存储稀疏矩阵的非零元素，除非零元素的值外，还应有一些辅助信息。顺序存储节省存储空间，但插入和删除不方便。稀疏矩阵的表示可用三元组[i,j,aij]来表示，其中，i、j、aij分别表示行列位置和值。由此可见，稀疏矩阵可由表示非零元的三元组和其行列数唯一确定。节点中除元素值外，还有元素所在行、列信息。节点结构如下：
|
|
|
|
|
| 对如下图所示的稀疏矩阵，其三元组表示为（1, 2, 12），（1, 3, 9），（3, 1, -3），（3, 6, 14），（4, 3, 24），（5, 2, 18），（6, 1, 15），（6, 3, -7）。
|
|
|
|
|
|
|
|
|
|
|
| 可利用三元组表实现矩阵的运算（以行序为主序），如矩阵的转置和矩阵的相乘等。
|
|
|
| 对于矩阵am×n转置为bn×m，使a[i, j]=b[j, i]，其中，1≤i≤n, 1≤j≤m，其实现步骤如下。
|
|
|
|
|
|
|
|
|
| 按a.data中三元组的次序进行转置，将转置后的三元组置入b中恰当的位置，如能预先确定M中每一列的第一个非零元在b.data中的相应位置，则转置时可直接放入b.data恰当的位置。先求每一列非零元的个数，设num、cpot两个向量，num[col]表示M中第col列非零元个数，cpot[col]的初值表示M中第col列第一个非零元在b.data中的位置。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
