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++語言實現了稀疏矩陣乘法 運算器的實現, 通過一個實例驗證了所實現算法的正確性, 培養了對編程的興趣，同時也提 高了編程的能力. 同時, 本文中所設計的關於稀疏矩陣數據的存儲, 稀疏矩陣的創建以及稀 疏矩陣相乘對初學者具有一定的指導作用.
