稀疏矩阵的应用

武汉工程大学计算机科学与工程学院《数据结构》实验报告专业班级实验地点学生学号指导教师学生姓名实验时间实验项目实验类别操作性（）验证性（）设计性（）综合性（Y）其它（）实验目的及要求（1）掌握掌握稀疏矩阵的表示方法及其运算的实现；（2）实现稀疏矩阵在三元组、十字链表等表示下的各运算并分析其效率。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律认真完成实验任务30分报告质量程序代码规范、功能正确填写内容完整、体现收获70分说明：评阅教师：日期：年月日计算机科学与工程学院《计算机程序设计基础》实验报告2稀疏矩阵的应用1、实验目的：（1）掌握掌握稀疏矩阵的表示方法及其运算的实现；（2）实现稀疏矩阵在三元组、十字链表等表示下的各运算并分析其效率。2、实验内容在m×n的矩阵中，有t个非零元。令δ=t/(m*n),称δ矩阵的稀疏因子，常认为δ≤0.05时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。用三元组表实现稀疏矩阵的转置，用（顺序取，直接存）方法。3、实验说明：引入两个数组作为辅助数据结构：num[nu]：表示矩阵A中某列的非零元素的个数；cpot[nu]：初始值表示矩阵A中某列的第一个非零元素在B中的位置。num与cpot递推关系：1.实验分析：在本次实验当中，需要注意一下几个关键点：1.设置转置后矩阵B的行数、列数和非零元素的个数；2.计算A中每一列的非零元素个数；3.计算A中每一列的第一个非零元素在B中的下标；4.依次取A中的每一个非零元素对应的三元组；2.1确定该元素在B中的下标pb；2.2将该元素的行号列号交换后存入B中pb的位置；2.3预置该元素所在列的下一个元素的存放位置；具体要定义如下若干个函数：voidsetup（）初始化非零元的个数voidtransition（）转置函数voidinput（）输入函数voidprint1()输出函数voidprint2()输出函数cpot[0]=0；cpot[col]=cpot[col-1]+num[col-1]；1≤col＜nu计算机科学与工程学院《计算机程序设计基础》实验报告32.源程序代码：#includeiostreamusingnamespacestd;#includemalloc.h#definemaxsize50typedefintdatatype;typedefstruct{intp,q;datatypex;}List;typedefstruct{intmd,nd,td;}tabletype;intn,m;/*稀疏矩阵的行数、列数*/voidinput(datatypea[maxsize][maxsize]);voidsetup(datatypea[maxsize][maxsize],Listta[],tabletype*ta1);voidtransition(tabletype*ta1,tabletype*tb1,Listta[],Listtb[]);voidprint1(datatypea[maxsize][maxsize]);voidprint2(Lista[],intnn);intmain(){datatypea[maxsize][maxsize];/*稀疏矩阵*/Listta[maxsize],tb[maxsize];/*三元组顺序表*/tabletype*ta1,*tb1;if((ta1=(tabletype*)malloc(sizeof(tabletype)))==NULL){cout申请空间错误！\n;return0;}if((tb1=(tabletype*)malloc(sizeof(tabletype)))==NULL){cout申请空间错误！\n;return0;}input(a);setup(a,ta,ta1);transition(ta1,tb1,ta,tb);cout\n原稀疏矩阵为：\n;print1(a);cout\n原三元组顺序表为：\n;计算机科学与工程学院《计算机程序设计基础》实验报告4print2(ta,ta1-td);cout\n转置后的三元组顺序表：\n;print2(tb,tb1-td);return1;}/*输入*/voidinput(datatypea[maxsize][maxsize]){inti,j;cout\n请输入稀疏矩阵的行数＝;cinn;cout\n请输入稀疏矩阵的列数＝;cinm;for(i=0;in;i++)for(j=0;jm;j++){printf(\n请输入数据a[%d][%d]=,i,j);cina[i][j];}}/*建立*/voidsetup(datatypea[maxsize][maxsize],Listta[],tabletype*ta1){inti,j;ta1-td=0;/*初始化非零元素个数*/for(i=0;in;i++)for(j=0;jm;j++)if(a[i][j]!=0){ta[ta1-td].p=i;ta[ta1-td].q=j;ta[ta1-td].x=a[i][j];ta1-td++;}ta1-md=n;ta1-nd=m;}/*转置*/voidtransition(tabletype*ta1,tabletype*tb1,Listta[],Listtb[]){inti,j,nn=0;tb1-md=ta1-nd;tb1-nd=ta1-md;tb1-td=ta1-td;if(ta1-td!=0)for(i=0;ita1-nd;i++)/*i原矩阵的列下标*/计算机科学与工程学院《计算机程序设计基础》实验报告5for(j=0;jta1-td;j++)/*j原三元组顺序表的下标*/if(ta[j].q==i)/*寻找原矩阵中最小列下标*/{tb[nn].p=ta[j].q;tb[nn].q=ta[j].p;tb[nn].x=ta[j].x;nn++;}}/*矩阵输出*/voidprint1(datatypea[maxsize][maxsize]){inti,j;for(i=0;in;i++){for(j=0;jm;j++)couta[i][j];cout\n;}}/*三元组顺序表输出*/voidprint2(Lista[],intnn){inti;cout\t行号\t列号\t元素值\n;for(i=0;inn;i++)couta[i].pa[i].qa[i].x\n;cout\n;}实验内容计算机科学与工程学院《计算机程序设计基础》实验报告63.测试用例：1,当输入原稀疏矩阵为A[3][3]={2,0,3;1,0,4;0,0,1}时程序运行结果如下：计算机科学与工程学院《计算机程序设计基础》实验报告72.当输入稀疏矩阵为A[2][2]={1,0;0,2}时运行结果如下：实验内容计算机科学与工程学院《计算机程序设计基础》实验报告8实验总结4.实验总结：针对稀疏矩阵的压缩存储应用，通过本次实验对它有一定的系统了解，在这次实验的的过程当中起初有很多问题比较疑惑，甚至根本动不了手，但是通过资料的查询，以及向同学的请教，这些问题很快就解决掉了，通过对稀疏矩阵的三元组存储方式省掉了系统的很多空间，也提高了效率，这对日后的编程打下了一定的基础。