稀疏矩阵的压缩存储及运算.doc

稀疏矩阵的压缩存储及运算1、 实验内容实现稀疏矩阵的压缩存储方法以及在特定存储方法下的基本运算2、 实验母的掌握数组的应用，包括稀疏矩阵、特殊矩阵的压缩存储方法。矩阵的基本运算的实现，包括矩阵相加、转置、乘法等。3、 问题描述1）用行逻辑链接顺序表和十字链表分别实现稀疏矩阵的压缩存储2）编程实现矩阵的转置运算和乘法运算（运用行逻辑链接顺序表或十字链表作为存储结构）四、问题的实现稀疏矩阵的抽象数据类型定义：ADT SpareseMatrix数据对象： 数据关系： ：基本操作：CreateSMatrix(&M)；操作结果：创建稀疏矩阵M。PrintSMatrix(M)；初始条件：稀疏矩阵M存在。操作结果：输出稀疏矩阵M。AddSMatrix(M，N，&Q)；初始条件：稀疏矩阵M和N的行数和列数对应相等。操作结果：求稀疏矩阵的和Q=M+N。MultSMatrix(M，N，&Q)；初始条件：稀疏矩阵M的列数等于N的行数。操作结果：求稀疏矩阵乘积Q=M*N。TransposeSMatrix(M,&T)；初始条件：稀疏矩阵M存在。操作结果：求稀疏矩阵M的转置矩阵T。ADT SpareseMatrix5、 主要源程序代码#includeusing namespace std;#define MAXSIZE 100;int num100;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;coutM.mu;cinM.nu;cinM.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请输入稀疏矩阵，若为空，则退出i;cinj;cine;while (i!=0)p=(OLink)malloc(sizeof(OLNode);p-i=i;p-j=j;p-e=e;if (M.rheadi=NULL | M.rheadi-jj) p-right=M.rheadi;M.rheadi=p;elseq=M.rheadi;while (q-right & q-right-jright;p-right=q-right;q-right=p;if (M.cheadj=NULL | M.cheadj-ii) p-down=M.cheadj;M.cheadj=p;elseq=M.cheadj;while (q-down & q-down-idown;p-down=q-down;q-down=p;cini;cinj;cine;return 1; /创建十字链表void TurnSMatrix_OL(CrossList &M)int a,b;OLink p,q;for(a1;ai;p-i=p-j;p-j=b;q=p-right;p-right=p-down;p-down=q; /十字链表实现稀疏矩阵转置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;jnu;j+) cpj=A-cheadj;for(i=1;imu;i+)pa=A-rheadi;pb=B-rheadi;pre=NULL;while(pb)if(pa=NULL | pa-jpb-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(pa-jj) 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 cpp-j-down=p-down;free(p);pb=pb-right;A-mu=A-muB-mu? A-mu:B-mu;A-nu=A-nuB-nu? A-nu:B-nu;return 1; /十字链表实现两稀疏矩阵相加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稀疏矩阵A的列数和B的行数不相等，不能相乘;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;jjq0-i) q0=q0-down;else if(p0-ji) 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-down=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; /十字链表实现两稀疏矩阵相乘int ShowSMatrix(CrossList *A)int a;OLink p;for(a=1;amu;a+)if(A-rheada) p=A-rheada;while(p)printf(%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请选择操作：endl;cout1：实现稀疏矩阵的转置endl;cout2：实现两稀疏矩阵的相加endl;cout3：实现两稀疏矩阵的相乘endl;cout4：退出程序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;Creat