稀疏矩阵的加减法

1、数据结构课 程 设 计 报 告 书题 目： 稀疏矩阵的加减法 专 业： 计算机科学与技术 学 号： 学生姓名： 指导教师： 完成日期： 2016-06-20 稀疏矩阵的加减法运算1. 题目描述假设稀疏矩阵A和B（m行n列）都采用三元组表示，编写程序计算CA+B，D=A-B，矩阵C和D也采用三元组表示。编写程序实现，并输出结果。2. 预备知识 函数模块调用关系 三元组中抽象数据类型定义 三元组表的赋值操作 三元组和稀疏矩阵之间的转换3. 问题分析该程序主要实现以下功能：（1）用三元组存储方式创建稀疏矩阵；（2）用三元组存储方式进行稀疏矩阵的加法；（3）用三元组存储方式进行稀疏矩阵的减法；程序流程

2、和设计思想可以用以下流程图来描述：输入menu中的编号2. 求两个矩阵相减差1. 求两个矩阵相加和 0. 退出系统运行结果并显示出来 图1.程序运行流程图4. 数据结构设计抽象数据类型定义三元组中抽象数据类型定义 typedef struct /三元组表中元素类型的定义int i,j;int e;Triple; typedef struct a) Triple dataMAX+1; /存放非零元素的数组，行优先b) int row,nu,tu;Matrix; /三元组表类型名 InitMatrix(A); /初始化 AddMatrix(A,B,C);/矩阵相加 SubMatrix(A,B,C)

3、;/矩阵相减5. 模块设计 void InitMatrix(Matrix &M) /初始化三元组矩阵int num=0;M=*(Matrix *)malloc(sizeof(Matrix); /为三元组申请内存 printf("请输入矩阵的行、列和非零元素个数:n");scanf("%d %d",&M.row,&M.nu); /输入矩阵的行、列和非零元素个数 printf("请输入矩阵的非零元值:n"); scanf("%d",&num);getchar();M.tu=num;for

4、(int i=1;i<=M.tu;i+) /输入三元组 printf("请输入第%d个非零元值:n",i); scanf("%d%d%d",&M.datai.i,&M.datai.j,&M.datai.e); getchar(); void AddMatrix(Matrix A,Matrix B,Matrix &C) /将A，B的值相加放到C上 C=*(Matrix *)malloc(sizeof(Matrix); /为三元组C申请内存 int i=1,j=1,k=1; int v; if(A.row!=B.row|

5、A.nu!=B.nu) /判断A、B的行列数是否相等 printf("error!n"); else C.row=A.row; /把A的行数赋给C C.nu=A.nu; /把A的列数赋给C while(i<=A.tu&&j<=B.tu) if(A.datai.i=B.dataj.i) /如果三元组A的行下标与B的行下标相等 if(A.datai.j<B.dataj.j)/如果三元组A的列下标小于B的行下标 C.datak.i=A.datai.i;/把当前三元组A行下标i插入三元组C C.datak.j=A.datai.j;/把当前三元组A下

6、列标j插入三元组C C.datak.e=A.datai.e;/把当前三元组A下标i对于的数值e插入三元组C k+; i+; else if(A.datai.j>B.dataj.j)/如果三元组A的列下标大于B的行下标 C.datak.i=B.dataj.i; C.datak.j=B.dataj.j; C.datak.e=B.dataj.e; k+; j+; else /如果三元组A的列下标等于B的行下标 v=A.datai.e+B.dataj.e; if(v!=0) C.datak.i=A.datai.i; /把当前三元组A行下标i插入三元组C C.datak.j=A.datai.j;

7、/把当前三元组A下列标j插入三元组C C.datak.e=v; /把三元组A-B下标i对于的数值v插入三元组C k+; i+; j+; else if(A.datai.i<B.dataj.i) /如果三元组A的行下标小于B的行下标 C.datak.i=A.datai.i; /把当前三元组A行下标i插入三元组C C.datak.j=A.datai.j; /把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e; /把当前三元组A下标i对于的数值e插入三元组C k+; i+; else C.datak.i=B.dataj.i;/把当前三元组B下行标i插入三元组C C.da

8、tak.j=B.dataj.j;/把当前三元组B下列标j插入三元组C C.datak.e=B.dataj.e;/把当前三元组B下标i对于的数值e插入三元组C k+; j+; while(i<=A.tu) C.datak.i=A.datai.i;/把当前三元组A下行标i插入三元组C C.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e;/把当前三元组A下标i对于的数值e插入三元组C k+; i+; while(j<=B.tu) C.datak.i=B.dataj.i;/把当前三元组B下行标i插入三元组C C.datak.

9、j=B.dataj.j;/把当前三元组B下列标j插入三元组C C.datak.e=B.dataj.e;/把当前三元组B下标i对于的数值e插入三元组C k+; j+; C.tu=k-1; void SubMatrix(Matrix A,Matrix B,Matrix &C) C=*(Matrix *)malloc(sizeof(Matrix); int i=1,j=1,k=1; int v; if(A.row!=B.row|A.nu!=B.nu) /判断A、B的行列数是否相等 printf("error!n"); else C.row=A.row; C.nu=A.nu

10、; while(i<=A.tu&&j<=B.tu) if(A.datai.i=B.dataj.i) if(A.datai.j<B.dataj.j) C.datak.i=A.datai.i;/把当前三元组A下行标i插入三元组C C.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e;/把当前三元组A下标i对于的数值e插入三元组C k+; i+; else if(A.datai.j>B.dataj.j) C.datak.i=B.dataj.i;/把当前三元组B下行标i插入三元组C C.datak.

11、j=B.dataj.j;/把当前三元组B下列标j插入三元组C C.datak.e=B.dataj.e;/把当前三元组B下标i对于的数值e插入三元组C k+; j+; else v=A.datai.e-B.dataj.e; if(v!=0) C.datak.i=A.datai.i;/把当前三元组A下行标i插入三元组C C.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=v; /把三元组A-B下标i对于的数值v插入三元组C k+; i+; j+; else if(A.datai.i<B.dataj.i) C.datak.i=A.datai.i;/

12、把当前三元组A下行标i插入三元组C C.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e;/把当前三元组A下标i对于的数值e插入三元组C k+; i+; else C.datak.i=B.dataj.i;/把当前三元组B下行标i插入三元组C C.datak.j=B.dataj.j;/把当前三元组B下列标j插入三元组C C.datak.e=B.dataj.e;/把当前三元组B下标i对于的数值e插入三元组C k+; j+; while(i<=A.tu) C.datak.i=A.datai.i;/把当前三元组A下行标i插入三元组C

13、 C.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e;/把当前三元组A下标i对于的数值e插入三元组C k+; i+; while(j<=B.tu) C.datak.i=B.dataj.i;/把当前三元组B下行标i插入三元组C C.datak.j=B.dataj.j;/把当前三元组B下列标j插入三元组C C.datak.e=B.dataj.e;/把当前三元组B下标i对于的数值e插入三元组C k+; j+; C.tu=k-1; void ShowMatrix(Matrix M) /输出三元组矩阵 printf("nn

14、矩阵信息:n");printf("row:%d nu:%d tu:%dn",M.row,M.nu,M.tu);printf(" i j kn");for(int i=1;i<=M.tu;i+) printf(" %d, %d, %d,n",M.datai.i,M.datai.j,M.datai.e); /输出三元组 int main( ) char x=' ' cout<<"t *"<<endl; cout<<"t 请选择相应的功能： &

15、quot;<<endl; cout<<"t -"<<endl; cout<<"t 1. 求两个矩阵相加和 "<<endl; cout<<"t -"<<endl; cout<<"t 2. 求两个矩阵相减差 "<<endl; cout<<"t -"<<endl; cout<<"t 0. 退出系统 "<<endl; cout&l

16、t;<"t "<<endl; int flag=1;while(flag)printf("请选择相应的功能:");int s;scanf("%d",&s);getchar();/输入menu编号 switch(s) case 1:Matrix A,B,C;printf("请输入第一个矩阵：n"); InitMatrix(A); /初始化 printf("请输入第二个矩阵：n"); InitMatrix(B); /初始化 printf("矩阵的和为:n"

17、;);AddMatrix(A,B,C); ShowMatrix(C);/输出三元组表 break; case 2:Matrix A,B,C;printf("请输入第一个矩阵：n"); InitMatrix(A);/初始化 printf("请输入第二个矩阵：n"); InitMatrix(B);/初始化 printf("矩阵的差为:n"); SubMatrix(A,B,C); ShowMatrix(C);/输出三元组表 break; case 0:flag=0;break; 6. 运行界面及运算结果图5-1图5-2图5-3图5-4附录：

18、#include<stdio.h>#include<stdlib.h>#include<iostream>using namespace std;#define MAX 1000/三元组typedef struct /三元组表中元素类型的定义int i,j;int e;Triple;typedef struct Triple dataMAX+1; /存放非零元素的数组，行优先int row,nu,tu;Matrix; /三元组表类型名 void InitMatrix(Matrix &M) /初始化三元组矩阵int num=0;M=*(Matrix *

19、)malloc(sizeof(Matrix); /为三元组申请内存 printf("请输入矩阵的行、列和非零元素个数:n");scanf("%d %d",&M.row,&M.nu); /输入矩阵的行、列和非零元素个数 printf("请输入矩阵的非零元值:n"); scanf("%d",&num);getchar();M.tu=num;for(int i=1;i<=M.tu;i+) /输入三元组 printf("请输入第%d个非零元值:n",i); scanf(&q

20、uot;%d%d%d",&M.datai.i,&M.datai.j,&M.datai.e); getchar();void ShowMatrix(Matrix M) /输出三元组矩阵 printf("nn矩阵信息:n");printf("row:%d nu:%d tu:%dn",M.row,M.nu,M.tu);printf(" i j kn");for(int i=1;i<=M.tu;i+) printf(" %d, %d, %d,n",M.datai.i,M.datai.

21、j,M.datai.e); /输出三元组void AddMatrix(Matrix A,Matrix B,Matrix &C) /将A，B的值相加放到C上 C=*(Matrix *)malloc(sizeof(Matrix); /为三元组C申请内存 int i=1,j=1,k=1; int v; if(A.row!=B.row|A.nu!=B.nu) /判断A、B的行列数是否相等 printf("error!n"); else C.row=A.row; /把A的行数赋给C C.nu=A.nu; /把A的列数赋给C while(i<=A.tu&&

22、j<=B.tu) if(A.datai.i=B.dataj.i) /如果三元组A的行下标与B的行下标相等 if(A.datai.j<B.dataj.j)/如果三元组A的列下标小于B的行下标 C.datak.i=A.datai.i;/把当前三元组A行下标i插入三元组C C.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e;/把当前三元组A下标i对于的数值e插入三元组C k+; i+; else if(A.datai.j>B.dataj.j)/如果三元组A的列下标大于B的行下标 C.datak.i=B.dataj.i

23、; C.datak.j=B.dataj.j; C.datak.e=B.dataj.e; k+; j+; else /如果三元组A的列下标等于B的行下标 v=A.datai.e+B.dataj.e; if(v!=0) C.datak.i=A.datai.i; /把当前三元组A行下标i插入三元组C C.datak.j=A.datai.j; /把当前三元组A下列标j插入三元组C C.datak.e=v; /把三元组A-B下标i对于的数值v插入三元组C k+; i+; j+; else if(A.datai.i<B.dataj.i) /如果三元组A的行下标小于B的行下标 C.datak.i=A.

24、datai.i; /把当前三元组A行下标i插入三元组C C.datak.j=A.datai.j; /把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e; /把当前三元组A下标i对于的数值e插入三元组C k+; i+; else C.datak.i=B.dataj.i;/把当前三元组B下行标i插入三元组C C.datak.j=B.dataj.j;/把当前三元组B下列标j插入三元组C C.datak.e=B.dataj.e;/把当前三元组B下标i对于的数值e插入三元组C k+; j+; while(i<=A.tu) C.datak.i=A.datai.i;/把当前三元

25、组A下行标i插入三元组C C.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e;/把当前三元组A下标i对于的数值e插入三元组C k+; i+; while(j<=B.tu) C.datak.i=B.dataj.i;/把当前三元组B下行标i插入三元组C C.datak.j=B.dataj.j;/把当前三元组B下列标j插入三元组C C.datak.e=B.dataj.e;/把当前三元组B下标i对于的数值e插入三元组C k+; j+; C.tu=k-1; void SubMatrix(Matrix A,Matrix B,Matri

26、x &C) C=*(Matrix *)malloc(sizeof(Matrix); int i=1,j=1,k=1; int v; if(A.row!=B.row|A.nu!=B.nu) /判断A、B的行列数是否相等 printf("error!n"); else C.row=A.row; C.nu=A.nu; while(i<=A.tu&&j<=B.tu) if(A.datai.i=B.dataj.i) if(A.datai.j<B.dataj.j) C.datak.i=A.datai.i;/把当前三元组A下行标i插入三元组C C

27、.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e;/把当前三元组A下标i对于的数值e插入三元组C k+; i+; else if(A.datai.j>B.dataj.j) C.datak.i=B.dataj.i;/把当前三元组B下行标i插入三元组C C.datak.j=B.dataj.j;/把当前三元组B下列标j插入三元组C C.datak.e=B.dataj.e;/把当前三元组B下标i对于的数值e插入三元组C k+; j+; else v=A.datai.e-B.dataj.e; if(v!=0) C.datak.i=A

28、.datai.i;/把当前三元组A下行标i插入三元组C C.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=v; /把三元组A-B下标i对于的数值v插入三元组C k+; i+; j+; else if(A.datai.i<B.dataj.i) C.datak.i=A.datai.i;/把当前三元组A下行标i插入三元组C C.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e;/把当前三元组A下标i对于的数值e插入三元组C k+; i+; else C.datak.i=B.dataj

29、.i;/把当前三元组B下行标i插入三元组C C.datak.j=B.dataj.j;/把当前三元组B下列标j插入三元组C C.datak.e=B.dataj.e;/把当前三元组B下标i对于的数值e插入三元组C k+; j+; while(i<=A.tu) C.datak.i=A.datai.i;/把当前三元组A下行标i插入三元组C C.datak.j=A.datai.j;/把当前三元组A下列标j插入三元组C C.datak.e=A.datai.e;/把当前三元组A下标i对于的数值e插入三元组C k+; i+; while(j<=B.tu) C.datak.i=B.dataj.i;/把当前三元组B下行标i插入三元组C C.datak.j=B.dataj.j;/把当前三元组B下列标j插入三元组C C.datak.e=B.dataj.e;/把当前三元组B下标i对于的数值e插入三元组C k+; j+; C.