1. 问题描述
稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特 点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵乘法运 算的运算器。以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个 矩阵相乘的运算。稀疏矩阵采用十字链表表示，而运算结果的矩阵则以通常的阵列形式列出
2 设计
2.1 用十字链表存储稀疏矩阵
为了能有效存储稀疏矩阵的元素 , 本文采用十字链表对数据进行存储, 所设计的十字链表C++语言描述如 下:
Typedef struct OLNode{
Int i , j ;
ElemType e;
Struct OLNode * right, * down;
}OLNode; *OLink;
Typedef struct{
OLink * rhead, * chead;
Int mu,nu,tu;
}CrossList;
2.2 稀疏矩阵相乘主 要算法设计
稀疏矩阵乘法运算器的设计主要设计到稀疏矩阵的创建和相乘运算, 下面 给出这两个过程的C++语言描述为:
2.2.1 稀疏矩阵的创建
Statue CreateSMatrix_OL (CrossList & M){
//创建稀疏矩阵M。
If (M) free(M);
Scanf (&m,&n,&t);
M.mu:=m; M.nu:=n; M.tu:=t;
If (! ( M.rhead=(OLink * )malloc( (m+1) * sizeof(OLink) ) ) ) exit (OVERFLOW)
If (! ( M.chead=(OLink * ) malloc( (n+1) * sizeof(OLink) ) ) ) exit (OVERFLOW)
M.rhead[ ] +M.chead[ ]=NULL;
For ( scanf( & i, & j, & e); i!=0 ; scanf ( &I, & j, &e ) ){
If(! ( p=(OLNode * ) malloc( sizeof (OLNode) ) ) ) exit ( OVERFLOW )
P—>i = i; p—>j=j ; p—>e=e;
If (M . rhead [ i ] = =NULL) M . rhead [ i ] = p;
Else{
For ( q = M . rhead [ i ]; ( q—>right ) && q—> right—> j < j; q = q—> right;)
p—>right =q—>right ; q—>right=p; }
if (M . chead [ j ] = =NULL) M . chead[ j ]=p;
else{
For ( q=M . chead [ j ] ; (q—>down) && q—>down—> i < i ; q = q—>down;)
p—>down = q—>down;
q—>down = p ;}
}
Return OK;
}//CreateSMatrix_OL
2.2.2 疏矩阵的相乘运算
Status MultSMatrix(RLSMatrix M, RLSMatrix N ,RLSMatrix & Q){
//求 矩阵乘积Q=M*N
if(M . nu! = N . mu) return ERROR;
Q . mu=M . mu; Q . nu = N . nu ; Q . tu= 0;
If (M . tu* N . tu ! = 0) {
For ( arow=1 ; arrow<=M.mu; ++arrow ){
Ctemp[ ]= 0;
Q.rpos[arrow]=Q . tu + 1;
For ( p = M . rpos[arrow]; p<M.rpos[arrow+]; ++p){
brow = M .data [ p ] . j;
if ( brow<N.nu ) t = N . rpos[ brow + 1 ];
else {t=N.tu+1}
for ( q = N . rpoe[ brow ]; q<t; ++q){
ccol = N . data[q] . j;
ctemp[ ccol ] += M . data[ p ] . e * N . data[ q ] . e;
}//for q
}
for ( ccol = 1 ; ccol <= Q.nu; ++ccol )
if (ctemp[ccol]){
if (++Q . tu > MAXSIZE) return ERROR;
Q.data[ Q . tu ] = { arrow, ccol, ctemp[ccol] };
}
}
}
return OK;
}
3 实验及其调试
3.1 测试数据
4 -3 0 0 1 3 0 0 0 -6 0
0 0 0 8 0 × 4 2 0 8 0 0
0 0 1 0 0 0 1 0 = 0 1 0
0 0 0 0 70 1 0 0 0 0 0
0 0 0
3.2 调试报告
稀疏矩阵相乘的基本操作是：对于M 中每个元素M . data . j = N . data [ q ] . i 的元素
N . data[ q ],求得M . data[ p ] . v和N . data[ q ] . v的乘积，而乘积矩阵Q中每个元素的值是个累计和，这个 乘积M . data[ p ] . v * n . data[ q ]只是Q( i , j )中的一部分。为便于操作，应对每 个元素设一累计和的变量，起初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当 的求累计的变量上
累加器ctemp的初始的时间复杂度为O（M . mu * N . nu ）,求Q的 所有非零元的时间复杂度为O（M . tu * N . tu / N . mu）,进行压缩存储的时间复杂度为O （M . mu * N . nu）,因此，总的时间复杂度为O（M.mu * N.nu+M.tu * N.tu / N.mu）。
在调试过程中，在程序的建立十字链表时的插入过程中，对插入元素的列和整个矩阵 的列时常混淆造成出错，以及在建立十字链表的行列头链表时，并没考虑行列的大小问题， 即没有考虑m, n的大小。
4 结束语
本文采用标准C++语言实现了稀疏矩阵乘法 运算器的实现, 通过一个实例验证了所实现算法的正确性, 培养了对编程的兴趣，同时也提 高了编程的能力. 同时, 本文中所设计的关于稀疏矩阵数据的存储, 稀疏矩阵的创建以及稀 疏矩阵相乘对初学者具有一定的指导作用.
