魏伟实验报告.doc

《魏伟实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机科学与工程学院《算法与数据结构》实验报告(五)专业班级2013级计算机工程专业02班实验地点403机房学生学号1305120617指导教师蔡琼学生姓名魏伟实验时间2015-05-02实验工程稀疏矩阵的应用实验类别基础性（√）设计性（）综合性（）其它（）实验目的及要求（1）掌握掌握稀疏矩阵的表示方法及其运算的实现；（2）实现稀疏矩阵在三元组、十字链表等表示下的各运算并分析其效率。成绩评定表类别评分规范分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明：评阅教师：蔡琼日期：2015年5月9日实

2、验内容7/7实验内容在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＜nu三元组表实现稀疏矩阵的转置

3、（顺序取，直接存）算法伪代码如下：1.设置转置后矩阵B的行数、列数和非零元素的个数；2.计算A中每一列的非零元素个数；3.计算A中每一列的第一个非零元素在B中的下标；4.依次取A中的每一个非零元素对应的三元组；2.1确定该元素在B中的下标pb；2.2将该元素的行号列号交换后存入B中pb的位置；2.3预置该元素所在列的下一个元素的存放位置；存储一个稀疏矩阵需要定义一个三元组和三元组顺序表，三元组存储稀疏矩阵中非零元素的行坐标，列坐标和元素值（规定行列下标值从0开始），而三元组顺序表里则存储稀疏矩阵的行数，列数和非零元素的个数及其数值。在实现矩阵转置的函数中，定义一个新的三

4、元组顺序表用于存放转置后的矩阵，用A表示要转置的稀疏矩阵，B表示转置后的矩阵，则B的行数等于A的列数，列数等于A的行数，再从A中定位到每个非零元素，将其行坐标和列坐标对换后存入B中即实现了整个过程，最后输出转置后的矩阵。系统共设置了8个子程序，各子程序的函数名及功能说明如下。 （1）CreateSMatrix(RLSMatrix &M) //创建稀疏矩阵 （2）void DestroySMatrix(RLSMatrix &M) 销毁稀疏矩阵 （3）void PrinRLSMatrix(RLSMatrix M) 遍历稀疏矩阵 （4）void print(RLSMatrix

5、 A) /打印矩阵函数，输出以阵列形式表示的矩阵7/7 （5）ransposeSMatrix(RLSMatrix M,RLSMatrix &T) //求稀疏矩阵的转置的一般算法 （6）FastTransposeSMatrix(RLSMatrix M,RLSMatrix &T) /快速转置算法 （7）void showtip()//工作区函数，显示程序菜单  （8）void main() 主函数预期结果5         0   0   70         1  0   01         0   0   0      可以用三元组表示为：  3   4   4   

6、                                                               1   1   5                                                                           1   4   7                                                                  2   2   1                                                         

7、         3   1   1源代码#include#defineM50#defineN50#defineMaxSize125typedefstruct{intr。intc。intd。}TupNode。typedefstruct{introws。intcols。intnums。7/7TupNodedata[MaxSize]。}TSMatrix。voidTranMat(TSMatrixa,TSMatrix&b)。voidGetMat(TSMatrix&a)。voidPriMat(TSMatrixa)。voidmain