数据结构课程设计报告矩阵的运算.doc

荆楚理工学院课程设计成果 学院:_荆楚理工学院_ 班 级: 计算机科学与技术本一班 学生姓名: 沈猛 学 号: 2012404010145 设计地点（单位）_ _设计题目:_矩阵的转置、加减和相乘_ 完成日期： 2013 年 12 月 30 日 指导教师评语: _ _ _ _ 成绩(五级记分制):_ 教师签名:_ _目 录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132模块划分24 详细设计241数据类型的定义342主要模块的算法描述35 测试分析96 课程设计总结11参考文献12附录 全部代码131 问题描述采用十字链表存储的稀疏矩阵，完成矩阵转置、加减和相乘功能。2 需求分析（1）先用do-while语句选择要操作的程序：1、矩阵的相加，2、矩阵的相乘，3、矩阵转置。（2）输入你想要操作的程序再用switch选择：转置函数void NormalTSMatrix(TSMatrix M，TSMatrix &T) ；加法函数void SeqAdd(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,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, , indexn ) 初始条件：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,tu;TSMatrix; /*三元组顺序表类型定义*/42主要模块的算法描述（1） 主函数 图1 主函数输入int i，进行switch选择：当输入时1时操作1即进行矩阵的加法，同理输入时2和3时进行的是矩阵的乘法和转置；输入是其他数时不进行任何操作只输出的是“choose error” 。（2） 建立十元数组矩阵图2 建立十元数组矩阵首先输入矩阵行数,列数,非零元素的个数，然后进行for循环，在循环中请输入元素所在行，列，值在判断m=0|nM-mu|nM-nu是否成立，若成立则输出input error!，若不成立则执行M-datai.i=m； M-datai.j=n；M-datai.e=e。（3） 输出矩阵图3 输出矩阵先是for语句控制输出的格式，再用两个for语句控制矩阵的行和列在等二个for语句中用if语句判断M.datat.i=m&M.datat.j=n若成立则printf(%dt,M.datat.e)；t+；否则printf(0t)，即在矩阵中没有数的地方输出0。（4）矩阵的加法图4 矩阵加法首先进行是while(i=a.tu & j=b.tu)循环，在此循环中分别判断两矩阵的行相等和不相等，列的相等和不相等时要分别执行不同的语句即a的行号等于b的行号和a的列号等于b的列号时此时将他们的数据直接相加；a的行号等于b的行号和a的列号小于b的列号时相加后的值等于列号更小的矩阵中对应元素的值；如果a的列号大于b的列号且行号相等,则相加后的值等于列号更小的矩阵中对应元素的值；如果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）矩阵的转置图6 矩阵的转置先把矩阵M的行数和列数分别赋给转置后矩阵T的列数和行数，元素个数不变；然后再找出矩阵的M的i列元素，得到矩阵T的i行元素，直至全部转置完。5 测试分析测试数据及结果如下：图7矩阵的加法测试分析结果根据矩阵加法测试结果分析可知：矩阵的加法是要比较矩阵A的行和列与矩阵B行和列分别之间大小，来执行不同的语句。图8 矩阵乘法测试分析结果根据矩阵乘法测试结果分析可知：首先要判断矩阵的列数是否与矩阵的行数相等，如果若相等则执行乘法相关语句，否则不能进行乘法语句。 图9 矩阵转置测试分析结果根据矩阵转置测试结果分析：只要你输入的矩阵是对的则就能转置。但注意不要超过MAXSIZE的值。6 课程设计总结通过这次课程设计使我充分的理解了用三元数组实现稀疏矩阵的加法，乘法，转置。虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。在刚开始编程的时候，我感到很吃力，不知如何去编写源程序，后来柳老师叫我们去看此题目要用到那些知识和去上网搜索相关程序，此后经过一个星期的努力终于编好了源程序，可是不能运行，我们这小组经过反复的讨论都没找出错误，此时我们只好请教柳老师，老师一看就发现了问题原来我们定义的MAXSIZE 的值溢出了。其余的问题不大，只是程序不够完美。所以我们又对程序进行改进直至完成。在此我非常要感谢的是我的指导老师柳小文老师，感谢老师的细心认真的辅导，让我对数据结构这门课程有了一定的研究。参考文献教学参考书1李素若.数据结构.北京：化学工业出版社，2009.参考资料：1 朱蓉，数据结构实验指导书2严蔚敏 吴伟民，.数据结构(C语言版)，1999，清华大学出版社；3严蔚敏 吴伟民，.数据结构题集(C语言版)，1999，清华大学出版社；4徐孝凯，数据结构课程实验，2002，清华大学出版社；5孟佳娜 胡潇琨，算法与数据结构实验与习题，2004，机械工业出版社；附录 全部代码#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; /*三元组顺序表类型定义*/void 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(); printf(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(&sm1); 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!=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 ShowTSM(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(TSMatrix 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.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.dataj.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.