数据结构课程设计-稀疏矩阵

数据结构

课程设计报告

设计题目：稀疏矩阵

专业：计算机科技 院系：计算机学院

姓名：xxxxxxx

学号：xxxxxxxx

时间：2013年9月22日

目录

一需求分析---------------------------------------------------------------- 3

1. 问题描述-------------------------------------------------------------------------------------- 3

2. 基本要求-------------------------------------------------------------------------------------- 3

3 实现提示-------------------------------------------------------------------------------------- 3

二概要设计----------------------------------------------------------------------3

三详细设计----------------------------------------------------------------------4

四调试分析-------------------------------------------------------------------- 10

五用户手册---------------------------------------------------------------------11

一需求分析

1.【问题描述】

稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。

2.【基本要求】

以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加，相减和相乘的运算，稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。

3.【实现提示】

（1）首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行，列数对于所要求作的运算是否匹配，可设矩阵的行数和列数均不超过20。

（2）程序可以对三元组的输入顺序加以限制，例如，按行优先。

（3）在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放

二概要设计

1. 设定数组的抽象数据类型定义：

ADT SparseMatrix{

数据对象：D={ m和n分别称为矩阵的行数和列数}

数据关系：R={Row，Col}

Row={<ai,j，ai,j+1>|1<=i<=m，a<=j<=n-1 }

Col={<ai,j，ai+1,j>|1<=i<=m-1，a<=j<=n }

基本操作：

CreateSMatrix(&M);

操作结果：创建稀疏矩阵M。

DestorySMatrix(&M);

初始条件：稀疏矩阵M存在。

操作结果：销毁稀疏矩阵M。

PrintSMatrix(M)；

初始条件：稀疏矩阵M存在。

操作结果: 输出稀疏矩阵M。

CopySMatrix(M,&T)；

初始条件：稀疏矩阵M存在。

操作结果：由稀疏矩阵M复制得到T。

AddSMatrix(M,N,&Q)；

初始条件：稀疏矩阵M与N的行数和列数对应相等。

操作结果：求稀疏矩阵的和Q=M+N。

SubtSMatrix(M,N,&Q);

初始条件：稀疏矩阵M与N的行数和列数对应相等。

操作结果：求稀疏矩阵的差Q=M-N。

MultSMatrix(M,N,&Q);

初始条件：稀疏矩阵M的列数等于N的行数。

操作结果：求稀疏矩阵乘积Q=M*N。

TransposeSMatrix(M,&T);

初始条件：稀疏矩阵M 存在。

操作结果：求稀疏矩阵M的转置矩阵T。

}ADTSparseMatrix

2．本程序包含的模块

（1）void main()

{

初始化；

do{ 接收命令；处理命令；}while(命令！=退出)；

}

（2）稀疏矩阵模块——实现稀疏矩阵抽象数据类型。

（3）稀疏矩阵求值模块——实现稀疏矩阵求值抽象数据类型。

稀疏矩阵求值模块包括：矩阵相加模块AddRLSMatrix()；

矩阵相减模块SubRLSMatrix()；相乘模块MulTSMatrix()；

三详细设计

#include<stdio.h>

#include<stdlib.h>

#define MAXSIZE 20

#define MAXRC 20

typedefstruct{ //稀疏矩阵的三元组顺序表存储表示

inti,j; //该非零元的行下标和列下标

int e;

}Triple;

typedefstruct

{

Triple data[MAXSIZE+1]; //非零元三元组表，data[0]未用

intrpos[MAXRC+1]; //各行第一个非零元的位置表

intmu,nu,tu; //矩阵的行数列数和非零元的个数

}RLSMatrix;

void CreateSMatrix(RLSMatrix *T) //输入创建稀疏矩阵

{

int k;

printf(" \n 请输入矩阵行数、列数及非零元个数: ");

scanf("%d%d%d",&T->mu,&T->nu,&T->tu);

printf("\n");

if(T->tu>MAXSIZE||T->mu>21)

{

printf(" 非零个数超出定义范围！出错！");

exit(0);

}

for(k=1;k<=T->tu;k++)

{

printf(" 请输入第%d个非零元素的行数,列数及其值: ",k);

scanf("%d%d%d",&T->data[k].i,&T->data[k].j,&T->data[k].e);

}

}

void AddRLSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix *Q) //稀疏矩阵相加

{

intp,q,k=1;

if(M.mu!=N.mu||M.nu!=N.nu)

{

printf(" 你的输入不满足矩阵相加的条件!\n"); exit(1); } Q->mu=M.mu;Q->nu=M.nu; for(p=1,q=1;p<=M.tu&&q<=N.tu;) { if(M.data[p].i==N.data[q].i) { if(M.data[p].j==N.data[q].j) { Q->data[k].i=M.data[p].i; Q->data[k].j=M.data[p].j; Q->data[k].e=M.data[p].e+N.data[q].e; p++;q++;k++; } else if(M.data[p].j<N.data[q].j) { Q->data[k].i=M.data[p].i; Q->data[k].j=M.data[p].j; Q->data[k].e=M.data[p].e; k++;p++; } else if(M.data[p].j>N.data[q].j) { Q->data[k].i=N.data[q].i; Q->data[k].j=N.data[q].j; Q->data[k].e=N.data[q].e; k++;p++; } } else if(M.data[p].i<N.data[q].i) {

Q->data[k].i=M.data[p].i;

Q->data[k].j=M.data[p].j;

Q->data[k].e=M.data[p].e;

k++;p++;

}

else if(M.data[p].i>N.data[q].i)

{

Q->data[k].i=N.data[q].i;

Q->data[k].j=N.data[q].j;

Q->data[k].e=N.data[q].e;

k++;q++;

}

}

if(p!=M.tu+1)

for(;p<=M.tu;p++)

{

Q->data[k].i=M.data[p].i;

Q->data[k].j=M.data[p].j;

Q->data[k].e=M.data[p].e;

k++;

}

if(q!=N.tu+1)

for(;q<=N.tu;q++)

{

Q->data[k].i=N.data[q].i;

Q->data[k].j=N.data[q].j;

Q->data[k].e=N.data[q].e;

k++;

}

}

void SubRLSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix *Q)

{

intp,q,k=1;

if(M.mu!=N.mu||M.nu!=N.nu)

{

printf(" 你的输入不满足矩阵相减的条件!\n");

exit(1);

}

Q->mu=M.mu;Q->nu=M.nu;

for(p=1,q=1;p<=M.tu&&q<=N.tu;)

{

if(M.data[p].i==N.data[q].i)

{

if(M.data[p].j==N.data[q].j)

//稀疏矩阵相减

{

Q->data[k].i=M.data[p].i;

Q->data[k].j=M.data[p].j;

Q->data[k].e=M.data[p].e-N.data[q].e;

p++;q++;k++;

}

else if(M.data[p].j<N.data[q].j)

{

Q->data[k].i=M.data[p].i;

Q->data[k].j=M.data[p].j;

Q->data[k].e=M.data[p].e;

k++;p++;

}

else if(M.data[p].j>N.data[q].j)

{

Q->data[k].i=N.data[q].i;

Q->data[k].j=N.data[q].j;

Q->data[k].e=-N.data[q].e;

k++;p++;

}

}

else if(M.data[p].i<N.data[q].i)

{

Q->data[k].i=M.data[p].i;

Q->data[k].j=M.data[p].j;

Q->data[k].e=M.data[p].e;

k++;p++;

}

else if(M.data[p].i>N.data[q].i)

{

Q->data[k].i=N.data[q].i;

Q->data[k].j=N.data[q].j;

Q->data[k].e=-N.data[q].e;

k++;q++;

}

}

if(p!=M.tu+1)

for(;p<=M.tu;p++)

{

Q->data[k].i=M.data[p].i;

Q->data[k].j=M.data[p].j;

Q->data[k].e=M.data[p].e;

k++;

}

} if(q!=N.tu+1) for(;q<=N.tu;q++) { Q->data[k].i=N.data[q].i; Q->data[k].j=N.data[q].j; Q->data[k].e=-N.data[q].e; k++; }

intMulTSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix *Q) //稀疏矩阵相乘

{

intccol=0,tp,brow,t,arow,p,q,i;

intctemp[MAXSIZE+1];

if(M.nu!=N.mu)

{

printf(" 你的输入不满足矩阵相乘的条件!\n");

return 0;

}

Q->mu=M.mu;

Q->nu=N.nu;

Q->tu=0;

if(M.tu*N.tu!=0)

{

for(arow=1;arow<=M.mu;++arow)

{

for(i=1;i<=N.nu;i++)

ctemp[i]=0;

Q->rpos[arow]=Q->tu+1;

if(arow<M.mu) tp=M.rpos[arow+1];

else tp=M.tu+1;

for(p=M.rpos[arow];p<tp;++p)

{

brow=M.data[p].j;

if(brow<N.mu) t=N.rpos[brow+1];

else t=N.tu+1;

for(q=N.rpos[brow];q<t;++q)

{

ccol=N.data[q].j;

ctemp[ccol]+=M.data[p].e*N.data[q].e;

}

}

for(ccol=1;ccol<=Q->nu;++ccol)

{

if(ctemp[ccol])

{

if(++Q->tu>MAXSIZE) return 0;

Q->data[Q->tu].i=arow;

Q->data[Q->tu].j=ccol;

Q->data[Q->tu].e=ctemp[ccol];

}

}

}

}

return 1;

}

void PrintSMatrix(RLSMatrix Q) //输出稀疏矩阵

{

int k=1,row,line;

printf("\n运算结果: ");

if(Q.tu==0) printf("0");

else

{

for(row=1;row<=Q.mu;row++)

{

for(line=1;line<=Q.nu;line++)

{

if(Q.data[k].i==row&&Q.data[k].j==line)printf("%d ",Q.data[k++].e); elseprintf("0 ");

}

printf("\n\t ");

}

}

}

void main()

{

RLSMatrix M,N,Q;

inti;

system("cls");

printf(" ┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf(" ┃㊣必做题，稀疏矩阵运算器㊣┃\n");

printf(" ┃姓名：xxxxx┃\n");

printf(" ┃学号：xxxxxxxxxxxx┃\n");

printf(" ┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); do

{

printf("╔════════════════════════════════╗\n"); printf("║欢迎进入稀疏矩阵运算器║\n");

printf("║------------------------------------------- ║\n");

printf("║1.矩阵相加║\n");

printf("║2.矩阵相减║\n");

printf("║3.矩阵相乘║\n");

printf("║4.退出系统║\n");

printf("╚════════════════════════════════╝\n"); printf(">>>>>>请选择功能(1-4): ");

scanf("%d",&i);

if(i==4) goto end;

else

{

} printf("\n 请输入第一个矩阵M:\n"); CreateSMatrix(&M); printf("\n 请输入第二个矩阵N:\n"); CreateSMatrix(&N); switch(i) { case 1:AddRLSMatrix(M,N,&Q);break; case 2:SubRLSMatrix(M,N,&Q);break; case 3:MulTSMatrix(M,N,&Q);break; default:break; } } PrintSMatrix(Q); getchar(); getchar(); end: ; }while(i!=4);

四 调试分析

（1） 问题：运行过程中发现加法减法能正常运行，而乘法却在存储数据步骤就

出现问题。

解决：经检查发现，由于在创建稀疏矩阵时没有输入矩阵相应的各行第一非零元的位置，所以在进行乘法运算时找不到矩阵的rpos值。将rpos补上，乘法函数即可正常运行。

（2） 问题：当加减结果为零矩阵时，输出结果是一个由0构成的矩阵，而不是

数值0。

解决：经检查发现，加减法函数过程中没有判断Q->tu的值，导致在输出函数里没有执行针对该情况的if判断语句。在加减函数里，每增加一个非零元，Q->tu加一。

（3） 问题：输出矩阵时，输出界面不整齐，非标准矩阵形式。解决：利用\n \t

及空格号使界面比较美观。

五、用户手册

1．本程序的运行环境为WIN7操作系统，执行文件为：phonesystem.exe。

2．进入演示程序后的界面：

(1) 主界面

(2) 矩阵相加

(3)矩阵相减

(4)矩阵相乘

14 / 14

本文来源：https://www.bwwdw.com/article/ilc4.html