数据结构课程设计(稀疏矩阵运算器)

可编辑版/实习报告题目：编制一个稀疏矩阵运算器的程序班级：智能科学与技术系姓名：尤雅萍学号：完成日期：2009-11-27一•需求分析1.[问题描述]稀疏矩阵是指那些多数元素为零的矩阵。利用"稀疏"特点进行存储和计算可以大大节省存储空间,提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2.[基本要求]以"带行逻辑链接信息"的三元组顺序表示稀疏矩阵,实现两个矩阵相加,相减和相乘的运算,稀疏矩阵的输入形式采用三元组表示,而运算结果的矩阵则以通常的阵列形式列出。3.[测试数据]〔110000001000009+00-1=008-10010-300-3〔21000010009-0-1=010-101-3-23〔34-30013000-600008042080000100*010=0100000701000000004.[实现提示]〔1首先应输入矩阵的行数和列数,并判别给出的两个矩阵的行,列数对于所要求作的运算是否匹配,可设矩阵的行数和列数均不超过20。〔2程序可以对三元组的输入顺序加以限制,例如,按行优先。〔3在用三元组表示稀疏矩阵时,相加或相减所得结果矩阵应该另生成,乘积矩阵也可用二维数组存放。二•概要设计设定数组的抽象数据类型定义：ADTSparseMatrix{数据对象：D={m和n分别称为矩阵的行数和列数}数据关系：R={Row,Col}Row={<ai,j,ai,j+1>|1<=i<=m,a<=j<=n-1}Col={<ai,j,ai+1,j>|1<=i<=m-1,a<=j<=n}基本操作：CreateSMatrix<&M>;操作结果：创建稀疏矩阵M。DestorySMatrix<&M>;初始条件：稀疏矩阵M存在。操作结果：销毁稀疏矩阵M。PrintSMatrix<M>；初始条件：稀疏矩阵M存在。操作结果:输出稀疏矩阵M。CopySMatrix<M,&T>；初始条件：稀疏矩阵M存在。操作结果：由稀疏矩阵M复制得到T。AddSMatrix<M,N,&Q>；初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的和Q=M+N。SubtSMatrix<M,N,&Q>;初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的差Q=M-N。MultSMatrix<M,N,&Q>;初始条件：稀疏矩阵M的列数等于N的行数。操作结果：求稀疏矩阵乘积Q=M*N。TransposeSMatrix<M,&T>;初始条件：稀疏矩阵M存在。操作结果：求稀疏矩阵M的转置矩阵T。}ADTSparseMatrix2．本程序包含的模块〔1voidmain<>{初始化；do{接收命令；处理命令；}while<命令！=退出>；}〔2稀疏矩阵模块——实现稀疏矩阵抽象数据类型。〔3稀疏矩阵求值模块——实现稀疏矩阵求值抽象数据类型。稀疏矩阵求值模块包括：矩阵相加模块AddRLSMatrix<>；矩阵相减模块SubRLSMatrix<>；相乘模块MulTSMatrix<>；三•详细设计typedefstruct//稀疏矩阵的三元组顺序表存储表示 inti,j;//该非零元的行下标和列下标 inte;}Triple;typedefstruct{ Tripledata[MAXSIZE+1];//非零元三元组表,data[0]未用 intrpos[MAXRC+1];//各行第一个非零元的位置表 intmu,nu,tu;//矩阵的行数列数和非零元的个数}RLSMatrix;VoidCreateSMatrix<RLSMatrix*T>//输入创建稀疏矩阵{ intk; printf<"\n请输入矩阵行数、列数及非零元个数:">; scanf<"%d%d%d",&T->mu,&T->nu,&T->tu>; printf<"\n">; if<T->tu>MAXSIZE||T->mu>21> { printf<"非零个数超出定义范围！出错！">; exit<0>; } for<k=1;k<=T->tu;k++> { printf<"请输入第%d个非零元素的行数,列数及其值:",k>; scanf<"%d%d%d",&T->data[k].i,&T->data[k].j,&T->data[k].e>; }}voidAddRLSMatrix<RLSMatrixM,RLSMatrixN,RLSMatrix*Q>//稀疏矩阵相加{ intp,q,k=1; if<M.mu!=N.mu||M.nu!=N.nu> { printf<"你的输入不满足矩阵相加的条件!\n">; exit<1>; } Q->mu=M.mu;Q->nu=M.nu; for<p=1,q=1;p<=M.tu&&q<=N.tu;> { if<M.data[p].i==N.data[q].i> { if<M.data[p].j==N.data[q].j> { Q->data[k].i=M.data[p].i; Q->data[k].j=M.data[p].j; Q->data[k].e=M.data[p].e+N.data[q].e; p++;q++;k++; } elseif<M.data[p].j<N.data[q].j> { Q->data[k].i=M.data[p].i; Q->data[k].j=M.data[p].j; Q->data[k].e=M.data[p].e; k++;p++; } elseif<M.data[p].j>N.data[q].j> { Q->data[k].i=N.data[q].i; Q->data[k].j=N.data[q].j; Q->data[k].e=N.data[q].e; k++;p++; } } elseif<M.data[p].i<N.data[q].i> { Q->data[k].i=M.data[p].i; Q->data[k].j=M.data[p].j; Q->data[k].e=M.data[p].e; k++;p++; } elseif<M.data[p].i>N.data[q].i> { Q->data[k].i=N.data[q].i; Q->data[k].j=N.data[q].j; Q->data[k].e=N.data[q].e; k++;q++; } } if<p!=M.tu+1> for<;p<=M.tu;p++> { Q->data[k].i=M.data[p].i; Q->data[k].j=M.data[p].j;Q->data[k].e=M.data[p].e; k++; } if<q!=N.tu+1> for<;q<=N.tu;q++> { Q->data[k].i=N.data[q].i; Q->data[k].j=N.data[q].j; Q->data[k].e=N.data[q].e; k++; }}voidSubRLSMatrix<RLSMatrixM,RLSMatrixN,RLSMatrix*Q>//稀疏矩阵相减{ intp,q,k=1; if<M.mu!=N.mu||M.nu!=N.nu> { printf<"你的输入不满足矩阵相减的条件!\n">; exit<1>; } Q->mu=M.mu;Q->nu=M.nu; for<p=1,q=1;p<=M.tu&&q<=N.tu;> { if<M.data[p].i==N.data[q].i> { if<M.data[p].j==N.data[q].j> { Q->data[k].i=M.data[p].i; Q->data[k].j=M.data[p].j; Q->data[k].e=M.data[p].e-N.data[q].e; p++;q++;k++; } elseif<M.data[p].j<N.data[q].j> { Q->data[k].i=M.data[p].i; Q->data[k].j=M.data[p].j; Q->data[k].e=M.data[p].e; k++;p++; } elseif<M.data[p].j>N.data[q].j> { Q->data[k].i=N.data[q].i; Q->data[k].j=N.data[q].j; Q->data[k].e=-N.data[q].e; k++;p++; } } elseif<M.data[p].i<N.data[q].i> { Q->data[k].i=M.data[p].i; Q->data[k].j=M.data[p].j; Q->data[k].e=M.data[p].e; k++;p++; } elseif<M.data[p].i>N.data[q].i> { Q->data[k].i=N.data[q].i; Q->data[k].j=N.data[q].j; Q->data[k].e=-N.data[q].e; k++;q++; } } if<p!=M.tu+1> for<;p<=M.tu;p++> { Q->data[k].i=M.data[p].i; Q->data[k].j=M.data[p].j;Q->data[k].e=M.data[p].e; k++; } if<q!=N.tu+1> for<;q<=N.tu;q++> { Q->data[k].i=N.data[q].i; Q->data[k].j=N.data[q].j; Q->data[k].e=-N.data[q].e; k++; }}intMulTSMatrix<RLSMatrixM,RLSMatrixN,RLSMatrix*Q>//稀疏矩阵相乘{ intccol=0,tp,brow,t,arow,p,q,i; intctemp[MAXSIZE+1]; if<M.nu!=N.mu> { printf<"你的输入不满足矩阵相乘的条件!\n">; return0; } Q->mu=M.mu; Q->nu=N.nu; Q->tu=0; if<M.tu*N.tu!=0> { for<arow=1;arow<=M.mu;++arow> { for<i=1;i<=N.nu;i++> ctemp[i]=0; Q->rpos[arow]=Q->tu+1; if<arow<M.mu>tp=M.rpos[arow+1]; elsetp=M.tu+1; for<p=M.rpos[arow];p<tp;++p> { brow=M.data[p].j; if<brow<N.mu>t=N.rpos[brow+1]; elset=N.tu+1; for<q=N.rpos[brow];q<t;++q> { ccol=N.data[q].j; ctemp[ccol]+=M.data[p].e*N.data[q].e; } } for<ccol=1;ccol<=Q->nu;++ccol> { if<ctemp[ccol]> { if<++Q->tu>MAXSIZE>return0; Q->data[Q->tu].i=arow; Q->data[Q->tu].j=ccol; Q->data[Q->tu].e=ctemp[ccol]; } } } } return1;} voidPrintSMatrix<RLSMatrixQ>//输出稀疏矩阵{ intk=1,row,line; printf<"\n运算结果:">; if<Q.tu==0>printf<"0">; else { for<row=1;row<=Q.mu;row++> { for<line=1;line<=Q.nu;line++> { if<Q.data[k].i==row&&Q.data[k].j==line>printf<"%d",Q.data[k++].e>; elseprintf<"0">; } printf<"\n\t">; } }}voidmain<>{ RLSMatrixM,N,Q; inti; do {printf<"\t\t***************************\n">; printf<"\t\t稀疏矩阵运算器\n">; printf<"\t\t***************************\n\n">; printf<"\t\t1.矩阵相加\n\n">; printf<"\t\t2.矩阵相减\n\n">; printf<"\t\t3.矩阵相乘\n\n">; printf<"\t\t4.退出\n\n">; printf<"\t\t请选择:">; scanf<"%d",&i>; if<i==4