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

1、实验三 稀疏矩阵的三元组表示实现矩阵转置算法 学院 专业 班 学号 姓名 一 实习目的1. 掌握稀疏矩阵的三元组顺序表存储表示；2. 掌握稀疏矩阵三元组表示的传统转置算法的实现；3. 掌握稀疏矩阵三元组表示的快速转置算法的实现；二 实习内容1. 稀疏矩阵的按三元组形式输入，即按行序输入非零元的行号、列号、值，实现传统转置算法，输出按通常的阵列形式输出。2. 稀疏矩阵的按三元组形式输入，即按行序输入非零元的行号、列号、值，实现快速转置算法，输出按通常的阵列形式输出。三 实验步骤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; / 矩阵的行数、列数和非零元个数 ;2. 创建稀疏矩阵M （按三元组形式输入，即按行序输入非零元的行号、列号、值）3. 编写三元组传统转置函数。 4. 编写三元组快速转置函数。4. .主函数 (1)程序代码#include "stdio.h" #include "stdlib.h"#define MAX_SIZE 100 /

3、非零元个数的最大值 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("请输入矩阵的行数,列数,非零元素数："); sc

4、anf("%d,%d,%d",&M.mu,&M.nu,&M.tu); if(M.tu>MAX_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(m<1|m>M

5、.mu|n<1|n>M.nu) / 行或列超出范围 k=1; if(m<M.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+

6、) for(j=1;j<=M.nu;j+) if(k<=M.tu&&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)

7、/ 求稀疏矩阵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,

8、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中每一

9、列含非零元素个数 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&q

10、uot;); 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(&q