稀疏矩阵三元组实现矩阵转置算法实验报告

实验三 稀疏矩阵的三元组表示实现矩阵转置算法 学院 专业 班 学号 姓名 一 实习目的1. 掌握稀疏矩阵的三元组顺序表存储表示；2. 掌握稀疏矩阵三元组表示的传统转置算法的实现；3. 掌握稀疏矩阵三元组表示的快速转置算法的实现；二 实习内容1. 稀疏矩阵的按三元组形式输入，即按行序输入非零元的行号、列号、值，实现传统转置算法，输出按通常的阵列形式输出。2. 稀疏矩阵的按三元组形式输入，即按行序输入非零元的行号、列号、值，实现快速转置算法，输出按通常的阵列形式输出。三 实验步骤1. 三元组的定义 #define MAX_SIZE 100 / 非零元个数的最大值 struct Triple int i,j; / 行下标,列下标 ElemType e; / 非零元素值 ; struct TSMatrix struct Triple dataMAX_SIZE+1; / 非零元三元组表，data0未用 int mu,nu,tu; / 矩阵的行数、列数和非零元个数 ;2. 创建稀疏矩阵M （按三元组形式输入，即按行序输入非零元的行号、列号、值）3. 编写三元组传统转置函数。 4. 编写三元组快速转置函数。4. .主函数 (1)程序代码#include stdio.h #include stdlib.h#define MAX_SIZE 100 / 非零元个数的最大值 typedef int ElemType;struct Triple int i,j; / 行下标,列下标 ElemType e; / 非零元素值 ; struct TSMatrix struct Triple dataMAX_SIZE+1; / 非零元三元组表，data0未用 int mu,nu,tu; / 矩阵的行数、列数和非零元个数 ; int CreateSMatrix(TSMatrix &M) / 创建稀疏矩阵M int i,m,n; ElemType e; int k; printf(请输入矩阵的行数,列数,非零元素数：); scanf(%d,%d,%d,&M.mu,&M.nu,&M.tu); if(M.tuMAX_SIZE) return -1; M.data0.i=0; / 为以下比较顺序做准备 for(i=1;i=M.tu;i+) do printf(请按行序顺序输入第%d个非零元素所在的行(1%d),列(1%d),元素值:,i,M.mu,M.nu); scanf(%d,%d,%d,&m,&n,&e); /输入非零元的行号、列号、元素值 k=0; if(mM.mu|nM.nu) / 行或列超出范围 k=1; if(mM.datai-1.i|m=M.datai-1.i&n=M.datai-1.j) / 行或列的顺序有错 k=1; while(k); M.datai.i =m; / 将m,n,e 填入M M.datai.j =n; M.datai.e =e; return 1; void PrintSMatrix(TSMatrix M) / 按矩阵形式输出M int i,j,k=1; Triple *p=M.data; p+; / p指向第1个非零元素 for(i=1;i=M.mu;i+) for(j=1;j=M.nu;j+) if(ki=i&p-j=j) / p指向非零元，且p所指元素为当前处理元素 printf(%3d,p-e); / 输出p所指元素的值 p+; / p指向下一个元素 k+; / 计数器+1 else / p所指元素不是当前处理元素 printf(%3d,0); / 输出0 printf(n); void TransposeSMatrix(TSMatrix M,TSMatrix &T) / 求稀疏矩阵M的转置矩阵T。int p,q,col; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu) q=1; for(col=1;col=M.nu;+col) for(p=1;p= M.tu; +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; void FastTransposeSMatrix(TSMatrix M,TSMatrix &T) / 快速求稀疏矩阵M的转置矩阵T。算法5.2改 int p,q,t, k ,col,*num,*cpot; num=(int *)malloc(M.nu+1)*sizeof(int); / 存M每列(T每行)非零元素个数(0不用) cpot=(int *)malloc(M.nu+1)*sizeof(int); / 存T每行的下1个非零元素的存储位置(0不用) T.mu=M.nu; / 给T的行、列数与非零元素个数赋值 T.nu=M.mu; T.tu=M.tu; if(T.tu) / 是非零矩阵 for(col=1;col=M.nu;+col) numcol=0; / 计数器初值设为0 for(t=1;t=M.tu;+t) / 求M中每一列含非零元素个数 k=M.datat.j; +num col; cpot1=1; / T的第1行的第1个非零元在T.data中的序号为1 for(col=2;col=M.nu;+col) cpotcol=cpotcol-1+numcol-1; / 求T的第col行的第1个非零元在T.data中的序号 printf(num数组的值为：n); for(col=1;col=M.nu;+col) printf(%4d,numcol); printf(n); printf(转置前cpot数组的值为：n); for(col=1;col=M.nu;+col) printf(%4d,cpotcol); printf(n); for(p=1;p=M.tu;+p) / 从M的第1个元素开始 col= M.datap.j; / 求得在M中的列数 q= cpotM.datap.j; / q指示M当前的元素在T中的序号 T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +cpotcol; / T第col行的下1个非零元在T.data中的序号 printf(转置后cpot数组的值为：n); for(col=1;col=M.nu;+col) printf(%4d,cpotcol); printf(n); free(num); free(cpot); void main() TSMatrix A,T; printf(创建矩阵A: ); CreateSMatrix(A); PrintSMatrix(A); TransposeSMatrix(A,T); printf