数据结构 数组矩阵.doc

数据结构与算法课程实验报告 实验三：稀疏矩阵的压缩存储及运算 姓名：沈靖雯 班级：14信息与计算科学（2）班 学号：2014326601094实验三 稀疏矩阵的压缩存储及运算【实验内容】 实现稀疏矩阵的压缩存储方法以及在特定存储方法下的基本运算。【实验目的】 掌握数组的应用，包括稀疏矩阵、特殊矩阵的压缩存储方法。矩阵的基本运算的实现，包括矩阵相加、转置、乘法等。【问题描述】 （1） 用行逻辑链接顺序表或十字链表分别实现稀疏矩阵的压缩存储。（2） 编程实现矩阵的转置运算和乘法运算（运用行逻辑链接顺序表或十字链表作为存储结构）。【问题实现】（1）抽象数据类型ADT RLSMatrix 数据对象: 数据关系： = - 基本操作： CreateMatrix(*M) 操作结果：创建稀疏矩阵M。 Trans(M,*T) 初始条件：稀疏矩阵M已存在。 操作结果：求稀疏矩阵M的转置矩阵T。 Mult(M,N,*T） 初始条件：稀疏矩阵M的列数等于稀疏矩阵N的行数。 操作结果：求稀疏矩阵乘积T=M*N。 Show(M) 初始条件：稀疏矩阵M已存在且非空。 操作结果：输出稀疏矩阵M。 ADT RLSMatrix （2）主要实现思路和程序代码： 1).首先定义抽象数据类型，构建程序框架； 2).定义稀疏矩阵创建函数； void CreateMatrix(RLSMatrix *M) 用户首先输入矩阵行数、列数、非零元个数后再依次输入非零元行数、列数、值，完成稀疏矩阵创建；scanf(%d %d %d,&M-mu,&M-nu,&M-tu); /判断行值、列值、元素个数是否合法 if(M-munututuM-mu*M-nu) printf(输入有误！); int k; printf(请输入非零元的行坐标 列坐标 值:n); for(k=1;ktu;k+) /输入稀疏矩阵元素 scanf(%d %d %d,&M-datak.i,&M-datak.j,&M-datak.e); /for 在稀疏矩阵创建函数中加入num和rpos两个向量的定义，前者记录稀疏矩阵每行非零元个数，后者记录每行第一个非零元所在矩阵的位置，为后续矩阵运算函数所用。if(M-tu) int num1000,t; for(col=1;colmu;+col) numcol=0; for(t=1;ttu;+t) +numM-datat.i; /求出M中每行非零元个数M-rpos1=1; /求矩阵M第col行第一个非零元在M.data中的位置 for(col=2;colmu;+col) M-rposcol=M-rposcol-1+numcol-1; 3).定义矩阵转置函数；int Trans(RLSMatrix M,RLSMatrix *T)快速转置法完成矩阵转置操作：if(T-tu)int q=1,t,p;int num1000; for(col=1;col=M.nu;+col) numcol=0; for(t=1;trpos1=1; /求矩阵M第col列(=矩阵T第col行)第一个非零元在T.data中的位置 for(col=2;colrposcol=T-rposcol-1+numcol-1; for(p=1;prposcol; T-dataq.i=M.datap.j; T-dataq.j=M.datap.i; T-dataq.e=M.datap.e; +T-rposcol; 4).使用行逻辑链接顺序表存储定义矩阵乘积函数； int Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *T) 规定矩阵M的列数等于矩阵N的行数，方可进行矩阵乘法操作。具体代码如下：if(M.tu*N.tu!=0)for(arow=1;arow=M.mu;+arow)int ctemp1000;for(i=1;inu;+i)ctempi=0;T-rposarow=T-tu+1;if(arowM.mu) tp=M.rposarow+1; else tp=M.tu+1; for(p=M.rposarow;ptp;+p) brow=M.datap.j; if(browN.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;qt;+q) ccol=N.dataq.j; ctempccol+=M.datap.e*N.dataq.e; for(ccol=1;ccolnu;+ccol) if(ctempccol) if(+T-tuSIZE) return ERROR; T-dataT-tu.i=arow; T-dataT-tu.j=ccol;T-dataT-tu.e=ctempccol; 5).定义矩阵输出函数输出矩阵；void Show(RLSMatrix M)通过双重循环，把稀疏矩阵中不为零的元素的行数、列数和值显示出来： for(col=1;col=M.mu;col+) for(p=1;p=M.tu;p+) if(M.datap.i=col) printf(%3d %3d %3dn,M.datap.i,M.datap.j,M.datap.e); 6).定义主函数，总体完成以上所有函数功能的实现。 程序运行如图1：图 1【总结】 实验结果基本实现问题要求。 在实验调试过程中主要出现了两个问题： 1.在定义函数时一开始照着书上定义矩阵变量，但程序总是报错；后来直接换成指针才得以解决； 2.在处理矩阵乘积函数时，函数测试结果总是出现问题，经过几次思考发现是num和rpos在该函数中不曾定义而直接使用导致问题，为避免重复定义，故将这两个向量定义到矩阵创建函数中（void CreateMatrix(RLSMatrix *M)）才得以解决问题。附件：源代码：#include #include #define ERROR -1 #define SIZE 12500int col;int ccol,arow,brow;typedef struct int i,j; / 非零元行下标和列下标 int e; Triple; typedef struct Triple dataSIZE+1; / data0未用 int rposSIZE+1;int mu,nu,tu; /矩阵行数、列数、非零元个数 RLSMatrix; /采用三元组顺序表存储表示，创建稀疏矩阵Mvoid CreateMatrix(RLSMatrix *M) scanf(%d %d %d,&M-mu,&M-nu,&M-tu); /判断行值、列值、元素个数是否合法 if(M-munututuM-mu*M-nu) printf(输入有误！); int k; printf(请输入非零元的行坐标 列坐标 值:n); for(k=1;ktu;k+) /输入稀疏矩阵元素 scanf(%d %d %d,&M-datak.i,&M-datak.j,&M-datak.e); /for if(M-tu) int num1000,t; for(col=1;colmu;+col) numcol=0; for(t=1;ttu;+t) +numM-datat.i; /求出M中每行非零元个数M-rpos1=1; /求矩阵M第col行第一个非零元在M.data中的位置 for(col=2;colmu;+col) M-rposcol=M-rposcol-1+numcol-1; /行逻辑顺序存储快速转置 int Trans(RLSMatrix M,RLSMatrix *T)T-mu=M.nu;T-nu=M.mu;T-tu=M.tu;if(T-tu)int q=1,t,p;int num1000; for(col=1;col=M.nu;+col) numcol=0; for(t=1;trpos1=1; /求矩阵M第col列(=矩阵T第col行)第一个非零元在T.data中的位置 for(col=2;colrposcol=T-rposcol-1+numcol-1; for(p=1;prposcol; T-dataq.i=M.datap.j; T-dataq.j=M.datap.i; T-dataq.e=M.datap.e; +T-rposcol; return 0;/求矩阵乘积T=M*N,行逻辑链接顺序表存储int Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *T)if(N.mu!=M.nu) return ERROR;T-mu=M.mu;T-nu=N.nu;T-tu=0;int tp,t,p,q,i;if(M.tu*N.tu!=0)for(arow=1;arow=M.mu;+arow)int ctemp1000;for(i=1;inu;+i)ctempi=0;T-rposarow=T-tu+1;if(arowM.mu) tp=M.rposarow+1; else tp=M.tu+1; for(p=M.rposarow;ptp;+p) brow=M.datap.j; if(browN.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;qt;+q) ccol=N.dataq.j; ctempccol+=M.datap.e*N.dataq.e; for(ccol=1;ccolnu;+ccol) if(ctempccol) if(+T-tuSIZE) return ERROR; T-dataT-tu.i=arow; T-dataT-tu.j=ccol;T-dataT-tu.e=ctempccol; return 0;/输出矩阵 void Show(RLSMatrix M)/通过双重循环，把稀疏矩阵中不为零的元素的行数、列数和值显示出来 int p; for(col=1;col=M.mu;col+) for(p=1;p=M.tu;p+) if(M.datap.i=col) printf(%3d %3d %3dn,M.datap.i,M.datap.j,M.datap.e);int main()RLSMatrix M,N,T,Q; printf(请输