【数据结构算法】实验3稀疏矩阵基本操作顺序结构(附源代码).pdf

《【数据结构算法】实验3稀疏矩阵基本操作顺序结构(附源代码).pdf》由会员分享，可在线阅读，更多相关《【数据结构算法】实验3稀疏矩阵基本操作顺序结构(附源代码).pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 浙江大学城市学院实验报告 课程名称 数据结构与算法 实验项目名称 实验三 稀疏矩阵的基本操作-用顺序存储结构 实验成绩 指导老师（签名）日期 一.实验目的和要求 1了解稀疏矩阵的三元组线性表存储方法。2掌握稀疏矩阵采用顺序存储结构时基本操作的实现。二.实验内容 1 编写稀疏矩阵采用顺序存储结构时基本操作的实现函数。基本操作包括：初始化稀疏矩阵；输入稀疏矩阵；输出稀疏矩阵；稀疏矩阵的相加运算。要求把稀疏矩阵的存储结构定义及基本操作实现函数存放在头文件SeqMatrix.h 中，主函数 main()存放在主文件 test7_1.cpp 中，在主函数中通过调用 SeqMatrix.h 中的函数进行

2、测试。2 选做：编写稀疏矩阵的相乘运算实现函数，要求把该函数添加到头文件SeqMatrix.h 中，并在主文件 test7_1.cpp 中添加相应语句进行测试。3 填写实验报告，实验报告文件取名为 report3.doc。4 上传实验报告文件 report3.doc 与源程序文件 SeqMatrix.h 及test7_1.cpp 到 Ftp 服务器上你自己的文件夹下。三.函数的功能说明及算法思路 包括每个函数的功能说明，及一些重要函数的算法实现思路 函数：void InitMatrix(SMatrix&M)功能：初始化稀疏矩阵 思路：将稀疏矩阵的行、列、元素个数均置为0 函数：void Inp

3、utMatrix(SMatrix&M,int m,int n)功能：输入稀疏矩阵 思路：以行、列、值的方式输入稀疏矩阵的每个元素 函数：void OutputMatrix(SMatrix M)功能：输出稀疏矩阵 思路：以行、列、值的方式输出稀疏矩阵的每个元素 函数：SMatrix Add(SMatrix M1,SMatrix M2)功能：稀疏矩阵的相加运算 思路：遍历 M1 与 M2，若两者的当前元素行列号相等则将值相加，形成新的元素加入结果矩阵 M（若为 0 则忽略），若不相等则按行列号顺序将小的那个加入结果矩阵 M 函数：SMatrix Multiply(SMatrix M1,SMatri

4、x M2)功能：选作：稀疏矩阵的相乘运算 思路：嵌套遍历 M1 与 M2，当 M1 的当前元素列号与 M2 的当前元素行号相等时相乘两个数，并将结果暂存入单链表。遍历保存结果的单链表，对单链表内元素按行号（实际行号已有序）、列号从小到大排序，同时，判断是否有属于结果矩阵同一个元素的结点，将他们的值加至同一个结点。每结束一个结点的遍历，该值确定，加入结果矩阵 M 中 四.实验结果与分析 包括运行结果截图等 测试数据：M1、M2 如图所示-10 2 7 M1 M2 结果分析：相加结果 M 如图所示，正确-10 3 -1 22 3 -2 -1 15 测试数据：M1、M2 如图所示 8 8 6 M1

5、M2 结果分析：相乘结果 M 如图所示，正确 84 70 测试数据：M1、M2 如图所示 5 2 1 3 6 5 7 15 -1 -2 21 M1 M2 结果分析：相加结果 M 如图所示，正确 9 5 15 -1 21 4 11 测试数据：M1、M2 如图所示 M1 M2 结果分析：相乘结果 M 如图所示，正确 2 5 1 4 11 0 2 3 1 1 2 1 1 2 0 1 3 5 0 4 6 五.心得体会 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。【附录-源程序】Test7_1.cpp#include#include#include#includeSeqMat

6、rix.h void main()SMatrix M1,M2,M;int m,n;InitMatrix(M1);coutmn;cout-M1-endl;InputMatrix(M1,m,n);InitMatrix(M2);cout-M2-endl;InputMatrix(M2,m,n);cout-M1+M2-endl;OutputMatrix(Add(M1,M2);coutendl*以下为选作部分*endlendl;InitMatrix(M1);cout-M1-endl;coutmn;InputMatrix(M1,m,n);InitMatrix(M2);cout-M2-endl;coutmn;

7、InputMatrix(M2,m,n);M=Multiply(M1,M2);cout-M1*M2-endl;cout行数：M.m 列数：M.nendl;OutputMatrix(M);SeqMatrix.h#define MaxTerms 100 typedef int ElemType;typedef struct int row,col;ElemType val;Triple;typedef struct int m,n,t;Triple smMaxTerms+1;SMatrix;struct LNode Triple t;LNode*next;/初始化稀疏矩阵 void InitMatr

8、ix(SMatrix&M)M.m=0;M.n=0;M.t=0;/输入稀疏矩阵 void InputMatrix(SMatrix&M,int m,int n)int k=0;int row,col,val;M.m=m;M.n=n;cout请输入 row,col,val,以 0 0 0 结尾：rowcolval;while(row!=0)k+;M.smk.row=row;M.smk.col=col;M.smk.val=val;cinrowcolval;M.t=k;/输出稀疏矩阵 void OutputMatrix(SMatrix M)int k=1;cout 1)cout(M.smk.row,M.

9、smk.col,M.smk.val),;k+;cout(M.smk.row,M.smk.col,M.smk.val)endl;/稀疏矩阵的相加运算 SMatrix Add(SMatrix M1,SMatrix M2)int k1=1,k2=1;SMatrix M;Triple t;InitMatrix(M);if(M1.m!=M2.m)|(M1.n!=M2.n)cerrtow Matrix measurenents are different!endl;exit(1);M.m=M1.m;M.n=M1.n;while(k1=M1.t&k2=M2.t)if(M1.smk1.row=M2.smk2.

10、row&M1.smk1.col=M2.smk2.col)t.val=M1.smk1.val+M2.smk2.val;if(t.val)t.row=M1.smk1.row;t.col=M1.smk1.col;M.sm+M.t=t;k1+;k2+;else if(M1.smk1.row=M2.smk2.row)M.sm+M.t=M1.smk1.col M2.smk2.col?M1.smk1+:M2.smk2+;else M.sm+M.t=M1.smk1.row M2.smk2.row?M1.smk1+:M2.smk2+;while(k1=M1.t)M.sm+M.t=M1.smk1;k1+;whil

11、e(k2=M2.t)M.sm+M.t=M2.smk2;k2+;return M;/选作：稀疏矩阵的相乘运算 SMatrix Multiply(SMatrix M1,SMatrix M2)int k1=1,k2=1;LNode*L,*p,*T;SMatrix M;InitMatrix(M);if(M1.n!=M2.m)cerrtow Matrix measurenents are different!next=NULL;p=L;/嵌套遍历 M1 与 M2，当 M1 的当前元素列号与 M2 的当前元素行号相等时 /相乘两个数，并将结果暂存入单链表 while(k1=M1.t)while(M2.sm

12、k2.row=M1.smk1.col&k2 t.row=M1.smk1.row;T-t.col=M2.smk2.col;T-t.val=M1.smk1.val*M2.smk2+.val;T-next=NULL;p-next=T;p=T;else k2+;k2=1;k1+;L=L-next;p=L;/遍历保存结果的单链表 /对单链表内元素按行号（实际行号已有序）、列号从小到大排序 /同时，判断是否有属于结果矩阵同一个元素的结点，将他们的值加至同一个结点 /每结束一个结点的遍历，该值确定，加入结果矩阵 M 中 while(p!=NULL)if(p-t.val=0)p=p-next;continue;T=p-next;while(T!=NULL&T-t.row=p-t.row)while(T!=NULL&T-t.val=0)T=T-next;if(T-t.col t.col)Triple temp;temp=p-t;p-t=T-t;T-t=temp;T=p-next;else if(T-t.col=p-t.col)p-t.val+=T-t.val;T-t.val=0;T=T-next;else T=T-next;M.sm+M.t=p-t;p=p-next;return M;