稀疏矩陣的壓縮存儲及運算

1、稀疏矩陣的壓縮存儲及運算1、 實驗內容實現(xiàn)稀疏矩陣的壓縮存儲方法以及在特定存儲方法下的基本運算2、 實驗母的掌握數(shù)組的應用，包括稀疏矩陣、特殊矩陣的壓縮存儲方法。矩陣的基本運算的實現(xiàn)，包括矩陣相加、轉置、乘法等。3、 問題描述1）用行邏輯鏈接順序表和十字鏈表分別實現(xiàn)稀疏矩陣的壓縮存儲2）編程實現(xiàn)矩陣的轉置運算和乘法運算（運用行邏輯鏈接順序表或十字鏈表作為存儲結構）四、問題的實現(xiàn)稀疏矩陣的抽象數(shù)據(jù)類型定義：ADT SpareseMatrix數(shù)據(jù)對象： 數(shù)據(jù)關系： ：基本操作：CreateSMatrix(&M)；操作結果：創(chuàng)建稀疏矩陣M。PrintSMatrix(M)；初始條件：稀疏矩陣M

2、存在。操作結果：輸出稀疏矩陣M。AddSMatrix(M，N，&Q)；初始條件：稀疏矩陣M和N的行數(shù)和列數(shù)對應相等。操作結果：求稀疏矩陣的和Q=M+N。MultSMatrix(M，N，&Q)；初始條件：稀疏矩陣M的列數(shù)等于N的行數(shù)。操作結果：求稀疏矩陣乘積Q=M*N。TransposeSMatrix(M,&T)；初始條件：稀疏矩陣M存在。操作結果：求稀疏矩陣M的轉置矩陣T。ADT SpareseMatrix5、 主要源程序代碼#include<iostream>using namespace std;#define MAXSIZE 100;int num10

3、0;typedef struct OLNodeint i,j;int e;struct OLNode *right,*down;OLNode,*OLink;typedef structOLink *rhead,*chead;int mu,nu,tu;CrossList; /十字鏈表結構體定義int CreatSMatrix_OL(CrossList &M)int i,j,e;OLink q;OLink p;cout<<"請輸入稀疏矩陣的行數(shù)，列數(shù)，非零元素的個數(shù)："cin>>M.mu;cin>>M.nu;cin>>M.

4、tu;M.rhead=(OLink *)malloc(M.mu+1)*sizeof(OLNode);M.chead=(OLink *)malloc(M.nu+1)*sizeof(OLNode);for(i=1;i<=M.mu;i+) M.rheadi=NULL;for(i=1;i<=M.nu;i+) M.cheadi=NULL;cout<<"請輸入稀疏矩陣，若為空，則退出"<<endl;cin>>i;cin>>j;cin>>e;while (i!=0)p=(OLink)malloc(sizeof(OLN

5、ode);p->i=i;p->j=j;p->e=e;if (M.rheadi=NULL | M.rheadi->j>j) p->right=M.rheadi;M.rheadi=p;elseq=M.rheadi;while (q->right && q->right->j<j) q=q->right;p->right=q->right;q->right=p;if (M.cheadj=NULL | M.cheadj->i>i) p->down=M.cheadj;M.cheadj=p

6、;elseq=M.cheadj;while (q->down && q->down->i<i)q=q->down;p->down=q->down;q->down=p;cin>>i;cin>>j;cin>>e;return 1; /創(chuàng)建十字鏈表void TurnSMatrix_OL(CrossList &M)int a,b;OLink p,q;for(a<1;a<=M.mu;a+)q=p=M.rheada;while(q)b=p->i;p->i=p->j;p-

7、>j=b;q=p->right;p->right=p->down;p->down=q; /十字鏈表實現(xiàn)稀疏矩陣轉置int AddSMatrix_OL(CrossList *A,CrossList *B)OLNode *pa,*pb,*p,*pre,*cp100;int i,j,t;t=A->tu+B->tu;for(j=1;j<=A->nu;j+) cpj=A->cheadj;for(i=1;i<=A->mu;i+)pa=A->rheadi;pb=B->rheadi;pre=NULL;while(pb)if(p

8、a=NULL | pa->j>pb->j)p=(OLink)malloc(sizeof(OLNode);if(!pre)A->rheadi=p;else pre->right=p;p->right=pa;pre=p;p->i=i;p->j=pb->j;p->e=pb->e;if(!A->cheadp->j)A->cheadp->j=cpp->j=p;p->down=NULL;elsecpp->j->down=p;cpp->j=p;pb=pb->right;else if

9、(pa->j<pb->j) pre=pa;pa=pa->right;else if(pa->e+pb->e)t-;pa->e+=pb->e;pre=pa;pa=pa->right;pb=pb->right;elset=t-2;if(!pre)A->rheadi=pa->right;else pre->right=pa->right;p=pa;pa=pa->right;if(A->cheadp->j=p) A->cheadp->j=cpp->j=p->down;else

10、cpp->j->down=p->down;free(p);pb=pb->right;A->mu=A->mu>B->mu? A->mu:B->mu;A->nu=A->nu>B->nu? A->nu:B->nu;return 1; /十字鏈表實現(xiàn)兩稀疏矩陣相加int MultSMatrix_OL(CrossList M,CrossList N,CrossList &Q)int i,j,e;OLink p0,q0,p,p1,p1a;if(M.nu!=N.mu)cout<<"稀

11、疏矩陣A的列數(shù)和B的行數(shù)不相等，不能相乘"return 0;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(!(Q.rhead=(OLink *)malloc(Q.mu+1)*sizeof(OLink)exit(-2);if(!(Q.chead=(OLink *)malloc(Q.nu+1)*sizeof(OLink)exit(-2);for(i=1;i<=Q.mu;i+) Q.rheadi=NULL;for(i=1;i<=Q.nu;i+) Q.cheadi=NULL;for(i=1;i<=Q.mu;i+)for(j=1;j<=Q.nu;j+)p0

12、=M.rheadi;q0=N.cheadj;e=0;while(p0 && q0)if(p0->j>q0->i) q0=q0->down;else if(p0->j<q0->i) p0=p0->right;elsee+=p0->e*q0->e;q0=q0->down;p0=p0->right;if(e)if(!(p=(OLink)malloc(sizeof(OLNode)exit(-2);Q.tu+;p->i=i;p->j=j;p->e=e;p->right=NULL;p->d

13、own=NULL;if(Q.rheadi=NULL)Q.rheadi=p1=p;else p1->right=p;p1=p;if(Q.cheadj=NULL)Q.cheadj=p;elsep1a=Q.cheadj;while(p1a->down)p1a=p1a->down;p1a->down=p;return 1; /十字鏈表實現(xiàn)兩稀疏矩陣相乘int ShowSMatrix(CrossList *A)int a;OLink p;for(a=1;a<=A->mu;a+)if(A->rheada) p=A->rheada;while(p)printf

14、("%3d%3d%3dn",p->i,p->j,p->e);p=p->right;return 1; /十字鏈表顯示void main() int n;char c;CrossList MM,TT,SS;CreatSMatrix_OL(MM);cout<<"您輸入的稀疏矩陣（只列出非零元素）："<<endl;cout<<"行列大小"<<endl;ShowSMatrix(&MM);cout<<"請選擇操作："<<e

15、ndl;cout<<"1：實現(xiàn)稀疏矩陣的轉置"<<endl;cout<<"2：實現(xiàn)兩稀疏矩陣的相加"<<endl;cout<<"3：實現(xiàn)兩稀疏矩陣的相乘"<<endl;cout<<"4：退出程序"<<endl;cin>>n;switch(n)case 1:TurnSMatrix_OL(MM);cout<<"轉置后的稀疏矩陣：行列大小"<<endl;ShowSMatrix(&MM);break;case 2:cout<<"請輸入另一個稀疏矩陣："<<endl;CreatSMatrix_OL(TT);AddSMatrix_OL(&MM,&TT);cout<<"相加后的矩陣為："<<endl;ShowSMatrix(&MM);break;case 3:cout<<"請輸入另一個稀疏矩陣："<<endl;CreatSMatr