稀疏矩阵.docx
- 文档编号:18529204
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:17
- 大小:99.41KB
稀疏矩阵.docx
《稀疏矩阵.docx》由会员分享,可在线阅读,更多相关《稀疏矩阵.docx(17页珍藏版)》请在冰点文库上搜索。
稀疏矩阵
目录
1概述2
1.1问题描述2
1.2实现目的2
2系统分析2
2.1需求分析2
2.2设计要求2
3概要设计2
3.1稀疏矩阵的加法运算思路2
3.2抽象数据类型稀疏矩阵的定义如下3
3.3本程序模块调用关系3
4详细设计4
4.1程序流程图4
4.2每个模块的分析4
4.2.1稀疏矩阵存储模块分析4
4.2.2稀疏矩阵加法模块分析5
4.2.3主函数模块分析6
5运行与测试7
6总结与心得8
参考文献:
9
附录:
9
1概述
1.1问题描述
稀疏矩阵是指那些多数元素为零的元素。
利用“稀疏”特点进行存储和设计可以大大节省存储空间,提高计算效率。
用三元组实现稀疏矩阵的加法。
1.2实现目的
在学习C++,C语言,数据结构等课程的基础上,更好地掌握多维数组的逻辑结构(非线性结构,逻辑特征是一个数据元素可能有多个直接前驱和多个直接后继)和存储结构,稀疏矩阵的存储方式和加法运算等。
2系统分析
2.1需求分析
根据设计要求,首先需要解决如何存储稀疏矩阵,一般都是采用顺序存储方法来表示多维数组,但实际中一般的顺序存储方法也不太实用,简单的一种是将一个稀疏矩阵对应存储到一个一维数组中,然后在进行矩阵加法运算时一次扫描矩阵A和B的行列值,并以行优先。
当行列相同时,将第三个元素值相加的和以及行列号三个元素存入结果数组C中;不相同时将A或B的三个元素直接存入结果数组中。
2.2设计要求
首先解决将一个稀疏矩阵对应存储到一个一维数组中,然后在进行矩阵加法运算时依次扫描矩阵A和B的行列值,并以行优先。
当行列相同时将第三个元素值相加的和以及行列号三个元素存入结果数组C中;不相同时,将A或B的三个元素直接存入结果数组中。
3概要设计
3.1稀疏矩阵的加法运算思路
比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为零的元素的行数及列数(即i与j),将i与j都相等的前后两个元素值相加,保持i,j不变存储在新的三元组中,不等的则分别储存在新的三元组中。
最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。
3.2抽象数据类型稀疏矩阵的定义如下
ADTSparseMatrix{
数据对象:
D={ai,j|i=1,2,…,m;j=1,2,…,n;
ai,j∈ElemSet,m和n分别称为矩阵的行数和列数}
数据关系:
R={Row,Col}
Row={
Col={
基本操作:
CreateSMatrix(&M)
操作结果:
初始化稀疏数组
AddSMatrix(M,N,&Q);
初始条件:
稀疏数组M、N已经存在
操作结果:
求矩阵的和Q=M+N
}ADTList
3.3本程序模块调用关系
图3-3程序模块调用图
4详细设计
4.1程序流程图
图4-1程序流程图
4.2每个模块的分析
4.2.1稀疏矩阵存储模块分析
类似于建立顺序存储稀疏矩阵的三元组。
假设A为一个系数矩阵,B为一个存储对应于A矩阵生成的数组。
在这个方法中,只要用一个二重循环来判断每个矩阵元素是否为零,若不为零,则将其行,列下标及其值存入到一维数组B中对应的元素中。
其实现算法如下:
/***转储稀疏矩阵的算法***/
voidCreatMatrix(intA[m][n],intB[50])
{
inti,j,k=0;
for(i=0;i for(j=0;j if(A[i][j]! =0) { B[k]=i;k++; B[k]=j;k++; B[k]=A[i][j];k++; } B[k]=-1;//非零元素存储的结束 } 4.2.2稀疏矩阵加法模块分析 voidMatrixAdd(intA[max],intB[max],intC[max]) { inti=0,j=0,k=0; while(A[i]! =-1&&B[j]! =-1) { if(A[i]==B[j])//行相等 { if(A[i+1]==B[j+1])//列相等 { C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]+B[j+2]; k=k+3; i=i+3; j=j+3; } elseif(A[i+1] { C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]; k=k+3; i=i+3; } else//B的列小于A的列,将B的三个元素直接存入C中 { C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } } elseif(A[i+1] { C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]; k=k+3; i=i+3; } else//B的行小于A的行,将B的三个元素直接存入C中 { C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } }//循环结束 if(A[i]==-1) while(B[j]! =-1)//A结束B还有元素,将B的所有元素直接存入C中 { C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } else while(A[i]! =-1) { C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]; k=k+3; i=i+3; } C[k]=-1; } 4.2.3主函数模块分析 voidmain() { intE[m][n],F[m][n],A[max],B[max],C[max]; inti,j,k; printf("请依次输入E矩阵: \n"); for(i=0;i for(j=0;j scanf("%d",&E[i][j]); printf("请依次输入F矩阵: \n"); for(i=0;i for(j=0;j scanf("%d",&F[i][j]); CreatMatrix(E,A);//E矩阵的非零元素存储到一维素组A中 CreatMatrix(F,B);//F矩阵的非零元素存储到一维素组B中 MatrixAdd(A,B,C);//A、B相加存入C i=0;j=0;k=0; printf("A数组内容如下: \n"); while(A[i]! =-1) { printf("%5d,%5d,%5d\n",A[i],A[i+1],A[i+2]);//输入A中的内容 i=i+3; } printf("B数组内容如下: \n"); while(B[j]! =-1) { printf("%5d,%5d,%5d\n",B[j],B[j+1],B[j+2]);//输入B中的内容 j=j+3; } printf("C数组内容如下: \n"); while(C[k]! =-1) { printf("%5d,%5d,%5d\n",C[k],C[k+1],C[k+2]);//输入C中的内容 k=k+3; } } 5运行与测试 初始界面: 输入E矩阵和F矩阵后得到的和矩阵: 6总结与心得 通过这几节数据结构课程设计的学习,使我对这门课程有更深的了解,这是一门属于综合类型设计的科目,它需要把理论变为上机调试,不仅锻炼我们上机的动手能力,也锻炼我们编程的能力。 每次在敲代码的时候,都会出现每次必犯的低级错误(字母拼写错误,大小写没区分,中英文状态下的符号),所以编程的时候我总在提醒自己一定要细心,细心,再细心,自己一点点小小的疏忽,都会导致编译的错误,也许最终会让我们前功尽弃。 通过这次课程设计,我也发现我的好多不足之处,对C语言中多维数组的陌生,数据结构中稀疏矩阵,三元组表的不了解,通过此次实验的学习,我深深的意识到温故而知新的哲理,从学过的知识里汲取新的营养成分,我也认识到学好计算机要重视自己实践操作和思维能力,不仅仅是学习C语言,还是其它的语言也一样。 参考文献: [1]数据结构课程设计苏仕华等编著机械工业出版社 [2]数据结构(C语言版)严蔚敏吴伟民编著清华大学出版社 [3]C程序设计(第三版)谭浩强著清华大学出版社 附录: 源代码: //主函数main.cpp #include #definem6 #definen8 #definemax50 #include"save1.c" #include"add1.c" voidmain() { intE[m][n],F[m][n],A[max],B[max],C[max]; inti,j,k; printf("请依次输入E矩阵: \n"); for(i=0;i for(j=0;j scanf("%d",&E[i][j]); printf("请依次输入F矩阵: \n"); for(i=0;i for(j=0;j scanf("%d",&F[i][j]); CreatMatrix(E,A);//E矩阵的非零元素存储到一维素组A中 CreatMatrix(F,B);//F矩阵的非零元素存储到一维素组B中 MatrixAdd(A,B,C);//A、B相加存入C i=0;j=0;k=0; printf("A数组内容如下: \n"); while(A[i]! =-1) { printf("%5d,%5d,%5d\n",A[i],A[i+1],A[i+2]);//输入A中的内容 i=i+3; } printf("B数组内容如下: \n"); while(B[j]! =-1) { printf("%5d,%5d,%5d\n",B[j],B[j+1],B[j+2]);//输入B中的内容 j=j+3; } printf("C数组内容如下: \n"); while(C[k]! =-1) { printf("%5d,%5d,%5d\n",C[k],C[k+1],C[k+2]);//输入C中的内容 k=k+3; } } //稀疏矩阵的存储save1.c #definem6 #definen8 /***转储稀疏矩阵的算法***/ voidCreatMatrix(intA[m][n],intB[50]) { inti,j,k=0; for(i=0;i for(j=0;j if(A[i][j]! =0) { B[k]=i;k++; B[k]=j;k++; B[k]=A[i][j];k++; } B[k]=-1;//非零元素存储的结束 } //稀疏矩阵加法add1.c #definemax50 voidMatrixAdd(intA[max],intB[max],intC[max]) { inti=0,j=0,k=0; while(A[i]! =-1&&B[j]! =-1) { if(A[i]==B[j])//行相等 { if(A[i+1]==B[j+1])//列相等 { C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]+B[j+2]; k=k+3; i=i+3; j=j+3; } elseif(A[i+1] { C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]; k=k+3; i=i+3; } else//B的列小于A的列,将B的三个元素直接存入C中 { C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } } elseif(A[i+1] { C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]; k=k+3; i=i+3; } else//B的行小于A的行,将B的三个元素直接存入C中 { C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } }//循环结束 if(A[i]==-1) while(B[j]! =-1)//A结束B还有元素,将B的所有元素直接存入C中 { C[k]=B[j]; C[k+1]=B[j+1]; C[k+2]=B[j+2]; k=k+3; j=j+3; } else while(A[i]! =-1) { C[k]=A[i]; C[k+1]=A[i+1]; C[k+2]=A[i+2]; k=k+3; i=i+3; } C[k]=-1; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 稀疏 矩阵
![提示](https://static.bingdoc.com/images/bang_tan.gif)