稀疏矩阵的加减法

《数据结构》课程设计报告书题目：稀疏矩阵的加减法专业：计算机科学与技术学号：学生姓名：指导教师：完成日期：2016-06-202稀疏矩阵的加减法运算1.题目描述假设稀疏矩阵A和B（m行n列）都采用三元组表示，编写程序计算C＝A+B，D=A-B，矩阵C和D也采用三元组表示。编写程序实现，并输出结果。2.预备知识①函数模块调用关系②三元组中抽象数据类型定义③三元组表的赋值操作④三元组和稀疏矩阵之间的转换3.问题分析该程序主要实现以下功能：（1）用三元组存储方式创建稀疏矩阵；（2）用三元组存储方式进行稀疏矩阵的加法；（3）用三元组存储方式进行稀疏矩阵的减法；程序流程和设计思想可以用以下流程图来描述：图1.程序运行流程图输入menu中的编号1.求两个矩阵相加和0.退出系统2.求两个矩阵相减差运行结果并显示出来34.数据结构设计抽象数据类型定义三元组中抽象数据类型定义①typedefstruct//三元组表中元素类型的定义{inti,j;inte;}Triple;②typedefstruct{a)Tripledata[MAX+1];//存放非零元素的数组，行优先b)introw,nu,tu;}Matrix;//三元组表类型名③InitMatrix(A);//初始化④AddMatrix(A,B,C);//矩阵相加⑤SubMatrix(A,B,C);//矩阵相减5.模块设计①voidInitMatrix(Matrix&M)//初始化三元组矩阵{intnum=0;M=*(Matrix*)malloc(sizeof(Matrix));//为三元组申请内存printf(请输入矩阵的行、列和非零元素个数:\n);scanf(%d%d,&M.row,&M.nu);//输入矩阵的行、列和非零元素个数printf(请输入矩阵的非零元值:\n);scanf(%d,&num);getchar();M.tu=num;for(inti=1;i=M.tu;i++)//输入三元组{4printf(请输入第%d个非零元值:\n,i);scanf(%d%d%d,&M.data[i].i,&M.data[i].j,&M.data[i].e);getchar();}}②voidAddMatrix(MatrixA,MatrixB,Matrix&C)//将A，B的值相加放到C上{C=*(Matrix*)malloc(sizeof(Matrix));//为三元组C申请内存inti=1,j=1,k=1;intv;if(A.row!=B.row||A.nu!=B.nu)//判断A、B的行列数是否相等printf(error!\n);else{C.row=A.row;//把A的行数赋给CC.nu=A.nu;//把A的列数赋给Cwhile(i=A.tu&&j=B.tu){if(A.data[i].i==B.data[j].i)//如果三元组A的行下标与B的行下标相等{if(A.data[i].jB.data[j].j)//如果三元组A的列下标小于B的行下标{C.data[k].i=A.data[i].i;//把当前三元组A行下标i插入三元组CC.data[k].j=A.data[i].j;//把当前三元组A下列标j插入三元组CC.data[k].e=A.data[i].e;//把当前三元组A下标i对于的数值e插入三元组Ck++;i++;}elseif(A.data[i].jB.data[j].j)//如果三元组A的列下标大于B的行下标5{C.data[k].i=B.data[j].i;C.data[k].j=B.data[j].j;C.data[k].e=B.data[j].e;k++;j++;}else//如果三元组A的列下标等于B的行下标{v=A.data[i].e+B.data[j].e;if(v!=0){C.data[k].i=A.data[i].i;//把当前三元组A行下标i插入三元组CC.data[k].j=A.data[i].j;//把当前三元组A下列标j插入三元组CC.data[k].e=v;//把三元组A-B下标i对于的数值v插入三元组Ck++;}i++;j++;}}elseif(A.data[i].iB.data[j].i)//如果三元组A的行下标小于B的行下标{C.data[k].i=A.data[i].i;//把当前三元组A行下标i插入三元组CC.data[k].j=A.data[i].j;//把当前三元组A下列标j插入三元组CC.data[k].e=A.data[i].e;//把当前三元组A下标i对于的数值e插入三元组C6k++;i++;}else{C.data[k].i=B.data[j].i;//把当前三元组B下行标i插入三元组CC.data[k].j=B.data[j].j;//把当前三元组B下列标j插入三元组CC.data[k].e=B.data[j].e;//把当前三元组B下标i对于的数值e插入三元组Ck++;j++;}}while(i=A.tu){C.data[k].i=A.data[i].i;//把当前三元组A下行标i插入三元组CC.data[k].j=A.data[i].j;//把当前三元组A下列标j插入三元组CC.data[k].e=A.data[i].e;//把当前三元组A下标i对于的数值e插入三元组Ck++;i++;}while(j=B.tu){C.data[k].i=B.data[j].i;//把当前三元组B下行标i插入三元组CC.data[k].j=B.data[j].j;//把当前三元组B下列标j插入三元组CC.data[k].e=B.data[j].e;//把当前三元组B下标i对于的数值e插入三元组7Ck++;j++;}C.tu=k-1;}}③voidSubMatrix(MatrixA,MatrixB,Matrix&C){C=*(Matrix*)malloc(sizeof(Matrix));inti=1,j=1,k=1;intv;if(A.row!=B.row||A.nu!=B.nu)//判断A、B的行列数是否相等printf(error!\n);else{C.row=A.row;C.nu=A.nu;while(i=A.tu&&j=B.tu){if(A.data[i].i==B.data[j].i){if(A.data[i].jB.data[j].j){C.data[k].i=A.data[i].i;//把当前三元组A下行标i插入三元组CC.data[k].j=A.data[i].j;//把当前三元组A下列标j插入三元组CC.data[k].e=A.data[i].e;//把当前三元组A下标i对于的数值e插入三元组Ck++;8i++;}elseif(A.data[i].jB.data[j].j){C.data[k].i=B.data[j].i;//把当前三元组B下行标i插入三元组CC.data[k].j=B.data[j].j;//把当前三元组B下列标j插入三元组CC.data[k].e=B.data[j].e;//把当前三元组B下标i对于的数值e插入三元组Ck++;j++;}else{v=A.data[i].e-B.data[j].e;if(v!=0){C.data[k].i=A.data[i].i;//把当前三元组A下行标i插入三元组CC.data[k].j=A.data[i].j;//把当前三元组A下列标j插入三元组CC.data[k].e=v;//把三元组A-B下标i对于的数值v插入三元组Ck++;}i++;j++;}}elseif(A.data[i].iB.data[j].i){9C.data[k].i=A.data[i].i;//把当前三元组A下行标i插入三元组CC.data[k].j=A.data[i].j;//把当前三元组A下列标j插入三元组CC.data[k].e=A.data[i].e;//把当前三元组A下标i对于的数值e插入三元组Ck++;i++;}else{C.data[k].i=B.data[j].i;//把当前三元组B下行标i插入三元组CC.data[k].j=B.data[j].j;//把当前三元组B下列标j插入三元组CC.data[k].e=B.data[j].e;//把当前三元组B下标i对于的数值e插入三元组Ck++;j++;}}while(i=A.tu){C.data[k].i=A.data[i].i;//把当前三元组A下行标i插入三元组CC.data[k].j=A.data[i].j;//把当前三元组A下列标j插入三元组CC.data[k].e=A.data[i].e;//把当前三元组A下标i对于的数值e插入三元组Ck++;i++;}while(j=B.tu)10{C.data[k].i=B.data[j].i;//把当前三元组B下行标i插入三元组CC.data[k].j=B.data[j].j;//把当前三元组B下列标j插入三元组CC.data[k].e=B.data[j].e;//把当前三元组B下标i对于的数值e插入三元组Ck++;j++;}C.tu=k-1;}}④voidShowMatrix(MatrixM)//输出三元组矩阵{printf(\n\n矩阵信息:\n);printf(row:%dnu:%dtu:%d\n,M.row,M.nu,M.tu);printf(ijk\n);for(inti=1;i=M.tu;i++){printf(%d,%d,%d,\n,M.data[i].i,M.data[i].j,M.data[i].e);//输出三元组}}⑤intmain(){charx='';cout\t┏****************************************┓endl;cout\t┃请选择相应的功能：┃endl;cout\t┃----------------------------------------┃endl;cout\t┃1.求两个矩阵相加和┃endl;11cout\t┃----------------------------------------┃endl;cout\t┃2.求两个矩阵相减差┃endl;cout\t┃----------------------------------------┃endl;cout\t┃0.退出系统┃endl;cout\t┗━━━━━━━━━━━━━━━━━━━━┛endl;intflag=1;while(flag){printf(请选择相应的功能:);ints;scanf(%d,&s);getchar();//输入menu编号switch(s){case1:{MatrixA,B,C;printf(请输入第一个矩阵：\n);InitMatrix(A);//初始化printf(请输入第二个矩阵：\n);InitMatrix(B);//初始化printf(矩阵的和为:\n);AddMatrix(A,B,C);ShowMatrix(C);//输出三元组表break;}case2:{MatrixA,B,C;printf(请输入第一个矩阵：\n);InitMatrix(A);//初始化printf(请输入第二个矩阵：\n);12InitMatrix(B);//初始化printf(矩阵的差为:\n);SubMatrix(A,B,C);ShowMatrix(C);//输出三元组表break;}case0:flag=0;break;}}}6.运行界面及运算结果图5-113图5-2图5-314图5-415附录：16#includestdio.h#includestdlib.h#includeiostreamusingnamespacestd;#defineMAX1000//三元组typedefstruct