数据结构实验(4)数组.doc

计算机系数据结构实验报告（4）实验目的：深入研究数组的存储表示和实现技术，着重掌握对稀疏矩阵的表示方法及其运算的实现。问题描述：稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行存储和计算可以大大节省存储空间，提高效率。通过对稀疏矩阵的存储表示，实现矩阵的基本操作。实验要求：文法是一个四元1要求矩阵的输入形式采用三元组表示，以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。2设计矩阵的逆置算法，实现矩阵的逆置。3实现两个稀疏矩阵的相加、相减和相乘等运算。4要求运算结果的矩阵则以通常的阵列形式出现。算法分析：（1） 矩阵的输入采用的是三元组的形式，这样直接输入的话输入步骤显得繁琐（特别是非零元个数较多的情况下），而且一旦输入有误，之前的输入也得重现，因此，为了简化用户端的输入步骤并增加其容错性，可考虑先在一个缓冲区里将数据全部输入，然后由程序自动输入矩阵，在这里可以用一个文本文档存储数据，然后程序打开文本文档，完成输入。（2） 由于文本文档为ASCII文件，读入的是字符，要先转换成整型，并将处理后的数据入栈，最后出栈完成输入。具体步骤与实验2的表达式求值类似。（3） 在输入之后，行逻辑链接信息并未完成，此处使用Gain_rpos()，要求在已知三元组的情况下求出各行的rpos利用每行非零元个数与第一行的rpos=1及其递归来完成。（4） 向着满足用户界面友好方向考虑，可以在输入后，即刻输出矩阵的阵列形式。其中输出函数Output()，使用两层for循环遍历每个元素，判断某行某列元素值非零则输出其值，否则输出为零。（5） 本程序要实现的矩阵运算包括转置、加减、相乘。转置算法采用快速转置法，矩阵的相加减使用双层for循环和累加器。（6） 使用goto语句完成程序的循环。实验内容和过程：源程序：#include#include#include#includeusing namespace std;/-稀疏矩阵的三元组顺序表存储表示-#define MAX 12500#define MAXR 110typedef int ElemType;typedef struct int i,j;ElemType e;Triple;typedef struct int mu,nu,tu;Triple dataMAX+1;int rposMAXR+1;RLSMatrix; int In(char ch) /定义辅助函数：判断是否为数字字符 if(ch=0&ch=9) return 1; else return 0;FILE* input(RLSMatrix &M,FILE *fp) /以三元组形式输入一个矩阵，利用文件类型指针读取文本文档内的数据 char ch,flag= ;int a,b,k,num=0; stack status; 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);else a=(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);else b=(int)ch-48;status.push(b); +num;flag=ch;num=0;M.datak.e=status.top(); status.pop();M.datak.j=status.top(); status.pop();M.datak.i=status.top(); status.pop();return fp; /返回当前指针的值，以便下个矩阵的输入 int Input(RLSMatrix &M,RLSMatrix &N) /完成本程序两个矩阵的输入 FILE *fp,*FP;if(fp=fopen(E:矩阵数据.txt,r)=NULL) /在文本文档中打开文件，读取其中的字符做相应处理后读入矩阵中 coutfile can not open!;exit(0); FP=input(M,fp); input(N,FP); fclose(fp); /关闭文件 fp=FP=NULL;int Gain_rpos(RLSMatrix &T) /辅助函数：获得矩阵中第row行中第一个非零元在data中的位置 int arow,m,num100; for(arow=1;arow=T.mu;+arow) numarow=0; for(m=1;m=T.tu;+m) +numT.datam.i; /获得每行非零元个数 T.rpos1=1;for(arow=2;arow=T.mu;+arow) T.rposarow=T.rposarow-1+numarow-1;int Output(RLSMatrix T) /以阵列形式输出矩阵 int arow,ccol,num=0;for(arow=1;arow=T.mu;+arow)for (ccol=1;ccol=T.nu;+ccol)if(T.dataT.rposarow.j=ccol&T.dataT.rposarow.i=arow) coutsetw(10)T.dataT.rposarow.e; +T.rposarow; else coutsetw(10)num;coutendl;int TransposeSMatrix(RLSMatrix T,RLSMatrix &Q) /矩阵的转置 int p,q,t,ccol,cpot100,num100;Q.mu=T.nu; Q.nu=T.mu; Q.tu=T.tu;if(T.tu)for(ccol=1;ccol=T.nu;+ccol) numccol=0;for(t=1;t=T.tu;+t) +numT.datat.j;cpot1=1;for(ccol=2;ccol=T.nu;+ccol) cpotccol=cpotccol-1+numccol-1;for(p=1;p=T.tu;+p)ccol=T.datap.i; q=cpotccol;Q.dataq.i=T.datap.j; Q.dataq.j=T.datap.i;Q.dataq.e=T.datap.e; +cpotccol; Gain_rpos(Q); int PlusSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q) /矩阵相加 int arow,ccol,ctemp100,num;if(M.mu!=N.mu&M.nu!=N.nu) cout两矩阵无法相加; return 0;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)ctempnum=0; for(ccol=1;ccolMAX) return 0;Q.dataQ.tu.i=arow;Q.dataQ.tu.j=ccol;Q.dataQ.tu.e=ctempccol; Gain_rpos(Q);int Subtraction(RLSMatrix M,RLSMatrix N,RLSMatrix &Q) /矩阵相减 int arow,ccol,ctemp100,num;if(M.mu!=N.mu&M.nu!=N.nu) cout两矩阵无法相减; return 0;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)ctempnum=0; for(ccol=1;ccolMAX) return 0;Q.dataQ.tu.i=arow;Q.dataQ.tu.j=ccol;Q.dataQ.tu.e=ctempccol; Gain_rpos(Q);int MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)/矩阵相乘 int arow,brow,ccol,ctemp100,tp,p,q,t,num;if(M.nu!=N.mu) cout两矩阵无法相乘; return 0;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)ctempnum=0;Q.rposarow=Q.tu+1;if(arowM.mu) tp=M.rposarow+1;else tp=M.tu+1;for(p=M.rposarow;ptp;+p)brow=M.datap.j;if(browN.mu) t=N.rposbrow+1;else t=N.tu+1;for(q=N.rposbrow;qt;+q)ccol=N.dataq.j;ctempccol+=M.datap.e*N.dataq.e;for(ccol=1;ccolMAX) return 0;Q.dataQ.tu.i=arow;Q.dataQ.tu.j=ccol;Q.dataQ.tu.e=ctempccol; int main() RLSMatrix M,N,Q;char ch,CH,again;cout请在E盘中新建一个文本文档，文件名为“矩阵数据”endl;cout在该文档中以此格式输入矩阵M和N：endl矩阵行数 矩阵列数 矩阵非零元个数endl之后每行输入一个三元组：endl行数 列数 值 endl; cout保存该文件 完成上述步骤后按任意键继续endl; /提示 ch=getch(); /无回显读入字符 Input(M,N); /输入 Gain_rpos(M);Gain_rpos(N); coutM矩阵：endl; Output(M); coutN矩阵：endl; Output(N);AGAIN:cout请选择运算方式：endl;coutA M矩阵转置setw(10) B N矩阵转置setw(10) C 两矩阵相加setw(10) D 两矩阵相减setw(10) E 两矩阵相乘CH;switch(CH)caseA: TransposeSMatrix(M,Q); break;caseB: TransposeSMatrix(N,Q); break;caseC: PlusSMatrix(M,N,Q); break;caseD: Subtraction(M,N,Q); break;caseE: MultSMatrix(M,N,Q); break; default: goto AGAIN; cout运算结果：endl;Output(Q);coutContinue? Y or N?again;if(again!=N) goto AGAIN; 实验结果：结果分析：从界面来看，虽然输入部分简单，但由于提示部分太多，整个界面显得不美观、整齐，如果能使用一些关于屏幕输出方面的函数，应该可以弥补不足。总结和感想： 在设