数据构造与算法 特殊矩阵和稀疏矩阵.docx

《数据构造与算法 特殊矩阵和稀疏矩阵.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;【实验小结】本实验把握了对称矩阵的压缩存储表示，稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。明白了能够改变矩阵的储存方式来节省内存空间，今后能够利用这一思想来节省内存。.