十字链表实现稀疏矩阵的加法.docx

实验二十字链表
一、实验题目

以十字链表为储存结构，实现稀疏矩阵的求和运算。

二、问题描述
功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。
输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行
数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。
若输入
332
则表示这个稀疏矩阵有3行3列2个非零元
然后用户需要为这两个非零元输入行、列、非零元的值
如：
112
221
表示第一个非零元行为1，列为1,，值为2；第二个非零元行为2，列为2，值为1。
此过程输入的稀疏矩阵为：
200
010
000
输出要求：输出按矩阵输出，按行列依次输出，非零元则输出非零元的值，不是非
零元则输出“0”。各元素之间用空格隔开。最后输出完整的矩阵。

三、概要设计
1．稀疏矩阵的抽象数据类型定义如下：
ADTSparseMatrix{
数据对象：D={aij|i=1,2,3……m,j=1,2,3……n;
aij属于ElemSet,m和n分别是稀疏矩阵的行数和列数}
数据关系：R={Row,Col}
Row={<aij,aij+1>|1<=i<=m,1<=j<=n-1}
Col={<aij,ai+1j>|1<=i<=m-1,1<=j<=n}
基本操作：
CreateSMatrix(&M);
//建立稀疏矩阵M
DestroySMatrix(&M);
//销毁稀疏矩阵M；
TransposeSMatrix(M);
//求稀疏矩阵的转置矩阵
AddSMatrix(&M,&N);
//求稀疏矩阵M和N之和
MulSMatrix(&M,&N);
//求稀疏矩阵M和N之积
}ADTSparseMatrix

存储结构选择
采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。在十字链表中，每一个非零矩阵元素存储在一个结点内。每一个节点除了存储非零元素的三元组以外，还设置了right和down两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元结点。
其他函数
主函数main（）
作为友元函数的加法运算。

详细设计
用十字链表表示稀疏矩阵，需要定义结点类和链表类两个类
结点类MatrixNode
template<classType>classMatrixNode
{

friendclassLinkMatrix<Type>;
friendistream&operator>>(istream&,LinkMatrix<Type>&);
friendostream&operator<<(ostream&out,LinkMatrix<Type>&);
friendLinkMatrix<Type>operator+(constLinkMatrix<Type>&a,constLinkMatrix<Type>&b);
private:
introw,col;
MatrixNode<Type>*right,*down;
union{
Typedata;
MatrixNode<Type>*next;
};
};

链表类
template<classType>classLinkMatrix
{
private:
MatrixNode<Type>*head;
voidInsertInCol(MatrixNode<Type>*p);
voidDeleteInCol(MatrixNode<Type>*p);
public:
friendistream&operator>>(istream&in,LinkMatrix<Type>&);
friendostream&operator<<(ostream&out,LinkMatrix<Type>&);
MatrixNode<Type>*Head(inti);
LinkMatrix<Type>&operator+=(constLinkMatrix<Type>&a);
friendLinkMatrix<Type>operator+(constLinkMatrix<Type>&a,constLinkMatrix<Type>&b);

};

求头结点函数
template<classType>MatrixNode<Type>*LinkMatrix<Type>::Head(inti)
{
MatrixNode<Type>*a;
a=head->next;
for(intj=1;j<i;j++)
{
a=a->next;
}
returna;
}

将结点p插入p->col列中
template<classType>voidLinkMatr