稀疏矩阵的运算.doc

实验课程名称 交通资询系统设计 专 业 班 级 10级计科(1)班 学 生 姓 名 学 号 指 导 教 师 2012至2013学年第 一 学期第 1 至 18 周目 录第1章 概述2第2章系统分析32.1 算法的思想32.2 需求分析及研究意义32.3 研究意义3第3章 概要设计33.1课程设计的方案设计论证3第4章 详细设计44.1 主程序模块44.2 稀疏矩阵的存储44.3 稀疏矩阵加法4第5章 运行与测试4第6章 总结和心得46.1 实验总结46.2 心得4参考文献5伪代码5第1章 概述 数组是一种常用的数据类型，几乎所有的程序设计语言都把数据类型设为固有的类型。他的应用非常广泛。多维数组的一个特殊代表就是稀疏矩阵的运算。稀疏矩阵在现实中有很多应用,因此稀疏矩阵的计算近年来被广泛地研究. 稀疏矩阵是指多数元素为0的矩阵，利用素数特点进行存储和计算可以大大节省存储空间，提高计算效率，实现一个能进行稀疏加法的运算。 第2章 系统分析2.1 算法的思想（1）输入存储矩阵个算法。（2）存储稀疏矩阵用三元组表示。（3）稀疏矩阵的加法算法编写。（4）输出稀疏矩阵。2.2 需求分析及研究意义（1）首先输入矩阵的行数和列数，并判别给出的两个矩阵的行数，列数对于所求的运算是否匹配。（2）程序存储用三元组存储表表示，按行优先表示。（3）三元组表示稀疏矩阵，矩阵的相加所得结果矩阵另生成。2.3 研究意义矩阵加法了解：矩阵之间也可以相加。把两个矩阵对应位置的单个元素相加，得到的新矩阵就是加法的结果。由其运算法则可知，只有行数和列数相同的矩阵才能进行加法运算。矩阵之间相加没有顺序，假设A、B都是矩阵，则A+B=B+A。通常认为矩阵没有减法，若要与一个矩阵相减，在概念上是引入一个该矩阵的负矩阵，然后相加。A-B是A+(-B)的简写。第3章 概要设计3.1 课程设计的方案设计论证（1）输入存储矩阵的算法。（2）存储稀疏矩阵有用三元组表示。（3）稀疏矩阵的加法算法编写。（4）输出稀疏矩阵。第4章 详细设计4.1 主程序模块其中主函数为： main() 定义以及初始化 从文件中读取数据，输出矩阵调用转置和加法函数，输出转置矩阵以及加法矩阵4.2 稀疏矩阵的存储void CreateMatrix(int Amn,int B50) int i,j,k=0; for (i=0;im;i+)for (j=0;jn;j+)if(Aij!=0)Bk=i;k+;Bk=j;k+;Bk=Aij;k+;Bk=-1; 4.3 稀疏矩阵加法稀疏矩阵求值模块包括：矩阵相加模块AddRLSMatrix()； AddSMatrix(M,N,&Q)； 初始条件：稀疏矩阵M与N的行数和列数对应相等。 操作结果：求稀疏矩阵的和Q=M+N。第5章 运行与测试第6章 总结和心得6.1 实验总结首先必须了解稀疏矩阵的概念，存储及矩阵加法运算，三元组顺序表的存储表示。其次对三元组的输入运算、加法算法的输入算法，必须认真查阅书籍或上网了解，认真分析。最后，在对输入程序的运算情况作认真的错误分析，总结出错原因。6.2 心得原来我对稀疏矩阵的运算的知识很模糊，通过这次课程设计，我加深了对稀疏矩阵的存储和加法运算的了解，在做课程设计的过程中遇到很多问题，让我知道了自己对很多知识点都掌握的不够。随着这些问题的解决，对之前掌握的不过好的知识点进行了巩固和复习。总之，通过这次课程设计让我明白了自己在很多方面的不足，也让我学到了很多。参考文献1 数据结构:严蔚敏,吴伟民编著.北京：清华大学出版社，2007 2 数据结构与算法分析：苏仕华编著.合肥：中国科学技术大学出版社，20043 数据结构课程设计：苏仕华编著.北京：清华大学出版社，2002伪代码#include #define m 6 #define n 8 #define max 50/*转储稀疏矩阵的算法*/void creatematrix(int Amn,int B50) int i,j,k=0; for(i=0;im;i+) for(j=0;jn;j+) if (Aij!=0) Bk=i; k+; Bk=j; k+; Bk=Aij; k+;Bk=-1; /非零元素存储结束/*两个稀疏矩阵存储到两个数组中后相加存储到另一个数组中*/void matrixadd(int Amax,int Bmax,int Cmax) int i=0,j=0,k=0; while (Ai!=-1 & Bj!=-1) if (Ai=Bj) /行相等 if (Ai+1=Bj+1) /且列相等 Ck=Ai; Ck+1=Ai+1; Ck+2=Ai+2+Bj+2; k=k+3; i=i+3; j=j+3; else if (Ai+1Bj+1) /A的列小于B的列，将A的三个元素直接存入C中 Ck=Ai; Ck+1=Ai+1; Ck+2=Ai+2; k=k+3; i=i+3; else /B的列小于A的列，且B的三个元素直接存入C中 Ck=Bj; Ck+1=Bj+1; Ck+2=Bj+2; k=k+3; j=j+3; else if (AiBj) /A的行小于B的行，将A的三个元素直接存入C中 Ck=Ai; Ck+1=Ai+1; Ck+2=Ai+2+Bj+2; k=k+3; i=i+3; else /B的行小于A的行，将B的三个元素直接存入C中 Ck=Bj; Ck+1=Bj+1; Ck+2=Bj+2; k=k+3; j=j+3; /循环结束 if (Ai=-1) while (Bj!=-1) /A结束B还有元素，将B的所有元素直接存入C中 Ck=Bj; Ck+1=Bj+1; Ck+2=Bj+2; k=k+3;j=j+3; else while(Ai!=-1) /B结束，A还有元素，将A的所有元素直接存入C中 Ck=Ai; Ck+1=Ai+1; Ck+2=Ai+2; k=k+3; i=i+3;Ck=-1; void main() int Emn,Fmn,Amax,Bmax,Cmax; int i,j,k; printf(输入稀疏矩阵E：(%d,%d):n,m,n); for(i=0;im;i+) /输入稀疏矩阵E for(j=0;jn;j+) scanf(%d,&Eij); printf(输入稀疏矩阵F：(%d,%d):n,m,n); for(i=0;im;i+)/输入稀疏矩阵F for(j=0;jn;j+) scanf(%d,&Fij); creatematrix(E,A);/ E稀疏矩阵存储在数组A中 creatematrix(F,B);/ F稀疏矩阵存储在数组B中 matrixadd(A,B,C);/相加 i=0;j=0;k=0; printf(A数组内容如下：n); while(Ai!=-1) printf(%5d,%5d,%5dn,Ai,Ai+1,Ai+2); i=i+3; pr