稀疏矩阵的应用

1、武 汉 工 程 大 学计算机科学与工程学院数据结构实验报告专业班级实验地点学生学号指导教师学生姓名实验时间实验项目实验类别操作性（）验证性（ ）设计性（ ）综合性（ y ）其它（ ）实验（ 1）掌握掌握稀疏矩阵的表示方法及其运算的实现；目求（ 2）实现稀疏矩阵在三元组、 十字链表等表示下的各运算并分析其效率。的及要成 绩 评 定 表类别评 分 标 准分值得分合计上机表现积极出勤、遵守纪律30分认真完成实验任务报告质量程序代码规范、功能正确70分填写内容完整、体现收获说明：评阅教师：日 期：年月日稀疏矩阵的应用1、实验目的：（ 1）掌握掌握稀疏矩阵的表示方法及其运算的实现；（ 2）实现稀疏矩阵在

2、三元组、十字链表等表示下的各运算并分析其效率。2、实验内容在 m n 的矩阵中， 有 t 个非零元。 令 = t/(m*n),称矩阵的稀疏因子，常认为 0.05时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。 用三元组表实现稀疏矩阵的转置，用（顺序取，直接存）方法。3、实验说明：引入两个数组作为辅助数据结构：numnu ：表示矩阵a 中某列的非零元素的个数；cpotnu：初始值表示矩阵a中某列的第一个非零元素在b 中的位置。num与 cpot 递推关系：cpot0=0 ；cpotcol=cpotcol - 1+numcol - 1；1 col nu

3、1. 实验分析：在本次实验当中，需要注意一下几个关键点：1. 设置转置后矩阵 b 的行数、列数和非零元素的个数；2. 计算 a 中每一列的非零元素个数；3.计算 a 中每一列的第一个非零元素在b 中的下标；4. 依次取 a 中的每一个非零元素对应的三元组；2.1确定该元素在b 中的下标pb；2.2将该元素的行号列号交换后存入b 中 pb 的位置；2.3预置该元素所在列的下一个元素的存放位置；具体要定义如下若干个函数：void setup（）初始化非零元的个数void transition（）转置函数void inputvoid print1()void print2()（）输入函数输出函数输出

4、函数2. 源程序代码：#includeusing namespace std;#include #define maxsize 50typedef int datatype;typedef structintp,q;datatype x; list; typedef structint md,nd,td; tabletype;int n,m;/*稀疏矩阵的行数、列数*/void input(datatype amaxsizemaxsize );void setup (datatype amaxsizemaxsize, list ta,tabletype *ta1 ); void transit

5、ion (tabletype *ta1, tabletype *tb1, list ta,list tb); void print1(datatype amaxsizemaxsize);void print2(list a,int nn);int main( )datatype amaxsizemaxsize; list tamaxsize,tbmaxsize;/*/*稀疏矩阵 */三元组顺序表*/tabletype *ta1,*tb1;if (ta1=(tabletype *)malloc(sizeof(tabletype)=null)cout 申请空间错误！n;return 0;if (t

6、b1=(tabletype *)malloc(sizeof(tabletype)=null)cout 申请空间错误！n;return 0;input(a);setup(a,ta,ta1);transition(ta1, tb1, ta,tb);coutn原稀疏矩阵为：n;print1(a );couttd);couttd);return 1; /* 输入 */void input(datatype amaxsizemaxsize )int i,j;coutn;coutm;for(i=0;in;i+)for(j=0;jaij;/* 建立 */void setup (datatype amaxsi

7、zemaxsize, list ta, tabletype *ta1)int i,j;ta1-td=0;/*初始化非零元素个数*/for(i=0; in;i+)for(j=0;jtd.p=i;tata1-td.q=j;tata1-td.x=aij;ta1-td+;ta1-md=n;ta1-nd=m;/* 转置 */void transition (tabletype *ta1, tabletype *tb1, list ta,list tb)int i,j,nn=0;tb1-md=ta1-nd;tb1-nd=ta1-md;tb1-td=ta1-td;if(ta1-td!=0)for (i=0;

8、ind;i+)/*i原矩阵的列下标*/for(j=0;jtd;j+)/*j原三元组顺序表的下标*/if(taj.q=i)/*寻找原矩阵中最小列下标*/tbnn.p=taj.q;tbnn.q=taj.p;tbnn.x=taj.x;nn+;/* 矩阵输出 */void print1(datatype amaxsizemaxsize)int i,j;for(i=0; in;i+) for(j=0;jm;j+)coutaij ;coutn;/* 三元组顺序表输出*/void print2(list a,int nn)int i;coutt行号 t列号 t元素值 n;for(i=0; inn;i+)coutai.pai.qai.xn;coutn;实 验 内 容3. 测试用例：1, 当输入原稀疏矩阵为a33=2,0,3;1,0,4;0,0,1时程序运行结果如下：2. 当输入稀疏矩阵为a22=1,0;0,2时运行结果如下：实 验 内 容实 验 总 结4. 实验总结：针对稀疏矩阵的压缩存储应用， 通过本次实验对它有一定的系统了解， 在这次实验的的过程当中起初有很多问题比较疑惑， 甚至根本动不了手， 但是通过