2023年魏伟实验报告

计算机科学与工程学院《算法与数据结构》实验报告（五）专业班级2023级计算机工程专业02班实验地点403机房学生学号指导教师蔡琼学生姓名魏伟实验时间2023-05-02实验项目稀疏矩阵的应用实验类别基础性（J）设计性（）综合性0其它（）（1）掌握掌握稀疏矩阵的表达方法及其运算的实现；头认楮ilb儿龙牛仕—兀羽■、1子斑仔Tt■衣0卜刖骨■汪舁JT勿析其效率。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按规定完毕设计任务30分程序与报告程序代码规范、功能对的报告详实完整、体现收获70分说明：评阅教师：蔡琼A日期：2023年5月9日实验内容实验内容在mXn的矩阵中，有t个非零元。令8=t/(m*n),称5矩阵的稀疏因子,常认为6<0.05时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。用三元组表实现稀疏矩阵的转置，用(顺序取，直接存)方法。实验说明：引入两个数组作为辅助数据结构：onum[nu]:表达矩阵A中某列的非零元素的个数；-cpot[nu上初始值表达矩阵A中某列的第一个非零元素在B中的位置。3num与cpot递推关系：cpot[0]=0；0Ycpot[colJ=cpo([col-1]+num[col-1]；三元组表实现稀疏矩阵的转置(顺序取,直接存)算法伪代码如下：L设立转置后矩阵B的行数、列数和非零元素的个数；.计算A中每一列的非零元素个数：.计算A中每一列的第一个非零元素在B中的下标；.依次取A中的每一个非零元素相应的三元组：拟定该元素在B中的下标pb；将该元素的行号列号互换后存入B中pb的位置;预置该元素所在列的下一个元素的存放位置：存储一个稀疏矩阵需要定义一个三元组和三元组顺序表，三元组存储稀疏矩阵中非零元素的行坐标,列坐标和元素值(规定行列下标值从。开始)，而三元组顺序表里则存储稀疏矩阵的行数，列数和非零元素的个数及其数值。在实现矩阵转置的函数中，定义一个新的三元组顺序表用于存放转置后的矩阵，用A表达要转置的稀疏矩阵，B表达转置后的矩阵，则B的行数等于A的列数，列数等于A的行数，再从A中定位到每个非零元素，将其行坐标和列坐标对换后存入B中即实现了整个过程，最后输出转置后的矩阵。系统共设立了8个子程序，各子程序的函数名及功能说明如下。(1)CreateSMatrix(RLSMatrix&M)//创建稀疏矩阵(2)voidDestroySMatrix(RLSMairix&M)销毁稀疏矩阵voidPrinRLSMatrix(RLSMatrixM)遍历稀疏矩阵voidprint(RLSMatrixA)/打印矩阵函数，输出以阵列形式表达的矩阵(5)ransposeSMatrix(RLSMatrixM,RLSMatrix&T)//求稀疏矩阵的转置的一般算法(6)FastTransposeSMatrix(RLSMatrixM,RLSMatrix&T)/快速转置算法(7)voidshowtip()〃工作区函数,显示程序菜单(8)voidmain()主函数预期结果TOC\o"1-5"\h\z500701001000可以用三元组表达为：344115472111源代码inc1ude<stdio.h>^defineM50defineN50'defineMaxSize125typedefstruct(intr;®intc;intd；}TupNode;typedefstruct(。introws；ointco1s；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);叩rintf(〃通过转置后得到的矩阵的为:\n〃);PriMat(b);}voidTranMat(TSMatrixa,TSMatrix&b)(<>inte;«>b.rows=a.co1s;3b.cols=a.rows;。b.nums=a.nums;intn[N]={0}；intcpot[N]={0};for(intj=0；j<a.nums；j++)8n[a.data[j].c]++；for(inti=2;i<=a.cols;i++)®cpot[i]=cpot[i—1]+n[i-1];for(i=0；i<a.nums；i++)°{。intcol=a.dataLi],c;<»e=cpot[co1];4).data[e].c=a.data[i].r;8b.data[e].r=a.data[i].c;b.data[e].d=a.data[i].d;«>cpot[co1]++;°}}voidGetMat(TSMatrix&a)(叩rintf("请输入稀疏矩阵中非零元素的个数n：〃)；scanf("%dz，,&a.nums);叩rintf(〃请依次输入稀疏矩阵的行数和列数:〃)；scanf("%d%d”,&a,rows,&a,cols)；叩rintf(〃请按照三元组行、歹I」、值的方式依次输入该稀疏矩阵:\n〃)；for(inti=0;i<a.nums；i++)©scanf("%d%d%d”,&a.data[i],r,&a.data[i].c,&a.data[i].d)；}}voidPriMat(TSMatrixa)(inti;叩rintf(〃\t%d行\t%d歹U\n",a.rows,a.cols)；printf("\n〃)；叩rintf(〃\t行\t列\t值\n”)；for(i=0；i<a.nums;i++)aprintf(〃\t%d\t%d\t%d\n，z,a.data[i].r,a.data[i].c,a.data[i].d);叩rintf(〃\