稀疏矩阵的应用

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； 1colnu1.实验分

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

4、ude<iostream>using namespace std;#include <malloc.h>#define maxsize 50typedef int datatype;typedef struct int p,q;datatype x; List;typedef structint md,nd,td; tabletype;int n,m; /*稀疏矩阵的行数、列数*/ void input(datatype amaxsizemaxsize );void setup (datatype amaxsizemaxsize, List ta,tabletype *

5、ta1 );void transition (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<&

6、lt;"申请空间错误！n"return 0; if (tb1=(tabletype *)malloc(sizeof(tabletype)=NULL) cout<<"申请空间错误！n"return 0; input(a);setup(a,ta,ta1);transition(ta1, tb1, ta,tb);cout<<"n原稀疏矩阵为：n"print1(a );cout<<"n原三元组顺序表为：n"print2(ta,ta1->td);cout<<"n

7、转置后的三元组顺序表：n"print2(tb, tb1->td);return 1; /*输入*/void input(datatype amaxsizemaxsize ) int i,j;cout<<"n请输入稀疏矩阵的行数"cin>>n;cout<<"n请输入稀疏矩阵的列数"cin>>m;for(i=0;i<n;i+)for(j=0;j<m;j+) printf("n请输入数据a%d%d=",i,j);cin>>aij;/*建立*/void s

8、etup (datatype amaxsizemaxsize, List ta, tabletype *ta1) int i,j;ta1->td=0; /*初始化非零元素个数*/for(i=0; i<n;i+)for(j=0;j<m;j+)if (aij!=0) tata1->td.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,Lis

9、t 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;i<ta1->nd;i+) /*i 原矩阵的列下标*/for(j=0;j< ta1->td;j+) /*j 原三元组顺序表的下标*/ if(taj.q=i) /*寻找原矩阵中最小列下标*/ tbnn.p=taj.q;tbnn.q=taj.p;tbnn.x=taj.x;nn+; /*矩阵输出*/void print1(datatype amaxsizem

10、axsize) int i,j;for(i=0; i<n;i+) for(j=0;j<m;j+)cout<<aij<<" "cout<<"n" /*三元组顺序表输出*/void print2(List a,int nn) int i;cout<<"t行号t列号t元素值n"for(i=0; i<nn;i+)cout<<" "<<ai.p<<" "<<ai.q<<" "<<ai.x<<" "<<"n" cout<<"n"实 验 内 容3.测试用例：1,当输入原稀疏矩阵为A33=2,0,3;1,0,4;0,0,1时程序运行结果如下：2.当输入稀疏矩阵为A22=1,0;0,2时运行结果如