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

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

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

2、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 5int 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 dimen

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

5、j; ElemType e;Triple;typedef struct Triple dataMAXSIZE+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

6、,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, 15,0,0,-7,0,0,0, ; TSMatrix T,M; M.mu=6; M.nu=7; M.tu=0; k=1; for (i=0;i M.mu;i+) /*转换为稀疏矩阵的三元组表示*/ for (j=0;j M.nu;j+) if (tempij!=0) M.datak.i=i+1; M.datak.j=j+1; M.datak.e=tempij; k+; M.tu=k-1; FastTransposeSMatrix(&M,&T); /*调用转置算法进行转

7、置*/ /*输出转置结果*/ printf(稀疏矩阵：n); for (i=0;i M.mu;i+) /*转换为稀疏矩阵的三元组表示*/ for (j=0;j M.nu;j+) printf(%3d,tempij); printf(n); printf(转置前M三元组表：nmutnuttun); printf(%dt%dt%dn,M.mu,M.nu,M.tu); printf(nitjten); for (i=1;i=M.tu;i+) printf(%dt%dt%dn,M.datai.i,M.datai.j,M.datai.e); printf(转置后T三元组表：nmutnuttun); pr

8、intf(%dt%dt%dn,T.mu,T.nu,T.tu); 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-datap.e; +q; /*稀疏矩阵的快速转置算法*/void FastTransposeSMatrix(TSMatrix *M,TSMatrix *T) int

9、 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; /num数组的初始化 for(t=1;ttu;+t) +numM-datat.j; /求M中每一列的非零元素的个数 cpot1=1; /求col列中第一个非零元素在T中序号 for( col=2;colnu;+col) /求cpot数组的值 cpotcol=cpotcol-1+numcol-1; for( p=1;ptu;+p) /进行转置 col=M-datap.j; q=cpotcol; T-dataq.i=M-datap.j; T-dataq.j=M-datap.i; T-dataq.e=M-datap.e; +cpotcol; 【实验小结】 本实验掌握了对称矩阵的压缩存储表示，稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。明白了可以改变矩阵的储存方式来节省内存空间，今后可以利用这一思想来节省内存。