實現(xiàn)稀疏矩陣(采用三元組表示)的基本運算實驗報告

1、實現(xiàn)稀疏矩陣（采用三元組表示）的基本運算實驗報告一 實驗題目: 實現(xiàn)稀疏矩陣（采用三元組表示）的基本運算二 實驗要求: （1） 生成如下兩個稀疏矩陣的三元組 a 和 b； （上機實驗指導 P92 ）（2） 輸出 a 轉(zhuǎn)置矩陣的三元組 ；（3） 輸出a + b 的三元組；（4） 輸出 a * b 的三元組；三 實驗內(nèi)容:3.1 稀疏矩陣的抽象數(shù)據(jù)類型:ADT SparseMatrix  數(shù)據(jù)對象:D=aij| i =  1,2,3,.,m;  j =1,2,3,n;  ai,jElemS

2、et,m和n分別稱為矩陣的行數(shù)和列數(shù)   數(shù)據(jù)關系 :  R=  Row , Col   Row =<ai,j ,ai,j+1> |  1 im , 1 j n-1  Col =<a i,j , a i+1,j >|  1im-1,1jn基本操作:CreateSMatrix(

3、&M) 操作結(jié)果：創(chuàng)建稀疏矩陣 MPrintSMatrix(M) 初始條件：稀疏矩陣M已經(jīng)存在 操作結(jié)果：打印矩陣M DestroySMatrix(&M) 初始條件：稀疏矩陣M已經(jīng)存在 操作結(jié)果：銷毀矩陣M CopySMatrix(M, &T) 初始條件：稀疏矩陣M已經(jīng)存在 操作結(jié)果：復制矩陣M到T  AddSMatrix(M, N, &Q) 初始條件：稀疏矩陣M、N已經(jīng)存在 操作結(jié)果：求矩陣的和Q=M+

4、N  SubSMatrix(M, N, &Q) 初始條件：稀疏矩陣M、N已經(jīng)存在 操作結(jié)果：求矩陣的差Q=M-N TransposeSMatrix(M, & T) 初始條件：稀疏矩陣M已經(jīng)存在 操作結(jié)果：求矩陣M的轉(zhuǎn)置T MultSMatrix(M, N, &Q) 初始條件：稀疏矩陣M已經(jīng)存在 操作結(jié)果：求矩陣的積Q=M*NADT SparseMatrix3.2存儲結(jié)構的定義#define N 4typedef

5、int ElemType;#define MaxSize 100/矩陣中非零元素最多個數(shù)typedef structint r; /行號 int c;/列號 ElemType d; /元素值 TupNode; /三元組定義typedef structint rows; /行數(shù)值 int cols; /列數(shù)值 int nums; /非零元素個數(shù) TupNode dataMaxSize; TSMatrix; /三元組順序表定義3.3基本操作實現(xiàn):void CreatMat(TSMatrix &t,ElemType ANN)int i,j;t.rows=N;t.cols=N;t.nums=0

6、;for (i=0;i<N;i+)for (j=0;j<N;j+)if (Aij!=0)t.datat.nums.r=i;t.datat.nums.c=j;t.datat.nums.d=Aij;t.nums+;void DispMat(TSMatrix t)int i;if (t.nums<=0)return;printf("t%dt%dt%dn",t.rows,t.cols,t.nums);printf("t-n");for (i=0;i<t.nums;i+) printf("t%dt%dt%dn",t.da

7、tai.r,t.datai.c,t.datai.d);3.4解題思路： 1. 轉(zhuǎn)置矩陣：只要判定原矩陣有值，那么只要遍歷一遍原矩陣，把原來矩陣中非0元素行列變換一下賦值到新的矩陣中即可。2. 矩陣加法：用各種 if 判斷，區(qū)分出矩陣進行加法時的可能情況，分情況處理即可。3. 矩陣乘法：通過 getvalue（c ， i， j） 函數(shù)查找 矩陣c 中i 行j列，所儲存的元素的值。然后便是模擬矩陣乘法的過程進行求解。3.5解題過程：實驗源代碼如下：3.5.1順序表的各種運算#include <stdio.h>#define N 4typedef int ElemType;#define

8、 MaxSize 100/矩陣中非零元素最多個數(shù)typedef structint r; /行號 int c;/列號 ElemType d; /元素值 TupNode; /三元組定義typedef structint rows; /行數(shù)值 int cols; /列數(shù)值 int nums; /非零元素個數(shù) TupNode dataMaxSize; TSMatrix; /三元組順序表定義void CreatMat(TSMatrix &t,ElemType ANN)int i,j;t.rows=N;t.cols=N;t.nums=0;for (i=0;i<N;i+)for (j=0;j

9、<N;j+)if (Aij!=0)t.datat.nums.r=i;t.datat.nums.c=j;t.datat.nums.d=Aij;t.nums+;void DispMat(TSMatrix t)int i;if (t.nums<=0)return;printf("t%dt%dt%dn",t.rows,t.cols,t.nums);printf("t-n");for (i=0;i<t.nums;i+)printf("t%dt%dt%dn",t.datai.r,t.datai.c,t.datai.d);void

10、 TranMat(TSMatrix t,TSMatrix &tb)int p,q=0,v; /q為tb.data的下標tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if (t.nums!=0)for (v=0;v<t.cols;v+)/tb.dataq中的記錄以c域的次序排列for (p=0;p<t.nums;p+) /p為t.data的下標if (t.datap.c=v)tb.dataq.r=t.datap.c;tb.dataq.c=t.datap.r;tb.dataq.d=t.datap.d;q+;bool MatAdd(TS

11、Matrix a,TSMatrix b,TSMatrix &c)int i=0,j=0,k=0;ElemType v;if (a.rows!=b.rows | a.cols!=b.cols)return false; /行數(shù)或列數(shù)不等時不能進行相加運算c.rows=a.rows;c.cols=a.cols; /c的行列數(shù)與a的相同while (i<a.nums && j<b.nums) /處理a和b中的每個元素if (a.datai.r=b.dataj.r)/行號相等時if(a.datai.c<b.dataj.c) /a元素的列號小于b元素的列號c.d

12、atak.r=a.datai.r;/將a元素添加到c中c.datak.c=a.datai.c;c.datak.d=a.datai.d;k+;i+; else if (a.datai.c>b.dataj.c)/a元素的列號大于b元素的列號c.datak.r=b.dataj.r;/將b元素添加到c中 c.datak.c=b.dataj.c; c.datak.d=b.dataj.d; k+;j+; else/a元素的列號等于b元素的列號v=a.datai.d+b.dataj.d;if (v!=0)/只將不為0的結(jié)果添加到c中c.datak.r=a.datai.r;c.datak.c=a.dat

13、ai.c;c.datak.d=v;k+;i+;j+; else if (a.datai.r<b.dataj.r) /a元素的行號小于b元素的行號c.datak.r=a.datai.r; /將a元素添加到c中c.datak.c=a.datai.c;c.datak.d=a.datai.d;k+;i+; else /a元素的行號大于b元素的行號c.datak.r=b.dataj.r; /將b元素添加到c中c.datak.c=b.dataj.c;c.datak.d=b.dataj.d;k+;j+; c.nums=k;return true;int getvalue(TSMatrix c,int

14、i,int j) int k=0; while (k<c.nums && (c.datak.r!=i | c.datak.c!=j)k+; if (k<c.nums)return(c.datak.d); elsereturn(0);bool MatMul(TSMatrix a,TSMatrix b,TSMatrix &c) int i,j,k,p=0;ElemType s;if (a.cols!=b.rows)/a的列數(shù)不等于b的行數(shù)時不能進行相乘運算return false;for (i=0;i<a.rows;i+)for (j=0;j<b.c

15、ols;j+) s=0; for (k=0;k<a.cols;k+)s=s+getvalue(a,i,k)*getvalue(b,k,j); if (s!=0) /產(chǎn)生一個三元組元素 c.datap.r=i; c.datap.c=j; c.datap.d=s; p+; c.rows=a.rows;c.cols=b.cols;c.nums=p;return true;int main()ElemType a1NN= 1,0,3,0, 0,1,0,0, 0,0,1,0, 0,0,1,1;ElemType b1NN= 3,0,0,0, 0,4,0,0, 0,0,1,0, 0,0,0,2;TSMatrix a,b,c;CreatMat(a,a1); CreatMat(b,b1);printf("a的三元組:n");DispMat(a);printf("b的三元組:n");DispMat(b);printf("a轉(zhuǎn)