稀疏矩阵运算器

1、 数据结构课程实验报告 题目：稀疏矩阵运算器 班级： 姓名： 学号： 专业： 学院： 完成日期：1、 需求分析（1） 问题描述：稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。（2） 基本要求：以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。（3） 输入的形式：界面已设计好，智能输入（4） 测试数据2、 概要设计（1） 抽象数据类型数组的定义ADT Array数据对象:ji=0,.,bi-1

2、,i=1,2,.,n;D=aj1j2.jn|n(>0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2.jn (-ElemSet数据关系:R=R1,R2,.Rn|Ri=|0<=jk<=bk-1,1<=k<=n且k<>i,0<=ji<=bi-2,aj1.ji.jn,aj1.ji+1 .jn(-D,i=2,.n基本操作:InitArray(&A,n,bound1,.,boundn)若维数和各维长度合法,则构造相应的数组A,并返回OK.DestroyArray(&A)操作结果:销毁数组A.Value(

3、A,&e,index1,.,indexn)初始条件:A是n维数组,e为元素变量,随后是n个下标值.操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK.Assign(&A,e,index1,.,indexn)初始条件:A是n维数组,e为元素变量,随后是n个下标值.操作结果:若下标不超界,则将e的值赋给 所指定的A的元素,并返回OK.ADT Array（2） 数组的顺序存储表示和实现Status InitArray(Array &A,int dim,.);Status DestroyArray(Array &A);Status Value(Array

4、 A,ElemType &e,.);Status Assign(Array &A,ElemType e,.);基本操作的算法描述:Status InitArray(Array &A,int dim,.)if(dim<1|dim>MAX_ARRAY_DIM) return ERROR;A.dim=dim;A.bounds=(int *)malloc(dim *sizeof(int);if(!A.bounds) exit(OVERFLOW);elemtotal=1;va_start(ap,dim);for(i=1;i< p="">

5、A.boundsi=va_arg(ap,int);if(A.boundsi<0) return UNDERFLOW;elemtotal*=A.boundsi;va_end(ap);A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType);if(!A.base) exit(OVERFLOW);A.constants=(int *)malloc(dim*sizeof(int);if(!A.constants) exit(OVERFLOW);A.constantsdim-1=1;for(i=dim-2;i>=0;-i)A.constants

6、i=A.boundsi+1*A.constantsi+1;return OK;Status DestoyArray(Array &A)if(!A.base) return ERROR;free(A.base); A.base=NULL;if !(A.bounds) return ERROR;free(A.bounds); A.bounds=NULL;if!(A.constatns) return ERROR;free(A.constants); A.constants=NULL;return OK;Status Locate(Array A,va_list ap,int &of

7、f)off=0;for(i=0;i< p="">ind=va_arg(ap,int);if(ind<0|ind>=A.boundsi) return OVERFLOW;off+=A.constantsi*ind;return OK;Status Value(Array A,ElemType &e,.)va_start(ap,e);if(result=Locate(A,ap,off)<=0 return result;e=*(A.base+off);return OK;Status Assign(Array &A,ElemType

8、 e,.)va_start(ap,e);if(result=Locate(A,ap,off)<=0) return result;*(A.base+off)=e;return OK;3、 详细设计（1） 元素类型、结点类型和指针类型typedef int ElemType; typedef struct /三元组表示元素 int i,j; /非零元的行下标和列下标 ElemType e; /非零元的值 Triple; typedef struct Triple dataMAXSIZE+1; /非零元三元组表 int rposMAXRC+1; /各行第一个非零元在三元组的位置表 int m

9、u,nu,tu; /矩阵的行数，列数和非零元的个数 TSMatrix,*Matrix; （2） 初始化稀疏矩阵函数void Creat(TSMatrix &M) /初始化矩阵 int i,k; for(i=1;i<=MAXRC+1;i+) M.rposi=0; printf("请输入矩阵的行数、列数和非零元个数(以空格隔开):"); scanf("%d %d %d",&M.mu,&M.nu,&M.tu); for(i=1;i<=M.tu;i+)printf("请用三元组形式输入矩阵的元素(行 列 非零

10、元素):"); scanf("%d %d %d",&M.datai.i,&M.datai.j,&M.datai.e); for(i=1,k=1;i<=M.mu;i+) M.rposi=k; /记下每一行第一个非零元在X.data中的序号while(M.datak.i<=i && k<=M.tu) /移到下一行的第一个非零元k+; （3) 稀疏矩阵相加，相减函数void Xiangjia(TSMatrix A,TSMatrix B,TSMatrix &C,int n) /n为控制符（相加为+1，相减为

11、-1） int a,b,temp,l; C.mu=A.mu;C.nu=A.nu;a=b=l=1;while(a<=A.tu && b<=B.tu) if(A.dataa.i=B.datab.i) /元素所在行数相同 if(A.dataa.j<B.datab.j) /同一行元素A所在列数小于BC.datal+=A.dataa+; /把A中值赋给Celse if(A.dataa.j>B.datab.j) C.datal=B.datab; /否则把B中值赋给C C.datal+.e=n*B.datab+.e;elsetemp=A.dataa.e+n*B.dat

12、ab.e; /否则就相加if(temp) /判断是不是零 C.datal=A.dataa; C.datal.e=temp; l+; a+;b+; else if(A.dataa.i<B.datab.i) /元素所在行数不同且A的行小于B的行，把A直接赋给CC.datal+=A.dataa+; else C.datal=B.datab; /元素所在行数不同且B的行小于A的行，把B直接赋给CC.datal+.e=n*B.datab+.e; while(a<=A.tu) /A或B中多于的元素直接赋给C C.datal+=A.dataa+; while(b<=B.tu)C.datal

13、=B.datab; C.datal+.e=n*B.datab+.e; C.tu=l-1; （4） 稀疏矩阵相乘函数int Xiangcheng(TSMatrix A,TSMatrix B,TSMatrix &Q) /与书中的算法基本相同，不多做解释 int arow,brow,ccol,tp,p,q,t; int ctempMAXRC+1; if(A.nu!=B.mu)return 0; /A的行与B的列不想等Q.mu=A.mu;Q.nu=B.nu;Q.tu=0;if(A.tu*B.tu) for(arow=1;arow<=A.mu;arow+) /处理A的每一行 for(cco

14、l=1;ccol<=Q.nu;ccol+) ctempccol=0; /当前行各元素累加器清零 Q.rposarow=Q.tu+1; if(arow<A.mu)tp=A.rposarow+1;elsetp=A.tu+1;for(p=A.rposarow;p<tp;p+) /对当前行中的第一个非零元brow=A.datap.j; /找到对应元在B中的行号if(brow<B.mu)t=B.rposbrow+1;elset=B.tu+1;for(q=B.rposbrow;q<t;q+)ccol=B.dataq.j; /乘积元素在Q中列号ctempccol+=A.data

15、p.e*B.dataq.e; for(ccol=1;ccol<=Q.nu;ccol+) /压缩存储改行非零元 if(ctempccol) if(+Q.tu>MAXSIZE)return 0; Q.dataQ.tu.i=arow; Q.dataQ.tu.j=ccol; Q.dataQ.tu.e=ctempccol; return 1; （5） 三元组表打印出矩阵void Print_SMatrix(TSMatrix M) /将三元组表打印出矩阵 int k,l,n; Matrix p; p=&M; for(k=1,n=1;k<=p->mu;k+) for(l=1;

16、l<=p->nu;l+) if(p->datan.i=k && p->datan.j=l) printf("%5d",p->datan.e); /控制格式n+; else printf("%5d",0); printf("n"); printf("n"); （6） 销魂函数void Destory_SMatrix(TSMatrix &M) /销毁函数 M.mu=M.nu=M.tu=0; （7） 主函数void main() /主函数 TSMatrix A,B,C

17、; TSMatrix *p=&A,*q=&B;int flag,n; while(1) /操作界面 printf("tn"); printf("t * 稀疏矩阵的加、减、转、乘 * n");printf("tn"); printf("t 1、稀疏矩阵的加法 n"); printf("t 2、稀疏矩阵的减法 n"); printf("t 3、稀疏矩阵的乘法 n"); printf("t 4、退出该应用程序 n"); printf("

18、tn");printf("输入要进行的项目的编号:"); scanf("%d",&flag); if(flag=4)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.mu=B.mu && A.nu=B.nu) printf("A+B:n"); Xiangjia(A,B,C,n);Print_SMatrix(C); else print