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

《十字链表实现稀疏矩阵的加法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验二十字链表一、实验题目以十字链表为储存结构，实现稀疏矩阵的求和运算。二、问题描述1、功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。2、输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。若输入332则表示这个稀疏矩阵有3行3列2个非零元然后用户需要为这两个非零元输入行、列、非零元的值如：112221表示第一个非零元行为1，列为1,，值为2；第二个非零元行为2，列为2，值为1。此过程输入的稀疏矩阵为：20

2、00100003、输出要求：输出按矩阵输出，按行列依次输出，非零元则输出非零元的值，不是非零元则输出“0”。各元素之间用空格隔开。最后输出完整的矩阵。三、概要设计1．稀疏矩阵的抽象数据类型定义如下：ADTSparseMatrix{数据对象：D={aij

3、i=1,2,3……m,j=1,2,3……n;aij属于ElemSet,m和n分别是稀疏矩阵的行数和列数}数据关系：R={Row,Col}Row={

4、1<=i<=m,1<=j<=n-1}Col={

5、1<=i<=m-1,1<=j<=n}基本操作：CreateSMatrix(&M);//建

6、立稀疏矩阵MDestroySMatrix(&M);//销毁稀疏矩阵M；TransposeSMatrix(M);//求稀疏矩阵的转置矩阵AddSMatrix(&M,&N);//求稀疏矩阵M和N之和MulSMatrix(&M,&N);//求稀疏矩阵M和N之积}ADTSparseMatrix2、存储结构选择采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。在十字链表中，每一个非零矩阵元素存储在一个结点。每一个节点除了存储非零元素的三元组以外，还设置了right和down两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元结点。3、其他函数1）主函数m

7、ain（）2）作为友元函数的加法运算。四、详细设计用十字链表表示稀疏矩阵，需要定义结点类和链表类两个类1、结点类MatrixNodetemplateclassMatrixNode{friendclassLinkMatrix;friendistream&operator>>(istream&,LinkMatrix&);friendostream&operator<<(ostream&out,LinkMatrix&);friendLinkMatrixoperator+(constLinkMatrix

8、&a,constLinkMatrix&b);private:introw,col;MatrixNode*right,*down;union{Typedata;MatrixNode*next;};};2、链表类templateclassLinkMatrix{private:MatrixNode*head;voidInsertInCol(MatrixNode*p);voidDeleteInCol(MatrixNode*p);public:friendistream&operator>>(

9、istream&in,LinkMatrix&);friendostream&operator<<(ostream&out,LinkMatrix&);MatrixNode*Head(inti);LinkMatrix&operator+=(constLinkMatrix&a);friendLinkMatrixoperator+(constLinkMatrix&a,constLinkMatrix&b);};1、求头结点函数templateMatrixNode

10、e>*LinkMatrix::Head(inti){MatrixNode*a;a=head->next;for(intj=1;jnext;}returna;}2、将结点p插入p->col列中templatevoidLinkMatrix::InsertInCol(MatrixNode*p){MatrixNode*pre,*ch=Head(p->col);pre=ch;while(pre->down!