《数据构造与算法 特殊矩阵和稀疏矩阵.docx》由会员分享,可在线阅读,更多相关《数据构造与算法 特殊矩阵和稀疏矩阵.docx(16页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据构造与算法特殊矩阵和稀疏矩阵常熟理工学院(数据构造与算法)实验指导与报告书_2021-2022_学年第_1_学期专业:物联网工程实验名称:特殊矩阵和稀疏矩阵实验地点:N6-210指导老师:聂盼红计算机科学与工程学院2021实验五特殊矩阵和稀疏矩阵【实验目的】1、把握数组的构造类型静态的内存空间配置;通过数组的引用下标转换成该数据在内存中的地址;2、把握对称矩阵的压缩存储表示;3、把握稀疏矩阵的压缩存储-三元组表表示,以及稀疏矩阵的转置算法。【实验学时】2学时【实验预习】回答下面问题:1、什么是对称矩阵?写出对称矩阵压缩存储sak与aij之间的对应关系。若n阶矩阵A中的元素知足下述性质:ai
2、j=aji,则称为n阶对称矩阵。sak与矩阵元素aij之间存在着逐一对应的关系:若i=j,k=i*(i+1)/2+j;若i=j。对称矩阵为3,9,1,4,79,5,2,5,81,2,5,2,44,5,2,1,77,8,4,7,9参考程序如下:#include#defineN5intmain()intupperNN=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;/*对称矩阵*/introwMajor15;/*存储转换数据后以行为主的数组*/intIndex;/*数组的索引值*/inti,j;printf(Twodimensionalupper
3、triangulararray:n);for(i=0;i=j)/*下三角元素进行存储*/Index=i*(i+1)/2+j;/*ij与index的转换*/rowMajorIndex=upperij;printf(nRowMajoronedimensionalarray:n);for(i=0;iexp5_2.c部分代码如下:#include#defineMAXSIZE20/*非零元素个数最大值*/typedefintElemType;typedefstructinti,j;ElemTypee;Triple;typedefstructTripledataMAXSIZE+1;/*三元组表,data0
4、不用*/intmu,nu,tu;/*矩阵的行数、列数、非零元个数*/TSMatrix;voidTransposeSMatrix(TSMatrix*T,TSMatrix*M);/*一般转置算法*/voidFastTransposeSMatrix(TSMatrix*M,TSMatrix*T);/*快速转置算法*/intmain()inti,j,k,q,col,p;inttemp67=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,15,0,0,-7,0,0,0,;TSMatrixT
5、,M;M.mu=6;M.nu=7;M.tu=0;k=1;for(i=0;iprintf(%3d,tempij);printf(n);printf(转置前M三元组表:nmutnuttun);printf(%dt%dt%dn,M.mu,M.nu,M.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-dat
6、ap.e;+q;/*稀疏矩阵的快速转置算法*/voidFastTransposeSMatrix(TSMatrix*M,TSMatrix*T)intt,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;【实验小结】本实验把握了对称矩阵的压缩存储表示,稀疏矩阵的压缩存储-三元组表表示,以及稀疏矩阵的转置算法。明白了能够改变矩阵的储存方式来节省内存空间,今后能够利用这一思想来节省内存。.