矩阵转置及相加实验报告.doc

_1、 实验内容和要求1、 稀疏矩阵A,B均采用三元组表示，验证实现矩阵A快速转置算法，设计并验证A,B相加得到矩阵C的算法。（1） 从键盘输入矩阵的行数和列数，随机生成稀疏矩阵。（2） 设计算法将随机生成的稀疏矩阵转换成三元组顺序表示形式存储。（3） 设计算法将快速转置得到的与相加得到的三元组顺序表分别转换成矩阵形式。（4） 输出随机生成的稀疏矩阵A,B及其三元组顺序表、快速转置得到的与相加得到的三元组顺序表及其矩阵形式。2、 实验过程及结果1、 需求分析1、将随机生成的数定义为int型（为方便起见设定范围为-20至20（不含0），可修改），三元组存储的元素分别为非零元的行下标、列下标及该位置的元素值，零元不进行存储。实际上在生成稀疏矩阵时是随机选取一些位置生成非零元然后存入三元组中。2、从键盘输入矩阵的行数和列数后应能输出三元组顺序表及相应矩阵（按行和列排列形式输出）。3、 程序能实现的功能包括：随机产生稀疏矩阵；输出阵列形式的矩阵；输出三元组顺序表；将矩阵快速转置；将两个稀疏矩阵相加生成新的矩阵。 2、 概要设计1、稀疏矩阵的抽象数据类型定义：ADT TSMatrix数据对象：D= aij|i=1,2,m,j=1,2,n;Ai,jElemSet,m和n分别称为矩阵的行数和列数数据关系：R=Row，ColRow=|1im, 1jn-1Col =|1im-1, 1jn基本操作:CreateTSMatrix(&M)操作结果：创建矩阵MPrintTSMatrix(M)初始条件：矩阵M已存在操作结果：输出矩阵M中三元组形式的非零元素PrintTSMatrix1(M)初始条件：矩阵M已存在操作结果：以阵列形式输出矩阵UnZore(M, row, col)初始条件：矩阵M已存在操作结果：若位置(row,col)处存在非零元素，则返回该元素存储在矩阵中的序号TSMatrix_Add(M, N,&Q)初始条件：矩阵M，N已存在操作结果：将矩阵M,N相加得到Q并返回矩阵QFastTransposeSMatrix(M,&N)初始条件：矩阵M已存在操作结果：将矩阵M快速转置得到转置矩阵N并返回ADT TSMatrix； 本程序模块结构 主函数模块void main()初始化迷矩阵；创建矩阵并输出；将矩阵转置并输出；将矩阵相加并输出结果；三、详细设计1、基本数据类型操作typedef int ElemType; typedef struct int i,j; ElemType e; Triple;/数据类型 三元组 typedef struct Triple datamaxsize+1;/矩阵大小 int mu,nu,tu;/ TSMatrix;/矩阵抽象数据类型2、参数设置：#define maxsize 10000/-基本操作的算法描述-Status CreateTSMatrix(TSMatrix *M)/创建一个随机矩阵（data0未用）srand(int)time(NULL);printf(Please Input The Lines And Columns Of The Matrix:n);printf(.(矩阵的期望规格大于4*5(或5*4).n); scanf(M-mu，M-nu); for(m=0;mmu;m+) for(n=0;nnu;n+)kmn=rand()%20;if(kmn=0)if(rand()%2)M-datap.e=rand()%20+1;elseM-datap.e=rand()%20-20;M-datap.i=m+1;M-datap.j=n+1;p+; M-tu=p-1;/p从1开始，非零元个数刚好等于p-1 return OK;void PrintTSMatrix(TSMatrix M)/输出矩阵的三元组顺序表if(M.tu=0)printf(无非零元!n);elseprintf(该矩阵的行数为%d、列数为%d、非零元素个数为%d.n非零元的坐标及值:nn,M.mu,M.nu,M.tu);printf( 行 列 元素值n);for(i=1;i=M.tu;i+)printf(%4d%4d%6dn,M.datai.i,M.datai.j,M.datai.e);printf(n);void PrintTSMatrix1(TSMatrix M)/输出矩阵的阵列形式printf(阵列形式为:n); for(i=1;i=M.mu;i+) for(j=1;j=M.nu;j+) if (ki=i&p-j=j) printf(%4d,p-e); /data0未用，p从data1开始 p+; k+; else printf(%4d,0); printf(n); printf(n);int UnZore(TSMatrix M,int row,int col)while(order=M.tu)if(M.dataorder.i=row&M.dataorder.j=col)/order从1开始return order;order+;return 0;Status TSMatrix_Add(TSMatrix M,TSMatrix N,TSMatrix *Q)/矩阵相加得到新的矩阵，order从1开始if(M.mu=N.mu&M.nu=N.nu)for(row=1;row=M.mu;row+)for(col=1;coldataorder.i=row;Q-dataorder.j=col;Q-dataorder.e=M.dataorder1.e+N.dataorder2.e;order+;else if(order1&(!order2)Q-dataorder.e=M.dataorder1.e;Q-dataorder.i=M.dataorder1.i;Q-dataorder.j=M.dataorder1.j;order+;else if(!order1)&order2)Q-dataorder.e=N.dataorder2.e;Q-dataorder.i=N.dataorder2.i;Q-dataorder.j=N.dataorder2.j;order+;Q-mu=M.mu;Q-nu=M.nu;Q-tu=order-1;return OK;elseprintf(n不是同型矩阵不能进行相加!n);return ERROR;Status FastTransposeSMatrix(TSMatrix M,TSMatrix *N)/采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵N N-mu=M.nu; N-nu=M.mu; N-tu=M.tu; if(N-tu) for(i=1;i=M.nu;+i) numi=0; for(t=1;t=M.tu;+t) +numM.datat.j;/求M中每一列非零元个数 cpot1=1;/求第col列中第一个元素在b.data中的序号 for(i=2;i=M.nu;+i) cpoti=cpoti-1+numi-1; for(p=1;pdataq.i=M.datap.j; N-dataq.j=M.datap.i; N-dataq.e=M.datap.e; +cpoti; return OK; 主函数算法：void main()TSMatrix A,A1,B,C; printf(矩阵A:n); CreateTSMatrix(&A); PrintTSMatrix(A); PrintTSMatrix1(A); printf(由矩阵A转置得矩阵A1.n); FastTransposeSMatrix(A,&A1); PrintTSMatrix(A1); PrintTSMatrix1(A1); printf(矩阵B:n); CreateTSMatrix(&B); PrintTSMatrix(B); PrintTSMatrix1(B); printf(矩阵A加矩阵B得到矩阵C.n); if(TSMatrix_Add(A,B,&C)PrintTSMatrix(C);PrintTSMatrix1(C); 四、调试分析1、三元组顺序表的输出顺序应该是先按行排序再按列排序，即行主序，依次输出。2、生成的非零元应该有正数和负数，选取在-20到20之间的数（不包括0），生成随机数时同时随机生成其正负号，为正数时将rand()%20再加1，避免再产生0，为负数时将rand()%20-20。3、由于稀疏矩阵非零元个数极少，故要求矩阵规格在4*5（或5*4）以上为好，实际上生成非零元时其位置具备随机性，其个数也具备随机性，并不严格小于等于矩阵元素个数的5%，因为控制其随机位置的是通过rand()%20，当该随机数值为0时，将该位置做为非零元位置。开始时采取随机生成位置以便控制非零元个数小于等于矩阵元素个数的5%，但是这样就不便于将非零元按行列次序存储，而是谁先生成就先存储谁，也无法避免出现重复位置的情况。4、实验没有采取二维数组的方法来形成矩阵，而是直接用三元组存储的，在输出时通过for循环控制则可输出实现阵列形式的矩阵。 3、 用户说明与测试结果1、 本程序的运行环境为windows 7（64位）操作系统，执行文件为矩阵.exe；2、 进入演示程序后，即显示对话形式的提示操作过程， （1）提出输入矩阵的大小（2）按enter键输出随机生成的矩阵三元组顺序表和整个矩阵如图所示：（3）程序自动完成第一个矩阵的转置并输出；（4）提示输入矩阵B后，用户输入所需矩阵的行数和列数，然后程序将自动完成两个原始矩阵的相加，若不是同型矩阵则提示无法相加。如图所示：五、附录（源代码及注释）#include #include #include time.h#define maxsize 10000#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1typedef int ElemType;typedef int Status;typedef struct int i,j; ElemType e;Triple;/数据类型 三元组typedef struct Triple datamaxsize+1;/矩阵大小 int mu,nu,tu;/TSMatrix;/矩阵抽象数据类型Status CreateTSMatrix(TSMatrix *M);/创建矩阵void PrintTSMatrix(TSMatrix M);/输出矩阵非零元素void PrintTSMatrix1(TSMatrix M);/以阵列形式输出矩阵int UnZore(TSMatrix M,int row,int col);/判断位置(row,col)是否存在非零元素Status TSMatrix_Add(TSMatrix M,TSMatrix N,TSMatrix *Q);/将矩阵M,N相加得到QStatus FastTransposeSMatrix(TSMatrix M,TSMatrix *N);/快速转置void main() TSMatrix A,A1,B,C; printf(矩阵A:n); CreateTSMatrix(&A); PrintTSMatrix(A); PrintTSMatrix1(A); printf(由矩阵A转置得矩阵A1.n); FastTransposeSMatrix(A,&A1); PrintTSMatrix(A1); PrintTSMatrix1(A1); printf(矩阵B:n); CreateTSMatrix(&B); PrintTSMatrix(B); PrintTSMatrix1(B); printf(矩阵A加矩阵B得到矩阵C.n); if(TSMatrix_Add(A,B,&C)PrintTSMatrix(C);PrintTSMatrix1(C); Status CreateTSMatrix(TSMatrix *M) int m,n,p=1,num;/data0未用，p从1开始;num为非零元个数最大值int k100100; srand(int)time(NULL);printf(Please Input The Lines And Columns Of The Matrix:n);printf(.(矩阵的期望规格大于4*5(或5*4).n); printf(The Line Number:); scanf(%d,&M-mu);printf(The Column Number:); scanf(%d,&M-nu);/*for(m=1;mmu;m+) for(n=1;nnu;n+)kmn=0;num=(m*n)/20;printf(%d,num);for(p=1;pmu+1;n=rand()%M-nu+1;if(rand()%2=1)kmn=rand()%20+1;else if(rand()%2=0)kmn=rand()%20-20;for(m=1;mmu;m+) for(n=1;nnu;n+)if(kmn!=0)M-datap.e=kmn;M-datap.i=m;M-datap.j=n;p+; */ for(m=0;mmu;m+) for(n=0;nnu;n+)kmn=rand()%20;if(kmn=0)if(rand()%2)M-datap.e=rand()%20+1;elseM-datap.e=rand()%20-20;M-datap.i=m+1;M-datap.j=n+1;p+; M-tu=p-1;/p从1开始，刚好等于非零元个数-1 return OK;void PrintTSMatrix(TSMatrix M) int i;if(M.tu=0)printf(无非零元!n);elseprintf(该矩阵的行数为%d、列数为%d、非零元素个数为%d.n非零元的坐标及值:nn,M.mu,M.nu,M.tu);printf( 行 列 元素值n);for(i=1;i=M.tu;i+)printf(%4d%4d%6dn,M.datai.i,M.datai.j,M.datai.e);printf(n);void PrintTSMatrix1(TSMatrix M) int i,j,k=0; Triple *p=M.data;p+;/data0未用，从data1开始printf(阵列形式为:n); for(i=1;i=M.mu;i+) for(j=1;j=M.nu;j+) if (ki=i&p-j=j) printf(%4d,p-e); p+; k+; else printf(%4d,0); printf(n); printf(n);int UnZore(TSMatrix M,int row,int col)int order=1;/data0未用while(order=M.tu)if(M.dataorder.i=row&M.dataorder.j=col)return order;order+;return 0;Status TSMatrix_Add(TSMatrix M,TSMatrix N,TSMatrix *Q)int row,col;int order=1,order1,order2;/data0未用if(M.mu=N.mu&M.nu=N.nu)for(row=1;row=M.mu;row+)for(col=1;coldataorder.i=row;Q-dataorder.j=col;Q-dataorder.e