数据结构稀疏矩阵运算器

1、实习4 4.1稀疏矩阵运算器实习报告题目：设计一个能实现稀疏矩阵基本运算的运算器。班级：软件工程11-1 姓名：张艳艳 学号： 完成日期2012-11-23一、 需求分析1.本演示程序中，以“带行逻辑的链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的表示以阵列形式列出。首先应输入矩阵的行数和列数，并判断给出的两个矩阵的行和列对于所要求的运算是否相匹配。（矩阵的行数和列数均不超过20） 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（

2、滤去输入数据中的非法字符）和运算结果显示在其后。3.程序执行的命令包括：（1）构造链表；（2）输入数据；（3）数据处理；（4）结束4.测试数据（1）10 0 0 0 0 0 10 0 0 0 0 9 + 0 0 -1 = 0 0 8-1 0 0 1 0 -3 0 0 -3（2）10 0 0 0 10 0 0 9 - 0 -1 = 0 10 -1 0 1 -3 -2 3 3 0 0（3）4 -3 0 0 1 4 2 0 0 -60 0 0 0 8 0 * 0 1 0 = 800 0 0 1 0 0 1 0 0 010 0 0 0 0 70 0 0 0 000二、 概要设计包含的头文件#inclu

3、de #include #include 定义结构体以实现矩阵的生成typedef struct int i,j; /非零元的行下标和列下标 ElemType e; /非零元的值 Triple; typedef struct Triple dataMAXSIZE+1; int rposMAXRC+1; /各行第一个非零元在三元组的位置表 int hs,ls,fls; TSMatrix,*Matrix; void Creat(TSMatrix &M) /矩阵的生成算法void Add(TSMatrix A,TSMatrix B,TSMatrix &C,int n) /矩阵的相加与相减运算以n=1

4、或-1来调节加或减int Multiplication(TSMatrix A,TSMatrix B,TSMatrix &Q) /实现矩阵的相乘运算void Turn(TSMatrix *a,TSMatrix *b) /实现矩阵的转置三、 详细设计#include #include #include #define MAXSIZE 40 /假设非零元素个数的最大值为40 #define MAXRC 20/假设矩阵的最大行数为20 typedef int ElemType; typedef struct int i,j; /非零元的行下标和列下标 ElemType e; /非零元的值 Triple

5、; typedef struct Triple dataMAXSIZE+1; int rposMAXRC+1; /各行第一个非零元在三元组的位置表 int hs,ls,fls; TSMatrix,*Matrix; void Creat(TSMatrix &M) /矩阵的生成算法 int i,k; for(i=1;i=MAXRC+1;i+) M.rposi=0; printf(请输入矩阵的行数、列数和非零元个数(以空格隔开):); scanf(%d %d %d,&M.hs,&M.ls,&M.fls); for(i=1;i=M.fls;i+)printf(请用三元组形式输入矩阵的元素(行 列 非零

6、元素):); scanf(%d %d %d,&M.datai.i,&M.datai.j,&M.datai.e); for(i=1,k=1;i=M.hs;i+) M.rposi=k; while(M.datak.i=i & k=M.fls)k+; void Add(TSMatrix A,TSMatrix B,TSMatrix &C,int n) /矩阵的相加与相减运算以n=1或-1来调节加或减 int a,b,temp,l; C.hs=A.hs;C.ls=A.ls;a=b=l=1;while(a=A.fls & b=B.fls) if(A.dataa.i=B.datab.i) if(A.data

7、a.jB.datab.j)C.datal=B.datab;C.datal+.e=n*B.datab+.e;elsetemp=A.dataa.e+n*B.datab.e; if(temp)C.datal=A.dataa; C.datal.e=temp; l+; a+;b+; else if(A.dataa.iB.datab.i)C.datal+=A.dataa+; else C.datal=B.datab;C.datal+.e=n*B.datab+.e; while(a=A.fls)C.datal+=A.dataa+; while(b=B.fls)C.datal=B.datab;C.datal+

8、.e=n*B.datab+.e; C.fls=l-1; int Multiplication(TSMatrix A,TSMatrix B,TSMatrix &Q) /实现矩阵的相乘运算 int arow,brow,ccol,tp,p,q,t; int ctempMAXRC+1; if(A.ls!=B.hs)return 0; Q.hs=A.hs;Q.ls=B.ls;Q.fls=0;if(A.fls*B.fls) for(arow=1;arow=A.hs;arow+) for(ccol=1;ccol=Q.ls;ccol+) ctempccol=0; Q.rposarow=Q.fls+1; if(

9、arowA.hs)tp=A.rposarow+1;elsetp=A.fls+1;for(p=A.rposarow;ptp;p+)brow=A.datap.j;if(browB.hs)t=B.rposbrow+1;elset=B.fls+1;for(q=B.rposbrow;qt;q+)ccol=B.dataq.j;ctempccol+=A.datap.e*B.dataq.e; for(ccol=1;ccolMAXSIZE)return 0; Q.dataQ.fls.i=arow; Q.dataQ.fls.j=ccol; Q.dataQ.fls.e=ctempccol; return 1; vo

10、id Print_SMatrix(TSMatrix M) /矩阵的输出 int k,l,n; Matrix p; p=&M; for(k=1,n=1;khs;k+) for(l=1;lls;l+) if(p-datan.i=k & p-datan.j=l) printf(%5d,p-datan.e); n+; else printf(%5d,0); printf(n); printf(n); void Turn(TSMatrix *a,TSMatrix *b) /实现矩阵的转置int q,col,p;b-hs=a-ls;b-ls=a-hs;b-fls=a-fls;if(b-fls)q=1;fo

11、r(col=1;colls;col+) for(p=1;pfls;p+)if(a-datap.j=col)b-dataq.i=a-datap.j;b-dataq.j=a-datap.i;b-dataq.e=a-datap.e;+q;void Destory_SMatrix(TSMatrix &M) M.hs=M.ls=M.fls=0; void main() TSMatrix A,B,C; TSMatrix *p=&A,*q=&B;int flag,n; while(1) system(cls);printf(nnn); printf( t-欢迎使用稀疏矩阵运算器-nn); printf(t*

12、n); printf(t* * 稀疏矩阵的加、减、转、乘 * *n);printf(t*n); printf(t* 1、稀疏矩阵的加法 * n); printf(t* 2、稀疏矩阵的减法 *n); printf(t* 3、稀疏矩阵的转置 *n); printf(t* 4、稀疏矩阵的乘法 *n); printf(t* 5、退出该应用程序 *n); printf(t*n);printf(输入要进行的项目的编号:); scanf(%d,&flag); if(flag=5)break; Creat(A); printf(矩阵A:n); Print_SMatrix(A); switch(flag) ca

13、se 1:Creat(B);n=1; printf(矩阵B:n); Print_SMatrix(B); if(A.hs=B.hs & A.ls=B.ls) printf(A+B:n); Add(A,B,C,n);Print_SMatrix(C); else printf(错误!行列不一致n); break; case 2: Creat(B);n=-1; printf(矩阵B:n); Print_SMatrix(B); if(A.hs=B.hs & A.ls=B.ls) printf(A-B:n); Add(A,B,C,n); Print_SMatrix(C); else printf(错误!行

14、列不一致n); break; case 3: printf(A-B:n); Turn(p,q); Print_SMatrix(B);break; case 4:Creat(B); printf(矩阵B:n); Print_SMatrix(B); printf(A*B:n); n=Multiplication(A,B,C); if(!n)printf(错误!行列不匹配n); elsePrint_SMatrix(C);break; default:printf(输入错误!n);break; Destory_SMatrix(A); Destory_SMatrix(B); Destory_SMatrix(C); getchar();getchar();printf(nttt *程序已经退出*n);getchar();四、调试分析 本程序中主要应用了函数的调用，大大提高了程序的可读性。在编程的过程中，对于转置与相乘，由于原先C语言课本上又源代码，并没有费多大力气。但是对于矩阵的加减，刚开