|
|
稀疏矩阵是指矩阵中非零元素很少且分布没有规律。设二维数组Am×n有N个非零元素,N<ij]来表示,其中,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,4,-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中的位置。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|