基于C++的稀疏矩阵乘法运算器的实现

副标题#e#

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++语言描写为:

#p#副标题#e#

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

#p#副标题#e#

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;

}

#p#副标题#e#

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 的元素

#p#分页标题#e#

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++语言实现了稀疏矩阵乘法运算器的实现, 通过一个实例验证了所实现算法的正确性, 造就了对编程的乐趣，同时也提高了编程的本领. 同时, 本文中所设计的关于稀疏矩阵数据的存储, 稀疏矩阵的建设以及稀疏矩阵相乘对初学者具有必然的指导浸染.

关键字：