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

　　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;