稀疏矩阵的存储和快速转置实验报告.doc

福 建 工 程 学 院课程设计课 程： 数据结构 题 目： 稀疏矩阵的快速转置 专 业： 计算机类 班 级： 座 号： 姓 名： 2013年6月25日 实验题目：稀疏矩阵的快速转置一、要解决的问题利用三元组表存储稀疏矩阵，利用快速转置算法进行转置，并输出转置之前和之后的三元组表以及矩阵。二、算法基本思想描述：由于稀疏矩阵的非零元素较少，零元素较多，所以只需存储其非零元素。因此可以建立一个三元组表，分别保存稀疏矩阵的非零元素的行号、列号和元素值。对稀疏矩阵进行快速转置是可以引入两个向量numn+1,cpotn+1,分别标记矩阵中第col列的非零元素个数和第一个非零元素在转置后的矩阵的位置；再扫描三元组表，找到非零元素，直接对其在转置后的矩阵所在的位置上进行修改，以节省时间。三、详细设计元素类型，结点类型typedef struct int i,j; int e;Triple;typedef struct Triple dataMAXSIZE+1; int mu,nu,tu; Tsmatrix; 2.对抽象数据类型中的部分基本操作的伪码算法如下：Tsmatrix * creatarray(Tsmatrix *M) int m,n,p=1; int c; printf(please input the array A:n); for(m=1;m=a;m+) for(n=1;ndatap.e=c; M-datap.i=m; M-datap.j=n; p+; M-tu=p; M-mu=a; M-nu=b; printf(yuan lai san yuan zu de biao shi wei :nn); for(m=1;mtu;m+) printf(%3d%3d%3dt,M-datam.i,M-datam.j,M-datam.e); printf(n); return M; /*三元组快速转置*/Tsmatrix * fasttrans(Tsmatrix *M,Tsmatrix *T) int p,col,q,t,m; int num100; int cpot100; T-mu=M-nu; T-nu=M-mu; T-tu=M-tu; if(T-tu!=0) for(col=1;colnu;col+) numcol=0; for(t=1;ttu;t+) +numM-datat.j; cpot1=1; for(col=2;colnu;col+) cpotcol=cpotcol-1+numcol-1; for(p=1;ptu;+p) col=M-datap.j; q=cpotcol; T-dataq.i=M-datap.j; T-dataq.j=M-datap.i; T-dataq.e=M-datap.e; +cpotcol; printf(nnzhuan zhi hou de san yuan zu biao shi wei :nn); for(m=1;mtu;m+) printf(%3d%3d%3dt,T-datam.i,T-datam.j,T-datam.e); printf(n); return T;/*输出三元组函数*/void print(Tsmatrix *T,int x,int y) int m,n,p=1; int d; for(m=1;m=x;m+) printf(n); for(n=1;ndatap.i=m&T-datap.j=n) d=T-datap.e; p+; else d=0; printf(%6d,d); 3.主函数和其他函数的伪码算法void main() Tsmatrix *M,*T; M=(Tsmatrix *)malloc(sizeof(Tsmatrix); T=(Tsmatrix *)malloc(sizeof(Tsmatrix); printf(please input arrays row and col:n); scanf(%d%d,&a,&b); /*输入行列数*/ M=creatarray(M); /*创建稀疏矩阵*/ printf(you had creat the array:n); print(M,a,b); /*输出创建好的三元组*/ T=fasttrans(M,T); /*将三元组转置*/ printf(the trans array is:n); print(T,b,a); getch();4、模块结构及功能稀疏矩阵快速转置函数输出稀疏矩阵函数主程序创建稀疏矩阵3四、源程序清单：#include#define MAXSIZE 100typedef struct int i,j; int e;Triple;typedef struct Triple dataMAXSIZE+1; int mu,nu,tu; Tsmatrix;int a,b; /*定义全局变量数组的行数a和列数b*/*用数组创建三元组*/Tsmatrix * creatarray(Tsmatrix *M) int m,n,p=1; int c; printf(please input the array A:n); for(m=1;m=a;m+) for(n=1;ndatap.e=c; M-datap.i=m; M-datap.j=n; p+; M-tu=p; M-mu=a; M-nu=b; printf(yuan lai san yuan zu de biao shi wei :nn); for(m=1;mtu;m+) printf(%3d%3d%3dt,M-datam.i,M-datam.j,M-datam.e); printf(n); return M;/*三元组快速转置*/Tsmatrix * fasttrans(Tsmatrix *M,Tsmatrix *T) int p,col,q,t,m; int num100; int cpot100; T-mu=M-nu; T-nu=M-mu; T-tu=M-tu; if(T-tu!=0) for(col=1;colnu;col+) numcol=0; for(t=1;ttu;t+) +numM-datat.j; cpot1=1; for(col=2;colnu;col+) cpotcol=cpotcol-1+numcol-1; for(p=1;ptu;+p) col=M-datap.j; q=cpotcol; T-dataq.i=M-datap.j; T-dataq.j=M-datap.i; T-dataq.e=M-datap.e; +cpotcol; printf(nnzhuan zhi hou de san yuan zu biao shi wei :nn); for(m=1;mtu;m+) printf(%3d%3d%3dt,T-datam.i,T-datam.j,T-datam.e); printf(n); return T;/*输出三元组函数*/void print(Tsmatrix *T,int x,int y) int m,n,p=1; int d; for(m=1;m=x;m+) printf(n); for(n=1;ndatap.i=m&T-datap.j=n) d=T-datap.e; p+; else d=0; printf(%6d,d); void main() Tsmatrix *M,*T; M=(Tsmatrix *)malloc(sizeof(Tsmatrix); T=(Tsmatrix *)malloc(sizeof(Tsmatrix); printf(please input arrays row and col:n); scanf(%d%d,&a,&b); /*输入行列数*/ M=creatarray(M); printf(you had creat the array:n); print(M,a,b); T=fasttrans(M,T); printf(the trans array is:n); print(T,b,a); getch();五、测试数据及测试结果：（1）我