数据结构实验(4)数组

-1-计算机系数据结构实验报告（4）实验目的：深入研究数组的存储表示和实现技术，着重掌握对稀疏矩阵的表示方法及其运算的实现。问题描述：稀疏矩阵是指那些多数元素为零的矩阵。利用‘稀疏’特点进行存储和计算可以大大节省存储空间，提高效率。通过对稀疏矩阵的存储表示，实现矩阵的基本操作。实验要求：文法是一个四元1．要求矩阵的输入形式采用三元组表示，以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。2．设计矩阵的逆置算法，实现矩阵的逆置。3．实现两个稀疏矩阵的相加、相减和相乘等运算。4．要求运算结果的矩阵则以通常的阵列形式出现。算法分析：（1）矩阵的输入采用的是三元组的形式，这样直接输入的话输入步骤显得繁琐（特别是非零元个数较多的情况下），而且一旦输入有误，之前的输入也得重现，因此，为了简化用户端的输入步骤并增加其容错性，可考虑先在一个缓冲区里将数据全部输入，然后由程序自动输入矩阵，在这里可以用一个文本文档存储数据，然后程序打开文本文档，完成输入。（2）由于文本文档为ASCII文件，读入的是字符，要先转换成整型，并将处理后的数据入栈，最后出栈完成输入。具体步骤与实验2的表达式求值类似。（3）在输入之后，行逻辑链接信息并未完成，此处使用Gain_rpos()，要求在已知三元组的情况下求出各行的rpos利用每行非零元个数与第一行的rpos=1及其递归来完成。（4）向着满足用户界面友好方向考虑，可以在输入后，即刻输出矩阵的阵列形式。其中输出函数Output()，使用两层for循环遍历每个元素，判断某行某列元素值非零则输出其值，否则输出为零。（5）本程序要实现的矩阵运算包括转置、加减、相乘。转置算法采用快速转置法，矩阵的相加减使用双层for循环和累加器。（6）使用goto语句完成程序的循环。实验内容和过程：源程序：#includeiostream#includeiomanip#includestack#includeconio.husingnamespacestd;//-----稀疏矩阵的三元组顺序表存储表示-----#defineMAX12500#defineMAXR110typedefintElemType;typedefstruct{inti,j;ElemTypee;}Triple;typedefstruct{intmu,nu,tu;Tripledata[MAX+1];-2-intrpos[MAXR+1];}RLSMatrix;intIn(charch)//定义辅助函数：判断是否为数字字符{if(ch='0'&&ch='9')return1;elsereturn0;}FILE*input(RLSMatrix&M,FILE*fp)//以三元组形式输入一个矩阵，利用文件类型指针读取文本文档内的数据{charch,flag='';inta,b,k,num=0;stackintstatus;while(num3||In(flag)==1)//每次读取一个字符，并将字符型转换成整型{ch=fgetc(fp);if(!In(ch)){flag=ch;continue;}if(In(flag)==1){status.pop();--num;a=a*10+((int)ch-48);}elsea=(int)ch-48;status.push(a);//入栈++num;flag=ch;}M.tu=status.top();status.pop();//出栈并输入行数，列数，非零元个数M.nu=status.top();status.pop();M.mu=status.top();status.pop();num=0;for(k=1;k=M.tu;++k)//完成非零元的输入{while(num3||In(flag)==1){ch=fgetc(fp);if(!In(ch)){flag=ch;continue;}if(In(flag)==1){status.pop();--num;b=b*10+((int)ch-48);}elseb=(int)ch-48;status.push(b);++num;flag=ch;}num=0;M.data[k].e=status.top();status.pop();M.data[k].j=status.top();status.pop();M.data[k].i=status.top();status.pop();}-3-returnfp;//返回当前指针的值，以便下个矩阵的输入}intInput(RLSMatrix&M,RLSMatrix&N)//完成本程序两个矩阵的输入{FILE*fp,*FP;if((fp=fopen(E:\\矩阵数据.txt,r))==NULL)//在文本文档中打开文件，读取其中的字符做相应处理后读入矩阵中{coutfilecannotopen!;exit(0);}FP=input(M,fp);input(N,FP);fclose(fp);//关闭文件fp=FP=NULL;}intGain_rpos(RLSMatrix&T)//辅助函数：获得矩阵中第row行中第一个非零元在data中的位置{intarow,m,num[100];for(arow=1;arow=T.mu;++arow)num[arow]=0;for(m=1;m=T.tu;++m)++num[T.data[m].i];//获得每行非零元个数T.rpos[1]=1;for(arow=2;arow=T.mu;++arow)T.rpos[arow]=T.rpos[arow-1]+num[arow-1];}intOutput(RLSMatrixT)//以阵列形式输出矩阵{intarow,ccol,num=0;for(arow=1;arow=T.mu;++arow){for(ccol=1;ccol=T.nu;++ccol){if(T.data[T.rpos[arow]].j==ccol&&T.data[T.rpos[arow]].i==arow){coutsetw(10)T.data[T.rpos[arow]].e;++T.rpos[arow];}elsecoutsetw(10)num;}coutendl;}}intTransposeSMatrix(RLSMatrixT,RLSMatrix&Q)//矩阵的转置{intp,q,t,ccol,cpot[100],num[100];Q.mu=T.nu;Q.nu=T.mu;Q.tu=T.tu;if(T.tu){for(ccol=1;ccol=T.nu;++ccol)num[ccol]=0;for(t=1;t=T.tu;++t)++num[T.data[t].j];cpot[1]=1;for(ccol=2;ccol=T.nu;++ccol)cpot[ccol]=cpot[ccol-1]+num[ccol-1];for(p=1;p=T.tu;++p){ccol=T.data[p].i;q=cpot[ccol];-4-Q.data[q].i=T.data[p].j;Q.data[q].j=T.data[p].i;Q.data[q].e=T.data[p].e;++cpot[ccol];}}Gain_rpos(Q);}intPlusSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q)//矩阵相加{intarow,ccol,ctemp[100],num;if(M.mu!=N.mu&&M.nu!=N.nu){cout两矩阵无法相加;return0;}Q.mu=M.mu;Q.nu=M.nu;Q.tu=0;for(arow=1;arow=Q.mu;++arow){for(num=1;num=Q.nu;++num){ctemp[num]=0;}for(ccol=1;ccol=Q.nu;++ccol){if(M.data[M.rpos[arow]].j==ccol&&M.data[M.rpos[arow]].i==arow){ctemp[ccol]+=M.data[M.rpos[arow]].e;++M.rpos[arow];}if(N.data[N.rpos[arow]].j==ccol&&N.data[N.rpos[arow]].i==arow){ctemp[ccol]+=N.data[N.rpos[arow]].e;++N.rpos[arow];}if(ctemp[ccol]){if(++Q.tuMAX)return0;Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;Q.data[Q.tu].e=ctemp[ccol];}}}Gain_rpos(Q);}intSubtraction(RLSMatrixM,RLSMatrixN,RLSMatrix&Q)//矩阵相减{intarow,ccol,ctemp[100],num;if(M.mu!=N.mu&&M.nu!=N.nu){cout两矩阵无法相减;return0;}Q.mu=M.mu;Q.nu=M.nu;Q.tu=0;for(arow=1;arow=Q.mu;++arow){for(num=1;num=Q.nu;++num){ctemp[num]=0;}for(ccol=1;ccol=Q.nu;++ccol){if(M.data[M.rpos[arow]].j==ccol&&M.data[M.rpos[arow]].i==arow){ctemp[ccol]+=M.data[M.rpos[arow]].e;++M.rpos[arow];}if(N.data[N.rpos[arow]].j==ccol&&N.data[N.rpos[arow]].i==arow){ctemp[ccol]+=(N.data[N.rpos[arow]].e)*(-1);++N.rpos[arow];}if(ctemp[ccol]){if(++Q.tuMAX)return0;-5-Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;Q.data[Q.tu].e=ctemp[ccol];}}}Gain_rpos(Q);}intMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q)//矩阵相乘{intarow,brow,ccol,ctemp[100],tp,p,q,t,num;if(M.nu!=N.mu){cout两矩阵无法相乘;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(num=0;num=Q.nu;++num){ctemp[num]=0;}Q.rpos[arow]=Q.tu+1;if(arowM.mu)tp=M.rpos[arow+1];else{tp=M.tu+1;}for(p=M.rpos[arow];ptp;++p){brow=M.data[p].j;if(browN.mu)t=N.rpos[brow+1];else{t=N.tu+1;}for(q=N.rpos[brow];qt;++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.tuMAX)return0;Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;Q.data[Q.tu].e=ctemp[ccol];}}}}intmain(){RLSMatrixM,N,Q;charch,CH,again;cout请在E盘中新建一个文本文档，文件名为“矩阵数据”en