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 |