1305120411_何彬_实验报告05

计算机科学与工程学院《算法与数据结构》实验报告(五)专业班级2013网络工程01实验地点423机房学生学号指导教师赵卿松学生姓名实验时间实验项目稀疏矩阵的应用实验类别基础性（√）设计性（）综合性（）其它（）实验目的及要求（1）掌握掌握稀疏矩阵的表示方法及其运算的实现；（2）实现稀疏矩阵在三元组、十字链表等表示下的各运算并分析其效率。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明：评阅教师：赵卿松日期：2015年5月9日计算机科学与工程学院《算法与数据结构》实验报告2实验内容实验内容在m×n的矩阵中，有t个非零元。令δ=t/(m*n),称δ矩阵的稀疏因子，常认为δ≤0.05时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。用三元组表实现稀疏矩阵的转置，用（顺序取，直接存）方法。实验说明：引入两个数组作为辅助数据结构：num[nu]：表示矩阵A中某列的非零元素的个数；cpot[nu]：初始值表示矩阵A中某列的第一个非零元素在B中的位置。num与cpot递推关系：三元组表实现稀疏矩阵的转置（顺序取，直接存）算法伪代码如下：cpot[0]=0；cpot[col]=cpot[col-1]+num[col-1]；1≤col＜nu1.设置转置后矩阵B的行数、列数和非零元素的个数；2.计算A中每一列的非零元素个数；3.计算A中每一列的第一个非零元素在B中的下标；4.依次取A中的每一个非零元素对应的三元组；2.1确定该元素在B中的下标pb；2.2将该元素的行号列号交换后存入B中pb的位置；2.3预置该元素所在列的下一个元素的存放位置；计算机科学与工程学院《算法与数据结构》实验报告3实验内容#includestdio.h#defineM50#defineN50#defineMaxSize125typedefstruct{intr;//行号intc;//列号intd;//元素值}TupNode;typedefstruct{introws;//行intcols;//列intnums;TupNodedata[MaxSize];}TSMatrix;voidTranMat(TSMatrixa,TSMatrix&b);voidGetMat(TSMatrix&a);voidPriMat(TSMatrixa);voidmain(){TSMatrixa,b;GetMat(a);TranMat(a,b);printf(您输入的矩阵的为：\n);PriMat(a);printf(经过转置后得到的矩阵的为：\n);PriMat(b);}voidTranMat(TSMatrixa,TSMatrix&b){inte;b.rows=a.cols;b.cols=a.rows;b.nums=a.nums;intn[N]={0};//计算每一列a中的非零元素的个数intcpot[N]={0};//a中某列的非零元素在b中的位置for(intj=0;ja.nums;j++)计算机科学与工程学院《算法与数据结构》实验报告4n[a.data[j].c]++;for(inti=2;i=a.cols;i++)cpot[i]=cpot[i-1]+n[i-1];for(i=0;ia.nums;i++){intcol=a.data[i].c;e=cpot[col];b.data[e].c=a.data[i].r;b.data[e].r=a.data[i].c;b.data[e].d=a.data[i].d;cpot[col]++;}}voidGetMat(TSMatrix&a){printf(请输入稀疏矩阵中非零元素的个数n：);scanf(%d,&a.nums);printf(请依次输入稀疏矩阵的行数和列数：);scanf(%d%d,&a.rows,&a.cols);printf(请按照三元组行、列、值的方式依次输入该稀疏矩阵：\n);for(inti=0;ia.nums;i++){scanf(%d%d%d,&a.data[i].r,&a.data[i].c,&a.data[i].d);}}voidPriMat(TSMatrixa){inti;printf(\t%d行\t%d列\n,a.rows,a.cols);printf(-------------------------\n);printf(\t行\t列\t值\n);for(i=0;ia.nums;i++)printf(\t%d\t%d\t%d\n,a.data[i].r,a.data[i].c,a.data[i].d);printf(-------------------------\n);}计算机科学与工程学院《算法与数据结构》实验报告5实验内容计算机科学与工程学院《算法与数据结构》实验报告6实验总结通过这次上机实验，熟知了通过三元组的方式对稀疏矩阵的压缩存储。在对稀疏矩阵进行转置运算时，书上P121有一种算法，这种算法的时间复杂度是O(m*n),通过对实验指导书的观察，发现了一种比较好的快速转置的算法，时间复杂度只有O(n+t),算法更为巧妙。很好的通过设置的两个变量num和spot，它们之间的递归关系，再完成对稀疏矩阵的转置运算