稀疏矩阵的应用

稀疏矩阵的应用 计算机科学与工程学院 《数据结构》实验报告 专业班级 实验地点 学生学号 指导教师 学生姓名 实验时间 实验项目 实验类别 操作性()验证性( )设计性( )综合性(Y )其它( ) 实 验(1)掌握掌握稀疏矩阵的示方法及其运算的实现; 目求(2)实现稀疏矩阵在三元组、十字链表等表示下的各运算并其效率。 的 及 要 成 绩 评 定 表 类 别 评 分 标 准 分值 得分 合 计 积极出勤、遵守纪律 上机表现 30分 认真完成实验任务 程序代码、功能正确 报告质量 70分 填写内容完整、体现收获 说明: 评阅教师: 日 期: 年 月 日 计算机科学与工程学院 稀疏矩阵的应用 1、实验目的: (1)掌握掌握稀疏矩阵的表示方法及其运算的实现; (2)实现稀疏矩阵在三元组、十字链表等表示下的各运算并分析其效率。 2、实验内容 在m×n 的矩阵中，有t个非零元。令δ= t/(m*n),称δ矩阵的稀疏因子， 常认为δ?0.05时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用，不少 工程问题都可以转化为对稀疏矩阵的计算问题。用三元组表实现稀疏矩阵的转 置，用(顺序取，直接存)方法。 3、实验说明: 引入两个数组作为辅助数据结构: num[nu]:表示矩阵A中某列的非零元素的个数; cpot[nu]:初始值表示矩阵A中某列的第一个非零元素在B中的位置。 num与cpot递推关系: cpot[0]=0; cpot[col]=cpot[col-1]+num[col-1]; 1?col,nu 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 input()输入函数 void print1()输出函数 void print2()输出函数 2 《计算机程序设计基础》实验报告 计算机科学与工程学院 2.源程序代码: #include using namespace std; #include #define maxsize 50 typedef int datatype; typedef struct { int p,q; datatype x; } List; typedef struct { int md,nd,td; }tabletype; int n,m; /*稀疏矩阵的行数、列数*/ void input(datatype a[maxsize][maxsize] ); void setup (datatype a[maxsize][maxsize], List ta[],tabletype *ta1 ); void transition (tabletype *ta1, tabletype *tb1, List ta[],List tb[]); void print1(datatype a[maxsize][maxsize]); void print2(List a[],int nn); int main( ) { datatype a[maxsize][maxsize]; /*稀疏矩阵*/ List ta[maxsize],tb[maxsize]; /*三元组顺序表*/ tabletype *ta1,*tb1; if ((ta1=(tabletype *)malloc(sizeof(tabletype)))==NULL) { cout<<"申请空间错误～\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"; 3 《计算机程序设计基础》实验报告 计算机科学与工程学院 print2(ta,ta1->td); cout<<"\n转置后的三元组顺序表:\n"; print2(tb, tb1->td); return 1; } /*输入*/ void input(datatype a[maxsize][maxsize] ) { int i,j; cout<<"\n请输入稀疏矩阵的行数,"; cin>>n; cout<<"\n请输入稀疏矩阵的列数,"; cin>>m; for(i=0;i