稀疏矩阵的表示和转置
实验二 稀疏矩阵的表示和转置
实验人: 张俊为 学号: Xb11640218 时间: 10.15
一、 实验目的
1. 掌握稀疏矩阵的三元组顺序表存储结构 2. 掌握稀疏矩阵的转置算法。
二、
实验内容
采用三元组表存储表示,求稀疏矩阵M的转置矩阵T。 (算法5.1)
三、
实验步骤:
1. 构建稀疏矩阵M。
2. 求稀疏矩阵M的转置矩阵T。 3. 输出稀疏矩阵M和稀疏矩阵T。
四、 算法说明
首先要创建稀疏矩阵的三元组顺序表存储表示,定义mu,nu,tu分别表示矩阵的行数、列数和非零元个数。在进行稀疏矩阵的转置时要做到(1):将矩阵的行列值相互交换;(2):将每个三元组的i,j相互调换;(3):重排三元组之间的次序便可实现矩阵的转置。 五、
测试结果
六、
分析与探讨
在此次程序中转置的方法称为快速转置,在转置前,应先求得M的每一列中非零元的个数,进而求得每一列的第一个非零元的位置。 七、
附录:源代码
T->data[q].i=
M->data[p].j;T->data[q].j=M->data[p].i; T->data[q].e=M->data[p].e;
#include
#include #include
#define MAXSIZE 100 typedef struct
{int i,j; //该非零元的行下标和列下标 int e; }Triple;
typedef struct
{Triple data[MAXSIZE+1];//非零元三元组表,data[0]未用
int mu,nu,tu;//矩阵的行数、列数和非零元个数 }TSMatrix; int a,b;
TSMatrix *creatarray(TSMatrix *M); TSMatrix *TransposeSMatrix(TSMatrix *M,TSMatrix *T);
void print(TSMatrix *T,int x,int y); void main()
{TSMatrix *M,*T; M=(TSMatrix *)malloc(sizeof(TSMatrix)); T=(TSMatrix *)malloc(sizeof(TSMatrix)); printf("请输入矩阵的行数和列数:\n"); scanf("%d%d",&a,&b); M=creatarray(M);
printf("你已创建一个矩阵:\n"); print(M,a,b);
T=TransposeSMatrix(M,T); printf("转置后的一个矩阵:\n"); print(T,b,a); printf("\n");}
//三元组快速转置 TSMatrix *TransposeSMatrix(TSMatrix *M,TSMatrix *T)
{ //采用三组表储存表示,求稀疏矩阵M的转置矩阵T int p,col,q; T->mu=M->nu; T->nu=M->mu; T->tu=M->tu; if(T->tu != 0) {q=1;
for(col=1;colnu;++col) for(p=1;ptu;++p)
if(M->data[p].j==col) {
++q; }}
printf("\n\n转置后的三元组为:\n\n"); for(p=1;ptu;p++)
{printf("%3d%3d%3d",T->data[p].i,T->data[p].j,T->data[p].e); printf("\n"); }
printf("\n"); return T; }
//建立三元组
TSMatrix *creatarray(TSMatrix *M) {int m,n,p=1,c;
printf("请输入矩阵:\n"); for(m=1;m
{ M->data[p].e=c; M->data[p].i=m; M->data[p].j=n; p++; }}
M->tu=p;M->mu=a;M->nu=b;
printf("原来三元组的表示为:\n\n"); for(m=1;mtu;m++)
{printf("%3d%3d%3d",M->data[m].i,M->data[m].j,M->data[m].e); printf("\n"); }
printf("\n"); return M} //输出三元组
void print(TSMatrix *T,int x,int y) {int m,n,p=1; int d;
for(m=1;m
for(n=1;n
{ if(T->data[p].i==m && T->data[p].j==n) { d=T->data[p].e; p++; } else d=0;
printf("%6d",d); }}}