C语言数据结构 稀疏矩阵

实验十 稀疏矩阵#include #define OK 1#define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 100 typedef int Status; typedef float ElemType;typedef struct int i,j; /非零元素行下标和列下标 ElemType e; /非零元素值 Triple;typedef struct Triple dataMAXSIZE+1;/非零元三元组表，data0不用 int mu,nu,tu; /矩阵的行数、列数和非零元素个数 TSMatrix; TSMatrix NewMatrix(int m,int n); /新建一个三元组表示的稀疏矩阵 Status InsertElem(TSMatrix *M,int row,int col,ElemType e); /在三元组表示的稀疏矩阵M，第 row 行，第 col 列位置插入元素e /插入成功，返回OK，否则返回ERROR Status FindElem(const TSMatrix *M,int row,int col,ElemType *e); /查找三元组表示的稀疏矩阵M中，第 row 行，第 col列元素，若不为0， /则用e返回其值，并返回TRUE，否则返回FALSE Status TransposeSMatrix(const TSMatrix *M,TSMatrix *T); /采用三元组表存储表示，求稀疏矩阵M的转置矩阵T Status FastTransposeSMatrix(const TSMatrix *M,TSMatrix *T); /利用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T Status MultSMatrix(const TSMatrix *M,const TSMatrix *T,TSMatrix *Q); /稀疏矩阵的乘法,如果符合乘法规则，Q返回M*T结果，并返回OK,否则返回ERROR void PrintSMatrix(const TSMatrix *M); /打印稀疏矩阵所有元素 int main() TSMatrix M=NewMatrix(3,4); TSMatrix T; TSMatrix Q; InsertElem(&M,3,2,3.65); InsertElem(&M,2,2,2.31); printf(nM:); PrintSMatrix(&M); FastTransposeSMatrix(&M,&T); printf(nT(Transpose of M):); PrintSMatrix(&T); MultSMatrix(&M,&T,&Q); printf(nM*T=); PrintSMatrix(&Q); return 0; TSMatrix NewMatrix(int m,int n) /新建一个三元组表示的稀疏矩阵 TSMatrix M; M.mu=m; M.nu=n; M.tu=0; return M; Status InsertElem(TSMatrix *M,int row,int col,ElemType e) /在三元组表示的稀疏矩阵M，第 row 行，第 col 列位置插入元素e /插入成功，返回OK，否则返回ERROR int i,t,p; if(M-tu=MAXSIZE) /当前三元组表已满 printf(nError:There is no space in the matrix;n); return ERROR; if(rowM-mu|colM-nu|row1|coltu=0) /插入前矩阵M没有非零元素 M-datap.i=row; M-datap.j=col; M-datap.e=e; M-tu+; return OK; for(t=1;ttu;t+)/寻找合适的插入位置 if(row=M-datat.i)&(col=M-datat.j) p+; if(row=M-datat-1.i & col=M-datat-1.j)/插入前，该元素已经存在 M-datat-1.e=e; return OK; for(i=M-tu;i=p;i-)/移动p之后的元素 M-datai+1.i=M-datai.i; M-datai+1.j=M-datai.j; M-datai+1.e=M-datai.e; /插入新元素 M-datap.i=row; M-datap.j=col; M-datap.e=e; M-tu+; return OK; Status FindElem(const TSMatrix *M,int row,int col,ElemType *e) /查找三元组表示的稀疏矩阵M中，第 row 行，第 col列元素，若不为0， /则用e返回其值，并返回TRUE，否则返回FALSE int p; for(p=1;ptu;p+) if(M-datap.i=row&M-datap.j=col) *e=M-datap.e; return TRUE; return FALSE; Status TransposeSMatrix(const TSMatrix *M,TSMatrix *T) /采用三元组表存储表示，求稀疏矩阵M的转置矩阵T int col,p,q; T-mu=M-nu; T-nu=M-mu; T-tu=M-tu; if(T-tu) q=1; for(col=1;colmu;col+) for(p=1;ptu;p+) if(M-datap.j=col) T-dataq.i=M-datap.j; T-dataq.j=M-datap.i; T-dataq.e=M-datap.e; q+; return OK; Status FastTransposeSMatrix(const TSMatrix *M,TSMatrix *T) /利用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T int col,t,p,q,*num,*cpot; T-mu=M-nu; T-nu=M-mu; T-tu=M-tu; if(T-tu) num=(int *)malloc(sizeof(int)*M-tu); cpot=(int *)malloc(sizeof(int)*M-tu); if(!(num&cpot) printf(Apply for memory error.n); exit(0); for(col=1;colnu;col+) numcol=0; /求M中每一列含有非零元素的个数 for(t=1;ttu;t+) +numM-datat.j; cpot1=1; /求第col列中第一个非零元素在b.data中的序号 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-dataq.e; +cpotcol; /for /if return OK; Status MultSMatrix(const TSMatrix *M,const TSMatrix *T,TSMatrix *Q) /稀疏矩阵的乘法,如果符合乘法规则，Q返回M*T结果，并返回OK,否则返回ERROR int i,j,k,p; ElemType m,t,s; if(M-nu!=T-mu) printf(Sorry,these two matrice cant multiply.n); return ERROR; Q-mu=M-mu; Q-nu=T-nu; Q-tu=0; p=1; for(i=1;imu;i+) for(j=1;jnu;j+) s=0; for(k=1;knu;k+) if(FALSE=FindElem(M,i,k,&m) continue; if(FALSE=FindElem(T,k,j,&t) continue; s+=m*t; if(s!=0)/Qij非零 Q-datap.i=i; Q-datap.j=j; Q-datap.e=s; p+; Q-tu+; return OK; void PrintSMatrix(const TSMatrix *M) /打印稀疏矩阵所有元素 int i,j,p=1; printf(nsize:%d