数据结构与算法特殊矩阵和稀疏矩阵7395.pdf

《数据结构与算法特殊矩阵和稀疏矩阵7395.pdf》由会员分享，可在线阅读，更多相关《数据结构与算法特殊矩阵和稀疏矩阵7395.pdf（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 常熟理工学院 数据结构与算法实验指导与报告书 _2017-2018_学年 第_1_ 学期 专 业：物联网工程 实验名称：特殊矩阵和稀疏矩阵 实验地点：N6-210 指导教师：聂盼红 计算机科学与工程学院 2017 实验五 特殊矩阵和稀疏矩阵【实验目的】1、掌握数组的结构类型（静态的内存空间配置）；通过数组的引用下标转换成该数据在内存中的地址；2、掌握对称矩阵的压缩存储表示；3、掌握稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。【实验学时】2 学时【实验预习】回答以下问题：1、什么是对称矩阵写出对称矩阵压缩存储 sak与 aij 之间的对应关系。若 n 阶矩阵 A 中的元素满足下述

2、性质：aij=aji，则称为 n 阶对称矩阵。sak与矩阵元素 aij之间存在着一一对应的关系：若 i=j，k=i*(i+1)/2+j;若 ij，k=j*(j+1)/2+i。0=i,j=n-1 0=k=j。对称矩阵为 3,9,1,4,7 9,5,2,5,8 1,2,5,2,4 4,5,2,1,7 7,8,4,7,9 参考程序如下：#include#define N 5 int main()int upperNN=3,9,1,4,7,9,5,2,5,8,1,2,5,2,4,4,5,2,1,7,7,8,4,7,9 ;/*对称矩阵*/int rowMajor15;/*存储转换数据后以行为主的数组*/

3、int Index;/*数组的索引值*/int i,j;printf(Two dimensional upper triangular array:n);for(i=0;iN;i+)/*输出对称矩阵*/for(j=0;jN;j+)printf(%3d,upperij);printf(n);for(i=0;iN;i+)/*进行压缩存储*/for(j=0;j=j)/*下三角元素进行存储*/Index=i*(i+1)/2+j;/*ij 与 index 的转换*/rowMajorIndex=upperij;printf(nRow Major one dimensional array:n);for(i

4、=0;i15;i+)/*输出转换后的一维数组*/printf(%3d,rowMajori);printf(n);return 1;2、完成程序，实现稀疏矩阵的三元组表存储及稀疏矩阵的转置。调试并给出结果：补充完整程序，运行稀疏矩阵的一般转置算法；完成稀疏矩阵的快速转置算法，并修改主函数的转置调用算法，验证快速转置算法的正确性。部分代码如下：#include#define MAXSIZE 20 /*非零元素个数最大值*/typedef int ElemType;typedef struct int i,j;ElemType e;Triple;typedef struct Triple dataM

5、AXSIZE+1;/*三元组表，data0不用*/int mu,nu,tu;/*矩阵的行数、列数、非零元个数*/TSMatrix;void TransposeSMatrix(TSMatrix*T,TSMatrix*M);/*一般转置算法*/void FastTransposeSMatrix(TSMatrix*M,TSMatrix*T);/*快速转置算法*/int main()int i,j,k,q,col,p;int temp67=0,12,9,0,0,0,0,/*稀疏矩阵*/0,0,0,0,0,0,0,-3,0,0,0,0,14,0,0,0,24,0,0,0,0,0,18,0,0,0,0,0

6、,15,0,0,-7,0,0,0,;TSMatrix T,M;=6;=7;=0;k=1;for(i=0;i;i+)/*转换为稀疏矩阵的三元组表示*/for(j=0;j;j+)if(tempij!=0)k.i=i+1;k.j=j+1;k.e=tempij;k+;=k-1;FastTransposeSMatrix(&M,&T);/*调用转置算法进行转置*/*输出转置结果*/printf(稀疏矩阵：n);for(i=0;i;i+)/*转换为稀疏矩阵的三元组表示*/for(j=0;j;j+)printf(%3d,tempij);printf(n);printf(转置前 M 三元组表：nmutnuttu

7、n);printf(%dt%dt%dn,;printf(nitjten);for(i=1;i=;i+)printf(%dt%dt%dn,i.i,i.j,i.e);printf(转置后 T 三元组表：nmutnuttun);printf(%dt%dt%dn,;printf(nitjten);for(i=1;imu=M-nu;T-nu=M-mu;T-tu=M-tu;if(T-tu)q=1;for(col=1;colnu;+col)for(p=1;ptu;+p)if(M-datap.j=col)T-dataq.i=M-datap.j;T-dataq.j=M-datap.i;T-dataq.e=M-d

8、atap.e;+q;/*稀疏矩阵的快速转置算法*/void FastTransposeSMatrix(TSMatrix*M,TSMatrix*T)int t,q,col,p,numMAXSIZE,cpotMAXSIZE;T-mu=M-nu;T-nu=M-mu;T-tu=M-tu;if(T-tu)/*快速转置过程的实现，请补充代码*/for(col=1;colmu;+col)numcol=0;q=cpotcol;T-dataq.i=M-datap.j;T-dataq.j=M-datap.i;T-dataq.e=M-datap.e;+cpotcol;【实验小结】本实验掌握了对称矩阵的压缩存储表示，稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。明白了可以改变矩阵的储存方式来节省内存空间，今后可以利用这一思想来节省内存。