数据结构实验报告稀疏矩阵运算.doc

教学单位计算机科学与技术 学生学号012301714315 数据结构 课程设计报告书题目稀疏矩阵运算器 学生姓名秦豹专业名称软件工程指导教师李志敏实验目的：深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性。需要分析：稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。要求以带“行逻辑链接信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。输入以三元组表示，输出以通常的阵列形式列出。软件平台：Windows 2000，Visual C 6.0或WINTC概要设计：ADT Array 数据对象: D = aij | 0ib1-1, 0 jb2-1数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2 基本操作：CreateSMatrix(&M); /操作结果:创建稀疏矩阵M.Print SMatrix(M); /初始化条件: 稀疏矩阵M存在./操作结果:输出稀疏矩阵M.AddSMatrix(M,N,&Q);/初始化条件: 稀疏矩阵M与N的行数和列数对应相等./操作结果:求稀疏矩阵的和Q=M+N.SubSMatrix(M,N,&Q);/初始化条件: 稀疏矩阵M与N的行数和列数对应相等./操作结果:求稀疏矩阵的差Q=M-N.MultSMatrix(M,N,&Q);/初始化条件: 稀疏矩阵M的列数等于N的行数./操作结果:求稀疏矩阵的乘积Q=M*N. ADT Array调试测试：初始界面矩阵的加法矩阵的减法矩阵的转置矩阵的乘法程序源码：#include #include #include #define MAXSIZE 40 /假设非零元素个数的最大值为40 #define MAXRC 20/假设矩阵的最大行数为20 typedef int ElemType; 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) 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(请用三元组形式输入矩阵的元素(行 列 非零元素):); 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 Xiangjia(TSMatrix A,TSMatrix B,TSMatrix &C,int n) 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.dataa.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+.e=n*B.datab+.e; C.fls=l-1; int Xiangcheng(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(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; void 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 Zhuanzhi(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;for(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(tn); printf(t * 稀疏矩阵的加、减、转、乘 * n);printf(tn); printf(t 1、稀疏矩阵的加法 n); printf(t 2、稀疏矩阵的减法 n); printf(t 3、稀疏矩阵的转置 n); printf(t 4、稀疏矩阵的乘法 n); printf(t 5、退出该应用程序 n); printf(tn);printf(输入要进行的项目的编号:); scanf(%d,&flag); if(flag=5)break; Creat(A); printf(矩阵A:n); Print_SMatrix(A); switch(flag) case 1:Creat(B);n=1; printf(矩阵B:n); Print_SMatrix(B); if(A.hs=B.hs & A.ls=B.ls) printf(A+B:n); Xiangjia(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); Xiangjia(A,B,C,n); Print_SMatrix(C); else printf(错误!行列不一致n); break; case 3: printf(A-B:n); Zhuanzhi(p,q); Print_SMatrix(B);break; case 4:Creat(B); printf(矩阵B:n); Print_SMatrix(B); printf(A*B:n); n=Xiangcheng(A,B,C);