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

实验二 十字链表 一、实验题目 以十字链表为储存结构，实现稀疏矩阵的求和运算。 二、问题描述1、 功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。2、 输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。 若输入3 3 2 则表示这个稀疏矩阵有3行3列2个非零元 然后用户需要为这两个非零元输入行、列、非零元的值 如：1 1 22 2 1 表示第一个非零元行为1，列为1,，值为2；第二个非零元行为2，列为2，值为1。 此过程输入的稀疏矩阵为： 2 0 0 0 1 0 0 0 03、 输出要求：输出按矩阵输出，按行列依次输出，非零元则输出非零元的值，不是非零元则输出“0”。各元素之间用空格隔开。最后输出完整的矩阵。 三、概要设计1稀疏矩阵的抽象数据类型定义如下：ADT SparseMatrix 数据对象： D=aij|i=1,2,3m,j=1,2,3n; aij属于ElemSet,m和n分别是稀疏矩阵的行数和列数数据关系： R= Row, Col Row=|1=i=m,1=j=n-1Col=|1=i=m-1,1=j=n基本操作：CreateSMatrix(&M);/建立稀疏矩阵MDestroySMatrix(&M);/销毁稀疏矩阵M；TransposeSMatrix(M);/求稀疏矩阵的转置矩阵AddSMatrix(&M,&N);/求稀疏矩阵M和N之和MulSMatrix(&M,&N);/求稀疏矩阵M和N之积ADT SparseMatrix2、 存储结构选择采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。在十字链表中，每一个非零矩阵元素存储在一个结点内。每一个节点除了存储非零元素的三元组以外，还设置了right和down两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元结点。3、 其他函数1） 主函数main（）2） 作为友元函数的加法运算。四、 详细设计用十字链表表示稀疏矩阵，需要定义结点类和链表类两个类1、 结点类MatrixNodetemplateclass MatrixNode friend class LinkMatrix;friend istream&operator(istream&,LinkMatrix&); friend ostream&operator(ostream&out, LinkMatrix&); friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b);private:int row,col;MatrixNode*right,*down;unionType data;MatrixNode*next;2、 链表类templateclass LinkMatrixprivate:MatrixNode *head;void InsertInCol(MatrixNode*p);void DeleteInCol(MatrixNode*p);public:friend istream&operator(istream&in,LinkMatrix&);friend ostream&operator(ostream&out,LinkMatrix&);MatrixNode* Head(int i);LinkMatrix&operator +=(const LinkMatrix &a);friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b); ;3、 求头结点函数template MatrixNode* LinkMatrix:Head(int i) MatrixNode*a;a=head-next;for(int j=1;jnext; return a;4、 将结点p插入p-col列中templatevoid LinkMatrix:InsertInCol(MatrixNode*p)MatrixNode*pre,*ch=Head(p-col);pre=ch;while(pre-down!=ch&pre-down-rowrow)pre=pre-down;p-down=pre-down;pre-down=p;5、 在p-col列中删除结点p，并释放空间templatevoid LinkMatrix:DeleteInCol(MatrixNode*p)MatrixNode*pre,*ch=Head(p-col);pre=ch;while(pre-down!=ch&pre-down!=p)pre=pre-down;if(pre-down=p)pre-down=p-down;delete p;6、 重载函数templateistream&operator(istream&in,LinkMatrix&a)int m,n,terms,s;MatrixNode*cp,*p,*q;cout输入矩阵的行数、列数、和非零元素个数mnterms;if(nm)s=n;else s=m;a.head=new MatrixNode;a.head-row=m;a.head-col=n;a.head-right=a.head-down=NULL;cp=new MatrixNode*s+1;cp0=a.head;int i;for(i=1;i=s;i+)p=new MatrixNode;p-row=p-col=0;p-right=p-down=p;cpi=p;cpi-1-next=p;cps-next=a.head;for(i=1;i=terms;i+)cout输入一个非零元三元组(row,col,value)endl;p=new MatrixNode;inp-rowp-colp-data;q=cpp-row;while(q-right!=cpp-row&(q-right-colcol)q=q-right;p-right=q-right;q-right=p;q=cpp-col;while(q-down!=cpp-row&(q-down-colcol)q=q-down;p-down=q-down;q-down=p;deletecp;return in;7、 重载函数templateostream & operator(ostream & out ,LinkMatrix& a)for(int i=1;irow;i+)MatrixNode*b=a.Head(i);b=b-right;for(int j=1;jcol;j+)if(b-row=i&b-col=j)coutdataright;elsecout0 ;coutendl;return out; 8、 重载+=实现求和函数template /重载符合赋值运算符+=LinkMatrix&LinkMatrix:operator +=(const LinkMatrix &a)MatrixNode *pre,*pa,*h,*ah,*p,*tmp;if(head-col !=a.head-col|head-row !=a.head-row)/非同型矩阵不可相加coutnext;ah=a.head-next; /h、ah指向当前处理行的头结点while(h !=head) /逐一处理各行pre=h; p=h-right; /p指向被加矩阵的当前结点，pre指向其前驱pa=ah-right; /pa分别指向加矩阵的当前结点while(pa !=ah) /处理当前行if(p !=h&(p-colcol) /若被加矩阵的列标更小，则比较下一个pre=p; p=p-right;else if(p=h|p-colpa-col) tmp=new MatrixNode(*pa) ;pre-right=tmp; /在行链表中插入pa复制结点tmptmp-right=p;InsertInCol(tmp); /在列表中插入tmppre=tmp; /当前指针p的前驱变为tmppa=pa-right;else /列标相同，则做加法p-data +=pa-data;if(!p-data) /和为0，则删除之 （行、列都要删除）tmp=p;p=p-right;pre-right=p;/在行链表中将tmp摘下DeleteInCol(tmp); /在列链表中将tmp删除pre=p;p=p-right;pa=pa-right;h=h-next; ah=ah-next; /处理下一行return *this;9、 重载+template /重载加法运算符+LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b)LinkMatrix c(a); /复制构造函数得到被加矩阵A的一个副本放在矩阵C中c+=b;return c;五、 调试与测试1、 编译环境Visual C+ 6.02、 main函数int main()LinkMatrixa,b,c;cina;coutA矩阵为：nab;coutB矩阵为：nbendl;c=a+b;coutA+B=ncendl;system(pause);return 0;3、 具体步骤按F5编译，界面出现提示“请输入行数、列数、非零元个数”。输入3 3 3表示这个矩阵行数为3，列数为3，非零元个数为3，接着提示“请输入一个非零元三元组”。输入1 1 1表示第一个三元组的行为1，列为1，值为1然后程序继续提示“输入一个非零元三元组”。按要求再依次输入2 2 23 1 5则矩阵A输入完成，程序按矩阵格式输出矩阵A程序继续提示“请输入行数、列数、非零元个数”在按上述操作继续输入3 3 41 1 22 1 13 1 13 3 3为矩阵B输入，完成后程序输入矩阵B程序同时输出A+B3、 结果分析程序提供输入和输出，根据输入的矩阵A和矩阵B，A+B计算结果准确无误。六、 使用说明使用本程序简单明了，只需根据提示为稀疏矩阵输入，就可以计算出稀疏矩阵的和。附录2： 十字链表实现稀疏矩阵相加源程序 软件2班 201113040207#includeusing namespace std;templateclass MatrixNode; templateclass LinkMatrix;templateistream &operator(istream &,LinkMatrix&);templateostream &operator(ostream &,LinkMatrix&);templateLinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b);templateclass MatrixNode friend class LinkMatrix;friend istream&operator(istream&,LinkMatrix&); friend ostream&operator(ostream&out, LinkMatrix&); friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b);private:int row,col;MatrixNode*right,*down;unionType data;MatrixNode*next;templateclass LinkMatrixprivate:MatrixNode *head;void InsertInCol(MatrixNode*p);void DeleteInCol(MatrixNode*p);public:friend istream&operator(istream&in,LinkMatrix&);friend ostream&operator(ostream&out,LinkMatrix&);MatrixNode* Head(int i);LinkMatrix&operator +=(const LinkMatrix &a);friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b); ;int main()LinkMatrixa,b,c;cina;coutA矩阵为：nab;coutB矩阵为：nbendl;c=a+b;coutA+B=ncendl;system(pause);return 0;templateistream&operator(istream&in,LinkMatrix&a)int m,n,terms,s;MatrixNode*cp,*p,*q;cout输入矩阵的行数、列数、和非零元素个数mnterms;if(nm)s=n;else s=m;a.head=new MatrixNode;a.head-row=m;a.head-col=n;a.head-right=a.head-down=NULL;cp=new MatrixNode*s+1;cp0=a.head;int i;for(i=1;i=s;i+)p=new MatrixNode;p-row=p-col=0;p-right=p-down=p;cpi=p;cpi-1-next=p;cps-next=a.head;for(i=1;i=terms;i+)cout输入一个非零元三元组(row,col,value)endl;p=new MatrixNode;inp-rowp-colp-data;q=cpp-row;while(q-right!=cpp-row&(q-right-colcol)q=q-right;p-right=q-right;q-right=p;q=cpp-col;while(q-down!=cpp-row&(q-down-colcol)q=q-down;p-down=q-down;q-down=p;deletecp;return in;template MatrixNode* LinkMatrix:Head(int i) MatrixNode*a;a=head-next;for(int j=1;jnext; return a;templatevoid LinkMatrix:InsertInCol(MatrixNode*p)MatrixNode*pre,*ch=Head(p-col);pre=ch;while(pre-down!=ch&pre-down-rowrow)pre=pre-down;p-down=pre-down;pre-down=p;templatevoid LinkMatrix:DeleteInCol(MatrixNode*p)MatrixNode*pre,*ch=Head(p-col);pre=ch;while(pre-down!=ch&pre-down!=p)pre=pre-down;if(pre-down=p)pre-down=p-down;delete p;/else throw invalid_arguement(No such a Node to be deleted in DeleteInCol();template /重载符合赋值运算符+=LinkMatrix&LinkMatrix:operator +=(const LinkMatrix &a)MatrixNode *pre,*pa,*h,*ah,*p,*tmp;if(head-col !=a.head-col|head-row !=a.head-row)/非同型矩阵不可相加coutnext;ah=a.head-next; /h、ah指向当前处理行的头结点while(h !=head) /逐一处理各行pre=h; p=h-right; /p指向被加矩阵的当前结点，pre指向其前驱pa=ah-right; /pa分别指向加矩阵的当前结点while(pa !=ah) /处理当前行if(p !=h&(p-colcol) /若被加矩阵的列标更小，则比较下一个pre=p; p=p-right;else if(p=h|p-colpa-col) /若加矩阵的列标更小，则插入tmp=new MatrixNode(*pa) ;pre-right=tmp; /在行链表中插入pa复制结点tmptmp-right=p;InsertInCol(tmp); /在列表中插入tmppre=tmp; /当前指针p的前驱变为tmppa=pa-right;else /列标相同，则做加法p-data +=pa-data;if(!p-data) /和为0，则删除之 （行、列都要删除）tmp=p;p=p-right;pre-right=p;/在行链表中将tmp摘下DeleteInCol(tmp); /在列链表中将tmp删除pre=p;p=p-right;pa=pa-right;h=h-next; ah=ah-next; /处理下一行return *this;template /重载加法运算符+LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b)LinkMatrix c(a); /复制构造函数得到被加矩阵A的一个副本放在矩阵C中c+=b;return c;templateostream & operator(ostream & out ,LinkMatrix& a)for(int i=1;irow;i+)MatrixNode*b=a.Head(i);b=b-right;for(int j=1;jcol;j+)if(b-row=i&b-col=j)coutdataright;elsecout0 ;coutendl;return out;