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

实验二十字链表一、实验题目以十字链表为储存结构，实现稀疏矩阵的求和运算。二、问题描述1、功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。2、输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。若输入332则表示这个稀疏矩阵有3行3列2个非零元然后用户需要为这两个非零元输入行、列、非零元的值如：112221表示第一个非零元行为1，列为1,，值为2；第二个非零元行为2，列为2，值为1。此过程输入的稀疏矩阵为：2000100003、输出要求：输出按矩阵输出，按行列依次输出，非零元则输出非零元的值，不是非零元则输出“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);//建立稀疏矩阵MDestroySMatrix(&M);//销毁稀疏矩阵M；TransposeSMatrix(M);//求稀疏矩阵的转置矩阵AddSMatrix(&M,&N);//求稀疏矩阵M和N之和MulSMatrix(&M,&N);//求稀疏矩阵M和N之积}ADTSparseMatrix2、存储结构选择采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。在十字链表中，每一个非零矩阵元素存储在一个结点内。每一个节点除了存储非零元素的三元组以外，还设置了right和down两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元结点。3、其他函数1）主函数main（）2）作为友元函数的加法运算。四、详细设计用十字链表表示稀疏矩阵，需要定义结点类和链表类两个类1、结点类MatrixNodetemplateclassTypeclassMatrixNode{friendclassLinkMatrixType;friendistream&operator(istream&,LinkMatrixType&);friendostream&operator(ostream&out,LinkMatrixType&);friendLinkMatrixTypeoperator+(constLinkMatrixType&a,constLinkMatrixType&b);private:introw,col;MatrixNodeType*right,*down;union{Typedata;MatrixNodeType*next;};};2、链表类templateclassTypeclassLinkMatrix{private:MatrixNodeType*head;voidInsertInCol(MatrixNodeType*p);voidDeleteInCol(MatrixNodeType*p);public:friendistream&operator(istream&in,LinkMatrixType&);friendostream&operator(ostream&out,LinkMatrixType&);MatrixNodeType*Head(inti);LinkMatrixType&operator+=(constLinkMatrixType&a);friendLinkMatrixTypeoperator+(constLinkMatrixType&a,constLinkMatrixType&b);};3、求头结点函数templateclassTypeMatrixNodeType*LinkMatrixType::Head(inti){MatrixNodeType*a;a=head-next;for(intj=1;ji;j++){a=a-next;}returna;}4、将结点p插入p-col列中templateclassTypevoidLinkMatrixType::InsertInCol(MatrixNodeType*p){MatrixNodeType*pre,*ch=Head(p-col);pre=ch;while(pre-down!=ch&&pre-down-rowp-row)pre=pre-down;p-down=pre-down;pre-down=p;}5、在p-col列中删除结点p，并释放空间templateclassTypevoidLinkMatrixType::DeleteInCol(MatrixNodeType*p){MatrixNodeType*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;deletep;}}6、重载函数templateclassTypeistream&operator(istream&in,LinkMatrixType&a){intm,n,terms,s;MatrixNodeType**cp,*p,*q;cout输入矩阵的行数、列数、和非零元素个数endl;inmnterms;if(nm)s=n;elses=m;a.head=newMatrixNodeType;a.head-row=m;a.head-col=n;a.head-right=a.head-down=NULL;cp=newMatrixNodeType*[s+1];cp[0]=a.head;inti;for(i=1;i=s;i++){p=newMatrixNodeType;p-row=p-col=0;p-right=p-down=p;cp[i]=p;cp[i-1]-next=p;}cp[s]-next=a.head;for(i=1;i=terms;i++){cout输入一个非零元三元组(row,col,value)endl;p=newMatrixNodeType;inp-rowp-colp-data;q=cp[p-row];while((q-right!=cp[p-row]&&(q-right-colp-col)))q=q-right;p-right=q-right;q-right=p;q=cp[p-col];while((q-down!=cp[p-row]&&(q-down-colp-col)))q=q-down;p-down=q-down;q-down=p;}delete[]cp;returnin;}7、重载函数templateclassTypeostream&operator(ostream&out,LinkMatrixType&a){for(inti=1;i=a.head-row;i++){MatrixNodeType*b=a.Head(i);b=b-right;for(intj=1;j=a.head-col;j++){if(b-row==i&&b-col==j){coutb-data'';b=b-right;}else{cout'0''';}}coutendl;}returnout;}8、重载+=实现求和函数templateclassType//重载符合赋值运算符+=LinkMatrixType&LinkMatrixType::operator+=(constLinkMatrixType&a){MatrixNodeType*pre,*pa,*h,*ah,*p,*tmp;if(head-col!=a.head-col||head-row!=a.head-row)//非同型矩阵不可相加coutThetwomatricearen'tisomorphic!;//throwdomain_error(Thetwomatricearen'tisomorphic!);h=head-next;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-colpa-col)){//若被加矩阵的列标更小，则比较下一个pre=p;p=p-right;}elseif(p==h||p-colpa-col){tmp=newMatrixNodeType(*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、重载+templateclassType//重载加法运算符+LinkMatrixTypeoperator+(constLinkMatrixType&a,constLinkMatrixType&b){LinkMatrixTypec(a);//复制构造函数得到被加矩阵A的一个副本放在矩阵C中c+=b;returnc;}五、调试与测试1、编译环境VisualC++6.02、main函数intmain(){LinkMatrixinta,b,c;cina;coutA矩阵为：\naendl;cinb;coutB矩阵为：\nbendl;c=a+b;coutA+B=\ncendl;system(pause);return0;}3、具体步骤按F5编译，界面出现提示“请输入行数、列数、非零元个数”。输入333表示这个矩阵行数为3，列数为3，非零元个数为3，接着提示“请输入一个非零元三元组row,col,value”。输入111表示第一个三元组的行为1，列为1，值为1然后程序继续提示“输入一个非零元三元组row,col,value”。按要求再依次输入222315则矩阵A输入完成，程序按矩阵格式输出矩阵A程序继续提示“请输入行数、列数、非零元个数”在按上述操作继续输入334112211311333为矩阵B输入，完成后程序输入矩阵B程序同时输出A+B3、结果分析程序提供输入和输出，根据输入的矩阵A和矩阵B，A+B计算结果准确无误。六、使用说明使用本程序简单明了，只需根据提示为稀疏矩阵输入，就可以计算出稀疏矩阵的和。附录2：十字链表实现稀疏矩阵相加源程序软件2班201113040