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

浙江大学城市学院实验报告

课程名称 数据结构与算法 实验项目名称 实验三 稀疏矩阵的基本操作--用顺序存储结构 实验成绩 指导老师（签名 ） 日期

一. 实验目的和要求

1．了解稀疏矩阵的三元组线性表存储方法。

2．掌握稀疏矩阵采用顺序存储结构时基本操作的实现。

二. 实验内容

1． 编写稀疏矩阵采用顺序存储结构时基本操作的实现函数。基本操作包括：①初始化稀疏矩阵；②输入稀疏矩阵；③输出稀疏矩阵；④稀疏矩阵的相加运算。要求把稀疏矩阵的存储结构定义及基本操作实现函数存放在头文件SeqMatrix.h中，主函数main() 存放在主文件test7_1.cpp中，在主函数中通过调用SeqMatrix.h中的函数进行测试。

2． 选做：编写稀疏矩阵的相乘运算实现函数，要求把该函数添加到头文件SeqMatrix.h中，并在主文件test7_1.cpp中添加相应语句进行测试。 3． 填写实验报告，实验报告文件取名为report3.doc。

4． 上传实验报告文件report3.doc与源程序文件SeqMatrix.h及test7_1.cpp到Ftp服务器上你自己的文件夹下。

三. 函数的功能说明及算法思路

包括每个函数的功能说明，及一些重要函数的算法实现思路

函数：void InitMatrix(SMatrix &M) 功能：初始化稀疏矩阵

思路：将稀疏矩阵的行、列、元素个数均置为0

函数：void InputMatrix(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, SMatrix M2) 功能：选作：稀疏矩阵的相乘运算

思路：嵌套遍历M1与M2，当M1的当前元素列号与M2的当前元素行号相等时相乘两个数，并将结果暂存入单链表。遍历保存结果的单链表，对单链表内元素按行号（实际行号已有序）、列号从小到大排序，同时，判断是否有属于结果矩阵同一个元素的结点，将他们的值加至同一个结点。每结束一个结点的遍历，该值确定，加入结果矩阵M中

四. 实验结果与分析

包括运行结果截图等

结果分析：相加结果M

M2

测试数据：M1、M2如图所示

M1 结果分析：相乘结果

M如图所示，正确

M2

测试数据：M1、M2如图所示

M2

M1

结果分析：相加结果M如图所示，正确

测试数据：M1、M2如图所示

M1

结果分析：相乘结果M如图所示，正确

M2

五. 心得体会

记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。

【附录----源程序】 [Test7_1.cpp] #include<stdio.h> #include<iostream.h> #include<stdlib.h>

#include"SeqMatrix.h"

void main() {

SMatrix M1,M2,M; int m,n;

InitMatrix(M1);

cout<<"请输入相加矩阵的行数与列数："; cin>>m>>n;

cout<<"---------[M1]---------"<<endl; InputMatrix(M1, m, n); InitMatrix(M2);

cout<<"---------[M2]---------"<<endl; InputMatrix(M2, m, n);

cout<<"-------[M1 + M2]-------"<<endl; OutputMatrix(Add(M1,M2));

cout<<endl<<"**************以下**************"<<endl<<endl; InitMatrix(M1);

cout<<"---------[M1]---------"<<endl; cout<<"请输入行数与列数："; cin>>m>>n;

InputMatrix(M1, m, n); InitMatrix(M2);

cout<<"---------[M2]---------"<<endl; cout<<"请输入行数与列数：";

为选作部分

cin>>m>>n;

InputMatrix(M2, m, n); M = Multiply(M1,M2);

cout<<"-------[M1 * M2]-------"<<endl;

cout<<"行数："<<M.m<<" 列数："<<M.n<<endl; 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 sm[MaxTerms+1]; } SMatrix;

struct LNode{ Triple t;

LNode * next; };

//初始化稀疏矩阵

void InitMatrix(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结尾："<<endl; cin>>row>>col>>val; while(row != 0){ k++; M.sm[k].row = row; M.sm[k].col = col; M.sm[k].val = val; cin>>row>>col>>val; }

M.t = k; }

//输出稀疏矩阵

void OutputMatrix(SMatrix M) {

int k = 1;

cout<<"(";

while((M.t--) > 1){ cout<<"("<<M.sm[k].row<<","<<M.sm[k].col<<","<<M.sm[k].val<<"),"; k++; }

cout<<"("<<M.sm[k].row<<","<<M.sm[k].col<<","<<M.sm[k].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)){ cerr<<"tow Matrix measurenents are different!"<<endl; exit(1); }

M.m = M1.m; M.n = M1.n;

while( k1 <= M1.t && k2 <= M2.t){ if ( M1.sm[k1].row == M2.sm[k2].row && M1.sm[k1].col == M2.sm[k2].col){ t.val = M1.sm[k1].val + M2.sm[k2].val; if (t.val){ t.row = M1.sm[k1].row;

t.col = M1.sm[k1].col; M.sm[++M.t] = t; } k1++; k2++; } else if ( M1.sm[k1].row == M2.sm[k2].row){ M.sm[++M.t] = M1.sm[k1].col < M2.sm[k2].col? M1.sm[k1++] : M2.sm[k2++]; } else M.sm[++M.t] = M1.sm[k1].row < M2.sm[k2].row? M1.sm[k1++] : M2.sm[k2++]; }

while( k1 <= M1.t ){ M.sm[++M.t] = M1.sm[k1]; k1++; } …… 此处隐藏：2858字，全部文档内容请下载后查看。喜欢就下载吧 ……