1、数据结构课程设计报告矩阵的运算目 录1 问题描述 12 需求分析 13 概要设计 131抽象数据类型定义 132模块划分 24 详细设计 241数据类型的定义 342主要模块的算法描述 35 测试分析 96 课程设计总结 12参考文献 12附录(源程序清单) 131 问题描述用三元数组实现稀疏矩阵的加法,乘法,转置。2 需求分析(1)先用do-while语句选择要操作的程序:1、矩阵的相加,2、矩阵的相乘,3、矩阵转置。(2)输入你想要操作的程序再用switch选择:转置函数void NormalTSMatrix(TSMatrix M,TSMatrix &T) ;加法函数void SeqAdd
2、(TSMatrix a, TSMatrix b,TSMatrix &c);乘法函数void multsmatrix(TSMatrix M,TSMatrix N,TSMatrix &T);(3)在调用以上函数时先要建立三元数组输入函数void InitTSM(TSMatrix *M)和矩阵的输出函数void ShowTSM(TSMatrix M)。3 概要设计31抽象数据类型定义ADT Array数据对象:D=aj1j2jn|n(0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i 维下标,aj1j2jnElemSet, ji=0, ,bi-1, i=1,2, ,n数据关系:R=R1
3、,R2, ,RnRi=|0jkbk-1,1kn且ki, 0jibi-2,aj1.ji.jn,aj1ji+1jnD, i=2, ,n 基本操作: InitArray( &A, n, bound1, , boundn ) 操作结果:若维数n和各维长度合法,则构造相应的数组A,并返回OK。 DestroyArray( &A ) 操作结果:销毁数组A。 Value( A, &e, index1, , indexn ) 初始条件:A是n维数组,e为元素变量,随后是n个下标值。 操作结果:若各下标不越界,则e赋值为所指定的A的元素值,并返回OK。 Assign( &A, e, index1, , inde
4、xn ) 初始条件:A是n维数组,e为元素变量,随后是n个下标值。 操作结果:若下标不越界,则将e的值赋给所指定的A的元素,并返回OK。ADT Array32模块划分本程序包括三个模块:(1)主程序模块void main()矩阵的相加矩阵的相乘矩阵的转置(2)相加模块实现矩阵的相加(3)相乘模块实现矩阵的相乘(4)转置模块实现矩阵的转置4 详细设计41数据类型的定义#define MAXSIZE 1000typedef struct int e; int i,j;Triple; /*三元组类型定义*/typedef struct Triple dataMAXSIZE+1; int mu,nu,
5、tu;TSMatrix; /*三元组顺序表类型定义*/42主要模块的算法描述(1) 主函数 输入int i,进行switch选择:当输入时1时操作1即进行矩阵的加法,同理输入时2和3时进行的是矩阵的乘法和转置;输入是其他数时不进行任何操作只输出的是“choose error” 。(2) 建立三元数组矩阵首先输入矩阵行数,列数,非零元素的个数,然后进行for循环,在循环中请输入元素所在行,列,值在判断m=0|nM-mu|nM-nu是否成立,若成立则输出input error!,若不成立则执行M-datai.i=m; M-datai.j=n;M-datai.e=e。(3) 输出矩阵(数学形式)先是
6、for语句控制输出的格式,再用两个for语句控制矩阵的行和列在等二个for语句中用if语句判断M.datat.i=m&M.datat.j=n若成立则printf(%dt,M.datat.e);t+;否则printf(0t),即在矩阵中没有数的地方输出0。(4)矩阵的加法首先进行是while(i=a.tu & j=b.tu)循环,在此循环中分别判断两矩阵的行相等和不相等,列的相等和不相等时要分别执行不同的语句即a的行号等于b的行号和a的列号等于b的列号时此时将他们的数据直接相加;a的行号等于b的行号和a的列号小于b的列号时相加后的值等于列号更小的矩阵中对应元素的值;如果a的列号大于b的列号且行号
7、相等,则相加后的值等于列号更小的矩阵中对应元素的值;如果a的行号小于b的行号且列号相等,则相加后的值等于行号更小的矩阵中对应元素的值;如果a的行号大于b的行号且列号相等,则相加后的值等于行号更小的矩阵中对应元素的值。然后执行while(i=a.tu)和while(jdataQn.e=*(Qe+(i-1)*N.nu+j);T-dataQn.i=i; T-dataQn.j=j;。(6)矩阵的转置先把矩阵M的行数和列数分别赋给转置后矩阵T的列数和行数,元素个数不变;然后再找出矩阵的M的i列元素,得到矩阵T的i行元素,直至全部转置完。5 测试分析测试数据及结果如下矩阵的加法测试分析结果如下:根据矩阵加
8、法测试结果分析可知:矩阵的加法是要比较矩阵A的行和列与矩阵B行和列分别之间大小,来执行不同的语句。矩阵乘法测试分析结果如下:根据矩阵乘法测试结果分析可知:首先要判断矩阵的列数是否与矩阵的行数相等,如果若相等则执行乘法相关语句,否则不能进行乘法语句。矩阵转置测试分析结果如下: 根据矩阵转置测试结果分析:只要你输入的矩阵是对的则就能转置。但注意不要超过MAXSIZE的值。6 课程设计总结通过这次课程设计使我充分的理解了用三元数组实现稀疏矩阵的加法,乘法,转置。虽然此次的程序不是很完备,但是总体还是一个比较能体现数据结构知识点能力的程序了,当然只是相对于我这个初学者来说。在刚开始编程的时候,我感到很
9、吃力,不知如何去编写源程序,后来柳老师叫我们去看此题目要用到那些知识和去上网搜索相关程序,此后经过一个星期的努力终于编好了源程序,可是不能运行,我们这小组经过反复的讨论都没找出错误,此时我们只好请教柳老师,老师一看就发现了问题原来我们定义的MAXSIZE 的值溢出了。其余的问题不大,只是程序不够完美。所以我们又对程序进行改进直至完成。在此我非常要感谢的是我的指导老师柳小文老师,感谢老师的细心认真的辅导,让我对数据结构这门课程有了一定的研究。参考文献1 黄同成,黄俊民,董建寅数据结构M北京:中国电力出版社,20082 董建寅,黄俊民,黄同成数据结构实验指导与题解M北京:中国电力出版社,20083
10、 严蔚敏,吴伟民. 数据结构(C语言版)M. 北京:清华大学出版社,20024 刘振鹏,张晓莉,郝杰数据结构M北京:中国铁道出版社,20035 张福祥,C语言程序设计沈阳:辽宁大学出版社,2008附录(源程序清单)#includestdio.h#include stdlib.h#includemalloc.h#define MAXSIZE 1000typedef struct int e; int i,j;Triple; /*三元组类型定义*/typedef struct Triple dataMAXSIZE+1; int mu,nu,tu;TSMatrix; /*三元组顺序表类型定义*/vo
11、id InitTSM(TSMatrix *M); /函数声明void ShowTSM(TSMatrix M);void NormalTSMatrix(TSMatrix M,TSMatrix *T) ;void SeqAdd(TSMatrix a,TSMatrix b,TSMatrix *c);void multsmatrix(TSMatrix M,TSMatrix N,TSMatrix *T);void main() /主函数 int i; TSMatrix sm,sm1,sm2,sm3,tsm; do printf(*n); printf(请选择你想要的操作n);printf(); prin
12、tf(1 矩阵相加); printf(2 矩阵相乘); printf(3 转置n); scanf(%d,&i); switch(i) case 1: system(cls); printf(请创建A矩阵n); InitTSM(&sm1); ShowTSM(sm1); printf(请创建B矩阵n); InitTSM(&sm2); ShowTSM(sm2); printf(A加上B为:n); SeqAdd(sm1,sm2,&sm3); printf(*n); ShowTSM(sm3); break; case 2: system(cls); printf(请创建A矩阵n); InitTSM(&s
13、m1); ShowTSM(sm1); printf(请创建B矩阵n); InitTSM(&sm2); ShowTSM(sm2); printf(A乘以B为:n); multsmatrix(sm1,sm2,&sm3); ShowTSM(sm3); break; case 3: system(cls); printf(请创建矩阵n); InitTSM(&sm); ShowTSM(sm); printf(矩阵转置为:n); NormalTSMatrix( sm, &tsm) ; ShowTSM(tsm); break; default: printf(choose error!n); while(i
14、!=0); void InitTSM(TSMatrix *M) /初始化数组元素 int e,m,n,t,i; printf(请输入矩阵行数,列数,非零元素的个数:n); scanf(%d%d%d, &m,&n,&t); M-mu=m; M-nu=n; M-tu=t; for( i=1;i=t;i+) printf(请输入元素所在行,列,值:); scanf(%d%d%d, &m,&n,&e); if(m=0|nM-mu|nM-nu) printf(input error!n); i-; else M-datai.i=m; M-datai.j=n; M-datai.e=e; void Show
15、TSM(TSMatrix M) /显示数组元素 int m,n,i,t=1; printf(则矩阵为:n); for( i=1;i=M.nu;i+) printf(%dt,i); printf(n); printf(*n); for(m=1;m=M.mu;m+) for(n=1;nmu=M.nu; T-nu=M.mu; T-tu=M.tu; if(T-tu) int t,i,k=1; for( i=1;iM.nu;i+) for( t=1;tdatak.i=M.datat.j; T-datak.j=M.datat.i; T-datak+.e=M.datat.e; void SeqAdd(TSM
16、atrix a,TSMatrix b,TSMatrix *c) /矩阵加法 int i=1,j=1,k=1; /下标置初始值 while(i=a.tu & jdatak.i=a.datai.i; c-datak.j=a.datai.j; c-datak.e=a.datai.e+b.dataj.e;/此时将他们的数据直接相加 i+; j+; k+; else if(a.datai.jdatak.i=a.datai.i; c-datak.j=a.datai.j; c-datak.e=a.datai.e;/如果行号相等,则相加后的值等于列号更小的矩阵中对应元素的值 i+; k+; else if(a
17、.datai.jb.dataj.j)/a的列号大于b的列号 c-datak.i=b.dataj.i; c-datak.j=b.dataj.j; c-datak.e=b.dataj.e; /如果行号相等,则相加后的值等于列号更小的矩阵中对应元素的值 j+; k+; else if(a.datai.idatak.i=a.datai.i; c-datak.j=a.datai.j; c-datak.e=a.datai.e;/如果列号相等,则相加后的值等于行号更小的矩阵中对应元素的值 i+; k+; else if(a.datai.ib.dataj.i)/a的行号大于b的行号 c-datak.i=b.d
18、ataj.i; c-datak.j=b.dataj.j; c-datak.e=b.dataj.e;/如果列号相等,则相加后的值等于行号更小的矩阵中对应元素的值 j+; k+; while(idatak.e=a.datai.e; c-datak.i=a.datai.i; c-datak.j=a.datai.j; i+; k+; while(jdatak.e=a.dataj.e; c-datak.i=a.dataj.i; c-datak.j=a.dataj.j; j+; k+; c-nu=a.nu; c-mu=a.mu; c-tu=k; void multsmatrix(TSMatrix M,TS
19、Matrix N,TSMatrix *T) /矩阵乘法 int i,j,Qn=0; int *Qe; if(M.nu!=N.mu) printf(两矩阵无法相乘); T-mu=M.mu; T-nu=N.nu; Qe=(int *)malloc(M.mu*N.nu*sizeof(int); /* Qe为矩阵Q的临时数组*/ for(i=1;i=M.mu*N.nu;i+) *(Qe+i)=0; /* 矩阵Q的第i行j列的元素值存于*(Qe+(M.datai.i-1)*N.nu+N.dataj.j)中,初值为0 */ for(i=1;i=M.tu;i+) /* 结果累加到Qe */ for(j=1;j=N.tu;j+) if(M.datai.j=N.dataj.i) *(Qe+(M.datai.i-1)*N.nu+N.dataj.j)+=M.datai.e*N.dataj.e; for(i=1;i=M.mu;i+) /*Qe矩阵中,因为M的每一行和N的每一列相乘都是T的一个元素,不管它是零或非零 */for(j=1;jdataQn.e=*(Qe+(i-1)*N.nu+j); T-dataQn.i=i; T-dataQn.j=j; T-tu=Qn;