稀疏矩阵相乘.doc

稀疏矩阵相乘

1问题描述

1.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〕稀疏矩阵的十字链表表示

1.2根本要求

以“带行逻辑链接信息”的三元组表示稀疏矩阵；

输入矩阵用三元组顺序输入；

〔2〕稀疏矩阵采用十字链表表示；

〔3〕实现两个矩阵相乘的运算，而运算结果的矩阵那么以通常的阵列形式列出。

2设计思路

2.1存储结构设计

2.1.1三元组表示稀疏矩阵

只存储矩阵中极少的非零元素，采用row,col,value来唯一地确定每一个非零元素，其中row、col、value分别表示非零元素在矩阵中的的行下标、列下表和值。各数组元素的三元组按在原矩阵中的位置以行优先的顺序依次存放。

structtriple

{//三元组结构定义

introw,col; //非零元素行号,列号

Floatvalue;//非零元素的值

tripleoperator=(triplex)

{row=x.row;col=x.col;value=x.value;}

};

2.1.2十字链表表示稀疏矩阵

structelement{introw,col;floatvalue;};

classMatrix;

classnode

{//矩阵节点类的定义

friendclassMatrix;

public:

node():head(true){right=down=this;}//建立附加头结点

node(element*t)//建立非零元素结点

{

triple.col=t-col;

triple.row=t-row;

triple.value=t-value;

right=down=this;

head=false;

}

node*down,*right;//行列链表指针

boolhead;

union{elementtriple;node*next;};//无名联合

};

classMatrix

{//稀疏矩阵的类定义

friendistreamoperator(istream,Matrix);

friendostreamoperator(ostream,Matrix);

private:

intRow,Col,Terms,temp;//矩阵的总行数，总列数，和非零元素个数和临时变量；

node*headnode;//稀疏矩阵的总表头

public:

Matrix(intm,intn);//重载构造函数

Matrix();//对矩阵进行构造

Matrix(MatrixT);//复制构造函数

~Matrix(){makeEmpty();}//析构函数

voidInit(intm,intn);//初始化函数，又来初始化无参构造函数构造的矩阵

voidmakeEmpty();//清空矩阵

voidInsert(intm,intn,floatp);//插入矩阵元素

node*Locate(inti);//定位附加头结点

MatrixMul(Matrixb);//两个矩阵相乘

Matrixoperator=(MatrixT);//重载赋值号

};

在稀疏矩阵的十字链表表示中，矩阵的的每一行设置为一个带附加头结点的循环行链表，每一列也设置为一个带附加头结点的循环列链表。链表中的结点都属于类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存放行链表指针。

整个稀疏矩阵定义为类Matrix的一个对象，*headnode给出整个附加头