实验4 稀疏矩阵基本操作-链接结构.doc

浙江大学城市学院实验报告课程名称 数据结构与算法 实验项目名称 实验四 稀疏矩阵的基本操作-用链接存储结构 学生姓名 蓝礼巍 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1了解稀疏矩阵的三元组线性表存储方法。2掌握稀疏矩阵采用链式存储结构时基本操作的实现。二. 实验内容1 编写稀疏矩阵采用带行指针向量的链接存储结构时基本操作的实现函数。基本操作包括：初始化稀疏矩阵；输入稀疏矩阵；输出稀疏矩阵；稀疏矩阵的转置运算。要求把稀疏矩阵的存储结构定义及基本操作实现函数存放在头文件LinkMatrix.h中，主函数main() 存放在主文件test7_2.cpp中，在主函数中通过调用LinkMatrix.h中的函数进行测试。2 选做：编写稀疏矩阵的相乘运算实现函数，要求把该函数添加到头文件LinkMatrix.h中，并在主文件test7_2.cpp中添加相应语句进行测试。 3 填写实验报告，实验报告文件取名为report4.doc。4 上传实验报告文件report4.doc与源程序文件LinkMatrix.h及test7_2.cpp到Ftp服务器上你自己的文件夹下。三. 函数的功能说明及算法思路 包括每个函数的功能说明，及一些重要函数的算法实现思路初始化稀疏矩阵；void InitMatrix(LMatrix &M)输入稀疏矩阵；void InputMatrix(LMatrix &M,int m,int n)输出稀疏矩阵；void OutputMatrix(LMatrix M)稀疏矩阵的转置运算。LMatrix Transpose(LMatrix M)稀疏矩阵的相乘运算实现函数 LMatrix Multiply(LMatrix M1,LMatrix M2)四. 实验结果与分析包括运行结果截图等五. 心得体会记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。【附录-源程序】Cpp：/*1编写稀疏矩阵采用带行指针向量的链接存储结构时基本操作的实现函数。基本操作包括：初始化稀疏矩阵；输入稀疏矩阵；输出稀疏矩阵；稀疏矩阵的转置运算。要求把稀疏矩阵的存储结构定义及基本操作实现函数存放在头文件LinkMatrix.h中，主函数main() 存放在主文件test7_2.cpp中，在主函数中通过调用LinkMatrix.h中的函数进行测试。选做：编写稀疏矩阵的相乘运算实现函数，要求把该函数添加到头文件LinkMatrix.h中，并在主文件test7_2.cpp中添加相应语句进行测试。*/#include#include#includeLinkMatrix.hvoid main()LMatrix M;InitMatrix(M);int m,n;coutm;coutendl;coutn;coutendl;cout输入row col val！ 以输入 0 0 0结束: endl;InputMatrix(M,m,n);cout输出 Mendl;OutputMatrix( M);coutendl;cout输出 M的转置endl;OutputMatrix(Transpose(M);coutendl;LMatrix M1; InitMatrix(M1);coutm;coutendl;coutn;coutendl;cout输入row col val！ 已输入 0 0 0结束: endl;InputMatrix(M1,m,n);cout输出 M1endl;OutputMatrix( M1);coutendl;cout输出 M 和M1之和endl;Add(M,M1);coutendl;cout输出 M 和M1之积endl;Multiply( M, M1);coutendl;H:typedef int ElemType;#define MaxRows 100typedef struct Nodeint row ,col;ElemType val;struct Node *next;TripleNode;typedef structint m,n,t;TripleNode *vectorMaxRows+1;LMatrix;void InitMatrix(LMatrix &M)M.m=0;M.n=0;M.t=0;for(int i=1;irowcolval;while(row!=0)k+;p=new TripleNode;p-row=row;p-col=col;p-val=val;p-next=NULL;q=M.vectorrow;if(q=NULL)M.vectorrow=p;elsewhile(q-next!=NULL)q=q-next;q-next=p;cinrowcolval;M.m=m;M.n=n;M.t=k;void OutputMatrix(LMatrix M)int t;t=M.t;cout(;for(int i=1;i=M.m;i+)while(M.vectori!=NULL)cout(row,;coutcol,;coutval0)coutnext;cout);LMatrix Transpose(LMatrix M)LMatrix L;InitMatrix(L);L.m=M.m;L.n=M.n;L.t=M.t;if(L.t=0)return L;TripleNode *q,*p,*newptr;int col=1;while(col=M.m)for(int i=1;icol=col)newptr=new TripleNode;newptr-row=p-col;newptr-col=p-row;newptr-val=p-val;newptr-next=NULL;q=L.vectorcol;if(q=NULL)L.vectorcol=newptr;elsewhile(q-next!=NULL)q=q-next;q-next=newptr;p=p-next;col+;return L;LMatrix Add(LMatrix M1,LMatrix M2)LMatrix M;InitMatrix(M);if(M1.m!=M2.m)|(M1.n!=M2.n)cerrcuo leendl;exit(1);M.m=M1.m;M.n=M1.n;if(M1.t=0)&(M2.t=0)return M;int k=0;for(int i=1;icolcol)*newptr=*p1;p1=p1-next;else if(p1-colp2-col)*newptr=*p2;p2=p2-next;else*newptr=*p1;newptr-val+=p2-val;p1=p1-next;p2=p2-next;newptr-next=NULL;if(p=NULL)M.vectori=newptr;elsep-next=newptr;p=newptr;k+;while(p1!=NULL)TripleNode *newptr=new TripleNode;*newptr=*p1;newptr-next=NULL;if(p=NULL)M.vectori=newptr;elsep-next=newptr;p=newptr;p1=p1-next;k+;while(p2!=NULL)TripleNode *newptr=new TripleNode;*newptr=*p2;newptr-next=NULL;if(p=NULL)M.vectori=newptr;elsep-next=newptr;p=newptr;p2=p2-next;k+;M.t=k;OutputMatrix(M); return M;LMatrix Multiply(LMatrix M1,LMatrix M2)LMatrix M;InitMatrix(M);if(M1.m!=M2.m)|(M1.n!=M2.n)cerrcuo leendl;exit(1);M.m=M1.m;M.n=M1.n;if(M1.t=0)&(M2.t=0)return M;int k=0;for(int i=1;icol=p2-col)*newptr=*p1;newptr-val*=