稀疏矩陣運(yùn)算器

1、 數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告 題目：稀疏矩陣運(yùn)算器 班級(jí)： 姓名： 學(xué)號(hào)： 專(zhuān)業(yè)： 學(xué)院： 完成日期：1、 需求分析（1） 問(wèn)題描述：稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。（2） 基本要求：以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)果的矩陣則以通常的陣列形式列出。（3） 輸入的形式：界面已設(shè)計(jì)好，智能輸入（4） 測(cè)試數(shù)據(jù)2、 概要設(shè)計(jì)（1） 抽象數(shù)據(jù)類(lèi)型數(shù)組的定義ADT Array數(shù)據(jù)對(duì)象:ji=0,.,bi-1

2、,i=1,2,.,n;D=aj1j2.jn|n(>0)稱(chēng)為數(shù)組的維數(shù),bi是數(shù)組第i維的長(zhǎng)度,ji是數(shù)組元素的第i維下標(biāo),aj1j2.jn (-ElemSet數(shù)據(jù)關(guān)系:R=R1,R2,.Rn|Ri=|0<=jk<=bk-1,1<=k<=n且k<>i,0<=ji<=bi-2,aj1.ji.jn,aj1.ji+1 .jn(-D,i=2,.n基本操作:InitArray(&A,n,bound1,.,boundn)若維數(shù)和各維長(zhǎng)度合法,則構(gòu)造相應(yīng)的數(shù)組A,并返回OK.DestroyArray(&A)操作結(jié)果:銷(xiāo)毀數(shù)組A.Value(

3、A,&e,index1,.,indexn)初始條件:A是n維數(shù)組,e為元素變量,隨后是n個(gè)下標(biāo)值.操作結(jié)果:若各下標(biāo)不超界,則e賦值為所指定的A的元素值,并返回OK.Assign(&A,e,index1,.,indexn)初始條件:A是n維數(shù)組,e為元素變量,隨后是n個(gè)下標(biāo)值.操作結(jié)果:若下標(biāo)不超界,則將e的值賦給 所指定的A的元素,并返回OK.ADT Array（2） 數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn)Status InitArray(Array &A,int dim,.);Status DestroyArray(Array &A);Status Value(Array

4、 A,ElemType &e,.);Status Assign(Array &A,ElemType e,.);基本操作的算法描述:Status InitArray(Array &A,int dim,.)if(dim<1|dim>MAX_ARRAY_DIM) return ERROR;A.dim=dim;A.bounds=(int *)malloc(dim *sizeof(int);if(!A.bounds) exit(OVERFLOW);elemtotal=1;va_start(ap,dim);for(i=1;i< p="">

5、A.boundsi=va_arg(ap,int);if(A.boundsi<0) return UNDERFLOW;elemtotal*=A.boundsi;va_end(ap);A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType);if(!A.base) exit(OVERFLOW);A.constants=(int *)malloc(dim*sizeof(int);if(!A.constants) exit(OVERFLOW);A.constantsdim-1=1;for(i=dim-2;i>=0;-i)A.constants

6、i=A.boundsi+1*A.constantsi+1;return OK;Status DestoyArray(Array &A)if(!A.base) return ERROR;free(A.base); A.base=NULL;if !(A.bounds) return ERROR;free(A.bounds); A.bounds=NULL;if!(A.constatns) return ERROR;free(A.constants); A.constants=NULL;return OK;Status Locate(Array A,va_list ap,int &of

7、f)off=0;for(i=0;i< p="">ind=va_arg(ap,int);if(ind<0|ind>=A.boundsi) return OVERFLOW;off+=A.constantsi*ind;return OK;Status Value(Array A,ElemType &e,.)va_start(ap,e);if(result=Locate(A,ap,off)<=0 return result;e=*(A.base+off);return OK;Status Assign(Array &A,ElemType

8、 e,.)va_start(ap,e);if(result=Locate(A,ap,off)<=0) return result;*(A.base+off)=e;return OK;3、 詳細(xì)設(shè)計(jì)（1） 元素類(lèi)型、結(jié)點(diǎn)類(lèi)型和指針類(lèi)型typedef int ElemType; typedef struct /三元組表示元素 int i,j; /非零元的行下標(biāo)和列下標(biāo) ElemType e; /非零元的值 Triple; typedef struct Triple dataMAXSIZE+1; /非零元三元組表 int rposMAXRC+1; /各行第一個(gè)非零元在三元組的位置表 int m

9、u,nu,tu; /矩陣的行數(shù)，列數(shù)和非零元的個(gè)數(shù) TSMatrix,*Matrix; （2） 初始化稀疏矩陣函數(shù)void Creat(TSMatrix &M) /初始化矩陣 int i,k; for(i=1;i<=MAXRC+1;i+) M.rposi=0; printf("請(qǐng)輸入矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)(以空格隔開(kāi)):"); scanf("%d %d %d",&M.mu,&M.nu,&M.tu); for(i=1;i<=M.tu;i+)printf("請(qǐng)用三元組形式輸入矩陣的元素(行 列 非零

10、元素):"); scanf("%d %d %d",&M.datai.i,&M.datai.j,&M.datai.e); for(i=1,k=1;i<=M.mu;i+) M.rposi=k; /記下每一行第一個(gè)非零元在X.data中的序號(hào)while(M.datak.i<=i && k<=M.tu) /移到下一行的第一個(gè)非零元k+; （3) 稀疏矩陣相加，相減函數(shù)void Xiangjia(TSMatrix A,TSMatrix B,TSMatrix &C,int n) /n為控制符（相加為+1，相減為

11、-1） int a,b,temp,l; C.mu=A.mu;C.nu=A.nu;a=b=l=1;while(a<=A.tu && b<=B.tu) if(A.dataa.i=B.datab.i) /元素所在行數(shù)相同 if(A.dataa.j<B.datab.j) /同一行元素A所在列數(shù)小于BC.datal+=A.dataa+; /把A中值賦給Celse if(A.dataa.j>B.datab.j) C.datal=B.datab; /否則把B中值賦給C C.datal+.e=n*B.datab+.e;elsetemp=A.dataa.e+n*B.dat

12、ab.e; /否則就相加if(temp) /判斷是不是零 C.datal=A.dataa; C.datal.e=temp; l+; a+;b+; else if(A.dataa.i<B.datab.i) /元素所在行數(shù)不同且A的行小于B的行，把A直接賦給CC.datal+=A.dataa+; else C.datal=B.datab; /元素所在行數(shù)不同且B的行小于A的行，把B直接賦給CC.datal+.e=n*B.datab+.e; while(a<=A.tu) /A或B中多于的元素直接賦給C C.datal+=A.dataa+; while(b<=B.tu)C.datal

13、=B.datab; C.datal+.e=n*B.datab+.e; C.tu=l-1; （4） 稀疏矩陣相乘函數(shù)int Xiangcheng(TSMatrix A,TSMatrix B,TSMatrix &Q) /與書(shū)中的算法基本相同，不多做解釋 int arow,brow,ccol,tp,p,q,t; int ctempMAXRC+1; if(A.nu!=B.mu)return 0; /A的行與B的列不想等Q.mu=A.mu;Q.nu=B.nu;Q.tu=0;if(A.tu*B.tu) for(arow=1;arow<=A.mu;arow+) /處理A的每一行 for(cco

14、l=1;ccol<=Q.nu;ccol+) ctempccol=0; /當(dāng)前行各元素累加器清零 Q.rposarow=Q.tu+1; if(arow<A.mu)tp=A.rposarow+1;elsetp=A.tu+1;for(p=A.rposarow;p<tp;p+) /對(duì)當(dāng)前行中的第一個(gè)非零元brow=A.datap.j; /找到對(duì)應(yīng)元在B中的行號(hào)if(brow<B.mu)t=B.rposbrow+1;elset=B.tu+1;for(q=B.rposbrow;q<t;q+)ccol=B.dataq.j; /乘積元素在Q中列號(hào)ctempccol+=A.data

15、p.e*B.dataq.e; for(ccol=1;ccol<=Q.nu;ccol+) /壓縮存儲(chǔ)改行非零元 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; （5） 三元組表打印出矩陣void Print_SMatrix(TSMatrix M) /將三元組表打印出矩陣 int k,l,n; Matrix p; p=&M; for(k=1,n=1;k<=p->mu;k+) for(l=1;

16、l<=p->nu;l+) if(p->datan.i=k && p->datan.j=l) printf("%5d",p->datan.e); /控制格式n+; else printf("%5d",0); printf("n"); printf("n"); （6） 銷(xiāo)魂函數(shù)void Destory_SMatrix(TSMatrix &M) /銷(xiāo)毀函數(shù) M.mu=M.nu=M.tu=0; （7） 主函數(shù)void main() /主函數(shù) TSMatrix A,B,C

17、; TSMatrix *p=&A,*q=&B;int flag,n; while(1) /操作界面 printf("tn"); printf("t * 稀疏矩陣的加、減、轉(zhuǎn)、乘 * n");printf("tn"); printf("t 1、稀疏矩陣的加法 n"); printf("t 2、稀疏矩陣的減法 n"); printf("t 3、稀疏矩陣的乘法 n"); printf("t 4、退出該應(yīng)用程序 n"); printf("

18、tn");printf("輸入要進(jìn)行的項(xiàng)目的編號(hào):"); scanf("%d",&flag); if(flag=4)break; Creat(A); printf("矩陣A:n"); Print_SMatrix(A); switch(flag) case 1:Creat(B);n=1; printf("矩陣B:n"); Print_SMatrix(B); if(A.mu=B.mu && A.nu=B.nu) printf("A+B:n"); Xiangjia(A,B,C,n);Print_SMatrix(C); else print