稀疏矩阵相乘.doc

稀疏矩阵相乘
1问题描述

稀疏矩阵及其三元组表示
行(row)
列(col)
值(value)
[0]
0
3
22
[1]
0
6
15
[2]
1
1
11
[3]
1
5
17
[4]
2
3
-6
[5]
3
5
39
[6]
4
0
39
[7]
5
2
28
稀疏矩阵

(2)稀疏矩阵的十字链表表示

以“带行逻辑链接信息”的三元组表示稀疏矩阵;
输入矩阵用三元组顺序输入;
(2)稀疏矩阵采用十字链表表示;
(3)实现两个矩阵相乘的运算,而运算结果的矩阵则以通常的阵列形式列出。
2设计思路


只存储矩阵中极少的非零元素,采用<row,col,value>来唯一地确定每一个非零元素,其中row、col、value分别表示非零元素在矩阵中的的行下标、列下表和值。各数组元素的三元组按在原矩阵中的位置以行优先的顺序依次存放。
struct triple
{ //三元组结构定义
int row, col; //非零元素行号,列号
Float value; //非零元素的值
triple& operator=(triple &x)
{row=;col=;value=;}
};

struct element{ int row,col;float value;};
class Matrix;
class node
{ // 矩阵节点类的定义
friend class Matrix;
public:
node():head(true){ right=down=this;} //建立附加头结点
node(element *t) // 建立非零元素结点
{
=t->col;
=t->row;
=t->value;
right=down=this;
head=false;
}
node*down,*right;//行列链表指针
bool head;
union{ element triple;node*next;}; //无名联合
};
class Matrix
{//稀疏矩阵的类定义
friend istream&operator>>(istream&,Matrix&);
friend ostream&operator<<(ostream&,Matrix&);
private:
int Row,Col,Terms,temp; //矩阵的总行数,总列数,和非零元素个数和临时变量;
node*headnode; //稀疏矩阵的总表头
public:
Matrix(int m,int n); //重载构造函数
Matrix(); //对矩阵进行构造
Matrix(Matrix& T); //复制构造函数
~Matrix(){makeEmpty();} //析构函数
void Init(int m,int n); //初始化函数,又来初始化无参构造函数构造的矩阵
void makeEmpty(); //清空矩阵
void Insert(int m,int n,float p); //插入矩阵元素
node *Locate(int i); //定位附加头结点
Matrix Mul(Matrix b); //两个矩阵相乘
Matrix &operator=(Matrix &T); //重载赋值号
};
在稀疏矩阵的十字链表表示中,矩阵的的每一行设置为一个带附加头结点的循环行链表,每一列也设置为一个带附加头结点的循环列链表。链表中的结点都属于类node的对象,这个类包含一个域head,它用于区分改结点是附加头结点还是链表中的非零元素结点;head=true,表示该结点是附加头结点;head=false,表示该结点是矩阵中的非零元素结点。
每一个附加头结点还有三个域:down、right、next。第i个行链表和第i个列链表共用一个附加头结点,在它的right域存放第i行链表最前端的第一个结点的地址,在它的down域存放第i列链表的最前端第一个结点的地址,通过next域链接到第i+1个附加头结点。每一个非零元素结点包含六个域:head,row,col,down,right,value。Down存放列链表指针,right存放行链表指针。
整个稀疏矩阵定义为类Matr