数据结构 数组矩阵

1、数据结构与算法课程实验报告 实验三：稀疏矩阵的压缩存储及运算 姓名：沈靖雯 班级：14信息与计算科学（2）班 学号：2014326601094实验三 稀疏矩阵的压缩存储及运算【实验内容】 实现稀疏矩阵的压缩存储方法以及在特定存储方法下的基本运算。【实验目的】 掌握数组的应用，包括稀疏矩阵、特殊矩阵的压缩存储方法。矩阵的基本运算的实现，包括矩阵相加、转置、乘法等。【问题描述】 （1） 用行逻辑链接顺序表或十字链表分别实现稀疏矩阵的压缩存储。（2） 编程实现矩阵的转置运算和乘法运算（运用行逻辑链接顺序表或十字链表作为存储结构）。【问题实现】（1）抽象数据类型ADT RLSMatrix 数据对象:

2、数据关系： =Î= - 基本操作： 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) 用户首先

3、输入矩阵行数、列数、非零元个数后再依次输入非零元行数、列数、值，完成稀疏矩阵创建；scanf("%d %d %d",&M->mu,&M->nu,&M->tu); /判断行值、列值、元素个数是否合法 if(M->mu<=0)|(M->nu<=0)|(M->tu<=0)|(M->tu>M->mu*M->nu) printf("输入有误！"); int k; printf("请输入非零元的行坐标 列坐标 值:n"); for(k=1;k&l

4、t;=M->tu;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;col<=M->mu;+col) numcol=0; for(t=1;t<=M->tu;+t) +numM->

5、;datat.i; /求出M中每行非零元个数M->rpos1=1; /求矩阵M第col行第一个非零元在M.data中的位置 for(col=2;col<=M->mu;+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;t<=M.tu;+t) +n

6、umM.datat.j; /求出M中每列非零元个数T->rpos1=1; /求矩阵M第col列(=矩阵T第col行)第一个非零元在T.data中的位置 for(col=2;col<=M.nu;+col) T->rposcol=T->rposcol-1+numcol-1; for(p=1;p<=M.tu;+p) col=M.datap.j; q=T->rposcol; T->dataq.i=M.datap.j; T->dataq.j=M.datap.i; T->dataq.e=M.datap.e; +T->rposcol; 4).使用行

7、逻辑链接顺序表存储定义矩阵乘积函数； 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;i<=T->nu;+i)ctempi=0;T->rposarow=T->tu+1;if(arow<M.mu) tp=M.rposarow+1; else tp=M.tu+1; for(p=M.rposarow;p<tp;+p

8、) brow=M.datap.j; if(brow<N.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;q<t;+q) ccol=N.dataq.j; ctempccol+=M.datap.e*N.dataq.e; for(ccol=1;ccol<=T->nu;+ccol) if(ctempccol) if(+T->tu>SIZE) return ERROR; T->dataT->tu.i=arow; T->dataT->tu.j=ccol;T->dataT->tu.

9、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.在定义函数

10、时一开始照着书上定义矩阵变量，但程序总是报错；后来直接换成指针才得以解决； 2.在处理矩阵乘积函数时，函数测试结果总是出现问题，经过几次思考发现是num和rpos在该函数中不曾定义而直接使用导致问题，为避免重复定义，故将这两个向量定义到矩阵创建函数中（void CreateMatrix(RLSMatrix *M)）才得以解决问题。附件：源代码：#include <stdio.h> #include <stdlib.h> #define ERROR -1 #define SIZE 12500int col;int ccol,arow,brow;typedef struct

11、 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->mu<=0)|(M

12、->nu<=0)|(M->tu<=0)|(M->tu>M->mu*M->nu) printf("输入有误！"); int k; printf("请输入非零元的行坐标 列坐标 值:n"); for(k=1;k<=M->tu;k+) /输入稀疏矩阵元素 scanf("%d %d %d",&M->datak.i,&M->datak.j,&M->datak.e); /for if(M->tu) int num1000,t; for(co

13、l=1;col<=M->mu;+col) numcol=0; for(t=1;t<=M->tu;+t) +numM->datat.i; /求出M中每行非零元个数M->rpos1=1; /求矩阵M第col行第一个非零元在M.data中的位置 for(col=2;col<=M->mu;+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

14、;if(T->tu)int q=1,t,p;int num1000; for(col=1;col<=M.nu;+col) numcol=0; for(t=1;t<=M.tu;+t) +numM.datat.j; /求出M中每列非零元个数T->rpos1=1; /求矩阵M第col列(=矩阵T第col行)第一个非零元在T.data中的位置 for(col=2;col<=M.nu;+col) T->rposcol=T->rposcol-1+numcol-1; for(p=1;p<=M.tu;+p) col=M.datap.j; q=T->rpos

15、col; 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;+aro

16、w)int ctemp1000;for(i=1;i<=T->nu;+i)ctempi=0;T->rposarow=T->tu+1;if(arow<M.mu) tp=M.rposarow+1; else tp=M.tu+1; for(p=M.rposarow;p<tp;+p) brow=M.datap.j; if(brow<N.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;q<t;+q) ccol=N.dataq.j; ctempccol+=M.datap.e*N.dataq.e; for(

17、ccol=1;ccol<=T->nu;+ccol) if(ctempccol) if(+T->tu>SIZE) 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("请输入矩阵M的(行数 列数 非零元个数)：n");