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

数据构造与算法特殊矩阵和稀疏矩阵常熟理工学院（数据构造与算法）实验指导与报告书_2021-2022_学年第_1_学期专业：物联网工程实验名称：特殊矩阵和稀疏矩阵实验地点：N6-210指导老师：聂盼红计算机科学与工程学院2021实验五特殊矩阵和稀疏矩阵【实验目的】1、把握数组的构造类型静态的内存空间配置；通过数组的引用下标转换成该数据在内存中的地址；2、把握对称矩阵的压缩存储表示；3、把握稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。【实验学时】2学时【实验预习】回答下面问题：1、什么是对称矩阵？写出对称矩阵压缩存储sak与aij之间的对应关系。若n阶矩阵A中的元素知足下述性质：aij=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("Twodimensionaluppertriangulararray: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不用*/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,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->datap.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;【实验小结】本实验把握了对称矩阵的压缩存储表示，稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。明白了能够改变矩阵的储存方式来节省内存空间，今后能够利用这一思想来节省内存。.