稀疏矩陣的加減法

1、數(shù)據(jù)結構課 程 設 計 報 告 書題 目： 稀疏矩陣的加減法 專 業(yè)： 計算機科學與技術 學 號： 學生姓名： 指導教師： 完成日期： 2016-06-20 稀疏矩陣的加減法運算1. 題目描述假設稀疏矩陣A和B（m行n列）都采用三元組表示，編寫程序計算CA+B，D=A-B，矩陣C和D也采用三元組表示。編寫程序實現(xiàn)，并輸出結果。2. 預備知識 函數(shù)模塊調用關系 三元組中抽象數(shù)據(jù)類型定義 三元組表的賦值操作 三元組和稀疏矩陣之間的轉換3. 問題分析該程序主要實現(xiàn)以下功能：（1）用三元組存儲方式創(chuàng)建稀疏矩陣；（2）用三元組存儲方式進行稀疏矩陣的加法；（3）用三元組存儲方式進行稀疏矩陣的減法；程序流程

2、和設計思想可以用以下流程圖來描述：輸入menu中的編號2. 求兩個矩陣相減差1. 求兩個矩陣相加和 0. 退出系統(tǒng)運行結果并顯示出來 圖1.程序運行流程圖4. 數(shù)據(jù)結構設計抽象數(shù)據(jù)類型定義三元組中抽象數(shù)據(jù)類型定義 typedef struct /三元組表中元素類型的定義int i,j;int e;Triple; typedef struct a) Triple dataMAX+1; /存放非零元素的數(shù)組，行優(yōu)先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("請輸入矩陣的行、列和非零元素個數(shù):n");scanf("%d %d",&M.row,&M.nu); /輸入矩陣的行、列和非零元素個數(shù) 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的行列數(shù)是否相等 printf("error!n"); else C.row=A.row; /把A的行數(shù)賦給C C.nu=A.nu; /把A的列數(shù)賦給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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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的行列數(shù)是否相等 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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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. 退出系統(tǒng) "<<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; /存放非零元素的數(shù)組，行優(yōu)先int row,nu,tu;Matrix; /三元組表類型名 void InitMatrix(Matrix &M) /初始化三元組矩陣int num=0;M=*(Matrix *

19、)malloc(sizeof(Matrix); /為三元組申請內存 printf("請輸入矩陣的行、列和非零元素個數(shù):n");scanf("%d %d",&M.row,&M.nu); /輸入矩陣的行、列和非零元素個數(shù) 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的行列數(shù)是否相等 printf("error!n"); else C.row=A.row; /把A的行數(shù)賦給C C.nu=A.nu; /把A的列數(shù)賦給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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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的行列數(shù)是否相等 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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值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對于的數(shù)值e插入三元組C k+; j+; C.