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

1、.数据结构课程设计报告 设计题目：稀疏矩阵专业：计算机科技院系：计算机学院姓名： xxxxxxx学号： xxxxxxxx时间：2013年9月22日目录一 需求分析- 3 1. 问题描述- 32. 基本要求- 33 实现提示- 3二 概要设计-3三 详细设计-4四 调试分析- 10五 用户手册-11一 需求分析1.【问题描述】 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2.【基本要求】 以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加，相减和相乘的运算，稀疏矩阵的输入形式采用三元组

2、表示，而运算结果的矩阵则以通常的阵列形式列出。3.【实现提示】（1）首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行，列数对于所要求作的运算是否匹配，可设矩阵的行数和列数均不超过20。（2）程序可以对三元组的输入顺序加以限制，例如，按行优先。（3）在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放二 概要设计1. 设定数组的抽象数据类型定义：ADT SparseMatrix数据对象：D= m和n分别称为矩阵的行数和列数数据关系：R=Row，ColRow=<ai,j，ai,j+1 >|1<=i<=m，a<=j<=n-1

3、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的行数和列数对应相等。 操作

4、结果：求稀疏矩阵的和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。ADT SparseMatrix2本程序包含的模块（1）void main()初始化；do 接收命令；处理命令；while(命令！=退出)；（2）稀疏矩阵模块实现稀疏矩阵抽象数据

5、类型。（3）稀疏矩阵求值模块实现稀疏矩阵求值抽象数据类型。 稀疏矩阵求值模块包括：矩阵相加模块AddRLSMatrix()；矩阵相减模块SubRLSMatrix()；相乘模块MulTSMatrix()；三 详细设计#include<stdio.h>#include<stdlib.h>#define MAXSIZE 20#define MAXRC 20typedef struct /稀疏矩阵的三元组顺序表存储表示int i,j; /该非零元的行下标和列下标int e;Triple;typedef structTriple dataMAXSIZE+1; /非零元三元组表，d

6、ata0未用int rposMAXRC+1; /各行第一个非零元的位置表int mu,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(

7、" 非零个数超出定义范围！出错！");exit(0);for(k=1;k<=T->tu;k+)printf(" 请输入第%d个非零元素的行数,列数及其值: ",k);scanf("%d%d%d",&T->datak.i,&T->datak.j,&T->datak.e);void AddRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /稀疏矩阵相加int p,q,k=1;if(M.mu!=N.mu|M.nu!=N.nu)printf(&

8、quot; 你的输入不满足矩阵相加的条件!n");exit(1);Q->mu=M.mu;Q->nu=M.nu;for(p=1,q=1;p<=M.tu&&q<=N.tu;)if(M.datap.i=N.dataq.i)if(M.datap.j=N.dataq.j)Q->datak.i=M.datap.i;Q->datak.j=M.datap.j;Q->datak.e=M.datap.e+N.dataq.e;p+;q+;k+;else if(M.datap.j<N.dataq.j)Q->datak.i=M.datap.

9、i;Q->datak.j=M.datap.j;Q->datak.e=M.datap.e;k+;p+;else if(M.datap.j>N.dataq.j)Q->datak.i=N.dataq.i;Q->datak.j=N.dataq.j;Q->datak.e=N.dataq.e;k+;p+;else if(M.datap.i<N.dataq.i)Q->datak.i=M.datap.i;Q->datak.j=M.datap.j;Q->datak.e=M.datap.e;k+;p+;else if(M.datap.i>N.dat

10、aq.i)Q->datak.i=N.dataq.i;Q->datak.j=N.dataq.j;Q->datak.e=N.dataq.e;k+;q+;if(p!=M.tu+1)for(;p<=M.tu;p+)Q->datak.i=M.datap.i;Q->datak.j=M.datap.j; Q->datak.e=M.datap.e;k+;if(q!=N.tu+1)for(;q<=N.tu;q+)Q->datak.i=N.dataq.i;Q->datak.j=N.dataq.j;Q->datak.e=N.dataq.e;k+;vo

11、id SubRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /稀疏矩阵相减int p,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.datap.i=N.dataq.i)if(M.datap.j=N.dataq.j)Q->datak.i=M.datap.i;Q->datak.j=

12、M.datap.j;Q->datak.e=M.datap.e-N.dataq.e;p+;q+;k+;else if(M.datap.j<N.dataq.j)Q->datak.i=M.datap.i;Q->datak.j=M.datap.j;Q->datak.e=M.datap.e;k+;p+;else if(M.datap.j>N.dataq.j)Q->datak.i=N.dataq.i;Q->datak.j=N.dataq.j;Q->datak.e=-N.dataq.e;k+;p+;else if(M.datap.i<N.dataq

13、.i)Q->datak.i=M.datap.i;Q->datak.j=M.datap.j;Q->datak.e=M.datap.e;k+;p+;else if(M.datap.i>N.dataq.i)Q->datak.i=N.dataq.i;Q->datak.j=N.dataq.j;Q->datak.e=-N.dataq.e;k+;q+;if(p!=M.tu+1)for(;p<=M.tu;p+)Q->datak.i=M.datap.i;Q->datak.j=M.datap.j; Q->datak.e=M.datap.e;k+;i

14、f(q!=N.tu+1)for(;q<=N.tu;q+)Q->datak.i=N.dataq.i;Q->datak.j=N.dataq.j;Q->datak.e=-N.dataq.e;k+;int MulTSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /稀疏矩阵相乘int ccol=0,tp,brow,t,arow,p,q,i;int ctempMAXSIZE+1;if(M.nu!=N.mu) printf(" 你的输入不满足矩阵相乘的条件!n");return 0; Q->mu=M.mu;Q-&g

15、t;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+)ctempi=0; Q->rposarow=Q->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.dat

16、aq.j;ctempccol+=M.datap.e*N.dataq.e;for(ccol=1;ccol<=Q->nu;+ccol)if(ctempccol)if(+Q->tu>MAXSIZE) return 0;Q->dataQ->tu.i=arow;Q->dataQ->tu.j=ccol;Q->dataQ->tu.e=ctempccol;return 1;void PrintSMatrix(RLSMatrix Q) /输出稀疏矩阵int k=1,row,line;printf("n运算结果: ");if(Q.tu

17、=0) printf("0");elsefor(row=1;row<=Q.mu;row+)for(line=1;line<=Q.nu;line+)if(Q.datak.i=row&&Q.datak.j=line)printf("%d ",Q.datak+.e);else printf("0 ");printf("nt ");void main()RLSMatrix M,N,Q;int i;system("cls");printf(" n");pri

18、ntf(" 必做题，稀疏矩阵运算器 n");printf(" 姓名：xxxxx n");printf(" 学号：xxxxxxxxxxxx n");printf(" n");doprintf("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