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

1、稀疏矩阵三元组实现矩阵转置算法实验报告 实验三稀疏矩阵的三元组表示实现矩阵转置算法 学院专业班 学号姓名 实习目的 掌握稀疏矩阵的三元组顺序表存储表示； 掌握稀疏矩阵三元组表示的传统转置算法的实现； 掌握稀疏矩阵三元组表示的快速转置算法的实现； 实习内容 稀疏矩阵的按三元组形式输入，即按行序输入非零元的行号、列号、值，实现传统转置算法，输出按通常的阵列形式输出。 稀疏矩阵的按三元组形式输入，即按行序输入非零元的行号、列号、值，实现快速转置算法，输出按通常的阵列形式输出。 实验步骤 三元组的定义 #define MAX_SIZE 100 / 非零元个数的最大值 struct Triple int

2、 i,j; / 行下标,列下标 Elemtype e; / 非零元素值 ; struct TSMatrix struct Triple dataMAX_SIZE+1; / 非零元三元组表，data0未用 int mu,nu,tu; / 矩阵的行数、列数和非零元个数 ; 创建稀疏矩阵M （按三元组形式输入，即按行序输入非零元的行号、列号、值） 3. 编写三元组传统转置函数。 4. 编写三元组快速转置函数。 4. .主函数 (1)程序代码 #include "stdio.h" #include "stdlib.h" #define MAX_SIZE

3、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("请输入矩阵的行数,列数,非零元素数：&quo

4、t;); 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(m1|mM.mu|n1|nM

5、.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(k=M.t

6、u&&p-i=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

7、; 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

8、(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中的

9、序号为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(

10、"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(&qu